# Safety of DSA key parameters sharing

I'm looking for a solution to use in a context where I need to be able to generate new asymmetric key pairs quickly (using a widely recognized algorithm, and EC-DSA is not applicable). It sounds like DSA would be the adequate solution.

According to the documentation, just generating DSA parameters once allows then to generate a large number of separate keys pairs only requiring the step of selecting a random private key 'x' for each of them. FIPS 186-3 says :

the intended signatory shall first obtain appropriate domain parameters, either by generating the domain parameters itself, or by obtaining domain parameters that another entity has generated

Is there any security issue I'm missing before reusing the same domain parameters for a large number of keys ? How frequently ought the domain parameters be changed ? (There's some reference around to the possibility for a CA to use the same domain parameters for all the certificates it issues)

-
The question mentions "new symmetric key pairs" and DSA. This is a contradiction. Is asymmetric meant? –  fgrieu Nov 27 '12 at 15:35
it's corrected now –  jmd Nov 27 '12 at 20:50

So I actually asked the theoretical version of this question a while ago: what happens if you choose multiple keys from the same group?

The answer, as best as I determined, is its still secure. First, this practice is used both in the Internet Key Agreement Protocole (IKE) in IPSEC, and for SSH.

Second, the best algorithms for breaking DSA effectively involve solving the discrete log problem. Although these are faster in a fixed group, they are not fast enough. There are still somewhere far slower than polynomial and slighter faster than exponential. You can see the results here, there is a summary towards the end.

Thus the only concern is two people pick the same private key. This really unlikely in any group that is large enough to be secure.

-

In DSA (and ECDSA), it is possible and common to share the same domain parameters, across multiples users. AFAIK (and according to common wisdom, including FIPS recommendations) this introduce no known security weakness. The only common reasons to change domain parameters are to increase key size, or purposely introduce on interoperability barrier (e.g. to force an upgrade).

One advantage of fixed domain parameters $(p,q,g)$ in DSA is that it simplifies the choice of a user's key: basically one selects a random private $x\in[1, q–1]$ and computes the public $y=g^x\bmod p$.

As pointed in this other answer, sharing domain parameters increase odds that several users share the same key. However, for a good RNG, $2^n$ users and the lowest security level in FIPS 186, odds that it happens are less then $2^{160-2⋅n}$; that's negligible even for one key per day per human on our planet during a century. And if the RNG is flawed, all bets are off anyway.

-
I'm surprised I never saw until now explicitly a mention of this advantage of DSA over RSA for generating key pairs faster, but I'm now convinced there's no reason to hesitate to take advantage of it. Thanks –  jmd Nov 27 '12 at 20:49