James Randall, RSA Laboratories
March 11, 2005
The news of vulnerabilities in the SHA-1 algorithm emerged at a panel discussion at RSA Conference 2005 in San Francisco. An abstract from the research team of Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu described how two separate messages could be found that deliver the same SHA-1 hash using 269 operations, far fewer than the 280 operations previously thought needed to find a "collision" with an SHA-1 hash. This is basically the same kind of breakthrough as with the MD5 result last summer that required only 240 operations to find a collision.
This attack seems to have uncovered an unexpected weakness in one of the essential properties of SHA-1, a one-way hash function with a 160-bit output. Essentially, this new research suggests it is considerably less difficult than expected to create two somewhat different data files that can be reduced and compressed to an identical hash value. Cryptographers call these "collisions" in hash outputs. In this SHA-1 attack an attacker first tries to find near-collisions involving a single block pair and then searches for 2 distinct second blocks. It is the search for the second block pair that results in the estimated 269 possible evaluations.
A hash function takes a variable-length digital input and coverts it into a fixed-length pseudo-random hash value that can serve as a useful "fingerprint" for the input file. A one-way hash function like SHA-1 is easy to compute in one direction, but it's extremely difficult to reconstitute any message from the hash value. A good hash function is also expected to be "collision-free." That is, it should be hard to generate two input files which, when put through the hash function, generate the same hash value. (Hash function collisions must exist, of course, since the hash inputs can be longer than the outputs—but the design goal is to make collisions hard to find in practice.)
These attributes have made the one-way hash one of the most useful "primitives" in modern cryptography. Hash functions are, for example, essential in deriving message authentication codes (MACs) and "message digests”, the small files that are actually cryptographically "signed" to create a "digital signature" for larger files, in a typical public key cryptography application. The security of MACs and message digests is not affected by these attacks.
The practical impact of the new SHA-1 results on most applications today is still limited. It is, however, a wake-up call for cryptographers and the industry leaders concerned with the long-term vitality of our technology. For instance, existing signatures are not at risk due to a collision attack nor are the many applications that rely only on the one-way property or the pseudo-randomness of SHA-1. Furthermore, any successful attack on SHA-1 based on the new result would still involve a huge amount of computer processing, so this latest research is unlikely to have any significant impact on current applications, though it remains possible that the results could be improved further.
New signatures are only at risk if a signer is willing to sign messages essentially as directed by the attacker. For example, an attacker finds two messages with the same hash (in 269 operations), presents one of the messages to be signed, and then later replaces the first message with the second one and claims the second one was signed instead. If the messages the attacker finds happen to be something like “I promise to pay the recipient $100” and “I promise to pay the recipient $10,000”, the result would probably end in a court battle trying to determine which of the two messages is legitimate. For such situations, the cautious signer can just incorporate a little random data at the beginning of the message to thwart the attack.
Next-generation products will need to move to new algorithms. Most at risk are uses where a signature in computed on a message exactly as specified by the requestor or simply on the hash. However, the applications that use Message Authentication Codes (such as HMAC-SHA-1) are not affected by the attack described in this research.
NIST probably will accelerate its schedule, announced earlier this month, calling for migrating from the 160-bit SHA-1 algorithm to algorithms such as SHA-256 by 2010. Moreover, the news may force cryptographers to take a deeper look at the Merkle–Damgard construction for hash functions that use an iterative compression approach. The main significance of the SHA-1 results is the research community had not discovered this result in 10 years of research (although there was a gradual stream of improvements, including prior attacks such as on MD5 and SHA-0; the SHA-1 result built on them). Many people looked at the algorithm and certified it as "secure" (by cryptographers' definitions). Now that this design flaw has been discovered, researchers need to see how much further it can be extended, and whether there are similar attacks on related hash functions including SHA-256. Even though no similar flaws have been reported in SHA-256 yet, several months of analysis will be needed by the cryptographic community before any reassuring conclusions can be drawn.
Beyond that, it is now clear the industry needs an open evaluation process -- like the Advanced Encryption Standard competition—to establish a new hash function standard for the long term, or at least an alternative if SHA-256 and above are determined to be good enough after review. RSA Laboratories encourages others in the industry to work together with NIST on this effort.
NOTE: The above bulletin updates the "Collisions for SHA0, MD5, HAVAL, MD4, and RIPEMD, but SHA1 still secure" bulletin. RSA Laboratories will continue to update and follow-up on the SHA1 developments.