From 8aed2a7548362e88e84a7feb795a3a97e8395008 Mon Sep 17 00:00:00 2001 From: Andy Polyakov Date: Fri, 12 Sep 2014 00:13:20 +0200 Subject: [PATCH] Reserve option to use BN_mod_exp_mont_consttime in ECDSA. Submitted by Shay Gueron, Intel Corp. RT: 3149 Reviewed-by: Rich Salz (cherry picked from commit f54be179aa4cbbd944728771d7d59ed588158a12) --- crypto/ec/ec.h | 6 ++++ crypto/ec/ec_lcl.h | 11 +++++++ crypto/ec/ec_lib.c | 71 +++++++++++++++++++++++++++++++++++++++++ crypto/ecdsa/ecs_ossl.c | 36 ++++++++++++++++++--- 4 files changed, 119 insertions(+), 5 deletions(-) diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h index 7ae8e8ad58..b8551c527e 100644 --- a/crypto/ec/ec.h +++ b/crypto/ec/ec.h @@ -243,6 +243,12 @@ int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIG */ const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group); +/** Returns the montgomery data for order(Generator) + * \param group EC_GROUP object + * \return the currently used generator (possibly NULL). +*/ +BN_MONT_CTX *EC_GROUP_get_mont_data(const EC_GROUP *group); + /** Gets the order of a EC_GROUP * \param group EC_GROUP object * \param order BIGNUM to which the order is copied diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index b0d48b6b5c..22b53d28a9 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -235,6 +235,8 @@ struct ec_group_st { void *field_data1; /* method-specific (e.g., Montgomery structure) */ void *field_data2; /* method-specific */ int (*field_mod_func)(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); /* method-specific */ + + BN_MONT_CTX *mont_data; /* data for ECDSA inverse */ } /* EC_GROUP */; struct ec_key_st { @@ -444,3 +446,12 @@ void ec_GFp_nistp_points_make_affine_internal(size_t num, void *point_array, void (*felem_contract)(void *out, const void *in)); void ec_GFp_nistp_recode_scalar_bits(unsigned char *sign, unsigned char *digit, unsigned char in); #endif +int ec_precompute_mont_data(EC_GROUP *); + +#ifdef ECP_NISTZ256_ASM +/** Returns GFp methods using montgomery multiplication, with x86-64 optimized + * P256. See http://eprint.iacr.org/2013/816. + * \return EC_METHOD object + */ +const EC_METHOD *EC_GFp_nistz256_method(void); +#endif diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c index e2c4741b5b..7fe31157ca 100644 --- a/crypto/ec/ec_lib.c +++ b/crypto/ec/ec_lib.c @@ -98,6 +98,7 @@ EC_GROUP *EC_GROUP_new(const EC_METHOD *meth) ret->meth = meth; ret->extra_data = NULL; + ret->mont_data = NULL; ret->generator = NULL; BN_init(&ret->order); @@ -129,6 +130,9 @@ void EC_GROUP_free(EC_GROUP *group) EC_EX_DATA_free_all_data(&group->extra_data); + if (group->mont_data) + BN_MONT_CTX_free(group->mont_data); + if (group->generator != NULL) EC_POINT_free(group->generator); BN_free(&group->order); @@ -152,6 +156,9 @@ void EC_GROUP_clear_free(EC_GROUP *group) EC_EX_DATA_clear_free_all_data(&group->extra_data); + if (group->mont_data) + BN_MONT_CTX_free(group->mont_data); + if (group->generator != NULL) EC_POINT_clear_free(group->generator); BN_clear_free(&group->order); @@ -197,6 +204,25 @@ int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) return 0; } + if (src->mont_data != NULL) + { + if (dest->mont_data == NULL) + { + dest->mont_data = BN_MONT_CTX_new(); + if (dest->mont_data == NULL) return 0; + } + if (!BN_MONT_CTX_copy(dest->mont_data, src->mont_data)) return 0; + } + else + { + /* src->generator == NULL */ + if (dest->mont_data != NULL) + { + BN_MONT_CTX_free(dest->mont_data); + dest->mont_data = NULL; + } + } + if (src->generator != NULL) { if (dest->generator == NULL) @@ -306,6 +332,11 @@ int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIG else BN_zero(&group->cofactor); + /* We ignore the return value because some groups have an order with + * factors of two, which makes the Montgomery setup fail. + * |group->mont_data| will be NULL in this case. */ + ec_precompute_mont_data(group); + return 1; } @@ -315,6 +346,10 @@ const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group) return group->generator; } +BN_MONT_CTX *EC_GROUP_get_mont_data(const EC_GROUP *group) + { + return group->mont_data; + } int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) { @@ -1094,3 +1129,39 @@ int EC_GROUP_have_precompute_mult(const EC_GROUP *group) else return 0; /* cannot tell whether precomputation has been performed */ } + +/* ec_precompute_mont_data sets |group->mont_data| from |group->order| and + * returns one on success. On error it returns zero. */ +int ec_precompute_mont_data(EC_GROUP *group) + { + BN_CTX *ctx = BN_CTX_new(); + int ret = 0; + + if (group->mont_data) + { + BN_MONT_CTX_free(group->mont_data); + group->mont_data = NULL; + } + + if (ctx == NULL) + goto err; + + group->mont_data = BN_MONT_CTX_new(); + if (!group->mont_data) + goto err; + + if (!BN_MONT_CTX_set(group->mont_data, &group->order, ctx)) + { + BN_MONT_CTX_free(group->mont_data); + group->mont_data = NULL; + goto err; + } + + ret = 1; + +err: + + if (ctx) + BN_CTX_free(ctx); + return ret; + } diff --git a/crypto/ecdsa/ecs_ossl.c b/crypto/ecdsa/ecs_ossl.c index 7725935610..c23343b64d 100644 --- a/crypto/ecdsa/ecs_ossl.c +++ b/crypto/ecdsa/ecs_ossl.c @@ -187,11 +187,37 @@ 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)) - { - ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); - goto err; - } + if (EC_GROUP_get_mont_data(group) != NULL) + { + /* We want inverse in constant time, therefore we utilize the + * fact order must be prime and use Fermats Little Theorem + * instead. */ + if (!BN_set_word(X, 2) ) + { + ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); + goto err; + } + if (!BN_mod_sub(X, order, X, order, ctx)) + { + ECDSAerr(ECDSA_F_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))) + { + ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); + goto err; + } + } + else + { + if (!BN_mod_inverse(k, k, order, ctx)) + { + ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); + goto err; + } + } + /* clear old values if necessary */ if (*rp != NULL) BN_clear_free(*rp); -- 2.25.1