Cryptologist At Lucent Technologies' Bell Labs Offers Improvement for Future Security of E-Commerce.

Business Editors

MURRAY HILL, N.J.--(BUSINESS WIRE)--Feb. 5, 2001

Scientist Discovers Significant Flaw That Would Have Threatened

the Integrity of On-Line Transactions

A cryptologist at Bell Labs, the R&D arm of Lucent Technologies (NYSE: LU), has shown how to improve a standard method for ensuring the trustworthiness of e-commerce transactions, after discovering a flaw that could have made such transactions vulnerable to tampering in the future.

Daniel Bleichenbacher, a member of Bell Labs' Information Sciences Research Center, recently discovered a significant flaw in the random number generation technique used with the widely implemented Digital Signature Algorithm (DSA). A digital signature enables software at the receiving end of an electronic transaction to confirm the identity of the party initiating the transaction and to verify the integrity of the received information.

The vulnerability of DSA, which is part of the Digital Signature Standard, does not pose an immediate threat because of the computing power required to launch an attack. If not addressed, however, this weakness could have compromised the future integrity of secure transactions on the Internet and on corporate and governmental intranets. Virtual private networks, online shopping, and financial transactions are among the applications that could have been affected.

DSA and other elements of the Digital Signature Standard are focused on making transactions trustworthy -- ensuring that no one can impersonate another party or alter information in a signed transaction without being detected. Complementary standards provide techniques for keeping confidential information secure.

The vulnerability that Bleichenbacher found in DSA lies in the method that it specifies for generating a secret, random numerical key for each message. The effectiveness of the keys depends on how random the numbers actually are, since this determines how much information an adversary can infer about them. The probability that the algorithm will generate any particular number should be virtually uniform across the range of all possible results.

Bleichenbacher discovered that DSA's random number generator is biased -- it is twice as likely to choose a secret key from one range of numbers than from another. Bleichenbacher further discovered that this bias significantly weakens DSA and could eventually make it more vulnerable to tampering. Though the task of cracking digital signatures would challenge today's most powerful supercomputers, it will become easier for future generations of computers.

"While e-commerce is not currently threatened," said Bleichenbacher, "a good cryptosystem should always have a comfortable security margin. That is, it should be secure even in 10 or 20 years from the day it is used, assuming the usual progress in hardware development. Without a fix, DSA would not have that security margin."

DSA was designed by National Security Agency and is one of three authentication algorithms approved for generating and verifying digital signatures under the Digital Signature Standard. This standard was developed by the National Institute of Standards and Technology (NIST) and has been adopted by both the American National Standards Institute (ANSI) and the Institute of Electrical and Electronics Engineers (IEEE). According to Bleichenbacher, these organizations could specify a simple fix to DSA, which providers of applications and services could implement in software.

"NIST commends Dr. Bleichenbacher for his work and agrees that the weakness due to the bias of the random key generation that he has discovered should be fixed to preserve the future security of the DSA," said Edward Roback, chief of the Computer Security Division in NIST's Information Technology Laboratory. NIST is now preparing a revision of the specification, which will be proposed in February. "In the meantime," Roback said, "those who are using DSA can continue to use it with confidence that DSA signatures done under the present standard will remain secure for many more years."

Bleichenbacher first presented his findings on November 15, 2000, at a meeting of the IEEE P1363 working group. The conference, on standard specifications for public-key cryptography, was hosted by the National Security Agency at its headquarters in Fort Meade, Md.

Bleichenbacher found the flaw while analyzing an appendix to the Digital Signature Standard. He has devised a modification to the algorithm that would, for all practical purposes, eliminate the the bias in DSA's random number generator and ensure the effectiveness of the secret keys.

With 30,000 employees in 30 countries, Bell Labs is the world's largest R&D organization dedicated to communications and the leading source of new communications technologies. Bell Labs has generated more than 28,000 patents since 1925 and has played a pivotal role in inventing or perfecting key communications technologies, including transistors, digital networking and signal processing, lasers and fiber-optic communications systems, communications satellites, cellular telephony, electronic switching of calls, touch-tone dialing, and modems. Bell Labs scientists have received six Nobel Prizes in Physics, nine U.S. Medals of Science, and six U.S. Medals of Technology.

Lucent Technologies, headquartered in Murray Hill, N.J., USA, designs and delivers the systems, software, silicon and services for next-generation communications networks for service providers and enterprises. Backed by the research and development of Bell Labs, Lucent focuses on high-growth areas such as broadband and mobile Internet infrastructure; communications software; communications semiconductors and optoelectronics; Web-based enterprise solutions that link private and public networks; and professional network design and consulting services. For more information on Lucent Technologies and Bell Labs, visit the Web sites http://www.lucent.com and http://www.bell-labs.com.