Very simple script that uses birthday paradox to find a collision for hash function H(x) that truncates output of SHA-256(x) to 50 bits. Written for cryptography class. Note that this is very memory-intensive, using up to 4.5GB's of main memory when no collision is found.

sha-collision.py

#
# Very simple script that uses birthday paradox to find collision for hash function H(x)
# that truncates the output of SHA-256(x) to 50 bits. Written for cryptography class.
# See [Stinson, 2005] for why this works. 
#

import hashlib
import os
import binascii

def hash(s):
	sha256 = hashlib.new('sha256')
	sha256.update(s)
	y = sha256.hexdigest()
	return hex(int(y[-13:-12],16) & 3)+y[-12:]

def search(N = 2**25):
	d = {}
	while N >= 0:
		s = os.urandom(4)
		k = hash(s)
		if k in d and d[k] != s:
			print s, d[k]
			return (s, d[k])
		else: d[k] = s
		N -= 1
	if N < 0: print "Sorry, no luck"
	# we failed; life is meaningless now; just return something
	return ("a", "b")

# entry point 
if __name__ == '__main__':
	(s1, s2) = search()
	print [hex(ord(c)) for c in s1]
	print [hex(ord(c)) for c in s2]