Sebastian Kirsch: Blog

Wednesday, 16 February 2005

SHA-1 Broken

Filed under: — Sebastian Kirsch @ 11:26

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) 280 to 269. This is factor of about 2000. The practical effect of this is rather negligible, as 269 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.

Comments

No comments yet.

RSS feed for comments on this post.

Leave a comment

Sorry, the comment form is closed at this time.


Copyright © 1999--2004 Sebastian Marius Kirsch webmaster@sebastian-kirsch.org , all rights reserved.