[cryptography] was this FIPS 186-1 (first DSA) an attemped NSA backdoor?

Adam Back adam at cypherspace.org
Thu Oct 10 09:30:20 EDT 2013

Some may remember Bleichenbacher found a random number generator bias in the
original DSA spec, that could leak the key after soem number of signatures
depending the circumstances.

Its described in this summary of DSA issues by Vaudenay "Evaluation Report
on DSA"


Bleichenbacher's attack is described in section 5.

The conclusion is "Bleichenbacher estimates that the attack would be
practical for a non-negligible fraction of qs with a time complexity of
2^63, a space complexity of 2^40, and a collection of 2^22 signatures.  We
believe the attack can still be made more efficient."

NIST reacted by issuing special publication SP 800-xx to address and I
presume that was folded into fips 186-3.  Of course NIST is down due to the
USG political level stupidity (why take the extra work to switch off the web
server on the way out I dont know).

That means 186-1 and 186-2 were vulnerable.

An even older NSA sabotage spotted by Bleichenbacher?

Anyway it highlights the significant design fragility in DSA/ECDSA not just
in the entropy of the secret key, but in the generation of each and every k
value, which leads to the better (but non-NIST recommended) idea adopted by
various libraries and applied crypto people to use k=H(m,d) so that the
signture is determinstic in fact, and the same k value will only be used
with the same message (which is harmless as thts just reissuing the bitwise
same signature).  

What happens if a VM is rolled back including the RNG and it outputs the
same k value to a different network dependeng m value?  etc.  Its just
unnecessarily fragile in its NIST/NSA mandated form.


More information about the cryptography mailing list