13
$\begingroup$

I'm adding some Diffie-Hellman groups to a program as specified in RFC 3526, More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE).

When I test some of the group parameters per OpenSSL's DH_check, a result is returned that essentially states: 2 is not a suitable generator for Group 5 or the 1536-bit MODP Group.

According to DH_check() claims that RFC 3526 groups have DH_NOT_SUITABLE_GENERATOR, it appears OpenSSL's tests are (from crypto/dh/check.c):

  • for $g = 2$, $p \bmod 24 = 11$
  • for $g = 3$, $p \bmod 12 = 5$
  • for $g = 5$, $p \bmod 10 = 3$ or $7$

The posting then goes on to state 2048, 4096, and 8192 are congruent to 23 modulo 24, not 11. I've confirmed the 2048-bit and 4096-bit MODP groups as well.

I can't find reading on the expected residues (they probably exists, I just have not come across the paper).

Is it acceptable to relax the test such that $p \bmod 24 = 23$ when $g = 2$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ RFC 3526 does not require $g$ to be a generator of the finite field $\operatorname{GF}(p)^*$ of its MODP parameters. For example, the "2048-bit MODP Group" that it defines as $p=2^{2048}-2^{1984}-1+2^{64}⋅(⌊2^{1918}⋅\pi⌋+124476)$, $g=2$ is such that $g^{(p-1)/2}\bmod p=1$. That does not by itself make the parameters insecure, but might be related to why DH_check() fails. Unfortunately, RFC 3526 does not state its criteria for parameters selection; we get that it "follows the criteria established by Richard Schroeppel", without reference, and I fail to find one. $\endgroup$ – fgrieu♦ Jan 16 '14 at 20:24
  • 2
    $\begingroup$ @fgrieu: See RFC 2412, appendix E $\endgroup$ – poncho Jan 16 '14 at 21:10
  • 1
    $\begingroup$ @poncho: indeed, RFC 2412, appendix E. There's even the "Note that $2$ is technically not a generator in the number theory sense, because it omits half of the possible residues mod $p$. From a cryptographic viewpoint, this is a virtue.", which confirms your great answer. $\endgroup$ – fgrieu♦ Jan 16 '14 at 21:19
17
$\begingroup$

Actually, there is no major difference between $p \equiv 23\ (\bmod\ 24)$ vs $p \equiv 11\ (\bmod\ 24)$; any minor difference boils down to "do you prefer the DH shared secret to be limited to half the possible values; or do you prefer to leak a bit of the secret exponents?". OpenSSL prefers to leak one bit; the RFC 3526 designers decided they preferred to limit the possible values.

To explain exactly why this is true, I need to expound on the structure of $Z_p^*$ when $p$ is a strong prime; that is, if $(p-1)/2$ is also prime.

In that case, there are three types of elements:

  • The trivial elements 1 and p-1; obviously, you wouldn't want to use those as a base for doing DH; we'll skip those as potential bases from here on out.

  • Quadratic residues; these are elements $x$ for which there exist a $y$ such that $y \cdot y \equiv x\ (\bmod p)$

  • Quadratic nonresidues; these are elements $x$ for which there is no such $y$ with $y \cdot y \equiv x\ (\bmod p)$

Here's why the distinction is important:

  • If $g$ is a quadratic nonresidue, then $g$ is also a generator; that is, for every value $h$, there is an $i$ with $g^i \equiv h$. In contrast, if $g$ is a quadratic residue, then that is not true; $g^i$ will only take on values that are quadratic residues themselves.

What this means is that if use a $g$ which is a quadratic nonresidue as a base for the Diffie-Hellman operation, then any value $[1, p)$ is possible for the shared secret; if you use a quadratic residue, then half the values are possible (those values which are themselves quadratic residues).

  • If $g$ is a quadratic nonresidue, then given the values $g^x$, it is computationally feasible to determine $x \bmod 2$; that is, the lsbit of $x$. The attacker can do this by checking whether $g^x$ is a quadratic residue (for example, by checking whether $(g^x)^{(p-1)/2} = 1$; if it is, then $x \equiv 0 \bmod 2$; if it isn't, then $x \equiv 1 \bmod 2$.

In the Diffie-Hellman protocol, each side picks a secret $x$, and transmits $g^x$; if $g$ is a Quadratic nonresidue, then the attacker can use this observation to recontruct one bit of $x$; if $g$ is a Quadratic residue, this observation does not apply.

Now, what does this have to do with $p \bmod 24$? Well, it turns out that, if $p \equiv 11 \bmod 24$, then $g=2$ will be a Quadratic nonresidue (and hence Diffie-Hellman can generate any shared secret value, but the attacker can learn the lsbit of the secret exponents). On the other hand, if $p \equiv 23 \bmod 24$, then $g=2$ will be a Quadratic residue (and hence the Diffie-Hellman will be restricted to the Quadratic residue values, but the attacker isn't give any bits of the secret exponent for free).

And, in case you're wondering, if $p$ is a safe prime > 7, then $p \bmod 24$ will be one of those two values.

So, there really isn't all that much difference between the two; however my personal preference is for $p \equiv 23$; while leaking one bit from a perhaps 256 bit secret exponent isn't all that harmful, I don't see the point in leaking anything at all.

Improve this answer
$\endgroup$
3
  • $\begingroup$ if g is a quadratic residue, then it is still a generator, of a much smaller group though $\endgroup$ – David 天宇 Wong Jan 5 '16 at 22:37
  • 1
    $\begingroup$ @David天宇Wong: in that sense, all elements generate some group. I was using the meaning of "generating the entire $\mathbb Z^*_p$ group. $\endgroup$ – poncho Jan 6 '16 at 14:28
  • $\begingroup$ About "RFC 3526 designers decided they preferred to limit the possible values": they also choose $p+1\bmod2^{64}=0$, which allows a speedup in Montgomery reduction, and implies $p\bmod8=7$. They decided to use $g=2$, which allows another speedup. Thus performance (combined with mathematical facts) could also be part of the rationale for having $g$ of order $(p-1)/2$ rather than $p-1$. $\endgroup$ – fgrieu♦ yesterday

Your Answer

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