Confessions of an operating systems junkie

Tuesday August 17, 2004

SHA-1 weakened, all other hashes broken I just finished watching the live webcast of the CRYPTO 2004 rump session, in which Eli Biham announced significant progress in finding collisions in SHA-1. He can do better than the birthday attack up to about 53 rounds (out of 80 total) of SHA-1 (this might be off by up to 10 rounds - I couldn't read the slides over the webcast). For reference, the time from a similar announcement for SHA-0 to a full collision was about 6 years - but most researchers were ignoring SHA-0 already as NIST proposed SHA-1 to replace SHA-0, due to known (to the NSA at least) weaknesses in SHA-0.

Eli Beham's talk was followed by announcements of full collisions in SHA-0 (by Antoine Joux), MD5, HAVAL-128, and RIPEMD (by Xiaoyun Wang). As a bit of fun, Xiaoyun Wang also presented a method to find collisions in MD4 that is so simple that it can be computed by hand (complexity 2²-2⁶ - that is, 4 - 64).

Before today, the state of the art in cryptographic hashes could be summarized as "Use SHA-1, everything else is either weak or unknown." Now it can be summarized as "SHA-1 is weak and everything else is broken."

I am, of course, ecstatic, as this strongly supports my paper opposing compare-by-hash, which depends on having a strong (not yet broken) cryptographic hash.

Thanks to Fred Douglis for adding a comment to my weblog pointing me to these results. For the record, no, I don't read Slashdot, but I'm beginning to think I should get back into the habit...

(2004-08-17 20:14:33.0) Permalink Comments [3]