Re: monitoring entropy

Theodore Y. Ts'o (tytso@MIT.EDU)
Thu, 16 Oct 1997 17:17:22 -0400

Yes, I was sloppy about about the difference between the work factor for
finding an arbitrary collision and a collision value with a specific
hash --- although there's a big difference between 2**80 and 2**160. My
apologies for that. I don't know what I was thinking when I wrote
2**2048 instead of 2**4095. Serves me right for trying to write that
message too late last night.

One comment from Colin:

>>Since it is considered extremely hard (2**64 is a very large
>>number), all you need to do in order to "prove" that MD5 is
>>broken is to present two input texts which hash to the same MD5
>>value.
>
>Which Hans Dobbertin has done, BTW. He showed them at Eurocrypt '96.
>But not for SHA.

Actually, I don't think Hans Dobbertin has done that. He's found a
collision in the compression function used by MD5 --- which is certainly
bad, but it's not the same as a collision in MD5 itself. See
http://www.ph.tn.tudelft.nl/~visser/dobbertin.txt for a sci.crypt
posting from Hans Dobbertin himself. Basically, the collision occurs if
you use a specific hash state, or IV. This hash state is not the hash
state used by MD5, and there is currently no known way of forcing a
particular hash state. I also don't believe there are (yet!) known ways
of extending his attack to work on arbitrary IV's.

- Ted