MD5 collisions?

[Greg Rose]

At 12:04 2004-08-18 -0400, Whyte, William wrote:

> > There has been criticism about the Wang et. al paper that "it doesn't
> > explain how they get the collisions". That isn't right. Note that from the
>
> > incorrect paper to the corrected one, the "delta" values didn't change.
> > Basically, if you throw random numbers in as inputs, in pairs with the
> > specified deltas, you should eventually be able to create your own MD5
> > collisions for fun or profit.
>
>So this is big. This doesn't just break collision resistance, it
>breaks second preimage resistance. Is that right?

If I've understood it correctly, the answer is "sort of". For a given 
input, it seems that there is some non-trivial chance that the input+delta 
would produce the same hash, that is, a 2nd preimage. But the probability, 
for any single arbitrary message, might be quite low (especially since 
you'd have to multiply the probabilities of success for the first and 
second blocks; see my other message just before this one). But it seems to 
me that that probability would still be much better than the 2^-n that it 
should be for an n-bit hash.

For example, the MD5 collision in 2^40 work is really two separate 
near-collisions, each taking a bit less than 2^40 work. If you apply the 
deltas to a random message M, both blocks at the same time, it seems to me 
that the probability of success is about 2^-80; it either works or it 
doesn't. But that 2^-80 is a much better chance than you would have had for 
two random messages (which is really message M and a random delta).

But I could also be mistaken on this.

Greg.


Greg Rose                                    INTERNET: ggr at qualcomm.com
Qualcomm Australia       VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,             http://people.qualcomm.com/ggr/
Gladesville NSW 2111/232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com