From a38c878c2e5e05016bc9faa8d0828eb96efba1c2 Mon Sep 17 00:00:00 2001 From: Bernd Edlinger Date: Wed, 10 Jul 2019 15:52:36 +0200 Subject: [PATCH] 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 Reviewed-by: Kurt Roeckx (Merged from https://github.com/openssl/openssl/pull/9363) --- CHANGES | 6 ++++ apps/dhparam.c | 6 +++- crypto/dh/dh_check.c | 36 ++++++---------------- crypto/dh/dh_gen.c | 54 +++++++++++++++----------------- crypto/dh/dh_key.c | 15 +++++++-- doc/man1/dhparam.pod | 7 +++-- include/openssl/dh.h | 2 +- test/dhtest.c | 73 +++++++++++++++++++++++++++++++++++++++++++- 8 files changed, 135 insertions(+), 64 deletions(-) diff --git a/CHANGES b/CHANGES index e517aceba9..0ad7ac8d2e 100644 --- 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 b13a34ad9b..7cd69b9270 100644 --- 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 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; diff --git a/doc/man1/dhparam.pod b/doc/man1/dhparam.pod index 67a3894169..dd871b3b48 100644 --- a/doc/man1/dhparam.pod +++ b/doc/man1/dhparam.pod @@ -19,6 +19,7 @@ B [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 is present, parameters are generated with the default generator 2. @@ -156,7 +157,7 @@ L =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 e96c81154d..7c509b4c0f 100644 --- 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 7b2edec321..f80d5b3f4d 100644 --- a/test/dhtest.c +++ b/test/dhtest.c @@ -17,6 +17,7 @@ #include #include #include +#include #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; } -- 2.25.1