Chinese researchers crack major U.S. government algorithm used in digital signatures
Wednesday, February 16, 2005
According to computer security expert Bruce Schneier, a widely-used cryptography algorithm, known as SHA-1, has been broken by three researchers at Shandong University in China. Designed by the US intelligence agency NSA, SHA-1 has been adopted as an official US government standard and has become widely-used in security applications worldwide, notably digital signatures. The three female researchers, Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, have reduced the amount of time needed to find two documents with the same signature by a factor of more than 2000.
The SHA-1 algorithm is used to compute a short string of numbers, known as a hash, for any digital document. The algorithm is constructed such that small changes in the document cause the hash to change drastically. By this means, the hash can be used to verify that a document has not been tampered with.
The attack that Schneier describes is a "collision attack," rather than the more useful "pre-image" attack. In a pre-image attack, the codebreaker is able to find a document with different contents that matches an existing hash and so can claim an existing signature was on something else. In the somewhat less valuable "collision attack," the codebreaker is able to devise two documents that both have some particular hash. A adversary might use this to claim that an altered document is the original on the grounds that they have the same hash. A crafty adversary might also be able to trick someone into signing an innocuous document, one of a pair from a collision. The other document, which might not be as harmless, would then also appear to have been signed by the same person. If collisions can be found for SHA-1, then digital signatures will no longer vouch for a document's authenticity.
The attack, for now, is more of a theoretical than a practical kind: it would currently take thousands of years on a modern personal computer, and would still be slow even if a large number of computers were used in parallel.
Xiaoyun Wang is currently a professor at Shandong University, while Hongbo Yu is a doctoral candidate at the same institution. Yiqun Lisa Yin is currently a visiting researcher at the Princeton Architecture Laboratory for Multimedia and Security (PALMS). Last year, Xiaoyun Wang and Hongbo Yu also took part in breaking a series of similar algorithms, including the widely used MD5 hash, as documented in their paper presented at the Crypto 2004 conference.
Officials from the National Institute of Standards and Technology (NIST) have recently recommended dropping SHA-1 in favor of stronger, slower algorithms, such as SHA-256, Federal Computer Week reported on February 7, 2005, just 7 days before Schneier announced the SHA-1 break. Despite deprecating SHA-1, William Burr, the head of NIST's security technology group, said that "SHA-1 is not broken, and there is not much reason to suspect that it will be soon."
Sources
- Bruce Schneier. "SHA-1 broken" — Schneier on Security, February 15, 2005
- Florence Olsen. "Hashing out encryption" — Federal Computer Week, February 7, 2005
- National Institute of Standards and Technology. "FIPS PUB 180-1 (SHA-1 standard)" — NIST website, April 17, 1995
