Deduplicate built-in curves and give custom curves an order_mont. I still need to revive the original CL, but right now I'm interested in giving every EC_GROUP an order_mont and having different ownership of that field between built-in and custom groups is kind of a nuisance. If I'm going to do that anyway, better to avoid computing the entire EC_GROUP in one go. I'm using some manual locking rather than CRYPTO_once here so that it behaves well in the face of malloc errors. Not that we especially care, but it was easy to do. This speeds up our ECDH benchmark a bit which otherwise must construct the EC_GROUP each time (matching real world usage). Before: Did 7619 ECDH P-224 operations in 1003190us (7594.8 ops/sec) Did 7518 ECDH P-256 operations in 1060844us (7086.8 ops/sec) Did 572 ECDH P-384 operations in 1055878us (541.7 ops/sec) Did 264 ECDH P-521 operations in 1062375us (248.5 ops/sec) After: Did 8415 ECDH P-224 operations in 1066695us (7888.9 ops/sec) Did 7952 ECDH P-256 operations in 1022819us (7774.6 ops/sec) Did 572 ECDH P-384 operations in 1055817us (541.8 ops/sec) Did 264 ECDH P-521 operations in 1060008us (249.1 ops/sec) Bug: 20 Change-Id: I7446cd0a69a840551dcc2dfabadde8ee1e3ff3e2 Reviewed-on: https://boringssl-review.googlesource.com/23073 Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c index 4916b1d..14c7450 100644 --- a/crypto/fipsmodule/ec/ec.c +++ b/crypto/fipsmodule/ec/ec.c
@@ -279,63 +279,6 @@ #endif } -// built_in_curve_scalar_field_monts contains Montgomery contexts for -// performing inversions in the scalar fields of each of the built-in -// curves. It's protected by |built_in_curve_scalar_field_monts_once|. -DEFINE_LOCAL_DATA(BN_MONT_CTX **, built_in_curve_scalar_field_monts) { - const struct built_in_curves *const curves = OPENSSL_built_in_curves(); - - BN_MONT_CTX **monts = - OPENSSL_malloc(sizeof(BN_MONT_CTX *) * OPENSSL_NUM_BUILT_IN_CURVES); - if (monts == NULL) { - return; - } - - OPENSSL_memset(monts, 0, sizeof(BN_MONT_CTX *) * OPENSSL_NUM_BUILT_IN_CURVES); - - BIGNUM *order = BN_new(); - BN_CTX *bn_ctx = BN_CTX_new(); - BN_MONT_CTX *mont_ctx = NULL; - - if (bn_ctx == NULL || - order == NULL) { - goto err; - } - - for (size_t i = 0; i < OPENSSL_NUM_BUILT_IN_CURVES; i++) { - const struct built_in_curve *curve = &curves->curves[i]; - const unsigned param_len = curve->param_len; - const uint8_t *params = curve->params; - - mont_ctx = BN_MONT_CTX_new(); - if (mont_ctx == NULL) { - goto err; - } - - if (!BN_bin2bn(params + 5 * param_len, param_len, order) || - !BN_MONT_CTX_set(mont_ctx, order, bn_ctx)) { - goto err; - } - - monts[i] = mont_ctx; - mont_ctx = NULL; - } - - *out = monts; - goto done; - -err: - BN_MONT_CTX_free(mont_ctx); - for (size_t i = 0; i < OPENSSL_NUM_BUILT_IN_CURVES; i++) { - BN_MONT_CTX_free(monts[i]); - } - OPENSSL_free((BN_MONT_CTX**) monts); - -done: - BN_free(order); - BN_CTX_free(bn_ctx); -} - EC_GROUP *ec_group_new(const EC_METHOD *meth) { EC_GROUP *ret; @@ -462,13 +405,18 @@ return 0; } + BN_MONT_CTX_free(group->order_mont); + group->order_mont = BN_MONT_CTX_new(); + if (group->order_mont == NULL || + !BN_MONT_CTX_set(group->order_mont, &group->order, NULL)) { + return 0; + } + ec_group_set0_generator(group, copy); return 1; } -static EC_GROUP *ec_group_new_from_data(unsigned built_in_index) { - const struct built_in_curves *const curves = OPENSSL_built_in_curves(); - const struct built_in_curve *curve = &curves->curves[built_in_index]; +static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) { EC_GROUP *group = NULL; EC_POINT *P = NULL; BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL; @@ -517,9 +465,11 @@ goto err; } - const BN_MONT_CTX **monts = *built_in_curve_scalar_field_monts(); - if (monts != NULL) { - group->order_mont = monts[built_in_index]; + group->order_mont = BN_MONT_CTX_new(); + if (group->order_mont == NULL || + !BN_MONT_CTX_set(group->order_mont, &group->order, ctx)) { + OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); + goto err; } ec_group_set0_generator(group, P); @@ -541,29 +491,65 @@ return group; } -EC_GROUP *EC_GROUP_new_by_curve_name(int nid) { - const struct built_in_curves *const curves = OPENSSL_built_in_curves(); - EC_GROUP *ret = NULL; +// Built-in groups are allocated lazily and static once allocated. +// TODO(davidben): Make these actually static. https://crbug.com/boringssl/20. +struct built_in_groups_st { + EC_GROUP *groups[OPENSSL_NUM_BUILT_IN_CURVES]; +}; +DEFINE_BSS_GET(struct built_in_groups_st, built_in_groups); +DEFINE_STATIC_MUTEX(built_in_groups_lock); +EC_GROUP *EC_GROUP_new_by_curve_name(int nid) { + struct built_in_groups_st *groups = built_in_groups_bss_get(); + EC_GROUP **group_ptr = NULL; + const struct built_in_curves *const curves = OPENSSL_built_in_curves(); + const struct built_in_curve *curve = NULL; for (size_t i = 0; i < OPENSSL_NUM_BUILT_IN_CURVES; i++) { - const struct built_in_curve *curve = &curves->curves[i]; - if (curve->nid == nid) { - ret = ec_group_new_from_data(i); + if (curves->curves[i].nid == nid) { + curve = &curves->curves[i]; + group_ptr = &groups->groups[i]; break; } } - if (ret == NULL) { + if (curve == NULL) { OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP); return NULL; } - ret->curve_name = nid; + CRYPTO_STATIC_MUTEX_lock_read(built_in_groups_lock_bss_get()); + EC_GROUP *ret = *group_ptr; + CRYPTO_STATIC_MUTEX_unlock_read(built_in_groups_lock_bss_get()); + if (ret != NULL) { + return ret; + } + + ret = ec_group_new_from_data(curve); + if (ret == NULL) { + return NULL; + } + + EC_GROUP *to_free = NULL; + CRYPTO_STATIC_MUTEX_lock_write(built_in_groups_lock_bss_get()); + if (*group_ptr == NULL) { + *group_ptr = ret; + // Filling in |ret->curve_name| makes |EC_GROUP_free| and |EC_GROUP_dup| + // into no-ops. At this point, |ret| is considered static. + ret->curve_name = nid; + } else { + to_free = ret; + ret = *group_ptr; + } + CRYPTO_STATIC_MUTEX_unlock_write(built_in_groups_lock_bss_get()); + + EC_GROUP_free(to_free); return ret; } void EC_GROUP_free(EC_GROUP *group) { if (group == NULL || + // Built-in curves are static. + group->curve_name != NID_undef || !CRYPTO_refcount_dec_and_test_zero(&group->references)) { return; } @@ -574,17 +560,16 @@ ec_point_free(group->generator, 0 /* don't free group */); BN_free(&group->order); + BN_MONT_CTX_free(group->order_mont); OPENSSL_free(group); } -const BN_MONT_CTX *ec_group_get_order_mont(const EC_GROUP *group) { - return group->order_mont; -} - EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) { - if (a == NULL) { - return NULL; + if (a == NULL || + // Built-in curves are static. + a->curve_name != NID_undef) { + return (EC_GROUP *)a; } // Groups are logically immutable (but for |EC_GROUP_set_generator| which must
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h index 65ce61f..22c8e45 100644 --- a/crypto/fipsmodule/ec/internal.h +++ b/crypto/fipsmodule/ec/internal.h
@@ -132,7 +132,7 @@ int curve_name; // optional NID for named curve - const BN_MONT_CTX *order_mont; // data for ECDSA inverse + BN_MONT_CTX *order_mont; // data for ECDSA inverse // The following members are handled by the method functions, // even if they appear generic @@ -163,11 +163,6 @@ EC_GROUP *ec_group_new(const EC_METHOD *meth); -// ec_group_get_order_mont returns a Montgomery context for operations modulo -// |group|'s order. It may return NULL in the case that |group| is not a -// built-in group. -const BN_MONT_CTX *ec_group_get_order_mont(const EC_GROUP *group); - int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, const EC_POINT *p, const BIGNUM *p_scalar, BN_CTX *ctx);
diff --git a/crypto/fipsmodule/ecdsa/ecdsa.c b/crypto/fipsmodule/ecdsa/ecdsa.c index 0e2adb6..8d01c6f 100644 --- a/crypto/fipsmodule/ecdsa/ecdsa.c +++ b/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -278,10 +278,8 @@ } // Compute the inverse of k. The order is a prime, so use Fermat's Little - // Theorem. Note |ec_group_get_order_mont| may return NULL but - // |bn_mod_inverse_prime| allows this. - if (!bn_mod_inverse_prime(kinv, k, order, ctx, - ec_group_get_order_mont(group))) { + // Theorem. + if (!bn_mod_inverse_prime(kinv, k, order, ctx, group->order_mont)) { OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); goto err; }