#solutions to assignment 7

import hashlib
import random
import time

#generate a random ASCII string of given length
def rand_string(length):
    lets=[chr(ord('a')+j) for j in range(26)]
    lets+=[chr(ord('A')+j) for j in range(26)]
    result=''
    for j in range(length):
        u=random.randint(0,51)
        result+=lets[u]
    return result

#return top order 20 bits of sha1 hash as 5-digit hex string

def hash20(s):
    ha=hashlib.sha1(s).hexdigest()
    return ha[:5]

#return top order 40 bits of sha1 hash as 10-digit hex string

def hash40(s):
    ha=hashlib.sha1(s).hexdigest()
    return ha[:10]

#compute hashcash tag for s:  append up to 16 hex digits
#as ASCII to a string so that the first 20 bits of the
#sha1 hash are zero. Return as a tuple the resulting string,
#the hash, and the number of calls to sha1 that were made
def compute_tag(s):
    count=0
    while True:
        append_tag=hex(random.randint(0,2**64-1))
        arg=s+append_tag[2:18]
        hashval = hash20(arg)
        count+=1
##        if count % 50000 == 0:
##            print count
        if hashval=='00000':
            break
    return (arg,count)


#Find a collision in the top 40 bits of sha1 with a standard birthday attack.
#Generate random strings,
#and place them in a dictionary, indexed by the hash value.
#Return the colliding
#values, their hash, and the number of hashes that were computed.

def birthday1():
    the_dict={}
    nextstring=rand_string(20)
    the_dict[hash40(nextstring)]=nextstring
    count=1
    while True:
        count+=1
##        if count%50000==0:
##            print count
        nextstring=rand_string(20)
        h=hash40(nextstring)
        if h in the_dict:
            return (nextstring,the_dict[h],count)
        the_dict[h]=nextstring

#Find collision in the top 40 bits of sha1 using low memory birthday attack.
#This is Floyd's Cycle Detection Algorithm. Return the colliding
#values, their hash, and the number of hashes that were computed

def birthday2():
    start=rand_string(20)
    x=hash40(start)
    y=hash40(x)
    count=2
    while x != y:
        count+=3
        x=hash40(x)
        y=hash40(hash40(y))
##        if (count/3)%50000 == 0:
##            print count
    z=start
    zz=hash40(z)
    yy=hash40(y)
    count+=2
    while zz!=yy:
        count+=2
##        if (count/2)%50000 == 0:
##            print count
        z=zz
        y=yy
        zz=hash40(z)
        yy=hash40(y)
        
    return (y,z,count)

#Find a meaningful collision in hash40.  We should need about
#2^20 'heads' messages, and 2^20 tails.  We'll err a bit
#and try to build 2^21 messages of each kind.

#First, take an integer n in the range 0 to 2^21-1 and use it
#to create a message predicting heads (1) or tails (0)
def gen_message(n,which):
    headmessage=[('I','I,'),(' ','  '),('Alice','ALICE'),(',',''),(' ','  ')]
    headmessage+=[('do ',''),('hereby ',''),('affirm and ',''),('swear ','SWEAR'),(', ',' ')]
    headmessage+=[('that the coin ','that the COIN '),('that ','which ')]
    headmessage+=[('I just ','I '),('tossed','flipped'),(' in the air ',''),(',',''),(' ','  ')]
    headmessage+=[('came up ','landed '),('showing ',''),('',' '),('heads.','HEADS.')]
    tailmessage=('tails.','TAILS.')
    genstring=''
    for j in range(20):
        genstring+=headmessage[j][n%2]
        n=n/2
    if which==1:
        genstring+=headmessage[20][n%2]
    else:
        genstring+=tailmessage[n%2]
    return genstring

def build_heads_dict():
    hashdict={}
    for n in range(2**21-1):
        message=gen_message(n,1)
        hashval=hash40(message)
        hashdict[hashval]=message
    return hashdict

def birthday3():
    print 'builing dictionary...'
    hashdict=build_heads_dict()
    print 'dictionary built'
    count = 2**21-1
    for j in range(2**21-1):
        message=gen_message(j,0)
        hashval=hash40(message)
        count+=1
        if count%50000 == 0:
            print count
        if hashval in hashdict:
            return (message,hashdict[hashval],count)

        
        


t=time.clock()
(arg,count)=compute_tag('0:141206:howard.straubing@gmail.com')
print 'tag:',arg
print 'hash of tag:',hash20(arg)
print 'number of hashes:',count
print 'time:', time.clock()-t
print
print 'Standard birthday attack:'
t=time.clock()
(arg1,arg2,count)=birthday1()
print 'colliding tags:',arg1,arg2
print 'hash of arguments:',hash40(arg1),hash40(arg2)
print 'number of hashes:', count
print 'time:',time.clock()-t
print
print
print 'Low memory birthday attack:'
t=time.clock()
(arg1,arg2,count)=birthday2()
print 'colliding tags:',arg1,arg2
print 'hash of arguments:',hash40(arg1),hash40(arg2)
print 'number of hashes:', count
print 'time:',time.clock()-t
print
print
print 'Birthday attack with meaningful collision:'
t=time.clock()
(arg1,arg2,count)=birthday3()
print 'colliding tags:'
print arg1
print arg2
print 'hash of arguments:',hash40(arg1),hash40(arg2)
print 'number of hashes:', count
print 'time:',time.clock()-t
print
print