Digital signatures could be forged, claim boffins

Encryption circles are buzzing with news that weaknesses in the mathematical functions of digital signatures could allow them to be forged.

French computer scientist Antoine Joux first claimed to have uncovered a flaw in a popular algorithm called MD5, often used with digital signatures. Then four Chinese researchers released a paper that reported a way to circumvent a second algorithm, SHA-0.

While their results are preliminary, these discoveries could eventually make it easier for intruders to insert undetectable back doors into computer code or to forge an electronic signature - unless a different, more secure algorithm is used.

A third announcement, which was even more anticipated, took place on Tuesday evening at the Crypto 2004 conference in California. Eli Biham and Rafi Chen, researchers at the Israel Institute of Technology, originally were scheduled to present a paper identifying ways to assail the security in the SHA-0 "Secure Hash Algorithm," which was known to have imperfections. In a presentation on Tuesday evening, however, Biham reported some early work toward identifying vulnerabilities in the SHA-1 algorithm, which is believed to be secure.

Biham's presentation was very preliminary, but it could call into question the long-term future of the wildly popular SHA-1 algorithm and spur researchers to identify alternatives.

Currently considered the gold standard of its class of algorithms, SHA-1 is embedded in popular programs like PGP and SSL. It's certified by the National Institute of Standards and Technology and is the only signing algorithm approved for use in the US government's Digital Signature Standard. SHA-1 yields a 160-bit output, which is longer than MD5's 128-bit output and is considered more secure.

Jim Hughes, general chairman of the Crypto 2004 conference, said on Tuesday morning that the news was sufficiently important that he was organising the first Webcast in the conference's 24-year history. "There are three significant rump session papers on hash collisions that will be presented," including an update on Joux's findings, Hughes said in a message to a cryptography-related mailing list.

"If you could find two contracts that hash out to the same signature, you could replace one with the other and in a court of law there would be at least an ambiguity about which one is valid," Hughes, a senior fellow at StorageTek, said in a telephone interview. "That's a very significant possibility."

The MD5, SHA-0, and SHA-1 algorithms are known to computer scientists as hash functions. They take all kinds of input, from an email message to an operating-system kernel, and generate what's supposed to be a unique fingerprint. Changing even one letter in the input file results in a completely different fingerprint.

Security applications rely on these fingerprints being unique. But if a malicious attacker could generate the same fingerprint with a different input stream, the cloned fingerprint - known as a hash collision -- would certify that software with a back door is safe to download and execute. It would help a crook who wanted to falsely sign an email instructing that someone's bank account be emptied.

Declan McCullagh writes for CNET News.com