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 22-26 - 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...

Comments:

The last word in the first paragraph should be SHA-0. The NSA knew of weaknesses in SHA-0 and proposed SHA-1 as a replacement. I don't think they've acknowledged any weaknesses in SHA-1.

Posted by Matt on August 17, 2004 at 02:07 PM PDT #

Thanks for catching that typo (fixed). To my knowledge, the NSA has not acknowledged any weaknesses in SHA-1.

Posted by Val Henson on August 17, 2004 at 02:21 PM PDT #

I think your HOTOS paper just became required reading in a whole lot of courses.

Posted by Fred Douglis on August 18, 2004 at 04:32 AM PDT #

Post a Comment:
Comments are closed for this entry.
About

val

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today