7
$\begingroup$

I am auditing some software that includes compiled in Diffie–Hellman parameters (2048 bits).

  • I can't be sure who generated the DH parameters or how they were generated.

Question:

  • Can DH parameters be weak if they were generated improperly or made intentionally weak?
  • Is it possible to test DH parameters, that I did not generate, to see if they are 'good'?

I realize this might be better discussed in security SE, however, I wanted to get a more abstract opinion about the cryptography in crypto SE, and depending on the answer here, I will raise a more specific question about the software in question, and what to do about it, on security SE.

UPDATE 2015-Oct-28: Since I asked this question, the https://weakdh.org analysis was published and the upstream provider ( https://www.stunnel.org ) is changing how they manage the DH parameters. The compiled-in DH parameters may be re-generated during build or software packaging and new DH parameters are generated every 24 hours.

$\endgroup$
  • $\begingroup$ oops, I think the first part of my question may be answered in crypto SE already (crypto.stackexchange.com/questions/10025/…). But I would still appreciate an answer for the second bullet. $\endgroup$ – Gregor Apr 16 '15 at 13:35
  • $\begingroup$ This answers your second question as well: find the order of $g$ and see how it factors. $\endgroup$ – fkraiem Apr 16 '15 at 14:08
10
$\begingroup$

There are several possible ways to generate a weak DH group:

  • The attacker can generate a $g$ with a small order; this would make deriving the shared secret from the public values easy.

  • The attacker can generate a $g$ with a smooth order; that is, the order is large, but is composed of small prime factors; this would make deriving the shared secret from the public values easy.

  • The attacker can generate a $g$ with a large order, but one with a number of small factors; if the implementation also doesn't use large secret exponents, this would also make deriving the shared secret easy

  • The attacker can select a prime $p$ that is easy to attack with the Special Number Sieve algorithm; this makes deriving the shared secret easier (but no picnic; I believe that attacking a 2048 bit modulus with SNFS may be in the range of the NSA at the moment).

  • The attacker may select a composite $p$. While this also makes it easier on the attacker, what this chiefly does is allow the attacker to disguise whether they're doing the above tricks.

With this in mind, the first thing I would do is check if $p$ is prime; if it is not, then either the implementer picked a random odd value for $p$ (which implies he's a bit clueless when it comes to cryptography), or he has something to hide -- neither of those sound good.

Assuming that $p$ is prime, then the next step would be to attempt to factor $p-1$ (or at least, search for any small factors, where 'small' means, perhaps, 128 bits or less); a tool that implements the Elliptic Curve Method to find small factors would be useful here. You'll get $p-1 = 2 \times p_1 \times p_2 \times ... \times p_n \times q$, where $p_1, p_2, ..., p_n$ are small primes, and $q$ is a large number with no small prime factors (and $q$ may be either prime or composite).

The ideal case is that there are no $p_1, p_2, ..., p_n$ and $q$ is prime; that means that we have a 'safe prime'; any $g$ (other than 1 and $p-1$) is good, and and the implementor is clueful; other than SNFS, we're good.

The other extreme is that there are no large factors; you managed to completely factor $p-1$ into small factors; this means that the DH problem is easy here; fail.

However, if it is somewhere in the middle, we then need to determine the order of $g$. First thing to check is if $g^{2\times p_1 \times p_2 \times ... \times p_n} = 1$; if so, then someone generated $g$ with a smooth order; fail.

The next step is to compute $g^q$; and find the minimal $r$ which is a divisor of $2 \times p_1 \times p_2 \times ... \times p_n$ with $(g^q)^r = 1$. Here, the ideal case is $g^q=1$ (as $r=1$). What this matters is that the attacker can compute the secret exponents modulo $r$. If $r$ is large, and if the secret exponents aren't, this can significantly reduce the strength of those secret exponents.

The last step is to check if the SNFS discrete log algorithm can be applied; I'm sorry, but I can't help you with that. On the other hand, SNFS isn't as large of a concern as these above issues.

$\endgroup$
  • $\begingroup$ Would sufficient M-R tests detect all these issues, as they all seem to involve composite numbers? $\endgroup$ – forest Feb 25 '18 at 6:22
  • 1
    $\begingroup$ @forest: M-R tests will detect the last one; other methods would be used to detect the others $\endgroup$ – poncho Feb 25 '18 at 17:49

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.