San Francisco — Three Chinese researchers said last week that they have compromised the SHA-1 hashing algorithm at the core of many of today's mainstream security products.

In the wake of the news, some cryptographers called for an accelerated transition to more-robust algorithms and a fundamental rethinking of the underlying hashing techniques.

"We've lost our safety margin, and we are on the edge," said William Burr, who manages the security technology group at the National Institute of Standards and Technology (NIST).

"This will create big waves, in my opinion," said the celebrated cryptographer Adi Shamir. "This break of SHA-1 is stunning," concurred Ronald Rivest, a professor at MIT who co-developed the RSA algorithm with Shamir.

But top cryptographers said that the Chinese approach, if it proves out, weakens but does not actually break the algorithm. A break would involve an attack where someone could create collisions with known messages.

"I think it may a little too early to tell if our results and techniques can lead to effective attacks on these other hash functions," said Yiqun Lisa Yin, one of the Chinese researchers, in an e-mail. "Historically, though, major advances in cryptanalysis often lead to broad applications."

The news of vulnerabilities in the SHA-1 algorithm emerged at a panel discussion at the RSA Conference here. Shamir, who is a professor at Israel's Weizmann Institute of Science, said he received an e-mail on Tuesday morning containing a draft technical abstract from the research team of Yin, Xiaoyun Wang and Hongbo Yu, two of whom have links to Shandong University in China. The abstract described how two separate messages could be found that deliver the same SHA-1 hash using less than 269 operations, far fewer than the 280 operations previously thought needed to find a "collision" with an SHA-1 hash.

"Large national intelligence agencies could do this in a reasonable amount of time with a few million dollars in computer time," said Burr of NIST (Gaithersburg, Md.).

Experts said that for a time, users can generally still rely on the vast majority of today's SHA-1-based systems and applications.

However, next-generation products will need to move to new algorithms. Most at risk are uses requiring blind digital certificates. However, the vast majority of applications that use Message Authentication Codes will not be directly affected by the attack, experts said.

The SHA-1 hash is a key technical underpinning of Secure Sockets Layer, a private-key technology used broadly to send secure information such as credit card numbers over the Internet. In addition, a handful of chip makers — including Atmel, Infineon, National Semiconductor and STMicroelectronics — use SHA-1 as the basis for so-called Trusted Platform Modules developed by the ad hoc Trusted Computing Group to provide a hardware root of trust in PCs and other devices.

"This means everyone needs to revise their security products, but it is hard to say when. We don't have to do it right away — [but] certainly in the next release of the OS," said a Microsoft Corp. manager responsible for some of the company's network security products.

Shamir and others said they believe the work of the Chinese team will probably be proven correct based on the trio's academic reputations, although details of the paper are still under review.

"It's extremely important to develop new kinds of hashing algorithms," said Shamir during the panel session here. "No one should be extremely worried or change designs of existing systems or programs. However, this diminishes our feeling of security in digital certificates in general."

"Digital signatures have become less secure," said MIT's Rivest at the same panel. "This is another reminder that conservatism is needed in the choice of an algorithm."

One member of the China team, Lisa Yin, was a PhD student who studied under him at MIT, Rivest said. Another was responsible for cracking the earlier MD5 hashing algorithm.

National effort?
Burr said that NIST will probably move up its schedule, announced earlier this month, calling for migrating from the 160-bit SHA-1 to algorithms such as SHA-256 by 2010. Moreover, he said, the news may force cryptographers to take a deeper look at the broad class of Vangard-Merkle algorithms, which use an iterative compression approach.

"We don't anticipate any problems in SHA-256, but we didn't anticipate any in SHA-1 either," he said. "We may need to think about whether we need to do something more fundamental and give academics time to study and publish on the issues here."

Some experts called for NIST to run an open process to find new and better hash techniques similar to the process used to forge the Advanced Encryption Standard. "It was a great model for developing future technologies," said Rivest.

"I shudder to think about it," said Burr. "It puts a large strain on a small group at NIST that already has a lot of things to do."

Scrambling to finish
Indeed, the 50-person security group at NIST is trying to finish by March specs for a new federal smart-card ID standard that could ultimately be used by as many as 5 million workers and influence other ID programs. "It's a huge effort in a short time. We are frantically trying to get this out," Burr said.

Some saw the SHA-1 attack as motivation for moving up to next-generation crypto techniques. Spyrus Inc. and Infineon Technologies announced during the RSA Conference their first products to implement the so-called Suite B crypto protocols. The protocols include elliptic-curve cryptography, which is mandated as a next-generation technology for the National Security Agency.

"Crypto is aging at a faster rate than anyone anticipated," said Sue Pontius, chief executive of Spyrus, a 12-year-old San Jose, Calif., security company that struck a partnership with Infineon in 1996.

Others were happy to stick with trailing-edge technology. Shamir pointed out that one of the Microsoft demos at a Bill Gates keynote speech here employed the MD5 hash algorithm to find spyware, despite the fact that the algorithm has been compromised and is no longer recommended for use.

Members of the Trusted Computing Group, meanwhile, said that they expect to continue using SHA-1, hard-coded into some of their products, in order to provide a hardware basis of trust for PCs and other systems. However, a future-generation specification will upgrade to new algorithms.

"If we were starting over today we would probably start with a new algorithm, but we feel no need to panic at this point," said a senior technologist in the group who asked not to be named.