March 13, 2005

How to Break MD5 and Other Hash Functions

Wang and Yu have released their draft paper(s) for Eurocrypt 2005:

Xiaoyun Wang and Hongbo Yu, "How to Break MD5 and Other Hash Functions"
Xiaoyun Wang and Hongbo Yu, "Cryptanalysis of the Hash Functions MD4 and RIPEMD"

Meanwhile, Vlastimil Klima has released a draft on his research trying to reverse engineer the Shandong team's results. Whereas the Shandong team managed MD5 collisions in one hour on their IBM P690 supercomputer, Klima claims he can do a collision, using different techniques, in only 8 hours on his 1.6GHz laptop!

V. Klima, Finding MD5 Collisions - a Toy For a Notebook

And, expect this to improve, Klima says, when the two differing techniques are compared and combined.

What does this mean, especially considering my earlier post on cryptographer's responsibility?

It is now easy to find a junk document that matches some MD5 hashed document. This is a collision attack. But, it will be harder to find a valid attacking document that hashs to the same MD5. This is called a pre-image attack, and is far more serious.

Further it remains harder to breach a protocol that relies on other things. But, do move from MD5 with due haste, as if collisions are easy to find, then pre-images can't be that far behind. And once we have pre-images, we can substitute in real live key pairs into the certs attack described earlier today.

Posted by iang at March 13, 2005 04:05 PM | TrackBack

Rivest has held water since 1992 now on to SHA-1 thru whatever to topple the FIPS. Now the question is who did what with whatever and where there damages. I sense a mad rush for the gates.

Posted by: Jimbo at March 13, 2005 05:04 PM

What you have said here is not quite correct. A collision attack lets the creator create both documents that hash to the same thing. This is what the new results allow. A pre-image attack lets you create a document (meaningful or meaningless, it doesn't matter) that has a desired hash, such as the hash of a pre-existing document. So far the new techniques don't help with that.

Another point, Klima is following in the footsteps of the Wang et al results and not publishing his techniques. He makes his claims and publishes a collision, but breathes not a word about how the magic is done. Must have had something up his sleeves.

But it is great to see that Wang and company are finally coming out with the goods.

Posted by: Cypherpunk at March 14, 2005 01:43 AM


please decrypt dis and send this to

Posted by: imalsha at June 22, 2010 05:12 AM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.