Cryptographers will start to move away from today’s most commonly used hashing algorithms, after three sets of researchers this week disclosed previously unpublished weaknesses in SHA and MD5 algorithms.
The findings, revealed at the Crypto 2004 conference in Santa Barbara, California this week, may signal the final nails in the coffins of the MD5 and SHA-0 algorithms, and have raised questions about the long-term security of SHA-1.
As a cryptographer, this is really interesting and exciting, but as a computer user there’s no real reason to worry, said crypto expert Bruce Schneier, CTO of Counterpane Internet Security. The attacks are still theoretical, not practical.
Researchers from France, Israel and China used the conference to separately demonstrate how MD5 and SHA-0 are not as secure as was thought, and that SHA-1 may, in future, demonstrate similar insecurities.
SHA-1 is a US government-endorsed standard, developed by the National Security Agency. It is used in many common applications such as SSL and PGP. SHA-0 is no longer in common use, but MD5 is still often used.
Princeton computing professor Edward Felten said the research casts serious doubt on the medium- and long-term viability of MD5 and SHA-1. Since systems being deployed today may be used for a long time, this is an immediate problem for system designers.
SHA-1, for Secure Hash Algorithm 1, takes any arbitrary block of data and produces a 160-bit message digest – essentially a gibberish string, or hash, that uniquely identifies that message.
This is used to ensure that data, be it text or executable code, is not tampered with while in transit. The algorithm has been approved for US government use by the National Institute of Standards and Technology since 1995.
NIST says: 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.
The attacks demonstrated were against this second no collision property – the fact that no two unique messages should generate the same hash. The researchers found full collisions in SHA-0 and MD5, and a partial collision in SHA-1.
In the case of SHA-0, French researcher Antoine Joux demonstrated a full collision. Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, of various Chinese universities, demonstrated several collisions in MD5.
Eli Biham of the Technion university in Haifa, Israel demonstrated that a collision could be found in SHA-1, which is still in wide use and is believed to be secure, but only when the algorithm was only partially executed.
According to RSA Labs’ chief scientist Burt Kaliski, the full SHA-1 requires 80 steps, or rounds to be performed on the data. If you only did 40 steps, a collision could be found, Kaliski said. That’s exactly why there are 80 steps.
While fascinating to cryptographers, practically speaking these findings probably have little impact. While two documents could generate the same hash, a real-world attack would require both documents to have meaning, Kaliski said.
For example, you could not easily just swap a $100 check with a $1,000 check and have both checks create the same hash. Likewise, you could not easily just insert a virus where a legitimate program was and create the same hash.
However, cryptographers said that now that weaknesses have been shown, developers should think about using other algorithms instead. The findings show that the peer review process critical to cryptographic research is working.
Due to the immense complexity of the mathematics involved in cryptanalysis, it’s said that you cannot ever say definitively say that an algorithm is unbreakable, you can only say that you know really smart people who cannot break it.
The fact that the process has found problems in these algorithms should give you more confidence in the other algorithms that the process has not found problems with, Kaliski said. Researchers are trying to break every algorithm, he said.
Schneier said SHA-224, SHA-256, SHA-384, and SHA-512, all standards, should be considered as replacements for SHA-1. Those algorithms use 224, 256, 384 and 512-bit hashes, in place of SHA-1’s 160-bit hash.
SHA-0 was created in 1994 and supplanted following year by SHA-1, after the NSA found undisclosed vulnerabilities in the algorithm. People stopped using SHA-0 then, but it has taken nine years for these latest vulnerabilities to come to light.
Think of all the big cryptographic institutes in the world – the US government, the Chinese government, Israel, Germany, Japan… Schneier said. We don’t know what they can do. We don’t know how far ahead they are.