So what if there's a SHA-1 collision?

| Comments (1) | TrackBacks (12) |
At the NIST hash function workshop yesterday ( liveblogging by Bruce Schneier), there was a lot of discussion about what the impact of an actual demonstrated collision in SHA-1 would be, as opposed to the "theoretical" 2^64 difficulty attacks published by Wang.

There are three reasons why you might think that an actual collision would be important. The first is that you don't 100% believe that Wang's attacks work, since after all they've never actually been tested. In that case, the existence of a collision is proof that the attacks actually work. I'm not qualified to have an opinion here, but my impression is that most cryptographers think that the attacks are likely to work. Assuming that they work, then 2^64 is totally within reach of a large-scale distributed computation mechanism, so it's basically a matter of time before someone publishes a collision, even if the analytic attacks are never improved.

The second reason is that you think that the attacks work but that the public (as opposed to the cryptographic community) would react differently to the news that there was an actual collision to the news that there was an actual collision. This could either be because they haven't correctly marked Wang's papers to market or because they would overreact to the news of an actual collision. This doesn't seem right to me. In fact, I suspect that most people who have heard that SHA-1 is broken (and there aren't that many of those) don't even know that no actual collision has been published.

The final concern is the impact of a single collision. As has been observed by Daum and Lucks, you can exploit a single collision to generate an arbitrary number of pairs of documents with the same message digest but that display differently. As I've noted before, I don't think that this is a very significant attack (though Georg Illies presented an interesting paper yesterday showing how to exploit this for some fairly primitive file formats). Most of the good attacks using collisions (e.g., to forge a certificate) require the ability to generate collisions in at least semi-real-time, rather than starting from a single fixed pair.

Bottom line: I expect to see a published collision in SHA-1 in the next few years. I doubt that it will cause widespread panic. If anything, it might make people feel better to get a feel for how much effort it took. All this assumes, of course, that no new analytic attack is published; and so the level of effort stays around 2^64 and the only difference is that a lot of computing power is applied to the problem. If the analytic attacks improve significantly, all bets are off.

12 TrackBacks

Listed below are links to blogs that reference this entry: So what if there's a SHA-1 collision?.

TrackBack URL for this entry: http://www.educatedguesswork.org/cgi-bin/mt/mt-tb.cgi/457

Fruit Baskets Read More

Disney Vacation from Disney Vacation on December 25, 2005 4:45 PM

Disney Vacation Read More

screams disjunctive Persianization!glaring stud?reformatting:multiples confessors atenolol http://atenolol.d-daystore.com/ Read More

Luxury Caribbean Cruise from Luxury Caribbean Cruise on January 8, 2006 8:14 AM

Luxury Caribbean Cruise Read More

Home Equity Loans from Home Equity Loans on January 14, 2006 10:47 AM

Home Equity Loans Read More

Cash Advance from Cash Advance on February 3, 2006 5:54 PM

Cash Advance Read More

Lasik Eye Read More

engagement ring from engagement ring on February 13, 2006 9:46 AM

platinum http://jewelry.dynu.com/platinum-rings platinum rings platinum Read More

Payday Advance from Payday Advance on February 15, 2006 7:30 PM

Payday Advance Read More

Barbecue Secrets from Barbecue Secrets on February 19, 2006 12:58 PM

Barbecue Secrets Read More

1 Comments

"In fact, I suspect that most people who have heard that SHA-1 is broken (and there aren't that many of those) don't even know that no actual collision has been published."

Lump me into this category. I had read that SHA-1 was broken, probably on this blog, but had not internalized the fact that no actual collision has been published. But then again, I only follow security matters from afar.

Leave a comment