demo of meet-in-the-middle attack (32bit)

meet-in-the-middle.py

# http://www.nruns.com/_downloads/advisory28122011.pdf
# http://bugs.python.org/issue13703
import sys
import string
import itertools


# hash function used by python string object
def hash(s):
    slen = len(s)
    x = ord(s[0]) << 7
    for c in s:
        x = mul32(1000003, x) ^ ord(c)
    x = x ^ slen
    if x == -1:
        x = -2
    return x


def mul32(x, y):
    z = (x * y) & 0xffffffff
    if z & 0x80000000:
        z -= 0x100000000
    return z

table = {}

def meet_in_the_middle(target, len, charset=string.letters):
    global table
    for chars in itertools.product(charset, repeat=len/2):
        s = "".join(chars)

        x = target ^ len
        for c in s[::-1]:
            #extended-euclid(1000003, 2**32) -> 2021759595
            x = mul32(x ^ ord(c), 2021759595)

        if x not in table:
            table[x] = [s,]
        else:
            table[x].append(s)

    for chars in itertools.product(charset, repeat=len/2):
        s = "".join(chars)

        x = ord(s[0]) << 7
        for c in s:
            x = mul32(1000003, x) ^ ord(c)
        if x in table:
            for e in table[x]:
                print s + e


def main():
    hash_target = 9
    meet_in_the_middle(target=hash_target, len=6)
    print "hash value is %d" % hash_target

if __name__ == "__main__":
    main()