U.S. mulls new digital-signature standard

Now the U.S. government is trying to figure out what to do about it.

The decade-old algorithm, called the Secure Hash Algorithm, or SHA-1, is an official federal standard and is embedded in every modern Web browser and operating system. Any change will be expensive and time-consuming--and a poor choice by the government would mean that the successor standard may not survive another 10 years.

"We're going to have to make a decision fairly soon about where to push people," said John Kelsey of the National Institute of Standards and Technology (NIST), which convened a workshop here on the topic Monday. Even though NIST is only technically responsible for government standards-setting, Kelsey noted, "we're likely to get a lot of other people to head in that direction as well."

The findings by the researchers at China's Shangdong University, which they described in an interview with CNET News.com in March, are still of more theoretical than practical interest. But as computing speed accelerates, their discovery eventually will make it easier for intruders to insert undetectable back doors into computer code or to forge an electronic signature--unless a different, more secure "hash" algorithm is adopted.

NIST is weighing two broad options: selecting a newer variant of SHA-1 believed to be more secure, or undertaking the much longer process of soliciting public suggestions for an entirely new algorithm that can be used for digital signatures. (The agency followed the second path before deciding on the Rijndael algorithm, used for data encryption rather than signatures.)

Complicating the decision-making process is a belief among computer scientists that even the newer algorithms related to SHA-1 may suffer from similar flaws.

Variants on SHA-1--originally devised by the National Security Agency--exist and are growing in popularity. NIST has announced a set of algorithms known generally as SHA-2 (sometimes called SHA-256, SHA-384, or SHA-512), but they haven't been subject to as much public scrutiny as SHA-1, which makes some researchers nervous. Orr Dunkelman, a doctoral student at Technion University in Israel, said "I have a strong suspicion that in the next five years, SHA-256 might be considered broken."

Last year, flaws also were reported in MD5, a similar algorithm widely used on the Internet. SHA-1 yields a 160-bit output, which is longer than MD5's 128-bit output and is considered more secure.

NIST's hash-bash
To computer scientists, the SHA and MD5 algorithms are known as hash functions. They take all kinds of input, from an e-mail message to an operating-system kernel, and generate what's supposed to be a unique fingerprint. Changing even one letter in the input file should result 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.

That would help a crook who wanted to falsely sign an e-mail instructing that someone's bank account be emptied. Or a digitally signed contract could, in theory, be altered but appear valid.

Steven Bellovin,
Columbia professor

There's no need to panic, said Steven Bellovin, a professor of computer science at Columbia University, who described the flaws in SHA-1 as still theoretical. But "even if we decide that SHA-1 is good enough for today, someday we are going to have to deploy new hash functions," Bellovin said.

Complicating that deployment is the dizzying scope of the upgrade project. Hundreds of protocols including TLS/SSL (used by Web browsers), SSH (used for remote logins) and IPsec (used in virtual private networks, or VPNs) eventually would have to be reworked to support the new standard. Then Internet users would have to be convinced to upgrade.

"You cannot deploy a new algorithm of any sort all over the place all at once," Bellovin said. "The Internet is far too large." He said that newer applications based on NIST's successor algorithm should be able to "switch-hit" and support the older algorithms when talking to older computers.

Although the U.S. government and most companies may gradually switch from SHA-1--including PGP Corp., which sells desktop encryption software--it won't be practical to abandon it anytime soon, said Niels Ferguson, a cryptographer who works for Microsoft. "You have to be able to read old files and talk to people who haven't updated their PCs in seven years," he said.

NIST has announced plans to ditch SHA-1 by 2010. But it is still far from making a decision. "We really have no strong preconceptions at this point about what we want to do," said Bill Burr, manager of NIST's computer security division.