In DH, are algorithms with fixed modulus p (large safe prime) to be avoided?

What if it was changed every x minutes?

  • 2
    $\begingroup$ If it is feasible for an attacker to break one DH modulus, secrecy for the period of using that one is gone already. Re-generating only buys you a little amount of time under this assumption. The solution would be to obviously only use secure lengths and only if needed to calm management / PR / ... regularly rotate (with the same size) $\endgroup$
    – SEJPM
    Jan 17 '19 at 20:16
  • 2
    $\begingroup$ Although every new parameter set (p,[q],g) must be distributed, and if it's not secured well and you habituate users to accepting changes, they may accept a nobbled group from an attacker that destroys security while superficially appearing safe (large enough). $\endgroup$ Jan 18 '19 at 0:25
  • $\begingroup$ How many connections are there in a minute? Time based changes are dangerous. $\endgroup$
    – Maarten Bodewes
    Jan 18 '19 at 2:47
  • $\begingroup$ @MaartenBodewes if think something in the thousands/min is a goof approximation of the average use $\endgroup$
    – Kroma
    Jan 18 '19 at 7:07
  • $\begingroup$ Use a counter, and switch after a few. The only drawback is maybe synchronization between threads, but hey; use a counter per thread or otherwise: it's a counter. With a timer you can have things like restarts of threads, time zones and summer / wintertime and whatnot. Besides that, if the key pair doesn't even get used for a minute, are you going to create a new one? That'll kill power saving, at least in your test rigs. $\endgroup$
    – Maarten Bodewes
    Jan 18 '19 at 12:22

There's a standard argument that NFS finite field discrete log computations can be factored into a precomputation for a particular group ($p$) and then a cheap computation to break each target $g^x$ and recover $x$.* See, e.g., https://weakdh.org for an application of this in practice to justify scrambling in 2015 to eradicate 512-bit ‘export-grade’—i.e., breakable by the NSA in 1995—DH groups.

The reasoning then goes that if every application uses a different $p$, it eliminates the batch advantage of doing a precomputation in the first place: the bad people in Ft. Meade, MD, would have to repeat the costly precomputation for every application. However, this precomputation is infeasible to do even once for sufficiently large groups: there's no evidence that humanity has the resources to do it for a well-chosen 2048-bit group in the foreseeable future.

But let's say you wanted to use bespoke DH groups for vanity's sake. This poses several problems:

  1. It's costly to find them—you can get a sense of how slow it is in the privacy of your own living room with the openssl dhparam command.

  2. The parties in an application have to agree on a DH group, and validating the group according to standard security criteria is costly—and has been a source of vulnerabilities in practice. Sometimes bogus DH parameters get hard-coded in software in the wild.

  3. We have known since 1993 of theoretical ways to put back doors in DH groups, and more recently that they might even be practical for reasonable group sizes like 2048 bits (summary).

Just use the smaller-faster-safer-simpler X25519 and forget about finite-field Diffie–Hellman groups, or if you must use FFDH, use the RFC 3526 groups chosen semi-rigidly by the RFC 2412 process.

* This is the case for multiplicative groups of integers modulo a large prime $p$—that is, finite-field discrete logs in prime fields. The story for binary fields is much worse, so nobody uses binary fields for this. In contrast, no such precomputation is known for elliptic curve discrete log computations—there's factor of $\sqrt{n}$ cost advantage to attacking a batch of $n$ targets simultaneously over attacking each of them individually, but it doesn't break down into a target-independent precomputation followed by a low per-target costs.

  • $\begingroup$ Is it known how the linked non-prime in socat crept? $\endgroup$
    – fgrieu
    Mar 8 '19 at 7:15
  • $\begingroup$ @fgrieu Not to my knowledge! But read the socat code and you'll get a sense of the level of care that went into the unfortunately invaluable tool, which makes it hard to distinguish malice from incompetence… Here's the commit: repo.or.cz/socat.git/commitdiff/… $\endgroup$ Mar 8 '19 at 7:16
  • $\begingroup$ dhparam doesn't have to be slow $\endgroup$ Mar 9 '19 at 2:29
  • $\begingroup$ @dave_thompson_085 The advice there is tacitly limited to ephemeral/ephemeral key agreement, and even if you used Schnorr groups instead of safe primes, finding them is still costly, thousands of times what a public key operation costs. $\endgroup$ Mar 9 '19 at 4:37
  • $\begingroup$ (Safe primes congruent to 7 mod 8 also admit faster public key operations because you can always pick 2 as the generator so you only need double-and-square, whereas with Schnorr groups you don't get a choice of generator and need a general multiply-and-square.) $\endgroup$ Mar 9 '19 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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