[openssl-users] RFC 7919 DH parameters and OpenSSL DH_check()

[Viktor Dukhovni]

On Jan 3, 2019, at 3:18 PM, Andy Schmidt <andrewrobertschmidt at gmail.com> wrote:

> I am adding the RFC 7919 Diffie-Hellman parameters to our TLS
> servers, and I've found that these parameters won't pass OpenSSL's
> Diffie Hellman parameter check function DH_check(). The return code
> is DH_NOT_SUITABLE_GENERATOR. Looking at the source code, it appears
> to fail because the remainder of the prime divided by 24 is not 11.
> That its, p mod 24 != 11. I have a couple of questions:
>
> What relationship between the prime p and the generator g is this checking
> for? I thought that since p was a safe prime, as long as the generator g
> wasn't 1 the only choice is between the full group and the subgroup of the
> squares?

For a safe prime $p = 2q + 1$ with $q$ also prime, the order of $2$ is $q$
provided $2$ is quadratic residue mod $p$, which, by quadratic reciprocity,
considering that $q$ is odd and not a multiple of 3 for any primes of interest,
gives $p \cong 23 mod 24$, which then gives $q \cong 11 mod 12$.

The order of $2$ is $2q$ when $2$ is not a quadratic residue mod $p$, which
then gives $p \cong 3 mod 8$ and so taking mod 3 into account
$p \cong 11 mod 24$.

So it seems that the check in question wants $2$ to generates the
full multiplicative group of order $2q$, rather than the prime-order
subgroup of quadratic residues of order $q$.

> I would like to use DH_check() to attempt to ensure that Diffie Hellman
> parameters haven't been tampered on operating systems that don't have
> digital signatures for executable binaries.
> 
> The OpenSSL version in use is 1.0.2q.

The primes in RFC7919 are all 23 mod 24, which has $o(2) = q$ rather
than $o(2) = 2q$.  This is actually fine, perhaps even better, and
the code in DH_check() is too strict in wanting the generator to
generate the full multiplicative group mod $p$, rather than just
the subgroup of of quadratic residues of order $q$.

So a pull request for OpenSSL would be welcome.  Given that we
should not care whether the order of $g$ is $q$ or $2q$, it suffices
to just check that $p$ is plausibly prime and $q = (p-1)/2 == (p
>> 1)$ is plausibly prime.  The special checks for $g == 2, 3 and
5$ should be removed.  For 1.1.1 the patch would be something like:

--- a/crypto/dh/dh_check.c
+++ b/crypto/dh/dh_check.c
@@ -88,8 +88,6 @@ int DH_check_ex(const DH *dh)
         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_INVALID_Q_VALUE);
     if ((errflags & DH_CHECK_INVALID_J_VALUE) != 0)
         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_INVALID_J_VALUE);
-    if ((errflags & DH_UNABLE_TO_CHECK_GENERATOR) != 0)
-        DHerr(DH_F_DH_CHECK_EX, DH_R_UNABLE_TO_CHECK_GENERATOR);
     if ((errflags & DH_CHECK_P_NOT_PRIME) != 0)
         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_P_NOT_PRIME);
     if ((errflags & DH_CHECK_P_NOT_SAFE_PRIME) != 0)
@@ -140,20 +138,7 @@ int DH_check(const DH *dh, int *ret)
         if (dh->j && BN_cmp(dh->j, t1))
             *ret |= DH_CHECK_INVALID_J_VALUE;
 
-    } else if (BN_is_word(dh->g, DH_GENERATOR_2)) {
-        l = BN_mod_word(dh->p, 24);
-        if (l == (BN_ULONG)-1)
-            goto err;
-        if (l != 11)
-            *ret |= DH_NOT_SUITABLE_GENERATOR;
-    } else if (BN_is_word(dh->g, DH_GENERATOR_5)) {
-        l = BN_mod_word(dh->p, 10);
-        if (l == (BN_ULONG)-1)
-            goto err;
-        if ((l != 3) && (l != 7))
-            *ret |= DH_NOT_SUITABLE_GENERATOR;
-    } else
-        *ret |= DH_UNABLE_TO_CHECK_GENERATOR;
+    }
 
     r = BN_is_prime_ex(dh->p, BN_prime_checks, ctx, NULL);
     if (r < 0)

-- 
	Viktor.