MD5 collisions?

[Greg Rose]

At 00:49 2004-08-19 +1000, Greg Rose 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.

This, too, is overly simplistic an explanation. Doing it like this would 
effectively multiply the work for the near-collision in the first block and 
the correction in the second block, which is not what you want. To be 
efficient, you need to divide-and-conquer; make random pairs of first 
blocks until you find a pair that have the right very small difference in 
their chaining outputs. Then, from those first blocks, try to find second 
blocks that work. This adds the amounts of work, rather than multiplying them.

Apologies for any confusion.

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