From 1794c5822963513c4dcd86b0ca3c193a259899d2 Mon Sep 17 00:00:00 2001 From: Adam Langley Date: Tue, 3 Nov 2015 14:02:04 -0800 Subject: DO NOT MERGE Compute ECDSA modular inverses with Fermal's Little Theorem. This is a partial cherry-pick of 18954938684e269ccd59152027d2244040e2b819. Bug: 33752052 Change-Id: Iddba4b931f88d2a0d2f7b9b1904b294fff1d8501 (cherry picked from commit 1f170d0b00fbf42c023c3746dd36eb96115e2a6e) --- src/crypto/ec/ec.c | 104 +++++++++++++++++++++++++++++++++++++++-------- src/crypto/ec/internal.h | 10 +++++ src/crypto/ecdsa/ecdsa.c | 16 +++++++- 3 files changed, 113 insertions(+), 17 deletions(-) diff --git a/src/crypto/ec/ec.c b/src/crypto/ec/ec.c index f38eba6..1bc2e26 100644 --- a/src/crypto/ec/ec.c +++ b/src/crypto/ec/ec.c @@ -67,6 +67,7 @@ #include +#include #include #include @@ -75,6 +76,7 @@ #include #include "internal.h" +#include "../internal.h" static const struct curve_data P224 = { @@ -233,6 +235,70 @@ const struct built_in_curve OPENSSL_built_in_curves[] = { {NID_undef, 0, 0}, }; +/* 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|. */ +static const BN_MONT_CTX **built_in_curve_scalar_field_monts; + +static CRYPTO_once_t built_in_curve_scalar_field_monts_once; + +static void built_in_curve_scalar_field_monts_init(void) { + unsigned num_built_in_curves; + for (num_built_in_curves = 0;; num_built_in_curves++) { + if (OPENSSL_built_in_curves[num_built_in_curves].nid == NID_undef) { + break; + } + } + + assert(0 < num_built_in_curves); + + built_in_curve_scalar_field_monts = + OPENSSL_malloc(sizeof(BN_MONT_CTX *) * num_built_in_curves); + if (built_in_curve_scalar_field_monts == NULL) { + return; + } + + 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; + } + + unsigned i; + for (i = 0; i < num_built_in_curves; i++) { + const struct curve_data *curve = OPENSSL_built_in_curves[i].data; + const unsigned param_len = curve->param_len; + const uint8_t *params = curve->data; + + 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; + } + + built_in_curve_scalar_field_monts[i] = mont_ctx; + mont_ctx = NULL; + } + + goto out; + +err: + BN_MONT_CTX_free(mont_ctx); + OPENSSL_free(built_in_curve_scalar_field_monts); + built_in_curve_scalar_field_monts = NULL; + +out: + BN_free(order); + BN_CTX_free(bn_ctx); +} + EC_GROUP *ec_group_new(const EC_METHOD *meth) { EC_GROUP *ret; @@ -325,25 +391,23 @@ int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, return 1; } -static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) { +static EC_GROUP *ec_group_new_from_data(unsigned built_in_index) { + const struct built_in_curve *curve = &OPENSSL_built_in_curves[built_in_index]; EC_GROUP *group = NULL; EC_POINT *P = NULL; - BN_CTX *ctx = NULL; BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL, *order = NULL; - int ok = 0; - unsigned param_len; const EC_METHOD *meth; - const struct curve_data *data; - const uint8_t *params; - if ((ctx = BN_CTX_new()) == NULL) { + int ok = 0; + BN_CTX *ctx = BN_CTX_new(); + if (ctx == NULL) { OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_MALLOC_FAILURE); goto err; } - data = curve->data; - param_len = data->param_len; - params = data->data; + const struct curve_data *data = curve->data; + const unsigned param_len = data->param_len; + const uint8_t *params = data->data; if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) || !(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) || @@ -387,6 +451,12 @@ static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) { goto err; } + CRYPTO_once(&built_in_curve_scalar_field_monts_once, + built_in_curve_scalar_field_monts_init); + if (built_in_curve_scalar_field_monts != NULL) { + group->mont_data = built_in_curve_scalar_field_monts[built_in_index]; + } + group->generator = P; P = NULL; if (!BN_copy(&group->order, order) || @@ -421,7 +491,7 @@ EC_GROUP *EC_GROUP_new_by_curve_name(int nid) { for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) { curve = &OPENSSL_built_in_curves[i]; if (curve->nid == nid) { - ret = ec_group_new_from_data(curve); + ret = ec_group_new_from_data(i); break; } } @@ -468,6 +538,7 @@ int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) { ec_pre_comp_free(dest->pre_comp); dest->pre_comp = ec_pre_comp_dup(src->pre_comp); + dest->mont_data = src->mont_data; if (src->generator != NULL) { if (dest->generator == NULL) { @@ -480,11 +551,8 @@ int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) { return 0; } } else { - /* src->generator == NULL */ - if (dest->generator != NULL) { - EC_POINT_clear_free(dest->generator); - dest->generator = NULL; - } + EC_POINT_clear_free(dest->generator); + dest->generator = NULL; } if (!BN_copy(&dest->order, &src->order) || @@ -497,6 +565,10 @@ int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) { return dest->meth->group_copy(dest, src); } +const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group) { + return group->mont_data; +} + EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) { EC_GROUP *t = NULL; int ok = 0; diff --git a/src/crypto/ec/internal.h b/src/crypto/ec/internal.h index 71062c1..89d86fd 100644 --- a/src/crypto/ec/internal.h +++ b/src/crypto/ec/internal.h @@ -200,6 +200,7 @@ struct ec_group_st { int curve_name; /* optional NID for named curve */ struct ec_pre_comp_st *pre_comp; + const BN_MONT_CTX *mont_data; /* data for ECDSA inverse */ /* The following members are handled by the method functions, * even if they appear generic */ @@ -230,6 +231,11 @@ struct ec_point_st { EC_GROUP *ec_group_new(const EC_METHOD *meth); int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src); +/* ec_group_get_mont_data returns a Montgomery context for operations in the + * scalar field of |group|. It may return NULL in the case that |group| is not + * a built-in group. */ +const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group); + int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *); @@ -321,6 +327,10 @@ void ec_GFp_nistp_recode_scalar_bits(uint8_t *sign, uint8_t *digit, uint8_t in); const EC_METHOD *EC_GFp_nistp256_method(void); +/* Returns GFp methods using montgomery multiplication, with x86-64 + * optimized P256. See http://eprint.iacr.org/2013/816. */ +const EC_METHOD *EC_GFp_nistz256_method(void); + struct ec_key_st { int version; diff --git a/src/crypto/ecdsa/ecdsa.c b/src/crypto/ecdsa/ecdsa.c index b71799e..86e41bb 100644 --- a/src/crypto/ecdsa/ecdsa.c +++ b/src/crypto/ecdsa/ecdsa.c @@ -322,7 +322,21 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, } while (BN_is_zero(r)); /* compute the inverse of k */ - if (!BN_mod_inverse(k, k, order, ctx)) { + if (ec_group_get_mont_data(group) != NULL) { + /* We want inverse in constant time, therefore we use that the order must + * be prime and thus we can use Fermat's Little Theorem. */ + if (!BN_set_word(X, 2) || + !BN_sub(X, order, X)) { + OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB); + goto err; + } + BN_set_flags(X, BN_FLG_CONSTTIME); + if (!BN_mod_exp_mont_consttime(k, k, X, order, ctx, + ec_group_get_mont_data(group))) { + OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB); + goto err; + } + } else if (!BN_mod_inverse(k, k, order, ctx)) { OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB); goto err; } -- cgit v1.2.3