At this year's Crypto conference, a 2^63 collisions attack on SHA1 was announced by Wang, but not delivered by her personally because the US State Department would not issue her a Visa. (According to participants, Adi Shamir humourously pointed out it was because she had admitted to attacking US systems with her collisions attack).
This is far superior to the suggestion from last year's conference, which destroyed all smaller hashes except SHA1 and suggested a 2^69 attack. That was 11 bits off the brute force searching limit of 2^80, and still was not really doable. Taking it to 17 bits and down to 2^63 puts it in reach of Internet attacks as we've already seen similar efforts (64 bit ciphers have been crunched on the net).
Note that this is on collisions between two random hashes, and most systems do not rely on this property. Rather, most systems rely on not being able to find another document from a given hash, or seeing through to the document from a given hash.
The strength of that normal usage is 2^160, the full length of brute forcing the entire hash space. Simplistically, if that space lost 2*17 bits, SHA1 would still be as strong as 2^126, which is well secure from crunching.
But it does mean that SHA1 is no longer Pareto-complete - no longer secure regardless of the circumstances. Crypto Engineers will have to check to make sure they are not relying on collision resistance between random hashes.
(I'll update this as more info comes to hand, check the blog. Here's a snippet:)
"Perry E. Metzger" writes:
...I was unable to watch webcast of the rump session at the Crypto conference last night, but I have heard that a proxy announced that Wang has an order 2^63 attack on SHA-1. Can anyone confirm that, and give details?Shamir gave her rump session talk (and first gave a humorous presentation on why she couldn't get a visa -- she admitted to attacking U.S. government systems, and used collisions). She is indeed claiming a 2^63 attack, and found a new path to use in the attack. Because of the new path, there is reason to think the attack will get even better. Shamir noted that 2^63 is within reach of a distributed Internet effort to actually find one.
--Steven M. Bellovin, http://www.cs.columbia.edu/~smb
Addendum: Bruce Schneier's blog has refs to the papers.
Ugh, the visa thing seems quite silly.
Perhaps Distributed.net should try and find a collision for SHA-1? It would be more interesting than trying to brute force a 72-bit RC5 key, which is what I think they're working on at the moment.
Posted by: Matt Crypto at August 17, 2005 10:59 AM