Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 mod 24 == 11
  • for g = 3, p mod 12 == 5
  • for g = 5, p mod 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 1536-bit MODP Group 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 mod 24 == 23 when g = 2?

share|improve this question
1  
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. –  fgrieu Jan 16 at 20:24
    
@fgrieu: See RFC 2412, appendix E –  poncho Jan 16 at 21:10
    
@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. –  fgrieu Jan 16 at 21:19

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
Very nice, poncho. –  jww Jan 16 at 21:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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