8
$\begingroup$

I know it has been already asked and answered whether it's possible to generate weak DH parameters.

But "recentely" we experienced the Logjam attack, which makes use of the pre-computation capabilities of the GNFS to quickly break many discrete logarithm problem (DLP) instances.

Now I know that the main workload of the GNFS is to do the pre-computation for the given group (more than 99% of the required workload).

Now I've asked myself:
Is it possible to generate DH parameters that allow for speeding up the GNFS pre-computation given some (secret) knowledge?

$\endgroup$
  • $\begingroup$ small subgroup attacks on ECDH curves such as NIST P-224 ? $\endgroup$ – Richie Frame Aug 21 '15 at 23:56
  • $\begingroup$ @RichieFrame, the question is aimed at plain $\mathbb Z_p$ Diffie-Hellman without EC and any ways to speed the GNFS pre-computation up. $\endgroup$ – SEJPM Aug 22 '15 at 12:53
9
$\begingroup$

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[2] including an objection to the now-infamous random generation of the per-signature secret). Though the computational cost was too high for an academic researcher to demonstrate it at the time, Gordon did suggest alleviating the concerns by using what we would today call a semi-rigid procedure for choosing the primes.

Fast-forward to 2016, when Fried, Gaudry, Heninger, and Thomé dusted off Gordon's algorithm and applied it in practice[3] to spend:

  • 12 core-hours choose a 1024-bit DSA prime $p$, with a 160-bit prime factor $q$ of $p - 1$, with an SNFS polynomial $f$ admitting…
  • a few hundred core years (spread across a few thousand cores for a couple of months on an academic cluster) of precomputation in order to enable…
  • a handful of core-days to compute each discrete log.

The paper [3] is worth reading for more technical details and historical background. There are some caveats:

  • The experiment produced a group for DSA, a Schnorr group with a 160-bit prime subgroup, not a safe prime for DH to avoid Lim–Lee active small-subgroup attacks[4] which are not relevant in signature applications. It's not immediately clear to me whether the technique would work to find a safe prime with a trapdoor: if nothing else, the arithmetic modulo a (say) 2047-bit $q$ would cost a dozen times what the arithmetic modulo a 160-bit $q$.

    Counterpoint: But there have been Schnorr groups inexplicably documented for use with DH, in RFC 5114. The paper [3] reports systems in the wild using primes with an obvious SNFS polynomial, like $2^{1024} - 1093337$. For years socat used a composite modulus[5]. And maybe a more careful reading of the costs than I have done would show that searching for a safe prime is not all that much costlier than a Schnorr group as demonstrated.

  • Obviously, a 1024-bit modulus is too small by today's standards: it has been considered plausible for some years now that well-funded governments or corporations could mount a GNFS discrete log computation in a group with a 1024-bit modulus.

    Counterpoint: But it shouldn't be within the reach of an academic cluster! If the trapdoor for this 1024-bit modulus is within the reach of an academic cluster today, is a trapdoor for a 2048-bit modulus within the reach of a major government or corporation?

So, while it is likely outside your budget to generate a 2048-bit safe prime with a hidden SNFS back door in the privacy of your own living room, you should definitely raise a lot of eyebrows at anyone suggesting to use DH primes other than the semi-rigid RFC 3526 ones.

Or just use elliptic curve DH, particularly X25519.

$\endgroup$

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.