Recent announcements of the "breaking" of the SHA-1 hash function, hard on the heels of successful attacks on the MD5 and SHA-0 algorithms last year, surprised the cryptography community [and possibly the NSA], who expected it, but not so soon. Will 2005 also be, as Adi Shamir said of 2004, another "year of the hash function?"
The SHA-1 function is widely used for digital signatures in such applications as e-mail and Web browsers. Though experts agree this
A hash function operates on a message -- which might be random characters, an e-mail, a software binary, etc. -- to produce a message digest, or hash. These functions have two security properties: it is extremely difficult to find two messages that produce the same hash value [collision resistant]; and they are one way, meaning that given a message digest, one cannot reconstruct the original document.
So the loose term "broken" must be refined to say which of these two properties is broken, and how badly. The SHA-1 function produces a hash 160 bits long. In theory,
The recent SHA-1 break is a collision in which two random, non-meaningful messages were found to have the same hash in 2^69 comparisons, or about 2000 times faster than the brute-force method. That is still a very long job. Furthermore, the researchers applied some constraints on what the input message can look like in order to achieve this result.
Breaking the one-way property -- reconstructing the original message -- is much harder. Finding a second pre-image is harder still, and according to Dr. Burt Kaliski, chief scientist at RSA Laboratories, "there is no suggestion here that that is possible."
"The discovery of these tools opens new avenues to researchers," Kaliski said, adding that we can expect to see "thorough analysis of SHA through the rest of this year, and likely incremental improvements on this result."
Even if breaking a digital signature were possible, each one would still be a big effort, and "an attack on software distribution, such as patches or ActiveX controls, seems more likely than one on e-mail," opined security consultant Olin Sibert of Oxford Systems, "since many users may trust a single software download signature."
Kaliski believes one should look for additional ways to defend against this sort of real-world threat.
For instance, SHA-1 is the most used descendent of a family of algorithms that began with Ron Rivest's MD4 in the early 1990s. Later versions that produce longer message digests and are thus harder to break are collectively called SHA-2. The National Institute of Standards and Technology [NIST] previously recommended migration to SHA-2 by 2010. Kaliski believes NIST is unlikely to move that date up, since it would take almost that long to implement a changeover anyway.
Migration to SHA-2 "is a good stopgap, but I'd like to see more," Bruce Schneier of Counterpane Internet Security commented in his blog. "I'd like to see NIST orchestrate a worldwide competition for a new hash function" not based on the MD4 family. Kaliski concurred: "I'm not suggesting we abandon present algorithms, but it's good to have diversity in our approaches."