Vaudenay's report writes up an attack developed by Daniel Bleichenbacher
which he presented to some standards groups but did not publish.  As a
result of that the DSA standard was modified.  As I recall with about
1million signatures he could recover the private key due to the small bias
from the formual Peter mentioned: k = G(t,KKEY) mod q ie if |n| = 256-bits
where n is the order of the group, then G(t,KKEY) is distributed with a
rectangular distribution in {0,2^256-1} and q is < 2^256-1.  As I read it
Bleichenbacker did not try that hard to optimize his attack, it was enough
to show the NIST/NSA designed DSA RNG was biased enough to break DSA in a
server / automated environment.

Maybe further optimizations would have been possible...  Maybe this DSA flaw
spotted by Bleichenbacker was another NSA soft-sabotage attempt (making
standards security brittle in the knowledge that it some people will fail to
harden it, and also it gives a plausibly deniable backdoor design for
colluding business entities, or double-agents on the payroll (former NSA
people say)).  In fact DSA was even designed by a former NSA cryptographer. (Dr David Kravitz,
a former NSA employee).

The approach I prefer is the deterministic DSA approach where k = MAC(d,M)
where d is the private DSA/ECDSA key and M is the message, plus bias
removal.  Bernsteins EdDSA (which despite the name is actually a Schnorr
signature over an Edwards curve) also uses the same technique.  This is
standardized in an RFC.  If people are going to use DSA/ECDSA they should
use this deterministic DSA.  Personally I prefer EC Schnorr because Schnorr
is just a better, simpler, more secure and more flexible signature (supports
simplel blinding, compact multi-sig, clearer security proofs, better
security margin, less dependence on hash properties etc).  To my mind DSA's
only reason for existence is historic due to patents.  It is inferior by all
metrics to Schnorr, just that Scnorr's patent didnt expire until feb 2008.

Anyway as Bernstein has put forward EdDSA with parameters and multiple
security, speed, simple constant time, non-key related, nor message
execution time, and provably non-cooked curve parameters (and there perhaps
remains some needless ambiguity about the magic constants used to seed the
ECDSA parameters) there is no reason in my opinion not to use EdDSA aka EC
Schnorr in any new systems.

Of course RSA is good also, and simpler parameter definition, the main
downside being the large keys for same security margin (3072-bit).


On Tue, Dec 17, 2013 at 06:23:43PM +1300, Peter Gutmann wrote:
Tom Ritter <> writes:
On 14 December 2013 14:51, Peter Gutmann <> wrote:

For example if you
 follow DSA's:

  k = G(t,KKEY) mod q

then you've leaked your x after a series of signatures, so you need to know
that you generate a large-than-required value before reducing mod q.  The
whole DLP family is just incredibly brittle, a problem that RSA doesn't

This is different from the normal 'repeated/non-random k leads to private
key', is it not?  Is there a paper/reference I can read more about this

Yes, this is one of several variations of subtle leak-the-private-key issues,
rather than the standard obvious-leak-the-private-key.  The code comment I've
got has, alongside other observations:

          The best reference for this is
          probably "The Insecurity of the Digital Signature Algorithm with
          Partially Known Nonces" by Phong Nguyen and Igor Shparlinski or
          more recently Serge Vaudenay's "Evaluation Report on DSA"

Then there's tricks like:

  Suppose that the
  certificate contains a copy of the certificate signer's DSA parameters,
  and the verifier of the certificate has a copy of the signer's public key
  but not the signer's DSA parameters (which are shared with other keys).
  If the verifier uses the DSA parameters from the certificate along with
  the signer's public key to verify the signature on the certificate, then
  an attacker can create bogus certificates by choosing a random u and
  finding its inverse v modulo q (uv is congruent to 1 modulo q).  Then
  take the certificate signer's public key g^x and compute g' = (g^x)^u.
  Then g'^v = g^x.  Using the DSA parameters p, q, g', the signer's public
  key corresponds to the private key v, which the attacker knows.  The
  attacker can then create a bogus certificate, put parameters (p, q, g')
  in it, and sign it with the DSA private key v to create an apparently
  valid certificate.  This works with the DSA OID that makes p, q, and g
  unauthenticated public parameters and y the public key, but not the one
  that makes p, q, g, and y the public key

That's not leaking the private key, but it allows signature forgery via
another mechanism that's totally unrelated to "was the fundamental DSA
algorithm implemented correctly".  As I said, the DLP algorithms are really,
really brittle, you have to worry about all sorts of things that aren't a
concern with RSA.


Reply via email to