Bell Labs cryptologist sees DSA flaw, fix

A scientist at Bell Labs, the research and development wing of Lucent Technologies Inc., has discovered a flaw in the Digital Signature Algorithm (DSA) that could have affected the integrity of secure transactions on the Internet and adversely impacted virtual private networks (VPNs), online shopping and online financial transactions.

Daniel Bleichenbacher, a member of Bell Labs’ Information Sciences Research Center, discovered a glitch in the random number generation technique used with the DSA, according to the company in a statement. He learned that the DSA’s random number generator was biased and was twice as likely to pick a set of numbers from one range than from another.

The U.S. National Security Agency designed DSA and it is one of three authentication algorithms approved for generating and verifying digital signature under the Digital Signature Standard. Digital signatures allow software at the end of an electronic transaction to confirm the identity of the party initiating the transaction and to verify the integrity of the information received.

The vulnerability does not pose any immediate threat as it takes massive computing power to launch an attack on the flaw, according to Bell Labs.

The Digital Signature Standard was developed by the U.S. National Institute of Standards and Technology (NIST) and has been adopted by the American National Standards Institute (ANSI) and the Institute of Electrical and Electronics Engineers (IEEE).

The standards organizations could develop a simple fix for DSA, which providers of applications and services could implement in software, according to Bleichenbacher. NIST has agreed to fix the weakness in the DSA and is now preparing a revision of the DSA specification, which will be proposed in February, said Edward Roback, chief of the computer security division in NIST’s Information Technology Laboratory, in a statement.

Bleichenbacher first disclosed the vulnerability on Nov. 15, 2000 during a meeting of a IEEE working group, which focused on standard specifications for public-key cryptography. He found the flaw while analyzing an appendix to the DSA and has since devised an alternation to the DSA algorithm that would, for all practical purposes, eliminate the bias in the random number generator, Bell Labs said.

Lucent Technologies, in Murray Hill, N.J., can be reached at