From 64db159dc0c3a43dacf75ab5d2392b81db84b616 Mon Sep 17 00:00:00 2001 From: tb <> Date: Sun, 29 Sep 2019 10:09:09 +0000 Subject: If a NULL or zero cofactor is passed to EC_GROUP_set_generator(), try to compute it using Hasse's bound. This works as long as the cofactor is small enough. Port of Brumley's fix for CVE-2019-1547 in OpenSSL 1.1.1 (old license) tests & ok inoguchi input & ok jsing commit 30c22fa8b1d840036b8e203585738df62a03cec8 Author: Billy Brumley Date: Thu Sep 5 21:25:37 2019 +0300 [crypto/ec] for ECC parameters with NULL or zero cofactor, compute it The cofactor argument to EC_GROUP_set_generator is optional, and SCA mitigations for ECC currently use it. So the library currently falls back to very old SCA-vulnerable code if the cofactor is not present. This PR allows EC_GROUP_set_generator to compute the cofactor for all curves of cryptographic interest. Steering scalar multiplication to more SCA-robust code. This issue affects persisted private keys in explicit parameter form, where the (optional) cofactor field is zero or absent. It also affects curves not built-in to the library, but constructed programatically with explicit parameters, then calling EC_GROUP_set_generator with a nonsensical value (NULL, zero). The very old scalar multiplication code is known to be vulnerable to local uarch attacks, outside of the OpenSSL threat model. New results suggest the code path is also vulnerable to traditional wall clock timing attacks. CVE-2019-1547 Reviewed-by: Matt Caswell Reviewed-by: Tomas Mraz Reviewed-by: Nicola Tuveri (Merged from https://github.com/openssl/openssl/pull/9781) --- src/lib/libcrypto/ec/ec.h | 3 +- src/lib/libcrypto/ec/ec_err.c | 3 +- src/lib/libcrypto/ec/ec_lib.c | 118 ++++++++++++++++++++++++++++++++++++++---- 3 files changed, 113 insertions(+), 11 deletions(-) (limited to 'src/lib') diff --git a/src/lib/libcrypto/ec/ec.h b/src/lib/libcrypto/ec/ec.h index d0e3673675..a95d99f6a9 100644 --- a/src/lib/libcrypto/ec/ec.h +++ b/src/lib/libcrypto/ec/ec.h @@ -1,4 +1,4 @@ -/* $OpenBSD: ec.h,v 1.17 2019/09/06 17:59:25 jsing Exp $ */ +/* $OpenBSD: ec.h,v 1.18 2019/09/29 10:09:09 tb Exp $ */ /* * Originally written by Bodo Moeller for the OpenSSL project. */ @@ -1286,6 +1286,7 @@ void ERR_load_EC_strings(void); #define EC_R_SLOT_FULL 108 #define EC_R_UNDEFINED_GENERATOR 113 #define EC_R_UNDEFINED_ORDER 128 +#define EC_R_UNKNOWN_COFACTOR 164 #define EC_R_UNKNOWN_GROUP 129 #define EC_R_UNKNOWN_ORDER 114 #define EC_R_UNSUPPORTED_FIELD 131 diff --git a/src/lib/libcrypto/ec/ec_err.c b/src/lib/libcrypto/ec/ec_err.c index 7c42618881..95c15a1110 100644 --- a/src/lib/libcrypto/ec/ec_err.c +++ b/src/lib/libcrypto/ec/ec_err.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_err.c,v 1.11 2019/09/06 17:59:25 jsing Exp $ */ +/* $OpenBSD: ec_err.c,v 1.12 2019/09/29 10:09:09 tb Exp $ */ /* ==================================================================== * Copyright (c) 1999-2011 The OpenSSL Project. All rights reserved. * @@ -124,6 +124,7 @@ static ERR_STRING_DATA EC_str_reasons[] = {ERR_REASON(EC_R_SLOT_FULL), "slot full"}, {ERR_REASON(EC_R_UNDEFINED_GENERATOR), "undefined generator"}, {ERR_REASON(EC_R_UNDEFINED_ORDER), "undefined order"}, + {ERR_REASON(EC_R_UNKNOWN_COFACTOR), "unknown cofactor"}, {ERR_REASON(EC_R_UNKNOWN_GROUP), "unknown group"}, {ERR_REASON(EC_R_UNKNOWN_ORDER), "unknown order"}, {ERR_REASON(EC_R_UNSUPPORTED_FIELD), "unsupported field"}, diff --git a/src/lib/libcrypto/ec/ec_lib.c b/src/lib/libcrypto/ec/ec_lib.c index e5d9620a00..df9061627e 100644 --- a/src/lib/libcrypto/ec/ec_lib.c +++ b/src/lib/libcrypto/ec/ec_lib.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_lib.c,v 1.31 2018/11/06 07:02:33 tb Exp $ */ +/* $OpenBSD: ec_lib.c,v 1.32 2019/09/29 10:09:09 tb Exp $ */ /* * Originally written by Bodo Moeller for the OpenSSL project. */ @@ -68,6 +68,7 @@ #include #include +#include "bn_lcl.h" #include "ec_lcl.h" /* functions for EC_GROUP objects */ @@ -252,6 +253,80 @@ EC_METHOD_get_field_type(const EC_METHOD *meth) return meth->field_type; } +/* + * Try computing the cofactor from generator order n and field cardinality q. + * This works for all curves of cryptographic interest. + * + * Hasse's theorem: | h * n - (q + 1) | <= 2 * sqrt(q) + * + * So: h_min = (q + 1 - 2*sqrt(q)) / n and h_max = (q + 1 + 2*sqrt(q)) / n and + * therefore h_max - h_min = 4*sqrt(q) / n. So if n > 4*sqrt(q) holds, there is + * only one possible value for h: + * + * h = \lfloor (h_min + h_max)/2 \rceil = \lfloor (q + 1)/n \rceil + * + * Otherwise, zero cofactor and return success. + */ +static int +ec_guess_cofactor(EC_GROUP *group) +{ + BN_CTX *ctx = NULL; + BIGNUM *q = NULL; + int ret = 0; + + /* + * If the cofactor is too large, we cannot guess it and default to zero. + * The RHS of below is a strict overestimate of log(4 * sqrt(q)). + */ + if (BN_num_bits(&group->order) <= + (BN_num_bits(&group->field) + 1) / 2 + 3) { + BN_zero(&group->cofactor); + return 1; + } + + if ((ctx = BN_CTX_new()) == NULL) + goto err; + + BN_CTX_start(ctx); + if ((q = BN_CTX_get(ctx)) == NULL) + goto err; + + /* Set q = 2**m for binary fields; q = p otherwise. */ + if (group->meth->field_type == NID_X9_62_characteristic_two_field) { + BN_zero(q); + if (!BN_set_bit(q, BN_num_bits(&group->field) - 1)) + goto err; + } else { + if (!BN_copy(q, &group->field)) + goto err; + } + + /* + * Compute + * h = \lfloor (q + 1)/n \rceil = \lfloor (q + 1 + n/2) / n \rfloor. + */ + + /* h = n/2 */ + if (!BN_rshift1(&group->cofactor, &group->order)) + goto err; + /* h = 1 + n/2 */ + if (!BN_add(&group->cofactor, &group->cofactor, BN_value_one())) + goto err; + /* h = q + 1 + n/2 */ + if (!BN_add(&group->cofactor, &group->cofactor, q)) + goto err; + /* h = (q + 1 + n/2) / n */ + if (!BN_div_ct(&group->cofactor, NULL, &group->cofactor, &group->order, + ctx)) + goto err; + + ret = 1; + err: + BN_CTX_end(ctx); + BN_CTX_free(ctx); + BN_zero(&group->cofactor); + return ret; +} int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, @@ -261,6 +336,33 @@ EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, ECerror(ERR_R_PASSED_NULL_PARAMETER); return 0; } + + /* Require group->field >= 1. */ + if (BN_is_zero(&group->field) || BN_is_negative(&group->field)) { + ECerror(EC_R_INVALID_FIELD); + return 0; + } + + /* + * Require order >= 1 and enforce an upper bound of at most one bit more + * than the field cardinality due to Hasse's theorem. + */ + if (order == NULL || BN_is_zero(order) || BN_is_negative(order) || + BN_num_bits(order) > BN_num_bits(&group->field) + 1) { + ECerror(EC_R_INVALID_GROUP_ORDER); + return 0; + } + + /* + * Unfortunately, the cofactor is an optional field in many standards. + * Internally, the library uses a 0 cofactor as a marker for "unknown + * cofactor". So accept cofactor == NULL or cofactor >= 0. + */ + if (cofactor != NULL && BN_is_negative(cofactor)) { + ECerror(EC_R_UNKNOWN_COFACTOR); + return 0; + } + if (group->generator == NULL) { group->generator = EC_POINT_new(group); if (group->generator == NULL) @@ -269,17 +371,15 @@ EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, if (!EC_POINT_copy(group->generator, generator)) return 0; - if (order != NULL) { - if (!BN_copy(&group->order, order)) - return 0; - } else - BN_zero(&group->order); + if (!BN_copy(&group->order, order)) + return 0; - if (cofactor != NULL) { + /* Either take the provided positive cofactor, or try to compute it. */ + if (cofactor != NULL && !BN_is_zero(cofactor)) { if (!BN_copy(&group->cofactor, cofactor)) return 0; - } else - BN_zero(&group->cofactor); + } else if (!ec_guess_cofactor(group)) + return 0; return 1; } -- cgit v1.2.3-55-g6feb