Re: SHA-1 broken

["Jonathan G. Lampe" <jonathan.lampe@xxxxxxxxxxxxxxxxxxxx>]

A Chinese research group now says that collisions can be found in the full 
SHA-1 in 2**69 hash operations, much less than the brute-force attack of 
2**80 operations based on the hash length.

If I am eyeballing this correctly, this makes the "cracked" SHA-1 just a 
little tougher (32x) than MD-5 was thought to be (2**64 operations) before 
MD5 was cracked.  (I believe, and I could be wrong, that MD5 is now 
considered to be 2**42 operations strong; one of the papers referenced 
below suggests the "1 hour IBM" MD5 crack was performed at a 2**25 
operation level of difficulty which would only be possible with some 
additional knowledge.)

Again, if I am eyeballing this correctly, SHA-1 is still currently 
134,217,728x more secure than MD5.  Before the SHA-1 announcement, SHA1 was 
thought to be 274,877,906,944x more secure than MD5, and originally, SHA-1 
was  thought to be just 65,536x more secure than MD5.  (MD5 has been "more 
cracked" than SHA-1 in recent months.)

According to Bruce Schneier, "It pretty much puts a bullet into SHA-1 as a 
hash function for digital signatures (although it doesn't affect 
applications such as HMAC where collisions aren't important)"

Schneier also lists the likely alternatives in the near future in another 
article.  "The National Institute of Standards and Technology (NIST) 
already has standards for longer --and harder-to-break -- hash functions: 
SHA-224, SHA-256, SHA-384 and SHA-512. They're already government standards 
and can already be used. This is a good stopgap, but I'd like to see more. "

See:
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
http://it.slashdot.org/comments.pl?sid=139602&cid=11686181
http://eprint.iacr.org/2004/199.pdf
http://eprint.iacr.org/2004/264.pdf

- Jonathan Lampe
- jonathan.lampe@xxxxxxxxxxxxxxxxxxxx

At 06:56 AM 2/16/2005, Gadi Evron wrote:
> Now, we've all seen this coming for a while.
> Where do we go from here?
>         Gadi.

******************* PLEASE NOTE ******************* 

This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed.
If you are not the named addressee you should not disseminate, distribute or copy this e-mail. Please delete this e-mail from your system. If you are not the intended recipient you are notified that disclosing, copying, distributing or taking any action in reliance on the contents of this information is strictly prohibited.