[15956] in cryptography@c2.net mail archive
RE: MD5 collisions?
daemon@ATHENA.MIT.EDU (Greg Rose)
Wed Aug 18 14:05:12 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 19 Aug 2004 02:51:35 +1000
To: "Whyte, William" <WWhyte@ntru.com>
From: Greg Rose <ggr@qualcomm.com>
Cc: Greg Rose <ggr@qualcomm.com>,
Mads Rasmussen <mads@opencs.com.br>, cryptography@metzdowd.com
In-Reply-To: <30F37C4533D8564FB1D58BFDAF6687C101670635@ohthree.jjj-i.com
>
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@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@metzdowd.com
