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)

diff --git a/CHANGES b/CHANGES
index e517aceba964c75e1563ed080815d500b65e1242..0ad7ac8d2e1c84eba9b9abaf2e1c823d04a942ad 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,12 @@
 
  Changes between 1.1.1 and 3.0.0 [xx XXX xxxx]
 
+  *) Changed DH parameters to generate the order q subgroup instead of 2q.
+     Previously generated DH parameters are still accepted by DH_check
+     but DH_generate_key works around that by clearing bit 0 of the
+     private key for those. This avoids leaking bit 0 of the private key.
+     [Bernd Edlinger]
+
   *) Added a new FUNCerr() macro that takes a function name.
      The macro SYSerr() is deprecated.
      [Rich Salz]

diff --git a/apps/dhparam.c b/apps/dhparam.c
index b13a34ad9bfbc398ae42132848f89f258fea7cf0..7cd69b9270258498ae020db8e1812e3d0b70ef35 100644 (file)
--- a/apps/dhparam.c
+++ b/apps/dhparam.c
@@ -37,7 +37,7 @@ typedef enum OPTION_choice {
     OPT_ERR = -1, OPT_EOF = 0, OPT_HELP,
     OPT_INFORM, OPT_OUTFORM, OPT_IN, OPT_OUT,
     OPT_ENGINE, OPT_CHECK, OPT_TEXT, OPT_NOOUT,
-    OPT_DSAPARAM, OPT_C, OPT_2, OPT_5,
+    OPT_DSAPARAM, OPT_C, OPT_2, OPT_3, OPT_5,
     OPT_R_ENUM
 } OPTION_CHOICE;
 
@@ -55,6 +55,7 @@ const OPTIONS dhparam_options[] = {
     OPT_R_OPTIONS,
     {"C", OPT_C, '-', "Print C code"},
     {"2", OPT_2, '-', "Generate parameters using 2 as the generator value"},
+    {"3", OPT_3, '-', "Generate parameters using 3 as the generator value"},
     {"5", OPT_5, '-', "Generate parameters using 5 as the generator value"},
 # ifndef OPENSSL_NO_DSA
     {"dsaparam", OPT_DSAPARAM, '-',
@@ -125,6 +126,9 @@ int dhparam_main(int argc, char **argv)
         case OPT_2:
             g = 2;
             break;
+        case OPT_3:
+            g = 3;
+            break;
         case OPT_5:
             g = 5;
             break;

diff --git a/crypto/dh/dh_check.c b/crypto/dh/dh_check.c
index 8be2b91a9e3d6d6445cb6c483ef11cab21caa2d2..aff7e3718138efbb31680cfb1fe7881cd8e56c6d 100644 (file)
--- 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 1e5c7ca2c92b79fff2efc34bfe4850d483510030..bbf774f1383f78c170620ff63200cd51114bc890 100644 (file)
--- 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 6b3a1247b2524e224e00648864e400975b88fd97..4df993e3452d71fe3e150f1fbacebf25b105fa98 100644 (file)
--- 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;

diff --git a/doc/man1/dhparam.pod b/doc/man1/dhparam.pod
index 67a38941696309d3707b398bbea86cb80d79e57d..dd871b3b4865b9c1d0d631d9a4d44056672ef47c 100644 (file)
--- a/doc/man1/dhparam.pod
+++ b/doc/man1/dhparam.pod
@@ -19,6 +19,7 @@ B<openssl dhparam>
 [B<-text>]
 [B<-C>]
 [B<-2>]
+[B<-3>]
 [B<-5>]
 [B<-rand file...>]
 [B<-writerand file>]
@@ -77,9 +78,9 @@ avoid small-subgroup attacks that may be possible otherwise.
 Performs numerous checks to see if the supplied parameters are valid and
 displays a warning if not.
 
-=item B<-2>, B<-5>
+=item B<-2>, B<-3>, B<-5>
 
-The generator to use, either 2 or 5. If present then the
+The generator to use, either 2, 3 or 5. If present then the
 input file is ignored and parameters are generated instead. If not
 present but B<numbits> is present, parameters are generated with the
 default generator 2.
@@ -156,7 +157,7 @@ L<dsaparam(1)>
 
 =head1 COPYRIGHT
 
-Copyright 2000-2017 The OpenSSL Project Authors. All Rights Reserved.
+Copyright 2000-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

diff --git a/include/openssl/dh.h b/include/openssl/dh.h
index e96c81154d836483504fce4298e31b090b4faee3..7c509b4c0f5489b1908a76cc29ddf751f7d0fbb1 100644 (file)
--- a/include/openssl/dh.h
+++ b/include/openssl/dh.h
@@ -65,7 +65,7 @@ extern "C" {
 DECLARE_ASN1_ITEM(DHparams)
 
 # define DH_GENERATOR_2          2
-/* #define DH_GENERATOR_3       3 */
+# define DH_GENERATOR_3          3
 # define DH_GENERATOR_5          5
 
 /* DH_check error codes */

diff --git a/test/dhtest.c b/test/dhtest.c
index 7b2edec321571d0f6b81fa8363e7bb30fba4d25e..f80d5b3f4d745fc21fe66f784b42977e4300ccb0 100644 (file)
--- a/test/dhtest.c
+++ b/test/dhtest.c
@@ -17,6 +17,7 @@
 #include <openssl/bn.h>
 #include <openssl/rand.h>
 #include <openssl/err.h>
+#include <openssl/obj_mac.h>
 #include "testutil.h"
 
 #ifndef OPENSSL_NO_DH
@@ -62,6 +63,17 @@ static int dh_test(void)
         || !TEST_true(DH_set0_pqg(dh, p, q, g)))
         goto err1;
 
+    if (!DH_check(dh, &i))
+        goto err2;
+    if (!TEST_false(i & DH_CHECK_P_NOT_PRIME)
+            || !TEST_false(i & DH_CHECK_P_NOT_SAFE_PRIME)
+            || !TEST_false(i & DH_CHECK_INVALID_Q_VALUE)
+            || !TEST_false(i & DH_CHECK_Q_NOT_PRIME)
+            || !TEST_false(i & DH_UNABLE_TO_CHECK_GENERATOR)
+            || !TEST_false(i & DH_NOT_SUITABLE_GENERATOR)
+            || !TEST_false(i))
+        goto err2;
+
     /* test the combined getter for p, q, and g */
     DH_get0_pqg(dh, &p2, &q2, &g2);
     if (!TEST_ptr_eq(p2, p)
@@ -130,7 +142,8 @@ static int dh_test(void)
     if (!TEST_false(i & DH_CHECK_P_NOT_PRIME)
             || !TEST_false(i & DH_CHECK_P_NOT_SAFE_PRIME)
             || !TEST_false(i & DH_UNABLE_TO_CHECK_GENERATOR)
-            || !TEST_false(i & DH_NOT_SUITABLE_GENERATOR))
+            || !TEST_false(i & DH_NOT_SUITABLE_GENERATOR)
+            || !TEST_false(i))
         goto err3;
 
     DH_get0_pqg(a, &ap, NULL, &ag);
@@ -609,6 +622,63 @@ static int rfc5114_test(void)
     TEST_error("Test failed RFC5114 set %d\n", i + 1);
     return 0;
 }
+
+static int rfc7919_test(void)
+{
+    DH *a = NULL, *b = NULL;
+    const BIGNUM *apub_key = NULL, *bpub_key = NULL;
+    unsigned char *abuf = NULL;
+    unsigned char *bbuf = NULL;
+    int i, alen, blen, aout, bout;
+    int ret = 0;
+
+    if (!TEST_ptr(a = DH_new_by_nid(NID_ffdhe2048)))
+         goto err;
+
+    if (!DH_check(a, &i))
+        goto err;
+    if (!TEST_false(i & DH_CHECK_P_NOT_PRIME)
+            || !TEST_false(i & DH_CHECK_P_NOT_SAFE_PRIME)
+            || !TEST_false(i & DH_UNABLE_TO_CHECK_GENERATOR)
+            || !TEST_false(i & DH_NOT_SUITABLE_GENERATOR)
+            || !TEST_false(i))
+        goto err;
+
+    if (!DH_generate_key(a))
+        goto err;
+    DH_get0_key(a, &apub_key, NULL);
+
+    /* now create another copy of the DH group for the peer */
+    if (!TEST_ptr(b = DH_new_by_nid(NID_ffdhe2048)))
+        goto err;
+
+    if (!DH_generate_key(b))
+        goto err;
+    DH_get0_key(b, &bpub_key, NULL);
+
+    alen = DH_size(a);
+    if (!TEST_ptr(abuf = OPENSSL_malloc(alen))
+            || !TEST_true((aout = DH_compute_key(abuf, bpub_key, a)) != -1))
+        goto err;
+
+    blen = DH_size(b);
+    if (!TEST_ptr(bbuf = OPENSSL_malloc(blen))
+            || !TEST_true((bout = DH_compute_key(bbuf, apub_key, b)) != -1))
+        goto err;
+
+    if (!TEST_true(aout >= 20)
+            || !TEST_mem_eq(abuf, aout, bbuf, bout))
+        goto err;
+
+    ret = 1;
+
+ err:
+    OPENSSL_free(abuf);
+    OPENSSL_free(bbuf);
+    DH_free(a);
+    DH_free(b);
+    return ret;
+}
 #endif
 
 
@@ -619,6 +689,7 @@ int setup_tests(void)
 #else
     ADD_TEST(dh_test);
     ADD_TEST(rfc5114_test);
+    ADD_TEST(rfc7919_test);
 #endif
     return 1;
 }