RFC 7919 DH parameters and OpenSSL DH_check()

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

RFC 7919 DH parameters and OpenSSL DH_check()

Andy Schmidt
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?

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.

Any help is greatly appreciated.
Andy Schmidt

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: RFC 7919 DH parameters and OpenSSL DH_check()

Viktor Dukhovni
On Jan 3, 2019, at 3:18 PM, Andy Schmidt <[hidden email]> 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.

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: RFC 7919 DH parameters and OpenSSL DH_check()

Kurt Roeckx
In reply to this post by Andy Schmidt
On Thu, Jan 03, 2019 at 12:18:05PM -0800, Andy Schmidt 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?
>
> 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.

See:
https://crypto.stackexchange.com/questions/12961/diffie-hellman-parameter-check-when-g-2-must-p-mod-24-11


Kurt

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: RFC 7919 DH parameters and OpenSSL DH_check()

Andy Schmidt
Thank you Victor and Kurt for your quick replies! They were very helpful

Best,
Andy Schmidt

On Thu, Jan 3, 2019 at 2:00 PM Kurt Roeckx <[hidden email]> wrote:
On Thu, Jan 03, 2019 at 12:18:05PM -0800, Andy Schmidt 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?
>
> 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.

See:
https://crypto.stackexchange.com/questions/12961/diffie-hellman-parameter-check-when-g-2-must-p-mod-24-11


Kurt

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users