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: [EMAIL PROTECTED] 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 [EMAIL PROTECTED]
