Some things to note.... 1 - Wang and Joux's attacks do not allow determination of original inputs from a given hash. 2 - The interesting and newsworthy part of Wang's paper is not that there are collisions in MD5 (and the other hash algs they produced collisions for), but that they can produce colliding inputs by some process other than random or bruteforce searching. They have some method that allows them to produce colliding inputs at will with a minimal amount of work - 32way 1.7ghz system produces unique 128byte colliding texts in under 1.5hrs. They have proven this is more than just random/bruteforce luck by providing two pairs of colliding inputs with wrong initial values for MD5, and in the same day (at Crypto2004) produced 2 new pairs of colliding inputs for the corrected MD5 init values. To truly understand the impacts of Wang's attacks, the actual collision prediction/search method needs to be published. From the information released so far, Wang is relying on very particular 128byte sequences with bits flipped in 6 or 7 bit positions between the two 128 byte sequences. It does not appear that a colliding input can be produced for just any arbitrary input/text with this attack -- it appears the original input needs to meet some very specific requirements to allow creation of a colliding (alternate) input that will produce the same output hash. More detail on Wang's alg/method is needed to know the full extent of the applied impacts. Regards, Anton Rager arager@xxxxxxxxx -----Original Message----- From: Gandalf The White [mailto:gandalf@xxxxxxxxxxx] Sent: Tuesday, December 07, 2004 3:55 PM To: Dan Kaminsky; BugTraq Subject: Re: MD5 To Be Considered Harmful Someday Greetings and Salutations: On 12/6/04 5:29 PM, "Dan Kaminsky" <dan@xxxxxxxxxxx> wrote: <snip> > Some highlights from the paper: > * The attack itself is pretty limited -- essentially, we can create > "doppelganger" blocks (my term) anywhere inside a file that may be > swapped out, one for another, without altering the final MD5 hash. This > lets us create any number of binary-inequal files with the same md5sum. >From my reading it appears that you need the original source to create the doppelganger blocks. It also appears that given a MD5 hash you could not create a input that would give that MD5 back. Passwords encoded with MD5 would not fall prey to your discovery. Is this correct? Unfortunately when "The Press" publicized the MD5 hash discovery by Joux and Wang it almost sounded like "The Press" was surprised to find collisions in the MD5 domain (intuitive to me, a limited number of outputs and a infinite number of inputs = Collisions). I assume that a "good" hash would have a even distribution of collisions across the domain and that the larger number of bits for the output the better the hash (assuming no cryptographic algorithm errors). Thanks, Ken --------------------------------------------------------------- Do not meddle in the affairs of wizards for they are subtle and quick to anger. Ken Hollis - Gandalf The White - gandalf@xxxxxxxxxxx - O- TINLC WWW Page - http://digital.net/~gandalf/ Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html Trolls crossposts - http://digital.net/~gandalf/trollfaq.html
