, 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. Moreover, while SHA-1 is important for many applications, a weakness in the algorithm's collision resistance only threatens a small percentage of them, he added.
"The vast majority of calls to a SHA-1 algorithm, only a very small proportion are vulnerable to collision attacks," Burr said.
Common applications that use hash algorithms are somewhat affected by the attacks, but could be modified to be more resistance to any weaknesses in the SHA-1 algorithm, according to Steven Bellovin, computer science professor at Columbia University.
"A collision attack means that it's possible to produce two messages with the same hash value," he said in an e-mail interview with SecurityFocus. "It does not mean that it's possible to produce a message with the same hash value as an existing message. That means that previously-signed documents are not in danger -- yet."
Bellovin co-authored, with security researcher Eric Rescorla, a survey of three popular applications that use hash functions: the secure e-mail protocol, S/MIME; the secure virtual private network protocol, IPSEC; and the TLS security protocol for messaging applications. The researchers found that, while all three are not critically impacted by the cryptographic attacks, the protocols will require modifications to handle an upgrade to a new hash algorithms.
"My concern is that the current protocols are not ready for upgrades, even if we had agreement on new hash functions," Bellovin said in the e-mail interview.
That leaves the cryptographers with a lot to talk about during a rump session, dubbed the Hash Bash, that will be held at the end of October to talk about the issue of SHA-1. While some researchers have advocated holding a competition to pick the next hash algorithm, similar to the run off to decide the Advanced Encryption Standard, other researchers have focused on simpler solutions--for example, adding 40 rounds of additional calculation--and pseudo-randomness--onto the SHA algorithm.
"We, as a community, have a lot of ways to fix this," said Bruce Schneier, chief technology officer for Counterpane Internet Security and a well-known cryptographer.
Schneier recommended that companies wait to see what advice comes out of the conclave of crypto specialists. Until then, developers that have to implement some hash algorithm should look to the strength of SHA-256, he said.
"The sky is not falling, but you can start to see cracks in the ceiling," Schneier added. "If you can wait at all, wait for October when we get together and try answer the questions about the future."