March 13, 2005
Buh-bye SHA-1
SHA-1 is in the news again. The best place to get up to speed on what's happening with SHA-1 is from Bruce Schneier. I'll try to summarize key points from Bruce's blog.
The Chinese researchers claim this: Use their technique and generate
2^69 byte strings, and for each of those byte strings, create the SHA-1
hash. In the course of doing this, you will generate two byte strings that
have the same SHA-1 hash function. Thus SHA-1 is "broken" because experts
previously believed that you would need to generate 2^80 such byte
strings.
If you have a byte string -- say, your latest bank statement -- how many byte strings would you have to generate in order to create an SHA-1 hash that matches the hash of your original byte string? The answer: close to 2^160. It's still infeasible to duplicate the hash of an existing byte string. To non-experts in the field, it hardly sounds like SHA-1 is "broken."
But as Bruce explains, to experts in the field, SHA-1 is broken. These experts expect a secure hash function to have two properties, and when either of these properties does not hold, the hash function is broken. The first property is that it's highly improbable that you can recover the original byte string from its hash value. The second property is that it's highly improbable to find two different byte strings that have the same hash value. In the case of SHA-1, the second property no longer holds because 2^69 is less than the theoretical, "brute-force" value of 2^80.
This discovery hardly means that all use of SHA-1 is insecure. But it does mean that if you proved, mathematically, that your protocol based on SHA-1 was secure, then one of underlying assumptions may no longer hold. You may need to fix your proof.
Without a doubt, new cryptographic protocols will not use SHA-1. Again, from Bruce's blog (the quote is from Jon Callas, CTO of PGP):
"It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off."
The most important take-away is to expect surprises in research on secure hash functions. As Bruce says:
Posted by Doug Sauder at March 13, 2005 04:53 PMHash functions are the least-well-understood cryptographic primitive, and hashing techniques are much less developed than encryption techniques. Regularly there are surprising cryptographic results in hashing.