A forthcoming paper by a set of Chinese security researchers lays out several newly discovered problems with the SHA-1 hash algorithm, a standard that is used the world over.
The paper, written by three researchers at Shandong University in China, describes a series of collisions in the algorithm that can allow attackers to forge digital signatures. SHA-1, like MD5 and other similar algorithms, is used to compute a hash, or digest version of a set of data. That digest is then used to generate a digital signature.
A collision occurs when two separate messages have the same hash value. This would in turn call into question the validity of other signatures generated by the same hash algorithm. The research done by the Shandong team—Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu—builds upon previous work on collisions in SHA-1, but their findings show that it is possible to cause collisions much faster than previously thought.
SHA-1 is used in dozens of common applications and is the basis for the digital signature function in protocols such as SSL (Secure Sockets Layer), which is used to encrypt traffic flowing to and from millions of Web sites. The new research does not allow attackers to decrypt this traffic, but instead creates doubt about the validity of the signatures generated by the protocol.
“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,” Bruce Schneier, chief technology officer at Counterpane Internet Security Inc. and a noted cryptographer, wrote on his Web site this week.
The new paper was a prime topic of conversation among the crypto community at the RSA Conference this week. Although the paper has yet to be published, many cryptographers have seen portions of it and say they are impressed by the work the Chinese team did.
“Its a phenomenal piece of work. As cryptographers, we knew this was coming, but not this soon or this severe,” Schneier said in an interview. “When you break NSA [National Security Agency] technology, you feel doubly good because its alien technology. Its dropped in your lap, and you know nothing about it.”
SHA-1, along with MD5, is one of the more common hash algorithms in use today, and until recently had been considered quite solid. The National Security Agency developed SHA-1 in the mid-1990s, and it received FIPS (Federal Information Processing Standard) certification as the Secure Hash Standard in 1995 from the National Institute of Standards and Technology.
“The SHA-1 is called secure because it is computationally infeasible to find a message which corresponds to a given message digest, or to find two different messages which produce the same message digest,” NIST said in its announcement of SHA-1 as the Secure Hash Standard.
Schneier emphasized that attacks on SHA-1 are still incredibly difficult and resource-intensive, and that newer hash algorithms, such as SHA-256, are available.
“Its time to walk, not run, to the fire exits. You cant see the fire, but you can feel the heat,” he said. “This is at the far edge of feasibility right now. But its very serious. Hash functions are the most commonly used cryptographic primitive. Far more so than encryption. SHA-1 is everywhere.”
Check out eWEEK.coms for the latest security news, reviews and analysis.