Sha-1 Broken

[eugene]

http://www.schneier.com/blog/archives/2005...ha1_broken.html (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html)

SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.

The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing their results:

* collisions in the 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.

* collisions in SHA-0 in 2**39 operations.

* collisions in 58-round SHA-1 in 2**33 operations.

This attack builds on previous attacks on SHA-0 and SHA-1, and is a major, major cryptanalytic result. 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).

The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team.

More details when I have them.

[caddickj]

Uh... not to show my ignorance or anything, but .... what does this mean in practical terms?

[eugene]

It means that the security minded may need to rethink hashing algorithms.

[Jeff]

Here's a link to a Q&A on the implications of this...

http://insight.zdnet.co.uk/internet/securi...39189917,00.htm (http://insight.zdnet.co.uk/internet/security/0,39020457,39189917,00.htm)


Last year was a bad year for the Secure Hashing Algorithm. This year has been worse.

A key technology used in digitally signing documents and programs, the Secure Hash Algorithm, or SHA, is used by goverment agencies and by corporations. It's used to reduce long documents to a smaller unique digital fingerprint, or hash, which is then signed using public-key encryption.

Last year, researchers found holes in various techniques used to create the numerical fingerprints. Among the results was a successful attack against the first version of the SHA algorithm, SHA-0.