How to implement a reduced rainbow table in python

Question

I'm attempting to understand how rainbow tables work and am trying to implement one in python but without much success.

I have some code which essentially creates a dictionary in a text file with plaintext strings mapped to their hashes, but can't figure out how to adapt this to generate a reduced rainbow table.

temp = itertools.product("abcdefghijklmnopqrstuvwxyz", repeat=5)
f = open("passwords.txt", "w")
for pw in temp:
    p = ''.join(pw)
    encode = hashlib.md5(p.encode()).hexdigest() 
    f.write(p + " " + encode + "\n")
f.close()

I've came across reduction functions and kinda understand them and so have defined one as:

def reduction(hash):
    return hash[:5]

But I don't know what to do from here :(

How can I adapt this code to generate a reduced rainbow table?

Answer 1

Your reduction function should generate a password made of characters of you character set and of length 5 (in your case). Here is an example that takes an integer as input.

import hashlib
chars="abcdefghijklmnopqrstuvwxyz"
chars_len = len(chars)

def reduce(i):
    # reduces int i to a 5 char password
    # think of i as a number encoded in base l
    pwd=""
    while len(pwd)<5:
        pwd = pwd + chars[ i%chars_len ]
        i = i // chars_len
    return pwd


table=[]
# generate 10 chains of 1000 pwd, print start and end
for s in range(0,10):
    # we can use reduce to generate the start of a chain
    start=reduce(s)

    p=start
    for i in range(0,1000):
        # hash
        h=hashlib.md5(p.encode('ascii')).hexdigest()
        # reduce
        p=reduce(int(h,16))

    table.append([start,p])

print (table)

You now have a table that can crack about 10k passwords but uses only the space of 20 passwords!

Note that for a real rainbow table, you would have to use a different reduction function for each step. e.g. rainbow_reduce(i,k) = reduce(i+k)

Using the table to find a password from a hash is left as an exercise :-) (or another question)