, SecurityFocus 2005-08-23
Three Chinese researchers have further refined an attack on the encryption standard frequently used to digitally sign documents, making the attack 64 times faster and leaving cryptographers to debate whether the standard, known as the Secure Hash Algorithm, should be phased out more quickly than planned.
The attack, presented last week at the Crypto conference in Santa Barbara, Calif., would allow a forger to create two documents that return the same digital fingerprint, a short sequence of numbers that represent the contents of a much larger document. While experts debate whether the attack is practical, the trend seems to indicate that the Secure Hash Algorithm (SHA-1) is succumbing to less processor-intensive breaks, said William E. Burr, manager of the the Security Technology Group at the National Institute of Standards and Technology (NIST).
"It is certainly somewhat alarming," Burr said. He likened the rapid advances in attacks on SHA-1 to a submarine under fire. "What we are figuring out right now is whether we have to do a crash dive drill-- where some people might not make it inside before we close the hatch, but at least we will save the ship."
The improved attacks on SHA-1 are the latest break against hash algorithms, mathematical techniques of producing digital fingerprints of files that perform a key function in encryption and digital signatures. A digital fingerprint, or hash, is a small string of numbers that represent a much larger file or document. A digital signature actually validates a document's fingerprint not the document itself, because signing an actual document would be far too processor-intensive.
Last year at the Crypto conference, two researchers at the Technion institute in Israel, Eli Biham and Rafi Chen, presented a paper summarizing weaknesses in the security of SHA-1. The researchers were originally scheduled to present further breaks in a weaker version of the algorithm, SHA-0, known to have imperfections.
By February, three Chinese researchers--Xiaoyun Wang and Hongbo Yu of Shandong University and Yiqun Lisa Yin, a independent security researcher based in Connecticut--expanded the weaknesses in an actual attack that reduced the complexity of breaking the SHA-1 standard to 269 from 280. The latest result--presented by Xiaoyun Wang, who is also a professor at Tsinghua University, and her two co-authors, Andrew Yao, a professor at Tsinghua University and Frances Yao, a professor at City University of Hong Kong--further simplifies the attack to a complexity of 263.
The complexity is a measure of the number of calculations that have to be performed to find a collision--that is, two documents or files that produce the same hash.
"Using these techniques, we believe it will not be long before people can produce actual collisions of SHA-1," Prof. Wang said in an e-mail interview with SecurityFocus.
The methods are also applicable to attacks against the weaker hash algorithm known as MD5. A run-of-the-mill PC can currently produce a collision within MD5 within hours, Wang said. Using the new techniques, that time could be reduced to minutes, she estimated.
While the theoretical weakening of the security of SHA-1 has cryptographers abuzz, the practical implications of the attacks are more questionable.
"We had already planned to phase out SHA-1 by 2010," NIST's Burr said. "Now we are talking about whether it is practical or necessary to speed that up."
Cryptographers originally thought that a computer that could perform an attack calculation 1 million times every second would find a collision only once in 38 billion years. In February, the original break found by the researchers consisted of a method that could produce a collision once every 19 million years. The latest result further speeds the search in finding a collision, but it would still occur once every 300,000 years.
Burr also stressed that no one has yet confirmed Wang's results.