September 6, 1999

NEWS ANALYSIS

Internet Code-Cracking Project Shows Need for Stronger Locks

By SARA ROBINSON

hen an international team of researchers demonstrated recently that they could break the standard lock that protects financial transactions over the Internet, they sent a clear message to the e-commerce community: Now is the time to get stronger locks.

The researchers' demonstration showed only that locks of a certain strength, known as RSA 512-bit encryption codes, could be broken. But it is precisely that code strength that is used for a number of the financial transactions with e-commerce sites on the Internet.

Chart A Weak Link in Internet Transactions How RSA encryption works, and one way it is vulnerable

The demonstration, part of a challenge sponsored by the company that invented the RSA system, required computing resources typically available only to governments or big corporations. But the computing power was insignificant compared with other code-cracking efforts, said Arjen Lenstra, one of the main researchers for the seven-month effort.

Moore's Law, which says that computing power roughly doubles every 18 months, suggests that such power may someday be available to individuals. Even more important, improvements in the techniques used for factoring large numbers -- a process that enables RSA codes to be cracked -- may dramatically reduce the computational resources required.

"As soon as you break something, then within a relatively short time, many people will be able to break it," said Lenstra, a computer scientist at Citicorp. "I have no doubt that within a few years it will be more or less a triviality."

The government has long restricted the export of strong encryption, citing concerns that it might be used to conceal messages or transactions by terrorists or drug traffickers. Over the last year, because of market pressures, it has relaxed those standards somewhat for encryption products related to e-commerce, but the 512-bit standard remains prevalent among Web sites.

"The level of security has been 512 for so long that it's still a part of the infrastructure," said David Wagner, a computer security researcher at the University of California at Berkeley. "It will be several years before this changes."

Dith Pran/The New York Times
Arjen Lenstra, a Citigroup computer scientist, worked on the encryption project.

The current export-control policy, which requires companies seeking to export encryption products to go through a one-time review, is so complex that many encryption experts, secure-software manufacturers and government officials interviewed for this article could not say how it applies to RSA products.

"The problem with the encryption policy is that the devil is in the details," said Roszel Thomsen, a lawyer specializing in export controls at Thomsen & Burke, a law firm in Washington. "The policy has been drafted with a degree of ambiguity that is calculated to allow the regulators to make up their minds case by case."

From the government's perspective, "complicated is in the eye of the beholder," said William Reinsch, the under secretary of commerce for export administration. "We're trying to pursue a balanced policy. I believe that the critics of our policy are those who do not believe that national security and law enforcement concerns are as important as we believe they are."

Many security experts believe that encryption export standards have been tied to levels decipherable by the National Security Agency, whose think tanks -- staffed with mathematicians -- devote enormous resources to code cracking.

"Organizations could already be breaking e-commerce keys regularly, and just not telling anyone," said Bruce Schneier, chief technology officer of Counterpane Internet Security Inc., a consulting company based in San Jose, Calif. "I think there's a 100 percent chance the NSA does this already They would be remiss in their charter if they didn't."

The researchers' actual feat was to factor a 155-digit number into its two component prime factors. The inherent hardness of factoring, an immensely difficult and time-consuming task for even the most powerful computers, provides the security for RSA. Factoring a certain large number associated with an RSA key enables that key to be cracked.

Named for its founders -- Ronald Rivest of the Massachusetts Institute of Technology, Adi Shamir of the Weizmann Institute of Science in Rehovoth, Israel, and Leonard Adleman of the University of Southern California -- RSA is an example of what is known as an asymmetric or public-key system.

Each merchant on the Web possesses a public RSA key, which is listed in a public record, and a private key, which is known only to that merchant. When a message has been locked with a public key, only the private key can unlock it.

Related Article Researchers Demonstrate Computer Code Can Be Broken (August 27, 1999)

This asymmetry of keys is essential for Internet transactions because unlike faster "symmetric key" methods of encryption, RSA does not require that the sender and the receiver of an encrypted message meet to transfer a secret key.

A secure Internet transaction, like a credit card purchase, typically takes place in a protected tunnel temporarily established between a computer user's Web browser and an e-commerce site. This protected tunnel, designed by Netscape but now an Internet standard, is known as SSL, or Secure Socket Layer.

Since RSA encryption is very slow for long messages, the browser establishes the tunnel with a faster, symmetric key technique. But then the symmetric key must be securely transported to the e-commerce site. This transport depends on RSA.

The transaction uses the strongest encryption that both the Web browser and the site support. To comply with the export controls, browsers come in both domestic and exportable versions. The exportable version, frequently shipped even with computers purchased in the United States, is limited to 512-bit RSA transactions except with certain authorized sites -- typically large banks or brokerage firms -- that have paid extra for stronger encryption capability.

Government controls have been eased since January, enabling a larger class of sites to use 1,024-bit RSA encryption -- considered secure by most experts -- in transactions with exportable browsers. But many restrictions still apply.

The bigger problem, however, is that many Web sites are using 512-bit encryption for all their Web transactions, regardless of the type of browser.

While new symmetric keys are generated for each individual transaction, the RSA key for each individual site typically stays fixed for one year. This means that a time-consuming code-breaking effort has a huge payoff: Cracking a single RSA key can potentially unlock a year's worth of transactions.

"There is no legal reason that American companies should persist in using low-level encryption for their sites," Thomsen said, adding, "No one in their right minds should be using 512 today." And yet many major e-commerce sites, like Microsoft's and Gateway's online stores, are still using 512-bit encryption for their Web transactions.

While security software can be designed to allow easy upgrades to higher levels of encryption, the government does not allow manufacturers to build this capability into their software, said Scott Schnell, senior vice president for marketing for RSA Data Security and its parent, Security Dynamics Technologies Inc. Thus, upgrading can be a costly process.

Security Dynamics had $39 million in revenues from encryption software last year, accounting for 42 percent of the worldwide market, in addition to licensing the RSA encryption algorithms to more than 500 other software makers. But Schnell said federal export regulations had hurt RSA severely in its sales abroad because "no one wants to buy weak encryption products."

"I think we need a clear base line that makes 1,024 the standard for public key cryptography," he said.

Even then, the pace at which cryptography standards will be broken may only increase. "In another 10 years, we can expect to make another jump of difficulty level," said Lenstra, the Citicorp computer scientist. "It's always going to be a race."

---

Related Sites
These sites are not part of The New York Times on the Web, and The Times has no control over their content or availability.

• Department of Commerce, Bureau of Export Administration: Commercial Encryption Export Controls

• National Security Agency

• RSA Data Security

• Security Dynamics Technologies Inc.

• RSA Laboratories: Cryptographic Challenges

• RSA Data Security: Frequently Asked Questions About RSA

• Netscape: Secure Socket Layer