4
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The question mentions "new symmetric key pairs" and DSA. This is a contradiction. Is asymmetric meant? $\endgroup$
    – fgrieu ♦
    Nov 27, 2012 at 15:35
  • $\begingroup$ it's corrected now $\endgroup$
    – jmd
    Nov 27, 2012 at 20:50

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – jmd
    Nov 27, 2012 at 20:49
1
$\begingroup$

Selecting domain parameters for asymmetric schemes such as DSA or ECDSA is a tricky task ( involves good prime number number generation, point counting algorithm ect). That means that most people aren't able to choose their own. Knowing that fact most standards publish, for each security level, a small set of parameters that everybody can use. In general the security of your scheme depends on the secrecy of your private key, not on the domain parameters themselves (as long as they are valid ones) That being said, some recent work showed that since we use a small pool of domain parameters, tons of users across very different domains can end up unknowingly sharing a public key which means that they also share the corresponding private key. In your case it means that if there exist an authority that generated of high number of key pairs (and kept the corresponding private key) it will likely be able to find a collision between the pairs you and she generated. In a nutshell apart from the small fact that I pointed out above changing domain parameters frequently and doing it well is harder than choosing DP from a good standard and you should only change when you think your security margin has become to low.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "it will likely be able to find a collision between the pairs you and she generated" [citation needed] For a reasonable security level that seems exceedingly rare (never happens in practice) $\endgroup$
    – CodesInChaos
    Nov 27, 2012 at 10:46
  • $\begingroup$ This discussion followed from the presentation of the paper Public Keys by Lenstra, Hughes et al at Crypto 2012 but the paper itself doesn't mention DH type keys. As for the "never happens in practice" bit you're probably right. $\endgroup$
    – Alexandre Yamajako
    Nov 27, 2012 at 12:13
  • 1
    $\begingroup$ While it is correct that using the same domain parameters for DSA or ECDSA increases the odds that two users share the same key pair, the increased odds (assuming a good random number generator) still are so low as to be irrelevant in practice. The fear should be about poor RNG seeding, which is the root cause of the disaster reported here, not accidental collision when using a good RNG. $\endgroup$
    – fgrieu ♦
    Nov 27, 2012 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.