Subject: Re: Bigger DSA keys

From: [email-masked] ("Hal Finney")
Date: Tue, 20 Sep 2005 11:02:19 -0700 (PDT)

There are a few differences between the OpenPGP requirements for DSA
keys and those in the DSS spec.

Usually, OpenPGP implementations do not use pre-calculated moduli
for DSA keys.  Likewise, OpenPGP does not require that DSA keys be
generated by the method described in the DSS standard.  This is the
reason why we generally call them DSA keys and not DSS keys in the spec.
Nevertheless we do follow the FIPS-186 recommendations for modulus sizes,
as their advice is good.

There are a few issues here.  Pre-calculated moduli do have some
advantages.  Generating the modulus is the slow part of DSA keygen.
With a pre-calculated modulus, all that is necessary to generate a key
is to pick a random value x and do one exponentiation to generate y = g^x
mod p.  This can also save space in key distribution; if there is a widely
shared modulus then only the y value has to be distributed for each key.

There are a few disadvantages though.  There are theoretical attacks where
the body that generates the pre-calculated modulus can use "trapdoor"
primes which allow faster calculation of discrete log.  Anyone who
generated a key using that shared modulus would be at risk of having
his private key broken by the body which created that modulus.

In order to protect users against this possibility, DSS specifies that
the public parameters (p, q, g) be generated using a randomization
technique which essentially eliminates the possibility of a trapdoor.
But it also requires that a sort of "certificate" of the parameter
generation be created and distributed, and that end users verify that
certificate to make sure that the public parameters have no trapdoors.

This is pretty complicated, and furthermore the general paranoia among
much of OpenPGP's audience is likely to make them mistrust even shared
parameters that are accompanied by such certificates.  As a result OpenPGP
has not pursued this approach.  There are no OpenPGP data structures to
share DSS public parameter certificates and nothing in the spec about
creating DSS keys in the standard way, or sharing and verifying such
certificates.

So OpenPGP generally envisions DSA keys being generated with fresh public
parameters for each key.  Not only is this more secure and simpler,
but it allows for the fast generation method I described in my mail
yesterday, which uses sieving.  Generating DSS moduli per FIPS-186 is
relatively slow, and extending that method to larger prime sizes may
become prohibitively slow.  (Of course, if the FIPS-186 method is used
with shared moduli, then keygen becomes very faster as I noted above,
just a single exponentiation to calculate y.)

I'm not sure how other systems that implement DSS handle the issue of
validating public parameter certificates.  It could be that OpenPGP is
the main user of DSA/DSS and nobody else worries about it.  I know I've
seen X.509 certificate specs for DSS keys and they don't have the extra
information necessary (although strangely, X.509 Diffie-Hellman keys do
have it!).  I guess they just assume that checks for legal DSS public
parameters are outside the scope of their spec.

Hal Finney

---

From: [email-masked] (Daniel A. Nagy)
Date: Wed, 21 Sep 2005 01:47:28 +0200

> parameters are outside the scope of their spec.

I know about one other major implementation of DSS, which is java.security
by Sun Microsystems. Their key generation method  uses pre-calculated
moduli for the common key sizes, but one can turn that feature off and
have the key generated from scratch (which takes a lot longer, of course).

The certificates of the pre-calculated moduli are in a comment of the source
code, which you may obtain from Sun upon request (they are very forthcoming
about that, becasue they understand that openness is the basis of trust in
crypto matters).

-- 
Daniel