[Back] We can analyse a hash function by looking at the balls in bins problem. In this, we take \(n\) bins and determine the probability of us getting two bins in a bin at any given throw:
Hash Analysis (Bins in Balls - BiBa)
The coding to determine the average number of throws to get two balls in at least one bin, and with \(n\) bins is:
import sys n = 2**128 if (len(sys.argv)>1): n=float(sys.argv) print ("Number of bins: %d\n" % n) print E=0 p_prev=1.0/n E=p_prev*2 for i in xrange(2,long(n)): pnew = p_prev*(n+1-i)*i/(n*(i-1)) E = E+pnew*(i+1) p_prev=pnew print "Average number of throws",E print "\nThrow\tProb of winning" val=(n-1)/(n) for i in xrange(2,long(n+2)): print ("%d\t%.3f" % (i,1-val)) val = val* (n-i)/n if (i>=100): print "Not printing after 100" break
A sample run for five bins is:
Number of bins: 5 Throw Prob of winning 2 0.20 3 0.52 4 0.81 5 0.96 6 1.00 Average number of throws 3.28
One area where we can use this collision is within a one-time signature (OTS) and with the method defined as "BiBa" ("Bins and Balls").
Basically with BiBa, Bob creates a number of random values for his private key:
\(Priv = x_1, x_2, … x_n\)
Next he creates his public key from the hashed versions of his private key:
\(Pub = SHA1(x_1), SHA1(x_2) … SHA1(x_n)\)
To create the signature for a message (\(M\)), he finds two values which will create a collision (as we have seen it should be fairly easy to find a collision within a reasonable amount of guesses):
\(H(M || x_i) == H(M || x_j)\)
He would then publish (\(x_i, x_j\)) as the signature of the message.
It would then be too difficult for Eve to find the values of \(x_i\) and \(x_j\) to create a collision, as Bob does not reveal them (they are only defined with their hash signature).
The presentation is here [slides]: