SHA-1 Broken

From Schneier on Security: SHA-1 Broken:

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).

This is pretty annoying since the WOD uses SHA-1 to calculate the fingerprints of the blocks in the system. We pretty much depend on the fact that the SHA-1 algorithm requires 2⁸⁰ comparisons in order to generate a data block whose fingerprint collides with another block's. The reduction in the overall namespace for fingerprints is a real pain. I'm already starting to look for another option that will fit in 160 bits and will have the original unrestricted namespace.

It also occurs to me at this point that we will need to build in some support for changing the hash algorithm used for fingerprints to allow for eventual upgrades to the hashing algorithms we are using. Maybe we need to add a couple of bits to a fingerprint that we can use to specify the algorithm used to generate the fingerprint. Of course, this would add a certain amount of overhead to the whole operation since we would have to decide which algorithm to use each time. We also run into the problem of figuring out how/when to change the algorithm, in other words, how do we figure out that a given algorithm is generating collisions now?