SHA-1 "hashing" algorithm broken

SHA-1 is a "hashing algorithm." Feed it a long string of digits -- like an MP3 -- and it will produce a supposedly unique "hash" of those digits that's much shorter. This hash can be used to determine, for example, whether a message has been tampered with: append a hash to an email message that's generated in combination with a PGP key and your recipients can repeat the operation and determine whether the message has been tampered with in transit. Or distribute a hash of the latest security update and your download manager can compare the hash with the value it gets when it hashes update and make sure you've got the real goods. P2P application designers use hashes in a number of ways: detecting spoof files and trojans, downloading the same file from many sources ("parallel downloading" -- a poor man's BitTorrent, essentially) and so forth. Spamfighters use hashes to spot spam -- it's a way to tell whether the message I've just received has already been flagged as spam by you, saving me the trouble of looking it up -- and proposals like LOAF use hashes to assemble lists of trusted senders by allowing friends to share contact lists without exposing the actual names of their other friends.

There are lots of ways to calculate hashes, but SHA-1 is one of the most widely used. Many SHA-1 applications rely on the absence of "collisions" -- that is, the ability to spoof it by having two files hash out to the same fingerprint. That's a key piece of any kind of digital signature system. But now, there's a break for SHA-1, a means that makes it relatively easy to find collisions in a relatively short time:

The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing 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.

Link