from collections import Counter
import sys
import string
import base64
from Crypto.Hash import SHA256
from random import randint
def raw2hex(raw):
    return raw.encode('hex')


def hex2raw(hexstring):
    return base64.b16decode(hexstring)

hexdigits = '0123456789ABCDEF'

def hash(message):
    h = SHA256.new()
    h.update(message)
    return h.digest()


def main():
    # Try to find a collision on the first 4 bytes (32 bits)

    # Step 1. Generate 2^16 different random messages
    while True:
        messages = []
        for i in range(1 << 16):
            msg = ""
            for j in range(8):
                msg = msg + chr(randint(0, 255))
            messages.append(msg)

    # Step 2. Compute hashes
        hashes = []
        fullhashes = []
        for msg in messages:
            hashes.append(hash(msg)[:4])
            fullhashes.append(hash(msg))


    # Step 3. Check if there exist two hashes that match in the first
    # four bytes.
        l = [k for k,v in Counter(hashes).items() if v>1]

        if len(l) == 0:
	     continue

    # Step 3a. If a match is found, print the messages and hashes
        indices = [i for i, x in enumerate(hashes) if x == l[0]]
        for i in indices:
           print "Hash ", raw2hex(fullhashes[i])
           print "Message ", raw2hex(messages[i])

    # Step 3b. If no match is found, repeat the attack with a new set
    # of random messages

if __name__ == "__main__":
    main()