Scientist discovers potential flaw in the integrity of on-line transactions

[February 6th 2001]

A cryptologist at Bell Labs 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."

Links
Bell Labs		http://www.bell-labs.com