The branch master has been updated via 60845a0aa4e54f2973bc178daa5ed475ea4e148d (commit) via 0dae8bafceabc8966383aa1f11ee8622f7dbde2f (commit) via a7b0b69c6e9fa172aeb1ac0ede5ef306315dd80c (commit) via fe2d3975880e6a89702f18ec58881307bf862542 (commit) from 06e0950d20d3110849dea28eb78cac4127618b48 (commit)
- Log ----------------------------------------------------------------- commit 60845a0aa4e54f2973bc178daa5ed475ea4e148d Author: Nicola Tuveri <nic....@gmail.com> Date: Wed Apr 25 15:27:59 2018 +0300 Add CHANGES entry for PR#6009 Reviewed-by: Richard Levitte <levi...@openssl.org> Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Rich Salz <rs...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6070) commit 0dae8bafceabc8966383aa1f11ee8622f7dbde2f Author: Billy Brumley <bbrum...@gmail.com> Date: Tue Apr 24 16:03:42 2018 +0300 Add blinding in BN_GF2m_mod_inv for binary field inversions Reviewed-by: Richard Levitte <levi...@openssl.org> Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Rich Salz <rs...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6070) commit a7b0b69c6e9fa172aeb1ac0ede5ef306315dd80c Author: Billy Brumley <bbrum...@gmail.com> Date: Tue Apr 24 16:01:53 2018 +0300 ECC: unify generic ec2 and ecp scalar multiplication, deprecate ec2_mult.c Reviewed-by: Richard Levitte <levi...@openssl.org> Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Rich Salz <rs...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6070) commit fe2d3975880e6a89702f18ec58881307bf862542 Author: Billy Brumley <bbrum...@gmail.com> Date: Tue Apr 24 16:00:08 2018 +0300 ECDSA: remove nonce padding (delegated to EC_POINT_mul) * EC_POINT_mul is now responsible for constant time point multiplication (for single fixed or variable point multiplication, when the scalar is in the range [0,group_order), so we need to strip the nonce padding from ECDSA. * Entry added to CHANGES * Updated EC_POINT_mul documentation - Integrate existing EC_POINT_mul and EC_POINTs_mul entries in the manpage to reflect the shift in constant-time expectations when performing a single fixed or variable point multiplication; - Add documentation to ec_method_st to reflect the updated "contract" between callers and implementations of ec_method_st.mul. Reviewed-by: Richard Levitte <levi...@openssl.org> Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Rich Salz <rs...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6070) ----------------------------------------------------------------------- Summary of changes: CHANGES | 20 +++ crypto/bn/bn_gf2m.c | 132 +++++---------- crypto/ec/build.info | 2 +- crypto/ec/ec2_mult.c | 404 ---------------------------------------------- crypto/ec/ec2_smpl.c | 11 +- crypto/ec/ec_lcl.h | 25 ++- crypto/ec/ec_mult.c | 4 +- crypto/ec/ecdsa_ossl.c | 17 -- doc/man3/EC_POINT_add.pod | 8 +- 9 files changed, 90 insertions(+), 533 deletions(-) delete mode 100644 crypto/ec/ec2_mult.c diff --git a/CHANGES b/CHANGES index a13183f..e8b92cc 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,26 @@ Changes between 1.1.0h and 1.1.1 [xx XXX xxxx] + *) Apply blinding to binary field modular inversion and remove patent + pending (OPENSSL_SUN_GF2M_DIV) BN_GF2m_mod_div implementation. + [Billy Bob Brumley] + + *) Deprecate ec2_mult.c and unify scalar multiplication code paths for + binary and prime elliptic curves. + [Billy Bob Brumley] + + *) Remove ECDSA nonce padding: EC_POINT_mul is now responsible for + constant time fixed point multiplication. + [Billy Bob Brumley] + + *) Revise elliptic curve scalar multiplication with timing attack + defenses: ec_wNAF_mul redirects to a constant time implementation + when computing fixed point and variable point multiplication (which + in OpenSSL are mostly used with secret scalars in keygen, sign, + ECDH derive operations). + [Billy Bob Brumley, Nicola Tuveri, Cesar Pereida GarcĂa, + Sohaib ul Hassan] + *) Updated CONTRIBUTING [Rich Salz] diff --git a/crypto/bn/bn_gf2m.c b/crypto/bn/bn_gf2m.c index 16868f7..287adf3 100644 --- a/crypto/bn/bn_gf2m.c +++ b/crypto/bn/bn_gf2m.c @@ -547,7 +547,8 @@ int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) * Hernandez, J.L., and Menezes, A. "Software Implementation of Elliptic * Curve Cryptography Over Binary Fields". */ -int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) +static int BN_GF2m_mod_inv_vartime(BIGNUM *r, const BIGNUM *a, + const BIGNUM *p, BN_CTX *ctx) { BIGNUM *b, *c = NULL, *u = NULL, *v = NULL, *tmp; int ret = 0; @@ -713,6 +714,46 @@ int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) return ret; } +/*- + * Wrapper for BN_GF2m_mod_inv_vartime that blinds the input before calling. + * This is not constant time. + * But it does eliminate first order deduction on the input. + */ +int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) +{ + BIGNUM *b = NULL; + int ret = 0; + + BN_CTX_start(ctx); + if ((b = BN_CTX_get(ctx)) == NULL) + goto err; + + /* generate blinding value */ + do { + if (!BN_priv_rand(b, BN_num_bits(p) - 1, + BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) + goto err; + } while (BN_is_zero(b)); + + /* r := a * b */ + if (!BN_GF2m_mod_mul(r, a, b, p, ctx)) + goto err; + + /* r := 1/(a * b) */ + if (!BN_GF2m_mod_inv_vartime(r, r, p, ctx)) + goto err; + + /* r := b/(a * b) = 1/a */ + if (!BN_GF2m_mod_mul(r, r, b, p, ctx)) + goto err; + + ret = 1; + + err: + BN_CTX_end(ctx); + return ret; +} + /* * Invert xx, reduce modulo p, and store the result in r. r could be xx. * This function calls down to the BN_GF2m_mod_inv implementation; this @@ -740,7 +781,6 @@ int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], return ret; } -# ifndef OPENSSL_SUN_GF2M_DIV /* * Divide y by x, reduce modulo p, and store the result in r. r could be x * or y, x could equal y. @@ -771,94 +811,6 @@ int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, BN_CTX_end(ctx); return ret; } -# else -/* - * Divide y by x, reduce modulo p, and store the result in r. r could be x - * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from - * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to the - * Great Divide". - */ -int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, - const BIGNUM *p, BN_CTX *ctx) -{ - BIGNUM *a, *b, *u, *v; - int ret = 0; - - bn_check_top(y); - bn_check_top(x); - bn_check_top(p); - - BN_CTX_start(ctx); - - a = BN_CTX_get(ctx); - b = BN_CTX_get(ctx); - u = BN_CTX_get(ctx); - v = BN_CTX_get(ctx); - if (v == NULL) - goto err; - - /* reduce x and y mod p */ - if (!BN_GF2m_mod(u, y, p)) - goto err; - if (!BN_GF2m_mod(a, x, p)) - goto err; - if (!BN_copy(b, p)) - goto err; - - while (!BN_is_odd(a)) { - if (!BN_rshift1(a, a)) - goto err; - if (BN_is_odd(u)) - if (!BN_GF2m_add(u, u, p)) - goto err; - if (!BN_rshift1(u, u)) - goto err; - } - - do { - if (BN_GF2m_cmp(b, a) > 0) { - if (!BN_GF2m_add(b, b, a)) - goto err; - if (!BN_GF2m_add(v, v, u)) - goto err; - do { - if (!BN_rshift1(b, b)) - goto err; - if (BN_is_odd(v)) - if (!BN_GF2m_add(v, v, p)) - goto err; - if (!BN_rshift1(v, v)) - goto err; - } while (!BN_is_odd(b)); - } else if (BN_abs_is_word(a, 1)) - break; - else { - if (!BN_GF2m_add(a, a, b)) - goto err; - if (!BN_GF2m_add(u, u, v)) - goto err; - do { - if (!BN_rshift1(a, a)) - goto err; - if (BN_is_odd(u)) - if (!BN_GF2m_add(u, u, p)) - goto err; - if (!BN_rshift1(u, u)) - goto err; - } while (!BN_is_odd(a)); - } - } while (1); - - if (!BN_copy(r, u)) - goto err; - bn_check_top(r); - ret = 1; - - err: - BN_CTX_end(ctx); - return ret; -} -# endif /* * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx diff --git a/crypto/ec/build.info b/crypto/ec/build.info index 1e7814f..db506c5 100644 --- a/crypto/ec/build.info +++ b/crypto/ec/build.info @@ -2,7 +2,7 @@ LIBS=../../libcrypto SOURCE[../../libcrypto]=\ ec_lib.c ecp_smpl.c ecp_mont.c ecp_nist.c ec_cvt.c ec_mult.c \ ec_err.c ec_curve.c ec_check.c ec_print.c ec_asn1.c ec_key.c \ - ec2_smpl.c ec2_mult.c ec_ameth.c ec_pmeth.c eck_prn.c \ + ec2_smpl.c ec_ameth.c ec_pmeth.c eck_prn.c \ ecp_nistp224.c ecp_nistp256.c ecp_nistp521.c ecp_nistputil.c \ ecp_oct.c ec2_oct.c ec_oct.c ec_kmeth.c ecdh_ossl.c ecdh_kdf.c \ ecdsa_ossl.c ecdsa_sign.c ecdsa_vrf.c curve25519.c ecx_meth.c \ diff --git a/crypto/ec/ec2_mult.c b/crypto/ec/ec2_mult.c deleted file mode 100644 index 891e810..0000000 --- a/crypto/ec/ec2_mult.c +++ /dev/null @@ -1,404 +0,0 @@ -/* - * Copyright 2002-2016 The OpenSSL Project Authors. All Rights Reserved. - * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved - * - * Licensed under the OpenSSL license (the "License"). You may not use - * this file except in compliance with the License. You can obtain a copy - * in the file LICENSE in the source distribution or at - * https://www.openssl.org/source/license.html - */ - -#include <openssl/err.h> - -#include "internal/bn_int.h" -#include "ec_lcl.h" - -#ifndef OPENSSL_NO_EC2M - -/*- - * Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective - * coordinates. - * Uses algorithm Mdouble in appendix of - * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over - * GF(2^m) without precomputation" (CHES '99, LNCS 1717). - * modified to not require precomputation of c=b^{2^{m-1}}. - */ -static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, - BN_CTX *ctx) -{ - BIGNUM *t1; - int ret = 0; - - /* Since Mdouble is static we can guarantee that ctx != NULL. */ - BN_CTX_start(ctx); - t1 = BN_CTX_get(ctx); - if (t1 == NULL) - goto err; - - if (!group->meth->field_sqr(group, x, x, ctx)) - goto err; - if (!group->meth->field_sqr(group, t1, z, ctx)) - goto err; - if (!group->meth->field_mul(group, z, x, t1, ctx)) - goto err; - if (!group->meth->field_sqr(group, x, x, ctx)) - goto err; - if (!group->meth->field_sqr(group, t1, t1, ctx)) - goto err; - if (!group->meth->field_mul(group, t1, group->b, t1, ctx)) - goto err; - if (!BN_GF2m_add(x, x, t1)) - goto err; - - ret = 1; - - err: - BN_CTX_end(ctx); - return ret; -} - -/*- - * Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery - * projective coordinates. - * Uses algorithm Madd in appendix of - * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over - * GF(2^m) without precomputation" (CHES '99, LNCS 1717). - */ -static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, - BIGNUM *z1, const BIGNUM *x2, const BIGNUM *z2, - BN_CTX *ctx) -{ - BIGNUM *t1, *t2; - int ret = 0; - - /* Since Madd is static we can guarantee that ctx != NULL. */ - BN_CTX_start(ctx); - t1 = BN_CTX_get(ctx); - t2 = BN_CTX_get(ctx); - if (t2 == NULL) - goto err; - - if (!BN_copy(t1, x)) - goto err; - if (!group->meth->field_mul(group, x1, x1, z2, ctx)) - goto err; - if (!group->meth->field_mul(group, z1, z1, x2, ctx)) - goto err; - if (!group->meth->field_mul(group, t2, x1, z1, ctx)) - goto err; - if (!BN_GF2m_add(z1, z1, x1)) - goto err; - if (!group->meth->field_sqr(group, z1, z1, ctx)) - goto err; - if (!group->meth->field_mul(group, x1, z1, t1, ctx)) - goto err; - if (!BN_GF2m_add(x1, x1, t2)) - goto err; - - ret = 1; - - err: - BN_CTX_end(ctx); - return ret; -} - -/*- - * Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) - * using Montgomery point multiplication algorithm Mxy() in appendix of - * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over - * GF(2^m) without precomputation" (CHES '99, LNCS 1717). - * Returns: - * 0 on error - * 1 if return value should be the point at infinity - * 2 otherwise - */ -static int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, - BIGNUM *x1, BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, - BN_CTX *ctx) -{ - BIGNUM *t3, *t4, *t5; - int ret = 0; - - if (BN_is_zero(z1)) { - BN_zero(x2); - BN_zero(z2); - return 1; - } - - if (BN_is_zero(z2)) { - if (!BN_copy(x2, x)) - return 0; - if (!BN_GF2m_add(z2, x, y)) - return 0; - return 2; - } - - /* Since Mxy is static we can guarantee that ctx != NULL. */ - BN_CTX_start(ctx); - t3 = BN_CTX_get(ctx); - t4 = BN_CTX_get(ctx); - t5 = BN_CTX_get(ctx); - if (t5 == NULL) - goto err; - - if (!BN_one(t5)) - goto err; - - if (!group->meth->field_mul(group, t3, z1, z2, ctx)) - goto err; - - if (!group->meth->field_mul(group, z1, z1, x, ctx)) - goto err; - if (!BN_GF2m_add(z1, z1, x1)) - goto err; - if (!group->meth->field_mul(group, z2, z2, x, ctx)) - goto err; - if (!group->meth->field_mul(group, x1, z2, x1, ctx)) - goto err; - if (!BN_GF2m_add(z2, z2, x2)) - goto err; - - if (!group->meth->field_mul(group, z2, z2, z1, ctx)) - goto err; - if (!group->meth->field_sqr(group, t4, x, ctx)) - goto err; - if (!BN_GF2m_add(t4, t4, y)) - goto err; - if (!group->meth->field_mul(group, t4, t4, t3, ctx)) - goto err; - if (!BN_GF2m_add(t4, t4, z2)) - goto err; - - if (!group->meth->field_mul(group, t3, t3, x, ctx)) - goto err; - if (!group->meth->field_div(group, t3, t5, t3, ctx)) - goto err; - if (!group->meth->field_mul(group, t4, t3, t4, ctx)) - goto err; - if (!group->meth->field_mul(group, x2, x1, t3, ctx)) - goto err; - if (!BN_GF2m_add(z2, x2, x)) - goto err; - - if (!group->meth->field_mul(group, z2, z2, t4, ctx)) - goto err; - if (!BN_GF2m_add(z2, z2, y)) - goto err; - - ret = 2; - - err: - BN_CTX_end(ctx); - return ret; -} - -/*- - * Computes scalar*point and stores the result in r. - * point can not equal r. - * Uses a modified algorithm 2P of - * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over - * GF(2^m) without precomputation" (CHES '99, LNCS 1717). - * - * To protect against side-channel attack the function uses constant time swap, - * avoiding conditional branches. - */ -static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, - EC_POINT *r, - const BIGNUM *scalar, - const EC_POINT *point, - BN_CTX *ctx) -{ - BIGNUM *x1, *x2, *z1, *z2; - int ret = 0, i, group_top; - BN_ULONG mask, word; - - if (r == point) { - ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT); - return 0; - } - - /* if result should be point at infinity */ - if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || - EC_POINT_is_at_infinity(group, point)) { - return EC_POINT_set_to_infinity(group, r); - } - - /* only support affine coordinates */ - if (!point->Z_is_one) - return 0; - - /* - * Since point_multiply is static we can guarantee that ctx != NULL. - */ - BN_CTX_start(ctx); - x1 = BN_CTX_get(ctx); - z1 = BN_CTX_get(ctx); - if (z1 == NULL) - goto err; - - x2 = r->X; - z2 = r->Y; - - group_top = bn_get_top(group->field); - if (bn_wexpand(x1, group_top) == NULL - || bn_wexpand(z1, group_top) == NULL - || bn_wexpand(x2, group_top) == NULL - || bn_wexpand(z2, group_top) == NULL) - goto err; - - if (!BN_GF2m_mod_arr(x1, point->X, group->poly)) - goto err; /* x1 = x */ - if (!BN_one(z1)) - goto err; /* z1 = 1 */ - if (!group->meth->field_sqr(group, z2, x1, ctx)) - goto err; /* z2 = x1^2 = x^2 */ - if (!group->meth->field_sqr(group, x2, z2, ctx)) - goto err; - if (!BN_GF2m_add(x2, x2, group->b)) - goto err; /* x2 = x^4 + b */ - - /* find top most bit and go one past it */ - i = bn_get_top(scalar) - 1; - mask = BN_TBIT; - word = bn_get_words(scalar)[i]; - while (!(word & mask)) - mask >>= 1; - mask >>= 1; - /* if top most bit was at word break, go to next word */ - if (!mask) { - i--; - mask = BN_TBIT; - } - - for (; i >= 0; i--) { - word = bn_get_words(scalar)[i]; - while (mask) { - BN_consttime_swap(word & mask, x1, x2, group_top); - BN_consttime_swap(word & mask, z1, z2, group_top); - if (!gf2m_Madd(group, point->X, x2, z2, x1, z1, ctx)) - goto err; - if (!gf2m_Mdouble(group, x1, z1, ctx)) - goto err; - BN_consttime_swap(word & mask, x1, x2, group_top); - BN_consttime_swap(word & mask, z1, z2, group_top); - mask >>= 1; - } - mask = BN_TBIT; - } - - /* convert out of "projective" coordinates */ - i = gf2m_Mxy(group, point->X, point->Y, x1, z1, x2, z2, ctx); - if (i == 0) - goto err; - else if (i == 1) { - if (!EC_POINT_set_to_infinity(group, r)) - goto err; - } else { - if (!BN_one(r->Z)) - goto err; - r->Z_is_one = 1; - } - - /* GF(2^m) field elements should always have BIGNUM::neg = 0 */ - BN_set_negative(r->X, 0); - BN_set_negative(r->Y, 0); - - ret = 1; - - err: - BN_CTX_end(ctx); - return ret; -} - -/*- - * Computes the sum - * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1] - * gracefully ignoring NULL scalar values. - */ -int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, - const BIGNUM *scalar, size_t num, - const EC_POINT *points[], const BIGNUM *scalars[], - BN_CTX *ctx) -{ - BN_CTX *new_ctx = NULL; - int ret = 0; - size_t i; - EC_POINT *p = NULL; - EC_POINT *acc = NULL; - - if (ctx == NULL) { - ctx = new_ctx = BN_CTX_new(); - if (ctx == NULL) - return 0; - } - - /* - * This implementation is more efficient than the wNAF implementation for - * 2 or fewer points. Use the ec_wNAF_mul implementation for 3 or more - * points, or if we can perform a fast multiplication based on - * precomputation. - */ - if ((scalar && (num > 1)) || (num > 2) - || (num == 0 && EC_GROUP_have_precompute_mult(group))) { - ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); - goto err; - } - - if ((p = EC_POINT_new(group)) == NULL) - goto err; - if ((acc = EC_POINT_new(group)) == NULL) - goto err; - - if (!EC_POINT_set_to_infinity(group, acc)) - goto err; - - if (scalar) { - if (!ec_GF2m_montgomery_point_multiply - (group, p, scalar, group->generator, ctx)) - goto err; - if (BN_is_negative(scalar)) - if (!group->meth->invert(group, p, ctx)) - goto err; - if (!group->meth->add(group, acc, acc, p, ctx)) - goto err; - } - - for (i = 0; i < num; i++) { - if (!ec_GF2m_montgomery_point_multiply - (group, p, scalars[i], points[i], ctx)) - goto err; - if (BN_is_negative(scalars[i])) - if (!group->meth->invert(group, p, ctx)) - goto err; - if (!group->meth->add(group, acc, acc, p, ctx)) - goto err; - } - - if (!EC_POINT_copy(r, acc)) - goto err; - - ret = 1; - - err: - EC_POINT_free(p); - EC_POINT_free(acc); - BN_CTX_free(new_ctx); - return ret; -} - -/* - * Precomputation for point multiplication: fall back to wNAF methods because - * ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate - */ - -int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx) -{ - return ec_wNAF_precompute_mult(group, ctx); -} - -int ec_GF2m_have_precompute_mult(const EC_GROUP *group) -{ - return ec_wNAF_have_precompute_mult(group); -} - -#endif diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c index 6bd5f9d..b73805a 100644 --- a/crypto/ec/ec2_smpl.c +++ b/crypto/ec/ec2_smpl.c @@ -47,14 +47,9 @@ const EC_METHOD *EC_GF2m_simple_method(void) ec_GF2m_simple_cmp, ec_GF2m_simple_make_affine, ec_GF2m_simple_points_make_affine, - - /* - * the following three method functions are defined in ec2_mult.c - */ - ec_GF2m_simple_mul, - ec_GF2m_precompute_mult, - ec_GF2m_have_precompute_mult, - + 0 /* mul */, + 0 /* precompute_mul */, + 0 /* have_precompute_mul */, ec_GF2m_simple_field_mul, ec_GF2m_simple_field_sqr, ec_GF2m_simple_field_div, diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index 413a906..36c65c5 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -120,6 +120,23 @@ struct ec_method_st { * EC_POINT_have_precompute_mult (default implementations are used if the * 'mul' pointer is 0): */ + /*- + * mul() calculates the value + * + * r := generator * scalar + * + points[0] * scalars[0] + * + ... + * + points[num-1] * scalars[num-1]. + * + * For a fixed point multiplication (scalar != NULL, num == 0) + * or a variable point multiplication (scalar == NULL, num == 1), + * mul() must use a constant time algorithm: in both cases callers + * should provide an input scalar (either scalar or scalars[0]) + * in the range [0, ec_group_order); for robustness, implementers + * should handle the case when the scalar has not been reduced, but + * may treat it as an unusual input, without any constant-timeness + * guarantee. + */ int (*mul) (const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *); @@ -426,14 +443,6 @@ int ec_GF2m_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, int ec_GF2m_simple_field_div(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); -/* method functions in ec2_mult.c */ -int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, - const BIGNUM *scalar, size_t num, - const EC_POINT *points[], const BIGNUM *scalars[], - BN_CTX *); -int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx); -int ec_GF2m_have_precompute_mult(const EC_GROUP *group); - #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128 /* method functions in ecp_nistp224.c */ int ec_GFp_nistp224_group_init(EC_GROUP *group); diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c index 6b5553c..1f34329 100644 --- a/crypto/ec/ec_mult.c +++ b/crypto/ec/ec_mult.c @@ -113,9 +113,9 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre) * * At a high level, it is Montgomery ladder with conditional swaps. * - * It performs either a fixed scalar point multiplication + * It performs either a fixed point multiplication * (scalar * generator) - * when point is NULL, or a generic scalar point multiplication + * when point is NULL, or a variable point multiplication * (scalar * point) * when point is not NULL. * diff --git a/crypto/ec/ecdsa_ossl.c b/crypto/ec/ecdsa_ossl.c index 2c9e5a8..7842851 100644 --- a/crypto/ec/ecdsa_ossl.c +++ b/crypto/ec/ecdsa_ossl.c @@ -105,23 +105,6 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, } while (BN_is_zero(k)); - /* - * We do not want timing information to leak the length of k, so we - * compute G*k using an equivalent scalar of fixed bit-length. - * - * We unconditionally perform both of these additions to prevent a - * small timing information leakage. We then choose the sum that is - * one bit longer than the order. This guarantees the code - * path used in the constant time implementations elsewhere. - * - * TODO: revisit the BN_copy aiming for a memory access agnostic - * conditional copy. - */ - if (!BN_add(r, k, order) - || !BN_add(X, r, order) - || !BN_copy(k, BN_num_bits(r) > order_bits ? r : X)) - goto err; - /* compute r the x-coordinate of generator * k */ if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); diff --git a/doc/man3/EC_POINT_add.pod b/doc/man3/EC_POINT_add.pod index 3c047e1..21abf46 100644 --- a/doc/man3/EC_POINT_add.pod +++ b/doc/man3/EC_POINT_add.pod @@ -43,10 +43,12 @@ The functions EC_POINT_make_affine and EC_POINTs_make_affine force the internal co-ordinate system. In the case of EC_POINTs_make_affine the value B<num> provides the number of points in the array B<points> to be forced. -EC_POINT_mul calculates the value generator * B<n> + B<q> * B<m> and stores the result in B<r>. The value B<n> may be NULL in which case the result is just B<q> * B<m>. +EC_POINT_mul is a convenient interface to EC_POINTs_mul: it calculates the value generator * B<n> + B<q> * B<m> and stores the result in B<r>. +The value B<n> may be NULL in which case the result is just B<q> * B<m> (variable point multiplication). Alternatively, both B<q> and B<m> may be NULL, and B<n> non-NULL, in which case the result is just generator * B<n> (fixed point multiplication). +When performing a single fixed or variable point multiplication, the underlying implementation uses a constant time algorithm, when the input scalar (either B<n> or B<m>) is in the range [0, ec_group_order). -EC_POINTs_mul calculates the value generator * B<n> + B<q[0]> * B<m[0]> + ... + B<q[num-1]> * B<m[num-1]>. As for EC_POINT_mul the value -B<n> may be NULL. +EC_POINTs_mul calculates the value generator * B<n> + B<q[0]> * B<m[0]> + ... + B<q[num-1]> * B<m[num-1]>. As for EC_POINT_mul the value B<n> may be NULL or B<num> may be zero. +When performing a fixed point multiplication (B<n> is non-NULL and B<num> is 0) or a variable point multiplication (B<n> is NULL and B<num> is 1), the underlying implementation uses a constant time algorithm, when the input scalar (either B<n> or B<m[0]>) is in the range [0, ec_group_order). The function EC_GROUP_precompute_mult stores multiples of the generator for faster point multiplication, whilst EC_GROUP_have_precompute_mult tests whether precomputation has already been done. See L<EC_GROUP_copy(3)> for information _____ openssl-commits mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-commits