Sebastian Kirsch: Blog

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /homepages/u37107/www.sebastian-kirsch.org/moebius/blog/wp-includes/functions-formatting.php on line 76

Bruce Schneier reports that SHA-1 has been broken. SHA-1 is the Secure Hash Algorithm, a 160-bit hash function designed by the National Security Agency in 1995. Schneier’s entry is scarce on details, as the original paper has not yet been published. The attack was devised by Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu from Shandong University in China, who previously published attacks on the MD-5 hash algorithm.

Of course, one has to take into account that a cryptographer’s “broken” is different from anyone else’s “broken". For one, it doesn’t mean that all applications using SHA-1 will magically stop working, or will suddenly be insecure.

The attack on SHA-1 is a collision attack, not a preimage attack. A collision attack is an attack in which two different data streams are produced that hash to the same value – and therefore can be used interchangeably as far as the hash value is concerned. In difference, a preimage attack would allow the generation of a data stream that hashes to a specific hash value. Because the attack on SHA-1 is a collision attack, it cannot be used when SHA-1 is used as a message authentication code. It only affects its use as a digital signature algorithm.

Another thing is the scale of the attack. It reduces the number of hash computations needed to find two data streams with the same hash value from (theoretical, brute force) 2⁸⁰ to 2⁶⁹. This is factor of about 2000. The practical effect of this is rather negligible, as 2⁶⁹ is still a pretty large number.

So the attack on SHA-1 is noteworthy primarily because it dispels the belief that SHA-1 is just as secure as a random function and can only be attacked by brute force. This in itself is not surprising – in fact, it is the basic premise of cryptoanalysis: That a better method than brute force is possible. The “major, major cryptoanalytic result” touted by Schneier seems to be that attacks on the SHA family of hash functions were not previously known.

So, what to do now, since SHA-1 is “broken"? As a software developer, I would not be too alarmed by this result. As detailed above, the hypothetical attack only concerns digital signatures – all the other areas where SHA-1 is used are still safe (for example, password hashing or integrity checking for files.) And even then, the required effort is still too large for casual usage.

As a cryptoanalyst, I would look forward to the publication of the paper. And as everyone else, I would start a bet on the time of the first attack on the lesser-known hash algorithms like RIPEMD-160.