The branch master has been updated via 1c073b9521ce7dbdd5689bdf7ae5fa87557c3529 (commit) via 37132c9702328940a99b1307f742ab094ef754a7 (commit) via fff7a0dcf6e3135c7f93e6cb5fb35e37dd0b384d (commit) via 3fc7a9b96cbed0c3da6f53c08e34d8d0c982745f (commit) from 83e034379fa3f6f0d308ec75fbcb137e26154aec (commit)
- Log ----------------------------------------------------------------- commit 1c073b9521ce7dbdd5689bdf7ae5fa87557c3529 Author: Andy Polyakov <ap...@openssl.org> Date: Sun Jul 15 17:59:59 2018 +0200 CHANGES: mention blinding reverting in ECDSA. [skip ci] Reviewed-by: Rich Salz <rs...@openssl.org> Reviewed-by: David Benjamin <david...@google.com> (Merged from https://github.com/openssl/openssl/pull/6664) commit 37132c9702328940a99b1307f742ab094ef754a7 Author: Andy Polyakov <ap...@openssl.org> Date: Thu Jul 12 22:27:43 2018 +0200 ec/ecdsa_ossl.c: switch to fixed-length Montgomery multiplication. Reviewed-by: Rich Salz <rs...@openssl.org> Reviewed-by: David Benjamin <david...@google.com> (Merged from https://github.com/openssl/openssl/pull/6664) commit fff7a0dcf6e3135c7f93e6cb5fb35e37dd0b384d Author: Andy Polyakov <ap...@openssl.org> Date: Fri Jul 6 16:13:29 2018 +0200 ec/ecdsa_ossl.c: formatting and readability fixes. Reviewed-by: Rich Salz <rs...@openssl.org> Reviewed-by: David Benjamin <david...@google.com> (Merged from https://github.com/openssl/openssl/pull/6664) commit 3fc7a9b96cbed0c3da6f53c08e34d8d0c982745f Author: Andy Polyakov <ap...@openssl.org> Date: Fri Jul 6 15:55:34 2018 +0200 ec/ecdsa_ossl.c: revert blinding in ECDSA signature. Originally suggested solution for "Return Of the Hidden Number Problem" is arguably too expensive. While it has marginal impact on slower curves, none to ~6%, optimized implementations suffer real penalties. Most notably sign with P-256 went more than 2 times[!] slower. Instead, just implement constant-time BN_mod_add_quick. Reviewed-by: Rich Salz <rs...@openssl.org> Reviewed-by: David Benjamin <david...@google.com> (Merged from https://github.com/openssl/openssl/pull/6664) ----------------------------------------------------------------------- Summary of changes: CHANGES | 4 ++ crypto/bn/bn_mod.c | 66 ++++++++++++++++++-- crypto/ec/ecdsa_ossl.c | 131 +++++++++++---------------------------- crypto/include/internal/bn_int.h | 2 + 4 files changed, 103 insertions(+), 100 deletions(-) diff --git a/CHANGES b/CHANGES index c1d4c2d..ae59f92 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,10 @@ Changes between 1.1.0h and 1.1.1 [xx XXX xxxx] + *) Revert blinding in ECDSA sign and instead make problematic addition + length-invariant. Switch even to fixed-length Montgomery multiplication. + [Andy Polyakov] + *) Use the new ec_scalar_mul_ladder scaffold to implement a specialized ladder step for binary curves. The new implementation is based on formulas from differential addition-and-doubling in mixed Lopez-Dahab projective diff --git a/crypto/bn/bn_mod.c b/crypto/bn/bn_mod.c index 76adfb7..463d2d6 100644 --- a/crypto/bn/bn_mod.c +++ b/crypto/bn/bn_mod.c @@ -35,18 +35,72 @@ int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, /* * BN_mod_add variant that may be used if both a and b are non-negative and - * less than m + * less than m. The original algorithm was + * + * if (!BN_uadd(r, a, b)) + * return 0; + * if (BN_ucmp(r, m) >= 0) + * return BN_usub(r, r, m); + * + * which is replaced with addition, subtracting modulus, and conditional + * move depending on whether or not subtraction borrowed. */ -int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, - const BIGNUM *m) +int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m) { - if (!BN_uadd(r, a, b)) + size_t i, ai, bi, mtop = m->top; + BN_ULONG storage[1024 / BN_BITS2]; + BN_ULONG carry, temp, mask, *rp, *tp = storage; + const BN_ULONG *ap, *bp; + + if (bn_wexpand(r, mtop) == NULL) return 0; - if (BN_ucmp(r, m) >= 0) - return BN_usub(r, r, m); + + if (mtop > sizeof(storage) / sizeof(storage[0]) + && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL) + return 0; + + ap = a->d != NULL ? a->d : tp; + bp = b->d != NULL ? b->d : tp; + + for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) { + mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); + temp = ((ap[ai] & mask) + carry) & BN_MASK2; + carry = (temp < carry); + + mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); + tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2; + carry += (tp[i] < temp); + + i++; + ai += (i - a->dmax) >> (8 * sizeof(i) - 1); + bi += (i - b->dmax) >> (8 * sizeof(i) - 1); + } + rp = r->d; + carry -= bn_sub_words(rp, tp, m->d, mtop); + for (i = 0; i < mtop; i++) { + rp[i] = (carry & tp[i]) | (~carry & rp[i]); + ((volatile BN_ULONG *)tp)[i] = 0; + } + r->top = mtop; + + if (tp != storage) + OPENSSL_free(tp); + return 1; } +int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m) +{ + int ret = bn_mod_add_fixed_top(r, a, b, m); + + if (ret) + bn_correct_top(r); + + return ret; +} + int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) { diff --git a/crypto/ec/ecdsa_ossl.c b/crypto/ec/ecdsa_ossl.c index dfb0d19..ad7a6f7 100644 --- a/crypto/ec/ecdsa_ossl.c +++ b/crypto/ec/ecdsa_ossl.c @@ -10,9 +10,8 @@ #include <string.h> #include <openssl/err.h> #include <openssl/obj_mac.h> -#include <openssl/bn.h> #include <openssl/rand.h> -#include <openssl/ec.h> +#include "internal/bn_int.h" #include "ec_lcl.h" int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen, @@ -53,13 +52,12 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, return 0; } - if (ctx_in == NULL) { + if ((ctx = ctx_in) == NULL) { if ((ctx = BN_CTX_new()) == NULL) { ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); return 0; } - } else - ctx = ctx_in; + } k = BN_new(); /* this value is later returned in *kinvp */ r = BN_new(); /* this value is later returned in *rp */ @@ -73,10 +71,6 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, goto err; } order = EC_GROUP_get0_order(group); - if (order == NULL) { - ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); - goto err; - } /* Preallocate space */ order_bits = BN_num_bits(order); @@ -87,23 +81,23 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, do { /* get random k */ - do + do { if (dgst != NULL) { - if (!BN_generate_dsa_nonce - (k, order, EC_KEY_get0_private_key(eckey), dgst, dlen, - ctx)) { + if (!BN_generate_dsa_nonce(k, order, + EC_KEY_get0_private_key(eckey), + dgst, dlen, ctx)) { ECerr(EC_F_ECDSA_SIGN_SETUP, - EC_R_RANDOM_NUMBER_GENERATION_FAILED); + EC_R_RANDOM_NUMBER_GENERATION_FAILED); goto err; } } else { if (!BN_priv_rand_range(k, order)) { ECerr(EC_F_ECDSA_SIGN_SETUP, - EC_R_RANDOM_NUMBER_GENERATION_FAILED); + EC_R_RANDOM_NUMBER_GENERATION_FAILED); goto err; } } - while (BN_is_zero(k)); + } while (BN_is_zero(k)); /* compute r the x-coordinate of generator * k */ if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { @@ -112,18 +106,16 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, } if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field) { - if (!EC_POINT_get_affine_coordinates_GFp - (group, tmp_point, X, NULL, ctx)) { + if (!EC_POINT_get_affine_coordinates_GFp(group, tmp_point, X, + NULL, ctx)) { ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); goto err; } } #ifndef OPENSSL_NO_EC2M else { /* NID_X9_62_characteristic_two_field */ - - if (!EC_POINT_get_affine_coordinates_GF2m(group, - tmp_point, X, NULL, - ctx)) { + if (!EC_POINT_get_affine_coordinates_GF2m(group, tmp_point, X, + NULL, ctx)) { ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); goto err; } @@ -133,8 +125,7 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); goto err; } - } - while (BN_is_zero(r)); + } while (BN_is_zero(r)); /* compute the inverse of k */ if (!ec_group_do_inverse_ord(group, k, k, ctx)) { @@ -172,8 +163,7 @@ ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, EC_KEY *eckey) { int ok = 0, i; - BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL, *blind = NULL; - BIGNUM *blindm = NULL; + BIGNUM *kinv = NULL, *s, *m = NULL; const BIGNUM *order, *ckinv; BN_CTX *ctx = NULL; const EC_GROUP *group; @@ -206,27 +196,13 @@ ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, } s = ret->s; - ctx = BN_CTX_secure_new(); - if (ctx == NULL) { - ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE); - goto err; - } - - BN_CTX_start(ctx); - tmp = BN_CTX_get(ctx); - m = BN_CTX_get(ctx); - blind = BN_CTX_get(ctx); - blindm = BN_CTX_get(ctx); - if (blindm == NULL) { + if ((ctx = BN_CTX_new()) == NULL + || (m = BN_new()) == NULL) { ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE); goto err; } order = EC_GROUP_get0_order(group); - if (order == NULL) { - ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_EC_LIB); - goto err; - } i = BN_num_bits(order); /* * Need to truncate digest if it is too long: first truncate whole bytes. @@ -237,7 +213,7 @@ ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); goto err; } - /* If still too long truncate remaining bits with a shift */ + /* If still too long, truncate remaining bits with a shift */ if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); goto err; @@ -258,59 +234,27 @@ ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, } /* - * The normal signature calculation is: - * - * s := k^-1 * (m + r * priv_key) mod order - * - * We will blind this to protect against side channel attacks - * - * s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod order + * With only one multiplicant being in Montgomery domain + * multiplication yields real result without post-conversion. + * Also note that all operations but last are performed with + * zero-padded vectors. Last operation, BN_mod_mul_montgomery + * below, returns user-visible value with removed zero padding. */ - - /* Generate a blinding value */ - do { - if (!BN_priv_rand(blind, BN_num_bits(order) - 1, - BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) - goto err; - } while (BN_is_zero(blind)); - BN_set_flags(blind, BN_FLG_CONSTTIME); - BN_set_flags(blindm, BN_FLG_CONSTTIME); - BN_set_flags(tmp, BN_FLG_CONSTTIME); - - /* tmp := blind * priv_key * r mod order */ - if (!BN_mod_mul(tmp, blind, priv_key, order, ctx)) { - ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); - goto err; - } - if (!BN_mod_mul(tmp, tmp, ret->r, order, ctx)) { - ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); - goto err; - } - - /* blindm := blind * m mod order */ - if (!BN_mod_mul(blindm, blind, m, order, ctx)) { - ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); - goto err; - } - - /* s : = (blind * priv_key * r) + (blind * m) mod order */ - if (!BN_mod_add_quick(s, tmp, blindm, order)) { - ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); - goto err; - } - - /* s := s * k^-1 mod order */ - if (!BN_mod_mul(s, s, ckinv, order, ctx)) { + if (!bn_to_mont_fixed_top(s, ret->r, group->mont_data, ctx) + || !bn_mul_mont_fixed_top(s, s, priv_key, group->mont_data, ctx)) { ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); goto err; } - - /* s:= s * blind^-1 mod order */ - if (BN_mod_inverse(blind, blind, order, ctx) == NULL) { + if (!bn_mod_add_fixed_top(s, s, m, order)) { ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); goto err; } - if (!BN_mod_mul(s, s, blind, order, ctx)) { + /* + * |s| can still be larger than modulus, because |m| can be. In + * such case we count on Montgomery reduction to tie it up. + */ + if (!bn_to_mont_fixed_top(s, s, group->mont_data, ctx) + || !BN_mod_mul_montgomery(s, s, ckinv, group->mont_data, ctx)) { ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); goto err; } @@ -324,11 +268,11 @@ ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_NEED_NEW_SETUP_VALUES); goto err; } - } else + } else { /* s != 0 => we have a valid signature */ break; - } - while (1); + } + } while (1); ok = 1; err: @@ -336,9 +280,8 @@ ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, ECDSA_SIG_free(ret); ret = NULL; } - if (ctx != NULL) - BN_CTX_end(ctx); BN_CTX_free(ctx); + BN_clear_free(m); BN_clear_free(kinv); return ret; } diff --git a/crypto/include/internal/bn_int.h b/crypto/include/internal/bn_int.h index e7fd899..f7d37d5 100644 --- a/crypto/include/internal/bn_int.h +++ b/crypto/include/internal/bn_int.h @@ -71,5 +71,7 @@ int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx); int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx); +int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m); #endif _____ openssl-commits mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-commits