lgommans/rainbowtable.py

## rainbowtable.py
#!/usr/bin/env python3

import sys
from hashlib import md5
from base64 import b64encode
from binascii import hexlify, unhexlify
from time import time


def reduction_function(hash, max_password_length):
    length = (hash[0] % (max_password_length - 1)) + 1
    return b64encode(hash[1:])[:length]


def create_chain(starting_value, chain_length, max_password_length, show_each_step):
    current_password = bytes(str(starting_value), "utf-8")
    begin = current_password

    for link in range(chain_length):
        hash = md5(current_password).digest()
        if show_each_step:
            sys.stdout.write("{}={} => ".format(str(current_password, "utf-8"), str(hexlify(hash[0:6]), "utf-8")))
        current_password = reduction_function(hash, max_password_length)

    end = current_password

    return begin, end


def create_table(num_chains, chain_length, max_password_length, show_each_step):
    table = {}
    for i in range(num_chains):
        if show_each_step:
            sys.stdout.write("Chain {}: ".format(i))

        begin, end = create_chain(i, chain_length, max_password_length, show_each_step)
        table[end] = begin

        if show_each_step:
            sys.stdout.write("{}\n".format(str(end, "utf-8")))

    return table


def print_table(table, show_each_step):
    if not show_each_step:
        length = 0
        for key in table:
            length += len(key) + len(table[key])
        print('Table size: {}KB / {} chains'.format(round(length/1024, 1), len(table)))
        return

    print("\nThe rainbow table contains:")
    for key in table:
        value = table[key]
        print("{} => {}".format(str(key, "utf-8"), str(value, "utf-8")))


def find_in_table(hash, rainbow_table, chain_length, max_password_length, show_each_step):
    password_reduced = reduction_function(hash, max_password_length)
    print("\nLooking for hash '{}', reduced to '{}'.".format(str(hexlify(hash[0:6]), "utf-8"), str(password_reduced, "utf-8")))

    current_password = password_reduced
    previous_password = password_reduced
    begin = None

    for link in range(chain_length):
        tmp_hash = md5(current_password).digest()
        current_password = reduction_function(tmp_hash, max_password_length)

        if show_each_step:
            print("hashed=>reduced '{}' to '{}'".format(str(previous_password, 'utf-8'), str(current_password, "utf-8")))

        if current_password in rainbow_table:
            begin = rainbow_table[current_password]
            if show_each_step:
                print("Found a match, {} is in our rainbow table:".format(str(current_password, 'utf-8')))
                print("    {} => {}".format(str(current_password, 'utf-8'), str(begin, 'utf-8')))
                print("The table starts with '{}'. Let's walk that chain and look for the hash.".format(str(begin, "utf-8")))
            break

        previous_password = current_password

    if begin is None:
        print('Reduced hash not found in any of the chains.')
        return

    current_password = begin
    for link in range(chain_length):
        tmp_hash = md5(current_password).digest()

        if show_each_step:
            print("hashed '{}' to {}...".format(str(current_password, 'utf-8'), str(hexlify(tmp_hash[0:6]), "utf-8")))

        if tmp_hash == hash:
            print("That hash matches! Found the password: {}".format(str(current_password, "utf-8")))
            return current_password

        current_password = reduction_function(tmp_hash, max_password_length)

    print("Password for hash '{}' not found.".format(str(hexlify(hash[0:6]), 'utf-8')))


num_chains = 5
chain_length = 15
max_password_length = 10
show_each_step = True

password_hashes = ['04b4284653cc01171b12655c6d35a60b'
    , '23f52cae795a0e4df7ea66eb47252cc7'
    , '5234beb92651a71318d2245698aa58a1'
    , '7668b281026237d6e7f2b6e209624153'
]

print("Creating rainbow table with {} chains of length {}...".format(num_chains, chain_length))
starttime = time()
rainbow_table = create_table(num_chains, chain_length, max_password_length, show_each_step)
print('That took {0:.2g} seconds.'.format(time() - starttime))

print_table(rainbow_table, show_each_step)

starttime = time()
for hash in password_hashes:
    find_in_table(unhexlify(hash), rainbow_table, chain_length, max_password_length, show_each_step)
print('That took {0:.2g} seconds.'.format(time() - starttime))
	#!/usr/bin/env python3

	import sys
	from hashlib import md5
	from base64 import b64encode
	from binascii import hexlify, unhexlify
	from time import time


	def reduction_function(hash, max_password_length):
	length = (hash[0] % (max_password_length - 1)) + 1
	return b64encode(hash[1:])[:length]


	def create_chain(starting_value, chain_length, max_password_length, show_each_step):
	current_password = bytes(str(starting_value), "utf-8")
	begin = current_password

	for link in range(chain_length):
	hash = md5(current_password).digest()
	if show_each_step:
	sys.stdout.write("{}={} => ".format(str(current_password, "utf-8"), str(hexlify(hash[0:6]), "utf-8")))
	current_password = reduction_function(hash, max_password_length)

	end = current_password

	return begin, end


	def create_table(num_chains, chain_length, max_password_length, show_each_step):
	table = {}
	for i in range(num_chains):
	if show_each_step:
	sys.stdout.write("Chain {}: ".format(i))

	begin, end = create_chain(i, chain_length, max_password_length, show_each_step)
	table[end] = begin

	if show_each_step:
	sys.stdout.write("{}\n".format(str(end, "utf-8")))

	return table


	def print_table(table, show_each_step):
	if not show_each_step:
	length = 0
	for key in table:
	length += len(key) + len(table[key])
	print('Table size: {}KB / {} chains'.format(round(length/1024, 1), len(table)))
	return

	print("\nThe rainbow table contains:")
	for key in table:
	value = table[key]
	print("{} => {}".format(str(key, "utf-8"), str(value, "utf-8")))


	def find_in_table(hash, rainbow_table, chain_length, max_password_length, show_each_step):
	password_reduced = reduction_function(hash, max_password_length)
	print("\nLooking for hash '{}', reduced to '{}'.".format(str(hexlify(hash[0:6]), "utf-8"), str(password_reduced, "utf-8")))

	current_password = password_reduced
	previous_password = password_reduced
	begin = None

	for link in range(chain_length):
	tmp_hash = md5(current_password).digest()
	current_password = reduction_function(tmp_hash, max_password_length)

	if show_each_step:
	print("hashed=>reduced '{}' to '{}'".format(str(previous_password, 'utf-8'), str(current_password, "utf-8")))

	if current_password in rainbow_table:
	begin = rainbow_table[current_password]
	if show_each_step:
	print("Found a match, {} is in our rainbow table:".format(str(current_password, 'utf-8')))
	print(" {} => {}".format(str(current_password, 'utf-8'), str(begin, 'utf-8')))
	print("The table starts with '{}'. Let's walk that chain and look for the hash.".format(str(begin, "utf-8")))
	break

	previous_password = current_password

	if begin is None:
	print('Reduced hash not found in any of the chains.')
	return

	current_password = begin
	for link in range(chain_length):
	tmp_hash = md5(current_password).digest()

	if show_each_step:
	print("hashed '{}' to {}...".format(str(current_password, 'utf-8'), str(hexlify(tmp_hash[0:6]), "utf-8")))

	if tmp_hash == hash:
	print("That hash matches! Found the password: {}".format(str(current_password, "utf-8")))
	return current_password

	current_password = reduction_function(tmp_hash, max_password_length)

	print("Password for hash '{}' not found.".format(str(hexlify(hash[0:6]), 'utf-8')))


	num_chains = 5
	chain_length = 15
	max_password_length = 10
	show_each_step = True

	password_hashes = ['04b4284653cc01171b12655c6d35a60b'
	, '23f52cae795a0e4df7ea66eb47252cc7'
	, '5234beb92651a71318d2245698aa58a1'
	, '7668b281026237d6e7f2b6e209624153'
	]

	print("Creating rainbow table with {} chains of length {}...".format(num_chains, chain_length))
	starttime = time()
	rainbow_table = create_table(num_chains, chain_length, max_password_length, show_each_step)
	print('That took {0:.2g} seconds.'.format(time() - starttime))

	print_table(rainbow_table, show_each_step)

	starttime = time()
	for hash in password_hashes:
	find_in_table(unhexlify(hash), rainbow_table, chain_length, max_password_length, show_each_step)
	print('That took {0:.2g} seconds.'.format(time() - starttime))