Change DH parameters to generate the order q subgroup instead of 2q

This avoids leaking bit 0 of the private key.

Reviewed-by: Viktor Dukhovni <viktor@openssl.org>
Reviewed-by: Kurt Roeckx <kurt@roeckx.be>
(Merged from https://github.com/openssl/openssl/pull/9363)

3 files changed, 47 insertions, 58 deletions

diff --git a/crypto/dh/dh_check.c b/crypto/dh/dh_check.c
index 8be2b91a9e..aff7e37181 100644
--- a/crypto/dh/dh_check.c
+++ b/crypto/dh/dh_check.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -24,7 +24,8 @@ int DH_check_params_ex(const DH *dh)
 {
     int errflags = 0;
 
-    (void)DH_check_params(dh, &errflags);
+    if (!DH_check_params(dh, &errflags))
+        return 0;
 
     if ((errflags & DH_CHECK_P_NOT_PRIME) != 0)
         DHerr(DH_F_DH_CHECK_PARAMS_EX, DH_R_CHECK_P_NOT_PRIME);
@@ -67,18 +68,14 @@ int DH_check_params(const DH *dh, int *ret)
 
 /*-
  * Check that p is a safe prime and
- * if g is 2, 3 or 5, check that it is a suitable generator
- * where
- * for 2, p mod 24 == 11
- * for 3, p mod 12 == 5
- * for 5, p mod 10 == 3 or 7
- * should hold.
+ * g is a suitable generator.
  */
 int DH_check_ex(const DH *dh)
 {
     int errflags = 0;
 
-    (void)DH_check(dh, &errflags);
+    if (!DH_check(dh, &errflags))
+        return 0;
 
     if ((errflags & DH_NOT_SUITABLE_GENERATOR) != 0)
         DHerr(DH_F_DH_CHECK_EX, DH_R_NOT_SUITABLE_GENERATOR);
@@ -102,10 +99,11 @@ int DH_check(const DH *dh, int *ret)
 {
     int ok = 0, r;
     BN_CTX *ctx = NULL;
-    BN_ULONG l;
     BIGNUM *t1 = NULL, *t2 = NULL;
 
-    *ret = 0;
+    if (!DH_check_params(dh, ret))
+        return 0;
+
     ctx = BN_CTX_new();
     if (ctx == NULL)
         goto err;
@@ -139,21 +137,7 @@ int DH_check(const DH *dh, int *ret)
             *ret |= DH_CHECK_INVALID_Q_VALUE;
         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, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
     if (r < 0)
diff --git a/crypto/dh/dh_gen.c b/crypto/dh/dh_gen.c
index 1e5c7ca2c9..bbf774f138 100644
--- a/crypto/dh/dh_gen.c
+++ b/crypto/dh/dh_gen.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -30,30 +30,29 @@ int DH_generate_parameters_ex(DH *ret, int prime_len, int generator,
 
 /*-
  * We generate DH parameters as follows
- * find a prime q which is prime_len/2 bits long.
- * p=(2*q)+1 or (p-1)/2 = q
- * For this case, g is a generator if
- * g^((p-1)/q) mod p != 1 for values of q which are the factors of p-1.
- * Since the factors of p-1 are q and 2, we just need to check
- * g^2 mod p != 1 and g^q mod p != 1.
+ * find a prime p which is prime_len bits long,
+ * where q=(p-1)/2 is also prime.
+ * In the following we assume that g is not 0, 1 or p-1, since it
+ * would generate only trivial subgroups.
+ * For this case, g is a generator of the order-q subgroup if
+ * g^q mod p == 1.
+ * Or in terms of the Legendre symbol: (g/p) == 1.
  *
  * Having said all that,
  * there is another special case method for the generators 2, 3 and 5.
- * for 2, p mod 24 == 11
- * for 3, p mod 12 == 5  <<<<< does not work for safe primes.
- * for 5, p mod 10 == 3 or 7
+ * Using the quadratic reciprocity law it is possible to solve
+ * (g/p) == 1 for the special values 2, 3, 5:
+ * (2/p) == 1 if p mod 8 == 1 or 7.
+ * (3/p) == 1 if p mod 12 == 1 or 11.
+ * (5/p) == 1 if p mod 5 == 1 or 4.
+ * See for instance: https://en.wikipedia.org/wiki/Legendre_symbol
  *
- * Thanks to Phil Karn for the pointers about the
- * special generators and for answering some of my questions.
- *
- * I've implemented the second simple method :-).
- * Since DH should be using a safe prime (both p and q are prime),
- * this generator function can take a very very long time to run.
- */
-/*
- * Actually there is no reason to insist that 'generator' be a generator.
- * It's just as OK (and in some sense better) to use a generator of the
- * order-q subgroup.
+ * Since all safe primes > 7 must satisfy p mod 12 == 11
+ * and all safe primes > 11 must satisfy p mod 5 != 1
+ * we can further improve the condition for g = 2, 3 and 5:
+ * for 2, p mod 24 == 23
+ * for 3, p mod 12 == 11
+ * for 5, p mod 60 == 59
  */
 static int dh_builtin_genparams(DH *ret, int prime_len, int generator,
                                 BN_GENCB *cb)
@@ -84,17 +83,14 @@ static int dh_builtin_genparams(DH *ret, int prime_len, int generator,
     if (generator == DH_GENERATOR_2) {
         if (!BN_set_word(t1, 24))
             goto err;
-        if (!BN_set_word(t2, 11))
+        if (!BN_set_word(t2, 23))
             goto err;
         g = 2;
     } else if (generator == DH_GENERATOR_5) {
-        if (!BN_set_word(t1, 10))
+        if (!BN_set_word(t1, 60))
             goto err;
-        if (!BN_set_word(t2, 3))
+        if (!BN_set_word(t2, 59))
             goto err;
-        /*
-         * BN_set_word(t3,7); just have to miss out on these ones :-(
-         */
         g = 5;
     } else {
         /*
@@ -102,9 +98,9 @@ static int dh_builtin_genparams(DH *ret, int prime_len, int generator,
          * not: since we are using safe primes, it will generate either an
          * order-q or an order-2q group, which both is OK
          */
-        if (!BN_set_word(t1, 2))
+        if (!BN_set_word(t1, 12))
             goto err;
-        if (!BN_set_word(t2, 1))
+        if (!BN_set_word(t2, 11))
             goto err;
         g = generator;
     }
diff --git a/crypto/dh/dh_key.c b/crypto/dh/dh_key.c
index 6b3a1247b2..4df993e345 100644
--- a/crypto/dh/dh_key.c
+++ b/crypto/dh/dh_key.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -125,6 +125,15 @@ static int generate_key(DH *dh)
             l = dh->length ? dh->length : BN_num_bits(dh->p) - 1;
             if (!BN_priv_rand(priv_key, l, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
                 goto err;
+            /*
+             * We handle just one known case where g is a quadratic non-residue:
+             * for g = 2: p % 8 == 3
+             */
+            if (BN_is_word(dh->g, DH_GENERATOR_2) && !BN_is_bit_set(dh->p, 2)) {
+                /* clear bit 0, since it won't be a secret anyway */
+                if (!BN_clear_bit(priv_key, 0))
+                    goto err;
+            }
         }
     }
 
@@ -136,11 +145,11 @@ static int generate_key(DH *dh)
         BN_with_flags(prk, priv_key, BN_FLG_CONSTTIME);
 
         if (!dh->meth->bn_mod_exp(dh, pub_key, dh->g, prk, dh->p, ctx, mont)) {
-            BN_free(prk);
+            BN_clear_free(prk);
             goto err;
         }
         /* We MUST free prk before any further use of priv_key */
-        BN_free(prk);
+        BN_clear_free(prk);
     }
 
     dh->pub_key = pub_key;