Security threats Toolkit

Hashing standard cracked

Tags:
Vulnerability,
Cryptography,
Broken,
SHA-1

Published: 17 Feb 2005 09:40 GMT

An encryption standard widely used in digitally signing documents and programs has a flaw in it that could allow for the creation of forgeries, sources said on Wednesday.

In a three-page research note seen by ZDNet UK sister site CNET News.com, three Chinese scientists -- Xiaoyun Wang and Hongbo Yu of Shandong University and Yiqun Lisa Yin, a visiting researcher at Princeton University -- stated they have found a way to significantly reduce the time required to break a algorithm, known as the Secure Hashing Algorithm, or SHA-1, widely used for digital fingerprinting data files.

Other cryptographers who have seen the document said that the results seemed to be genuine.

"At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team," Bruce Schneier, a cryptographer and chief technology officer for Counterpane Internet Security, said on his Web site.

An attacker could use the flaw to create two documents or programs that have the same digital fingerprint, also known as a hash; one file could be a legitimate version of the data, while the other could be a forgery. For example, code signing -- where a program is posted online along with its SHA-1 fingerprint as a way to guarantee its integrity -- would essentially be rendered meaningless by this attack.

This causes problems for digital signatures because signing documents is a two-step process. First, a digital fingerprint, or condensed version of the document, is created. Then public-key encryption is used to sign that hash. If two different documents create the same hash, then the process breaks because no one can prove which document was signed.

The latest attack made use of a cryptoanalysis attack against a similar, but more easily breakable, algorithm known as SHA-0.

While the problems -- if confirmed -- could lead to SHA-1 being phased out by the government, the effects of the break may not be dire, said Paul Kocher, a cryptographer and president of Cryptography Research.

"This is feasible if you have thousands of computers at your disposal," he said, at his company's booth in the exhibition hall of the RSA Conference in San Francisco. Moreover, the attack is a problem only if an untrustworthy source is generating the data that is being signed. That person could have generated two copies of the data: one public version that will be signed, and a forgery, or malicious version, that will be kept secret.

The break of the full SHA-1 algorithm reduces the complexity of producing a "collision" -- or matching hash value -- by a factor of about 2,000. If cluster of computers could handle 1 million hash values every second, it would still take about 19 million years to find two different documents whose digital fingerprints match.

That means the situation is serious but not desperate, Counterpane's Schneier said, adding that companies should start worrying about the attack over the next year. "The industry will produce better solutions really quick," he said, warning the industry and government not to tarry long. "Remember the motto of the NSA: Attacks only get better, they never get worse."