A paper being circulated at the RSA Conference security gathering in San Francisco this week claims researchers have found collisions in SHA-1 (Secure Hashing Algorithm 1), an algorithm previously relied upon as secure.
While the real-world impact for people using technology based on the algorithm – basically, anyone who uses a computer – will be miniscule in the short term, the paper could represent the most significant crypto crack in a decade.
For cryptographers, this is a crisis, crypto expert Burt Kaliski, chief scientist of RSA Security Inc’s RSA Labs, told ComputerWire. Full SHA-1 has been considered secure for years, and has withstood all previous attempts to crack it.
Almost everybody who is not a cryptographer can relax for the moment, but SHA-1 should no longer be built into new products, Kaliski said. Cryptographers also need to start looking for a new standard algorithm, he said.
The paper has not yet been published, but a 3-page precis is doing the rounds. The full paper is in the hands of a few cryptographers, who are cautiously agreeing that the researchers probably have done what they say they have.
Because of the credentials of the researchers involved, it is safe to assume they are on to something, Kaliski said. According to custom, the paper will have to be peer-reviewed before the crypto community fully backs its findings.
The researchers are Xiaoyun Wang and Hongbo Yu of Shandong University in China, and independent consultant Yiqun Lisa Yin, currently at Princeton University in the US.
SHA-1 is a hashing algorithm. It takes a block of data and outputs a message digest known as a hash. A hash is a string of nonsensical characters that (until now, perhaps) uniquely identifies that message.
Because no two documents are supposed to produce the same hash, what would be called a collision, it should be possible to ensure that data had not been tampered with while in storage or transit by looking at a digitally signed hash.
SHA-1 is 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, according to the US National Institute of Science and Technology.
Most of the applications of SHA-1 rely upon the fact that you cannot reverse-engineer a document from its hash. That quality of the algorithm is still sound. The other quality, which says no two documents have the same hash, is being questioned.
The Chinese researchers, if their paper stands up to scrutiny, have been able to find collisions using SHA-1. In other words, they can find two documents that produce the same hash or message digest, in a shorter time than should be possible.
We have developed a set of new techniques that are very effective for searching collisions in SHA-1, the research precis reads. Our analysis shows that collisions of SHA-1 can be found with complexity less than 2[to the power]69 hash operations.
This means that the researchers say they have broken through a statistical barrier known as the birthday paradox, demonstrating that SHA-1 is flawed, Kaliski said.
The birthday paradox says a collision becomes probable after a certain critical mass of documents are compared, which would enable a brute-force attack.
If you get 23 people in a room, the chance is better than 50% that two of them both have the same birthday, Kaliski said, explaining the principle. If you get enough messages in a room, chances are that two will have the same hash.
In SHA-1, which uses 160-bit hashes, the threshold should be 2 to the 80th power operations. The paper says it can be done in 2 to the 69th operations. This means there is a flaw in SHA-1 that allows a quicker crack than brute force.
It would require a massive amount of computational power to do this. It is said that it would take a $10m computer a year to process 2 to the 80th operations. But processing speeds are increasing, and crypto hacks have a tendency to become more efficient.
Cryptographers consider the greatest threat, still largely hypothetical, to be from a scenario in which an attacker creates two documents with the same hash, one is digitally signed, and then the attacker tries to claim it was the other document that was signed.
Kaliski said that it would be possible, assuming the research is correct, to create two documents that start and end identically, but have different content in the middle sections (a price change in a contract, for example), which still produce the same hash.
There are substantial mitigating factors. The forged document would usually be infected with nonsensical characters that, while they could sometimes be partially masked, would highlight which document was legitimate.
Still, this is all very surprising, Kaliski said, because SHA-1 has been considered secure for so long. It was developed by the US National Security Agency, and NIST approved it as a standard for US government use in 1995.
However, only two weeks ago NIST said it would start to phase out SHA-1, and start promoting stronger variants SHA-256 and SHA-512 in its place, with the object of replacing SHA-1 in government by 2010.
It’s not currently clear if NIST had advanced notice of the SHA-1 crack, or if it was basing its advice on a partial crack that was announced last August. It’s not yet clear if the SHA-1 crack could some day be applied to SHA-256 and SHA-512.
