Subject: Hash function statistics; MD5 and SHA-1

From: Graham Klyne <[email-masked]>
Date: Tue, 08 Jun 1999 20:29:39 +0100

At 16:54 08/06/99 +0200, Brad Knowles wrote:
>At 9:34 AM -0400 6/8/99, Dave Sill wrote:
>
>> Are you referring to Dobbertin's '96 work? If so, if I understand it
>> correctly, it may not have any practical application to MD5 since it
>> uses a different initial vector. MD5's initial vector may not have the
>> same problem.
>
>	I don't know for sure who's work it was, although I was under the 
>impression that it was Ron Rivest himself who later showed at least 
>some weaknesses in the MD5 hashing algorithm.

Bruce Schneier [Applied Crytography, 2nd ed, section 18.5, p441] cites 1993
work by den Boer and Bosselaers that sugests that "one of the basic design
principles of MD5 --to design a collision-resistant compression function--
has been violated".  I don't know how serious this is in practice, though
he does go on to say that this "has no practical impact on the security of
the hash function".

>> We're talking about message ID's here, not digital signatures. Is the
>> little extra uniqueness really worth a lot of extra CPU cycles?
>
>	I think the work done by Graham Klyne <[email-masked]> clearly 
>shows that the probability of collison with MD5 becomes significant, 
>even with very small population sizes.  It it my personal opinion 
>that a better hash algorithm is therefore warranted.

Hmmm... I don't think that (say) 10^12 (which yields a 10^(-15) probability
of collision) is a *very small* population size.  Especially in the context
of the number of messages sent through a given ISP in a single second.
What I did say is that despite the apparently very small probability of
generating the same ID twice, the probability increases surprisingly as the
number of samples increases.  This is a re-run of the "birthday paradox"
with larger numbers.

Certainly, increasing the size of the hash function used from 128 to 160
bits will improve the odds of avoiding a collision.

I've managed to re-run the calculations for a 160-bit hash function, and
this is what I get:

N is number of 160-bit hash values calculated;
P is probability that they are not all unique:

    N      P
    1     0.0
    2     6.8E-49
    1E1   3.1E-47
    1E3   3.4E-43
    1E6   3.4E-37
    1E9   3.4E-31
    1E12  3.4E-25
    1E15  3.4E-19
    1E18  3.4E-13
    1E21  3.4E-7
    1E24  0.2
    1E27  1.0

Actually, running the calculation for the case N=1E27 slightly differently
yields the probability P=(1.0 - 6.6E-148579) -- which is as close to 1.0 as
makes any practical difference :-)

CAVEAT:  these calculations are based on the assumption that the values of
the hash function are distributed evently and randomly through the value
space.

#g

------------
Graham Klyne
([email-masked])