A toy rainbow table script

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))

A brilliant demonstration of how RTs work, without unnecessary details to begin with, with thanks to Luc Gommans,