Diffie hellman: fixed modulus a risk?

Question

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

What if it was changed every x minutes?

Answer 1

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.}