Cryptologist at Lucent Technologies Bell Labs improves DSA encrypting

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."

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.