# MD5 collisions?

Greg Rose ggr at qualcomm.com
Wed Aug 18 12:51:35 EDT 2004

```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

```