From 15f1f9a32d4f34bc39118b6aa2531874d14f9d5c Mon Sep 17 00:00:00 2001 From: tb Date: Tue, 20 Jun 2023 14:37:15 +0000 Subject: [PATCH] Consolidate elliptic curve cofactor handling The various checks of the cofactor to be set in EC_GROUP_set_generator() are a bit all over the place. Move them into a single function and clean things up a little. Instead of calculating directly with the cofactor member of the group, use a temporary variable and copy this variable only if all tests passed. In cryptographic contexts the cofactor almost always fits if not into a single byte then into a word, so copying is cheap. Also streamline the computations a bit and remove some binary curve contortions. ok jsing --- lib/libcrypto/ec/ec_lib.c | 90 ++++++++++++++++++--------------------- 1 file changed, 41 insertions(+), 49 deletions(-) diff --git a/lib/libcrypto/ec/ec_lib.c b/lib/libcrypto/ec/ec_lib.c index 308a0f00614..817b0239be5 100644 --- a/lib/libcrypto/ec/ec_lib.c +++ b/lib/libcrypto/ec/ec_lib.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_lib.c,v 1.57 2023/05/04 13:51:59 tb Exp $ */ +/* $OpenBSD: ec_lib.c,v 1.58 2023/06/20 14:37:15 tb Exp $ */ /* * Originally written by Bodo Moeller for the OpenSSL project. */ @@ -236,7 +236,8 @@ EC_METHOD_get_field_type(const EC_METHOD *meth) } /* - * Try computing the cofactor from generator order n and field cardinality q. + * If there is a user-provided cofactor, sanity check and use it. Otherwise + * 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) @@ -250,56 +251,70 @@ EC_METHOD_get_field_type(const EC_METHOD *meth) * Otherwise, zero cofactor and return success. */ static int -ec_guess_cofactor(EC_GROUP *group) +ec_set_cofactor(EC_GROUP *group, const BIGNUM *in_cofactor) { BN_CTX *ctx = NULL; - BIGNUM *q = NULL; + BIGNUM *cofactor; 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; - } + BN_zero(&group->cofactor); if ((ctx = BN_CTX_new()) == NULL) goto err; BN_CTX_start(ctx); - if ((q = BN_CTX_get(ctx)) == NULL) + if ((cofactor = 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)) + /* + * 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 in_cofactor == NULL or in_cofactor >= 0. + */ + if (in_cofactor != NULL && !BN_is_zero(in_cofactor)) { + if (BN_is_negative(in_cofactor)) { + ECerror(EC_R_UNKNOWN_COFACTOR); goto err; - } else { - if (!bn_copy(q, &group->field)) + } + if (!bn_copy(cofactor, in_cofactor)) goto err; + goto done; } + /* + * 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) + goto done; + /* * Compute * h = \lfloor (q + 1)/n \rceil = \lfloor (q + 1 + n/2) / n \rfloor. */ /* h = n/2 */ - if (!BN_rshift1(&group->cofactor, &group->order)) + if (!BN_rshift1(cofactor, &group->order)) goto err; /* h = 1 + n/2 */ - if (!BN_add(&group->cofactor, &group->cofactor, BN_value_one())) + if (!BN_add_word(cofactor, 1)) goto err; /* h = q + 1 + n/2 */ - if (!BN_add(&group->cofactor, &group->cofactor, q)) + if (!BN_add(cofactor, cofactor, &group->field)) goto err; /* h = (q + 1 + n/2) / n */ - if (!BN_div_ct(&group->cofactor, NULL, &group->cofactor, &group->order, - ctx)) + if (!BN_div_ct(cofactor, NULL, cofactor, &group->order, ctx)) + goto err; + + done: + /* Use Hasse's theorem to bound the cofactor. */ + if (BN_num_bits(cofactor) > BN_num_bits(&group->field) + 1) { + ECerror(EC_R_INVALID_GROUP_ORDER); + goto err; + } + + if (!bn_copy(&group->cofactor, cofactor)) goto err; ret = 1; @@ -308,9 +323,6 @@ ec_guess_cofactor(EC_GROUP *group) BN_CTX_end(ctx); BN_CTX_free(ctx); - if (ret != 1) - BN_zero(&group->cofactor); - return ret; } @@ -339,16 +351,6 @@ EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, 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) @@ -360,18 +362,8 @@ EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, if (!bn_copy(&group->order, order)) return 0; - /* 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 if (!ec_guess_cofactor(group)) - return 0; - - /* Use Hasse's theorem to bound the cofactor. */ - if (BN_num_bits(&group->cofactor) > BN_num_bits(&group->field) + 1) { - ECerror(EC_R_INVALID_GROUP_ORDER); + if (!ec_set_cofactor(group, cofactor)) return 0; - } return 1; } -- 2.20.1