The branch master has been updated via 01ad66f85d22fd001582b5f2e6e18db8b820c550 (commit) via f45846f50036343778d7575578e7115e92a3fce1 (commit) via 66b0bca887eb4ad1f5758e56c45905fb3fc36667 (commit) via 3712436071c04ed831594cf47073788417d1506b (commit) via 51f3021d974f32539a2727908018664963695b5d (commit) from 3c849bc901fa191fc517bc20d905783e6e428de5 (commit)
- Log ----------------------------------------------------------------- commit 01ad66f85d22fd001582b5f2e6e18db8b820c550 Author: Nicola Tuveri <nic....@gmail.com> Date: Sun Jul 8 10:39:39 2018 +0300 EC2M Lopez-Dahab ladder: use it also for ECDSA verify By default `ec_scalar_mul_ladder` (which uses the Lopez-Dahab ladder implementation) is used only for (k * Generator) or (k * VariablePoint). ECDSA verification uses (a * Generator + b * VariablePoint): this commit forces the use of `ec_scalar_mul_ladder` also for the ECDSA verification path, while using the default wNAF implementation for any other case. With this commit `ec_scalar_mul_ladder` loses the static attribute, and is added to ec_lcl.h so EC_METHODs can directly use it. While working on a new custom EC_POINTs_mul implementation, I realized that many checks (e.g. all the points being compatible with the given EC_GROUP, creating a temporary BN_CTX if `ctx == NULL`, check for the corner case `scalar == NULL && num == 0`) were duplicated again and again in every single implementation (and actually some implementations lacked some of the tests). I thought that it makes way more sense for those checks that are independent from the actual implementation and should always be done, to be moved in the EC_POINTs_mul wrapper: so this commit also includes these changes. Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Matt Caswell <m...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6690) commit f45846f50036343778d7575578e7115e92a3fce1 Author: Nicola Tuveri <nic....@gmail.com> Date: Sat Jul 14 00:55:01 2018 +0300 EC2M Lopez-Dahab ladder implementation This commit uses the new ladder scaffold to implement a specialized ladder step based on differential addition-and-doubling in mixed Lopez-Dahab projective coordinates, modified to independently blind the operands. The arithmetic in `ladder_pre`, `ladder_step` and `ladder_post` is auto generated with tooling: - see, e.g., "Guide to ECC" Alg 3.40 for reference about the `ladder_pre` implementation; - see https://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3 for the differential addition-and-doubling formulas implemented in `ladder_step`; - see, e.g., "Fast Multiplication on Elliptic Curves over GF(2**m) without Precomputation" (Lopez and Dahab, CHES 1999) Appendix Alg Mxy for the `ladder_post` implementation to recover the `(x,y)` result in affine coordinates. Co-authored-by: Billy Brumley <bbrum...@gmail.com> Co-authored-by: Sohaib ul Hassan <soh.19.has...@gmail.com> Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Matt Caswell <m...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6690) commit 66b0bca887eb4ad1f5758e56c45905fb3fc36667 Author: Billy Brumley <bbrum...@gmail.com> Date: Sun Jul 8 01:27:34 2018 +0300 [test] test some important ladder corner cases and catch corner cases better and earlier Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Matt Caswell <m...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6690) commit 3712436071c04ed831594cf47073788417d1506b Author: Nicola Tuveri <nic....@gmail.com> Date: Sun Jul 8 00:50:49 2018 +0300 EC point multiplication: add `ladder` scaffold for specialized Montgomery ladder implementations PR #6009 and #6070 replaced the default EC point multiplication path for prime and binary curves with a unified Montgomery ladder implementation with various timing attack defenses (for the common paths when a secret scalar is feed to the point multiplication). The newly introduced default implementation directly used EC_POINT_add/dbl in the main loop. The scaffolding introduced by this commit allows EC_METHODs to define a specialized `ladder_step` function to improve performances by taking advantage of efficient formulas for differential addition-and-doubling and different coordinate systems. - `ladder_pre` is executed before the main loop of the ladder: by default it copies the input point P into S, and doubles it into R. Specialized implementations could, e.g., use this hook to transition to different coordinate systems before copying and doubling; - `ladder_step` is the core of the Montgomery ladder loop: by default it computes `S := R+S; R := 2R;`, but specific implementations could, e.g., implement a more efficient formula for differential addition-and-doubling; - `ladder_post` is executed after the Montgomery ladder loop: by default it's a noop, but specialized implementations could, e.g., use this hook to transition back from the coordinate system used for optimizing the differential addition-and-doubling or recover the y coordinate of the result point. This commit also renames `ec_mul_consttime` to `ec_scalar_mul_ladder`, as it better corresponds to what this function does: nothing can be truly said about the constant-timeness of the overall execution of this function, given that the underlying operations are not necessarily constant-time themselves. What this implementation ensures is that the same fixed sequence of operations is executed for each scalar multiplication (for a given EC_GROUP), with no dependency on the value of the input scalar. Co-authored-by: Sohaib ul Hassan <soh.19.has...@gmail.com> Co-authored-by: Billy Brumley <bbrum...@gmail.com> Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Matt Caswell <m...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6690) commit 51f3021d974f32539a2727908018664963695b5d Author: Nicola Tuveri <nic....@gmail.com> Date: Fri Jul 13 11:48:29 2018 +0300 Remove stale SM2 error codes Run `make update ERROR_REBUILD=-rebuild` to remove some stale error codes for SM2 (which is now using its own submodule for error codes, i.e., `SM2_*`). Reviewed-by: Andy Polyakov <ap...@openssl.org> Reviewed-by: Matt Caswell <m...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/6690) ----------------------------------------------------------------------- Summary of changes: CHANGES | 13 ++ crypto/ec/ec2_smpl.c | 328 ++++++++++++++++++++++++++++++++------- crypto/ec/ec_err.c | 21 ++- crypto/ec/ec_lcl.h | 81 ++++++++++ crypto/ec/ec_lib.c | 33 +++- crypto/ec/ec_mult.c | 183 +++++++++++++--------- crypto/ec/ecp_mont.c | 5 +- crypto/ec/ecp_nist.c | 5 +- crypto/ec/ecp_nistp224.c | 10 +- crypto/ec/ecp_nistp256.c | 12 +- crypto/ec/ecp_nistp521.c | 10 +- crypto/ec/ecp_nistz256.c | 29 +--- crypto/ec/ecp_smpl.c | 6 +- crypto/err/openssl.txt | 10 ++ crypto/include/internal/sm2err.h | 3 + include/internal/dsoerr.h | 3 + include/openssl/ecerr.h | 16 +- test/ectest.c | 13 +- 18 files changed, 586 insertions(+), 195 deletions(-) diff --git a/CHANGES b/CHANGES index 4765e0b..c1d4c2d 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,19 @@ Changes between 1.1.0h and 1.1.1 [xx XXX xxxx] + *) 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 + coordinates, modified to independently blind the operands. + [Billy Bob Brumley, Sohaib ul Hassan, Nicola Tuveri] + + *) Add a scaffold to optionally enhance the Montgomery ladder implementation + for `ec_scalar_mul_ladder` (formerly `ec_mul_consttime`) allowing + EC_METHODs to implement their own specialized "ladder step", to take + advantage of more favorable coordinate systems or more efficient + differential addition-and-doubling algorithms. + [Billy Bob Brumley, Sohaib ul Hassan, Nicola Tuveri] + *) Modified the random device based seed sources to keep the relevant file descriptors open rather than reopening them on each access. This allows such sources to operate in a chroot() jail without diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c index cef6ba4..9ce332b 100644 --- a/crypto/ec/ec2_smpl.c +++ b/crypto/ec/ec2_smpl.c @@ -15,63 +15,6 @@ #ifndef OPENSSL_NO_EC2M -const EC_METHOD *EC_GF2m_simple_method(void) -{ - static const EC_METHOD ret = { - EC_FLAGS_DEFAULT_OCT, - NID_X9_62_characteristic_two_field, - ec_GF2m_simple_group_init, - ec_GF2m_simple_group_finish, - ec_GF2m_simple_group_clear_finish, - ec_GF2m_simple_group_copy, - ec_GF2m_simple_group_set_curve, - ec_GF2m_simple_group_get_curve, - ec_GF2m_simple_group_get_degree, - ec_group_simple_order_bits, - ec_GF2m_simple_group_check_discriminant, - ec_GF2m_simple_point_init, - ec_GF2m_simple_point_finish, - ec_GF2m_simple_point_clear_finish, - ec_GF2m_simple_point_copy, - ec_GF2m_simple_point_set_to_infinity, - 0 /* set_Jprojective_coordinates_GFp */ , - 0 /* get_Jprojective_coordinates_GFp */ , - ec_GF2m_simple_point_set_affine_coordinates, - ec_GF2m_simple_point_get_affine_coordinates, - 0, 0, 0, - ec_GF2m_simple_add, - ec_GF2m_simple_dbl, - ec_GF2m_simple_invert, - ec_GF2m_simple_is_at_infinity, - ec_GF2m_simple_is_on_curve, - ec_GF2m_simple_cmp, - ec_GF2m_simple_make_affine, - ec_GF2m_simple_points_make_affine, - 0 /* mul */, - 0 /* precompute_mul */, - 0 /* have_precompute_mul */, - ec_GF2m_simple_field_mul, - ec_GF2m_simple_field_sqr, - ec_GF2m_simple_field_div, - 0 /* field_encode */ , - 0 /* field_decode */ , - 0, /* field_set_to_one */ - ec_key_simple_priv2oct, - ec_key_simple_oct2priv, - 0, /* set private */ - ec_key_simple_generate_key, - ec_key_simple_check_key, - ec_key_simple_generate_public_key, - 0, /* keycopy */ - 0, /* keyfinish */ - ecdh_simple_compute_key, - 0, /* field_inverse_mod_ord */ - 0 /* blind_coordinates */ - }; - - return &ret; -} - /* * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members * are handled by EC_GROUP_new. @@ -737,4 +680,275 @@ int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, return BN_GF2m_mod_div(r, a, b, group->field, ctx); } +/*- + * Lopez-Dahab ladder, pre step. + * See e.g. "Guide to ECC" Alg 3.40. + * Modified to blind s and r independently. + * s:= p, r := 2p + */ +static +int ec_GF2m_simple_ladder_pre(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx) +{ + /* if p is not affine, something is wrong */ + if (p->Z_is_one == 0) + return 0; + + /* s blinding: make sure lambda (s->Z here) is not zero */ + do { + if (!BN_priv_rand(s->Z, BN_num_bits(group->field) - 1, + BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) { + ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB); + return 0; + } + } while (BN_is_zero(s->Z)); + + /* if field_encode defined convert between representations */ + if ((group->meth->field_encode != NULL + && !group->meth->field_encode(group, s->Z, s->Z, ctx)) + || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx)) + return 0; + + /* r blinding: make sure lambda (r->Y here for storage) is not zero */ + do { + if (!BN_priv_rand(r->Y, BN_num_bits(group->field) - 1, + BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) { + ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB); + return 0; + } + } while (BN_is_zero(r->Y)); + + if ((group->meth->field_encode != NULL + && !group->meth->field_encode(group, r->Y, r->Y, ctx)) + || !group->meth->field_sqr(group, r->Z, p->X, ctx) + || !group->meth->field_sqr(group, r->X, r->Z, ctx) + || !BN_GF2m_add(r->X, r->X, group->b) + || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx) + || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx)) + return 0; + + s->Z_is_one = 0; + r->Z_is_one = 0; + + return 1; +} + +/*- + * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords. + * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3 + * s := r + s, r := 2r + */ +static +int ec_GF2m_simple_ladder_step(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx) +{ + if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx) + || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx) + || !group->meth->field_sqr(group, s->Y, r->Z, ctx) + || !group->meth->field_sqr(group, r->Z, r->X, ctx) + || !BN_GF2m_add(s->Z, r->Y, s->X) + || !group->meth->field_sqr(group, s->Z, s->Z, ctx) + || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx) + || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx) + || !BN_GF2m_add(s->X, s->X, r->Y) + || !group->meth->field_sqr(group, r->Y, r->Z, ctx) + || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx) + || !group->meth->field_sqr(group, s->Y, s->Y, ctx) + || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx) + || !BN_GF2m_add(r->X, r->Y, s->Y)) + return 0; + + return 1; +} + +/*- + * Recover affine (x,y) result from Lopez-Dahab r and s, affine p. + * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m) + * without Precomputation" (Lopez and Dahab, CHES 1999), + * Appendix Alg Mxy. + */ +static +int ec_GF2m_simple_ladder_post(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx) +{ + int ret = 0; + BIGNUM *t0, *t1, *t2 = NULL; + + if (BN_is_zero(r->Z)) + return EC_POINT_set_to_infinity(group, r); + + if (BN_is_zero(s->Z)) { + if (!EC_POINT_copy(r, p) + || !EC_POINT_invert(group, r, ctx)) { + ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB); + return 0; + } + return 1; + } + + BN_CTX_start(ctx); + t0 = BN_CTX_get(ctx); + t1 = BN_CTX_get(ctx); + t2 = BN_CTX_get(ctx); + if (t2 == NULL) { + ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE); + goto err; + } + + if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx) + || !group->meth->field_mul(group, t1, p->X, r->Z, ctx) + || !BN_GF2m_add(t1, r->X, t1) + || !group->meth->field_mul(group, t2, p->X, s->Z, ctx) + || !group->meth->field_mul(group, r->Z, r->X, t2, ctx) + || !BN_GF2m_add(t2, t2, s->X) + || !group->meth->field_mul(group, t1, t1, t2, ctx) + || !group->meth->field_sqr(group, t2, p->X, ctx) + || !BN_GF2m_add(t2, p->Y, t2) + || !group->meth->field_mul(group, t2, t2, t0, ctx) + || !BN_GF2m_add(t1, t2, t1) + || !group->meth->field_mul(group, t2, p->X, t0, ctx) + || !BN_GF2m_mod_inv(t2, t2, group->field, ctx) + || !group->meth->field_mul(group, t1, t1, t2, ctx) + || !group->meth->field_mul(group, r->X, r->Z, t2, ctx) + || !BN_GF2m_add(t2, p->X, r->X) + || !group->meth->field_mul(group, t2, t2, t1, ctx) + || !BN_GF2m_add(r->Y, p->Y, t2) + || !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; +} + +static +int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r, + const BIGNUM *scalar, size_t num, + const EC_POINT *points[], + const BIGNUM *scalars[], + BN_CTX *ctx) +{ + int ret = 0; + EC_POINT *t = NULL; + + /*- + * We limit use of the ladder only to the following cases: + * - r := scalar * G + * Fixed point mul: scalar != NULL && num == 0; + * - r := scalars[0] * points[0] + * Variable point mul: scalar == NULL && num == 1; + * - r := scalar * G + scalars[0] * points[0] + * used, e.g., in ECDSA verification: scalar != NULL && num == 1 + * + * In any other case (num > 1) we use the default wNAF implementation. + * + * We also let the default implementation handle degenerate cases like group + * order or cofactor set to 0. + */ + if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor)) + return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); + + if (scalar != NULL && num == 0) + /* Fixed point multiplication */ + return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx); + + if (scalar == NULL && num == 1) + /* Variable point multiplication */ + return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx); + + /*- + * Double point multiplication: + * r := scalar * G + scalars[0] * points[0] + */ + + if ((t = EC_POINT_new(group)) == NULL) { + ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE); + return 0; + } + + if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx) + || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx) + || !EC_POINT_add(group, r, t, r, ctx)) + goto err; + + ret = 1; + + err: + EC_POINT_free(t); + return ret; +} + +const EC_METHOD *EC_GF2m_simple_method(void) +{ + static const EC_METHOD ret = { + EC_FLAGS_DEFAULT_OCT, + NID_X9_62_characteristic_two_field, + ec_GF2m_simple_group_init, + ec_GF2m_simple_group_finish, + ec_GF2m_simple_group_clear_finish, + ec_GF2m_simple_group_copy, + ec_GF2m_simple_group_set_curve, + ec_GF2m_simple_group_get_curve, + ec_GF2m_simple_group_get_degree, + ec_group_simple_order_bits, + ec_GF2m_simple_group_check_discriminant, + ec_GF2m_simple_point_init, + ec_GF2m_simple_point_finish, + ec_GF2m_simple_point_clear_finish, + ec_GF2m_simple_point_copy, + ec_GF2m_simple_point_set_to_infinity, + 0, /* set_Jprojective_coordinates_GFp */ + 0, /* get_Jprojective_coordinates_GFp */ + ec_GF2m_simple_point_set_affine_coordinates, + ec_GF2m_simple_point_get_affine_coordinates, + 0, /* point_set_compressed_coordinates */ + 0, /* point2oct */ + 0, /* oct2point */ + ec_GF2m_simple_add, + ec_GF2m_simple_dbl, + ec_GF2m_simple_invert, + ec_GF2m_simple_is_at_infinity, + ec_GF2m_simple_is_on_curve, + ec_GF2m_simple_cmp, + ec_GF2m_simple_make_affine, + ec_GF2m_simple_points_make_affine, + ec_GF2m_simple_points_mul, + 0, /* precompute_mult */ + 0, /* have_precompute_mult */ + ec_GF2m_simple_field_mul, + ec_GF2m_simple_field_sqr, + ec_GF2m_simple_field_div, + 0, /* field_encode */ + 0, /* field_decode */ + 0, /* field_set_to_one */ + ec_key_simple_priv2oct, + ec_key_simple_oct2priv, + 0, /* set private */ + ec_key_simple_generate_key, + ec_key_simple_check_key, + ec_key_simple_generate_public_key, + 0, /* keycopy */ + 0, /* keyfinish */ + ecdh_simple_compute_key, + 0, /* field_inverse_mod_ord */ + 0, /* blind_coordinates */ + ec_GF2m_simple_ladder_pre, + ec_GF2m_simple_ladder_step, + ec_GF2m_simple_ladder_post + }; + + return &ret; +} + #endif diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c index 342b84f..cbe204f 100644 --- a/crypto/ec/ec_err.c +++ b/crypto/ec/ec_err.c @@ -70,10 +70,16 @@ static const ERR_STRING_DATA EC_str_functs[] = { "ec_GF2m_simple_group_check_discriminant"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, 0), "ec_GF2m_simple_group_set_curve"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_LADDER_POST, 0), + "ec_GF2m_simple_ladder_post"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_LADDER_PRE, 0), + "ec_GF2m_simple_ladder_pre"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_OCT2POINT, 0), "ec_GF2m_simple_oct2point"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINT2OCT, 0), "ec_GF2m_simple_point2oct"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINTS_MUL, 0), + "ec_GF2m_simple_points_mul"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, 0), "ec_GF2m_simple_point_get_affine_coordinates"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, 0), @@ -191,6 +197,7 @@ static const ERR_STRING_DATA EC_str_functs[] = { {ERR_PACK(ERR_LIB_EC, EC_F_EC_PKEY_PARAM_CHECK, 0), "ec_pkey_param_check"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINTS_MAKE_AFFINE, 0), "EC_POINTs_make_affine"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINTS_MUL, 0), "EC_POINTs_mul"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_ADD, 0), "EC_POINT_add"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_BN2POINT, 0), "EC_POINT_bn2point"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_CMP, 0), "EC_POINT_cmp"}, @@ -226,6 +233,8 @@ static const ERR_STRING_DATA EC_str_functs[] = { {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_SET_TO_INFINITY, 0), "EC_POINT_set_to_infinity"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_PRE_COMP_NEW, 0), "ec_pre_comp_new"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_SCALAR_MUL_LADDER, 0), + "ec_scalar_mul_ladder"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_WNAF_MUL, 0), "ec_wNAF_mul"}, {ERR_PACK(ERR_LIB_EC, EC_F_EC_WNAF_PRECOMPUTE_MULT, 0), "ec_wNAF_precompute_mult"}, @@ -261,12 +270,6 @@ static const ERR_STRING_DATA EC_str_functs[] = { {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_EC_KEYGEN, 0), "pkey_ec_keygen"}, {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_EC_PARAMGEN, 0), "pkey_ec_paramgen"}, {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_EC_SIGN, 0), "pkey_ec_sign"}, - {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_SM2_CTRL, 0), "pkey_sm2_ctrl"}, - {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_SM2_CTRL_STR, 0), "pkey_sm2_ctrl_str"}, - {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_SM2_INIT, 0), "pkey_sm2_init"}, - {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_SM2_KEYGEN, 0), "pkey_sm2_keygen"}, - {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_SM2_PARAMGEN, 0), "pkey_sm2_paramgen"}, - {ERR_PACK(ERR_LIB_EC, EC_F_PKEY_SM2_SIGN, 0), "pkey_sm2_sign"}, {ERR_PACK(ERR_LIB_EC, EC_F_VALIDATE_ECX_DERIVE, 0), "validate_ecx_derive"}, {0, NULL} }; @@ -320,6 +323,9 @@ static const ERR_STRING_DATA EC_str_reasons[] = { "invalid trinomial basis"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_KDF_PARAMETER_ERROR), "kdf parameter error"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_KEYS_NOT_SET), "keys not set"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_LADDER_POST_FAILURE), "ladder post failure"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_LADDER_PRE_FAILURE), "ladder pre failure"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_LADDER_STEP_FAILURE), "ladder step failure"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PARAMETERS), "missing parameters"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PRIVATE_KEY), "missing private key"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_NEED_NEW_SETUP_VALUES), @@ -339,6 +345,8 @@ static const ERR_STRING_DATA EC_str_reasons[] = { {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_ARITHMETIC_FAILURE), "point arithmetic failure"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_AT_INFINITY), "point at infinity"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_COORDINATES_BLIND_FAILURE), + "point coordinates blind failure"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_IS_NOT_ON_CURVE), "point is not on curve"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_RANDOM_NUMBER_GENERATION_FAILED), @@ -347,6 +355,7 @@ static const ERR_STRING_DATA EC_str_reasons[] = { {ERR_PACK(ERR_LIB_EC, 0, EC_R_SLOT_FULL), "slot full"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNDEFINED_GENERATOR), "undefined generator"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNDEFINED_ORDER), "undefined order"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_COFACTOR), "unknown cofactor"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_GROUP), "unknown group"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_ORDER), "unknown order"}, {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNSUPPORTED_FIELD), "unsupported field"}, diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index ae38029..8b16971 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -178,6 +178,15 @@ struct ec_method_st { int (*field_inverse_mod_ord)(const EC_GROUP *, BIGNUM *r, const BIGNUM *x, BN_CTX *); int (*blind_coordinates)(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx); + int (*ladder_pre)(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx); + int (*ladder_step)(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx); + int (*ladder_post)(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx); }; /* @@ -637,4 +646,76 @@ int X25519(uint8_t out_shared_key[32], const uint8_t private_key[32], void X25519_public_from_private(uint8_t out_public_value[32], const uint8_t private_key[32]); +/*- + * This functions computes a single point multiplication over the EC group, + * using, at a high level, a Montgomery ladder with conditional swaps, with + * various timing attack defenses. + * + * It performs either a fixed point multiplication + * (scalar * generator) + * when point is NULL, or a variable point multiplication + * (scalar * point) + * when point is not NULL. + * + * `scalar` cannot be NULL and should be in the range [0,n) otherwise all + * constant time bets are off (where n is the cardinality of the EC group). + * + * This function expects `group->order` and `group->cardinality` to be well + * defined and non-zero: it fails with an error code otherwise. + * + * NB: This says nothing about the constant-timeness of the ladder step + * implementation (i.e., the default implementation is based on EC_POINT_add and + * EC_POINT_dbl, which of course are not constant time themselves) or the + * underlying multiprecision arithmetic. + * + * The product is stored in `r`. + * + * This is an internal function: callers are in charge of ensuring that the + * input parameters `group`, `r`, `scalar` and `ctx` are not NULL. + * + * Returns 1 on success, 0 otherwise. + */ +int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r, + const BIGNUM *scalar, const EC_POINT *point, + BN_CTX *ctx); + int ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx); + +static inline int ec_point_ladder_pre(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx) +{ + if (group->meth->ladder_pre != NULL) + return group->meth->ladder_pre(group, r, s, p, ctx); + + if (!EC_POINT_copy(s, p) + || !EC_POINT_dbl(group, r, s, ctx)) + return 0; + + return 1; +} + +static inline int ec_point_ladder_step(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx) +{ + if (group->meth->ladder_step != NULL) + return group->meth->ladder_step(group, r, s, p, ctx); + + if (!EC_POINT_add(group, s, r, s, ctx) + || !EC_POINT_dbl(group, r, r, ctx)) + return 0; + + return 1; + +} + +static inline int ec_point_ladder_post(const EC_GROUP *group, + EC_POINT *r, EC_POINT *s, + EC_POINT *p, BN_CTX *ctx) +{ + if (group->meth->ladder_post != NULL) + return group->meth->ladder_post(group, r, s, p, ctx); + + return 1; +} diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c index 6a2d1b5..457cd35 100644 --- a/crypto/ec/ec_lib.c +++ b/crypto/ec/ec_lib.c @@ -919,11 +919,38 @@ int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) { - if (group->meth->mul == 0) + int ret = 0; + size_t i = 0; + BN_CTX *new_ctx = NULL; + + if ((scalar == NULL) && (num == 0)) { + return EC_POINT_set_to_infinity(group, r); + } + + if (!ec_point_is_compat(r, group)) { + ECerr(EC_F_EC_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + for (i = 0; i < num; i++) { + if (!ec_point_is_compat(points[i], group)) { + ECerr(EC_F_EC_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + } + + if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL) { + ECerr(EC_F_EC_POINTS_MUL, ERR_R_INTERNAL_ERROR); + return 0; + } + + if (group->meth->mul != NULL) + ret = group->meth->mul(group, r, scalar, num, points, scalars, ctx); + else /* use default */ - return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); + ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); - return group->meth->mul(group, r, scalar, num, points, scalars, ctx); + BN_CTX_free(new_ctx); + return ret; } int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c index 663db57..7e1b365 100644 --- a/crypto/ec/ec_mult.c +++ b/crypto/ec/ec_mult.c @@ -108,10 +108,9 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre) } while(0) /*- - * This functions computes (in constant time) a point multiplication over the - * EC group. - * - * At a high level, it is Montgomery ladder with conditional swaps. + * This functions computes a single point multiplication over the EC group, + * using, at a high level, a Montgomery ladder with conditional swaps, with + * various timing attack defenses. * * It performs either a fixed point multiplication * (scalar * generator) @@ -119,51 +118,85 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre) * (scalar * point) * when point is not NULL. * - * scalar should be in the range [0,n) otherwise all constant time bets are off. + * `scalar` cannot be NULL and should be in the range [0,n) otherwise all + * constant time bets are off (where n is the cardinality of the EC group). + * + * This function expects `group->order` and `group->cardinality` to be well + * defined and non-zero: it fails with an error code otherwise. * - * NB: This says nothing about EC_POINT_add and EC_POINT_dbl, - * which of course are not constant time themselves. + * NB: This says nothing about the constant-timeness of the ladder step + * implementation (i.e., the default implementation is based on EC_POINT_add and + * EC_POINT_dbl, which of course are not constant time themselves) or the + * underlying multiprecision arithmetic. * - * The product is stored in r. + * The product is stored in `r`. + * + * This is an internal function: callers are in charge of ensuring that the + * input parameters `group`, `r`, `scalar` and `ctx` are not NULL. * * Returns 1 on success, 0 otherwise. */ -static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, - const BIGNUM *scalar, const EC_POINT *point, - BN_CTX *ctx) +int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r, + const BIGNUM *scalar, const EC_POINT *point, + BN_CTX *ctx) { int i, cardinality_bits, group_top, kbit, pbit, Z_is_one; + EC_POINT *p = NULL; EC_POINT *s = NULL; BIGNUM *k = NULL; BIGNUM *lambda = NULL; BIGNUM *cardinality = NULL; - BN_CTX *new_ctx = NULL; int ret = 0; - if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL) + /* early exit if the input point is the point at infinity */ + if (point != NULL && EC_POINT_is_at_infinity(group, point)) + return EC_POINT_set_to_infinity(group, r); + + if (BN_is_zero(group->order)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_UNKNOWN_ORDER); + return 0; + } + if (BN_is_zero(group->cofactor)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_UNKNOWN_COFACTOR); return 0; + } BN_CTX_start(ctx); - s = EC_POINT_new(group); - if (s == NULL) + if (((p = EC_POINT_new(group)) == NULL) + || ((s = EC_POINT_new(group)) == NULL)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_MALLOC_FAILURE); goto err; + } if (point == NULL) { - if (!EC_POINT_copy(s, group->generator)) + if (!EC_POINT_copy(p, group->generator)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_EC_LIB); goto err; + } } else { - if (!EC_POINT_copy(s, point)) + if (!EC_POINT_copy(p, point)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_EC_LIB); goto err; + } } + EC_POINT_BN_set_flags(p, BN_FLG_CONSTTIME); + EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME); EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME); cardinality = BN_CTX_get(ctx); lambda = BN_CTX_get(ctx); k = BN_CTX_get(ctx); - if (k == NULL || !BN_mul(cardinality, group->order, group->cofactor, ctx)) + if (k == NULL) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_MALLOC_FAILURE); + goto err; + } + + if (!BN_mul(cardinality, group->order, group->cofactor, ctx)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } /* * Group cardinalities are often on a word boundary. @@ -174,11 +207,15 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, cardinality_bits = BN_num_bits(cardinality); group_top = bn_get_top(cardinality); if ((bn_wexpand(k, group_top + 1) == NULL) - || (bn_wexpand(lambda, group_top + 1) == NULL)) + || (bn_wexpand(lambda, group_top + 1) == NULL)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } - if (!BN_copy(k, scalar)) + if (!BN_copy(k, scalar)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } BN_set_flags(k, BN_FLG_CONSTTIME); @@ -187,15 +224,21 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, * this is an unusual input, and we don't guarantee * constant-timeness */ - if (!BN_nnmod(k, k, cardinality, ctx)) + if (!BN_nnmod(k, k, cardinality, ctx)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } } - if (!BN_add(lambda, k, cardinality)) + if (!BN_add(lambda, k, cardinality)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } BN_set_flags(lambda, BN_FLG_CONSTTIME); - if (!BN_add(k, lambda, cardinality)) + if (!BN_add(k, lambda, cardinality)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } /* * lambda := scalar + cardinality * k := scalar + 2*cardinality @@ -209,8 +252,13 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, || (bn_wexpand(s->Z, group_top) == NULL) || (bn_wexpand(r->X, group_top) == NULL) || (bn_wexpand(r->Y, group_top) == NULL) - || (bn_wexpand(r->Z, group_top) == NULL)) + || (bn_wexpand(r->Z, group_top) == NULL) + || (bn_wexpand(p->X, group_top) == NULL) + || (bn_wexpand(p->Y, group_top) == NULL) + || (bn_wexpand(p->Z, group_top) == NULL)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, ERR_R_BN_LIB); goto err; + } /*- * Apply coordinate blinding for EC_POINT. @@ -220,19 +268,19 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, * success or if coordinate blinding is not implemented for this * group. */ - if (!ec_point_blind_coordinates(group, s, ctx)) + if (!ec_point_blind_coordinates(group, p, ctx)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_POINT_COORDINATES_BLIND_FAILURE); goto err; + } - /* top bit is a 1, in a fixed pos */ - if (!EC_POINT_copy(r, s)) - goto err; - - EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME); - - if (!EC_POINT_dbl(group, s, s, ctx)) + /* Initialize the Montgomery ladder */ + if (!ec_point_ladder_pre(group, r, s, p, ctx)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_LADDER_PRE_FAILURE); goto err; + } - pbit = 0; + /* top bit is a 1, in a fixed pos */ + pbit = 1; #define EC_POINT_CSWAP(c, a, b, w, t) do { \ BN_consttime_swap(c, (a)->X, (b)->X, w); \ @@ -304,10 +352,12 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, for (i = cardinality_bits - 1; i >= 0; i--) { kbit = BN_is_bit_set(k, i) ^ pbit; EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one); - if (!EC_POINT_add(group, s, r, s, ctx)) - goto err; - if (!EC_POINT_dbl(group, r, r, ctx)) + + /* Perform a single step of the Montgomery ladder */ + if (!ec_point_ladder_step(group, r, s, p, ctx)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_LADDER_STEP_FAILURE); goto err; + } /* * pbit logic merges this cswap with that of the * next iteration @@ -318,12 +368,18 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one); #undef EC_POINT_CSWAP + /* Finalize ladder (and recover full point coordinates) */ + if (!ec_point_ladder_post(group, r, s, p, ctx)) { + ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_LADDER_POST_FAILURE); + goto err; + } + ret = 1; err: + EC_POINT_free(p); EC_POINT_free(s); BN_CTX_end(ctx); - BN_CTX_free(new_ctx); return ret; } @@ -355,7 +411,6 @@ 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 *ctx) { - BN_CTX *new_ctx = NULL; const EC_POINT *generator = NULL; EC_POINT *tmp = NULL; size_t totalnum; @@ -380,56 +435,35 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, * precomputation is not available */ int ret = 0; - if (!ec_point_is_compat(r, group)) { - ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); - return 0; - } - - if ((scalar == NULL) && (num == 0)) { - return EC_POINT_set_to_infinity(group, r); - } - if (!BN_is_zero(group->order) && !BN_is_zero(group->cofactor)) { /*- - * Handle the common cases where the scalar is secret, enforcing a constant - * time scalar multiplication algorithm. + * Handle the common cases where the scalar is secret, enforcing a + * scalar multiplication implementation based on a Montgomery ladder, + * with various timing attack defenses. */ if ((scalar != NULL) && (num == 0)) { /*- * In this case we want to compute scalar * GeneratorPoint: this - * codepath is reached most prominently by (ephemeral) key generation - * of EC cryptosystems (i.e. ECDSA keygen and sign setup, ECDH - * keygen/first half), where the scalar is always secret. This is why - * we ignore if BN_FLG_CONSTTIME is actually set and we always call the - * constant time version. + * codepath is reached most prominently by (ephemeral) key + * generation of EC cryptosystems (i.e. ECDSA keygen and sign setup, + * ECDH keygen/first half), where the scalar is always secret. This + * is why we ignore if BN_FLG_CONSTTIME is actually set and we + * always call the ladder version. */ - return ec_mul_consttime(group, r, scalar, NULL, ctx); + return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx); } if ((scalar == NULL) && (num == 1)) { /*- - * In this case we want to compute scalar * GenericPoint: this codepath - * is reached most prominently by the second half of ECDH, where the - * secret scalar is multiplied by the peer's public point. To protect - * the secret scalar, we ignore if BN_FLG_CONSTTIME is actually set and - * we always call the constant time version. + * In this case we want to compute scalar * VariablePoint: this + * codepath is reached most prominently by the second half of ECDH, + * where the secret scalar is multiplied by the peer's public point. + * To protect the secret scalar, we ignore if BN_FLG_CONSTTIME is + * actually set and we always call the ladder version. */ - return ec_mul_consttime(group, r, scalars[0], points[0], ctx); - } - } - - for (i = 0; i < num; i++) { - if (!ec_point_is_compat(points[i], group)) { - ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); - return 0; + return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx); } } - if (ctx == NULL) { - ctx = new_ctx = BN_CTX_new(); - if (ctx == NULL) - goto err; - } - if (scalar != NULL) { generator = EC_GROUP_get0_generator(group); if (generator == NULL) { @@ -736,7 +770,6 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, ret = 1; err: - BN_CTX_free(new_ctx); EC_POINT_free(tmp); OPENSSL_free(wsize); OPENSSL_free(wNAF_len); diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c index 358e998..fda9a23 100644 --- a/crypto/ec/ecp_mont.c +++ b/crypto/ec/ecp_mont.c @@ -63,7 +63,10 @@ const EC_METHOD *EC_GFp_mont_method(void) 0, /* keyfinish */ ecdh_simple_compute_key, 0, /* field_inverse_mod_ord */ - ec_GFp_simple_blind_coordinates + ec_GFp_simple_blind_coordinates, + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c index 58669d3..2c23525 100644 --- a/crypto/ec/ecp_nist.c +++ b/crypto/ec/ecp_nist.c @@ -65,7 +65,10 @@ const EC_METHOD *EC_GFp_nist_method(void) 0, /* keyfinish */ ecdh_simple_compute_key, 0, /* field_inverse_mod_ord */ - ec_GFp_simple_blind_coordinates + ec_GFp_simple_blind_coordinates, + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c index 6155b54..ecae568 100644 --- a/crypto/ec/ecp_nistp224.c +++ b/crypto/ec/ecp_nistp224.c @@ -292,7 +292,10 @@ const EC_METHOD *EC_GFp_nistp224_method(void) 0, /* keyfinish */ ecdh_simple_compute_key, 0, /* field_inverse_mod_ord */ - 0 /* blind_coordinates */ + 0, /* blind_coordinates */ + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; @@ -1393,7 +1396,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r, int j; unsigned i; int mixed = 0; - BN_CTX *new_ctx = NULL; BIGNUM *x, *y, *z, *tmp_scalar; felem_bytearray g_secret; felem_bytearray *secrets = NULL; @@ -1410,9 +1412,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r, const EC_POINT *p = NULL; const BIGNUM *p_scalar = NULL; - if (ctx == NULL) - if ((ctx = new_ctx = BN_CTX_new()) == NULL) - return 0; BN_CTX_start(ctx); x = BN_CTX_get(ctx); y = BN_CTX_get(ctx); @@ -1575,7 +1574,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r, err: BN_CTX_end(ctx); EC_POINT_free(generator); - BN_CTX_free(new_ctx); OPENSSL_free(secrets); OPENSSL_free(pre_comp); OPENSSL_free(tmp_felems); diff --git a/crypto/ec/ecp_nistp256.c b/crypto/ec/ecp_nistp256.c index 00fcfd5..22f172b 100644 --- a/crypto/ec/ecp_nistp256.c +++ b/crypto/ec/ecp_nistp256.c @@ -1821,7 +1821,12 @@ const EC_METHOD *EC_GFp_nistp256_method(void) ec_key_simple_generate_public_key, 0, /* keycopy */ 0, /* keyfinish */ - ecdh_simple_compute_key + ecdh_simple_compute_key, + 0, /* field_inverse_mod_ord */ + 0, /* blind_coordinates */ + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; @@ -2013,7 +2018,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, int ret = 0; int j; int mixed = 0; - BN_CTX *new_ctx = NULL; BIGNUM *x, *y, *z, *tmp_scalar; felem_bytearray g_secret; felem_bytearray *secrets = NULL; @@ -2031,9 +2035,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, const EC_POINT *p = NULL; const BIGNUM *p_scalar = NULL; - if (ctx == NULL) - if ((ctx = new_ctx = BN_CTX_new()) == NULL) - return 0; BN_CTX_start(ctx); x = BN_CTX_get(ctx); y = BN_CTX_get(ctx); @@ -2202,7 +2203,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, err: BN_CTX_end(ctx); EC_POINT_free(generator); - BN_CTX_free(new_ctx); OPENSSL_free(secrets); OPENSSL_free(pre_comp); OPENSSL_free(tmp_smallfelems); diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c index 4e6c0f9..06945b5 100644 --- a/crypto/ec/ecp_nistp521.c +++ b/crypto/ec/ecp_nistp521.c @@ -1660,7 +1660,10 @@ const EC_METHOD *EC_GFp_nistp521_method(void) 0, /* keyfinish */ ecdh_simple_compute_key, 0, /* field_inverse_mod_ord */ - 0 /* blind_coordinates */ + 0, /* blind_coordinates */ + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; @@ -1852,7 +1855,6 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r, int ret = 0; int j; int mixed = 0; - BN_CTX *new_ctx = NULL; BIGNUM *x, *y, *z, *tmp_scalar; felem_bytearray g_secret; felem_bytearray *secrets = NULL; @@ -1869,9 +1871,6 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r, const EC_POINT *p = NULL; const BIGNUM *p_scalar = NULL; - if (ctx == NULL) - if ((ctx = new_ctx = BN_CTX_new()) == NULL) - return 0; BN_CTX_start(ctx); x = BN_CTX_get(ctx); y = BN_CTX_get(ctx); @@ -2038,7 +2037,6 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r, err: BN_CTX_end(ctx); EC_POINT_free(generator); - BN_CTX_free(new_ctx); OPENSSL_free(secrets); OPENSSL_free(pre_comp); OPENSSL_free(tmp_felems); diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c index 045c2e7..4b5fc62 100644 --- a/crypto/ec/ecp_nistz256.c +++ b/crypto/ec/ecp_nistz256.c @@ -1139,12 +1139,10 @@ __owur static int ecp_nistz256_points_mul(const EC_GROUP *group, const BIGNUM *scalars[], BN_CTX *ctx) { int i = 0, ret = 0, no_precomp_for_generator = 0, p_is_infinity = 0; - size_t j; unsigned char p_str[33] = { 0 }; const PRECOMP256_ROW *preComputedTable = NULL; const NISTZ256_PRE_COMP *pre_comp = NULL; const EC_POINT *generator = NULL; - BN_CTX *new_ctx = NULL; const BIGNUM **new_scalars = NULL; const EC_POINT **new_points = NULL; unsigned int idx = 0; @@ -1162,27 +1160,6 @@ __owur static int ecp_nistz256_points_mul(const EC_GROUP *group, return 0; } - if (!ec_point_is_compat(r, group)) { - ECerr(EC_F_ECP_NISTZ256_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS); - return 0; - } - - if ((scalar == NULL) && (num == 0)) - return EC_POINT_set_to_infinity(group, r); - - for (j = 0; j < num; j++) { - if (!ec_point_is_compat(points[j], group)) { - ECerr(EC_F_ECP_NISTZ256_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS); - return 0; - } - } - - if (ctx == NULL) { - ctx = new_ctx = BN_CTX_new(); - if (ctx == NULL) - goto err; - } - BN_CTX_start(ctx); if (scalar) { @@ -1380,7 +1357,6 @@ __owur static int ecp_nistz256_points_mul(const EC_GROUP *group, err: if (ctx) BN_CTX_end(ctx); - BN_CTX_free(new_ctx); OPENSSL_free(new_points); OPENSSL_free(new_scalars); return ret; @@ -1731,7 +1707,10 @@ const EC_METHOD *EC_GFp_nistz256_method(void) 0, /* keyfinish */ ecdh_simple_compute_key, ecp_nistz256_inv_mod_ord, /* can be #define-d NULL */ - 0 /* blind_coordinates */ + 0, /* blind_coordinates */ + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index e0e4996..768922a 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -64,7 +64,10 @@ const EC_METHOD *EC_GFp_simple_method(void) 0, /* keyfinish */ ecdh_simple_compute_key, 0, /* field_inverse_mod_ord */ - ec_GFp_simple_blind_coordinates + ec_GFp_simple_blind_coordinates, + 0, /* ladder_pre */ + 0, /* ladder_step */ + 0 /* ladder_post */ }; return &ret; @@ -1418,4 +1421,3 @@ int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX_end(ctx); return ret; } - diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt index 007560a..3e2bc69 100644 --- a/crypto/err/openssl.txt +++ b/crypto/err/openssl.txt @@ -521,8 +521,11 @@ EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY:208:ec_GF2m_montgomery_point_multiply EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT:159:\ ec_GF2m_simple_group_check_discriminant EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE:195:ec_GF2m_simple_group_set_curve +EC_F_EC_GF2M_SIMPLE_LADDER_POST:285:ec_GF2m_simple_ladder_post +EC_F_EC_GF2M_SIMPLE_LADDER_PRE:288:ec_GF2m_simple_ladder_pre EC_F_EC_GF2M_SIMPLE_OCT2POINT:160:ec_GF2m_simple_oct2point EC_F_EC_GF2M_SIMPLE_POINT2OCT:161:ec_GF2m_simple_point2oct +EC_F_EC_GF2M_SIMPLE_POINTS_MUL:289:ec_GF2m_simple_points_mul EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES:162:\ ec_GF2m_simple_point_get_affine_coordinates EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES:163:\ @@ -601,6 +604,7 @@ EC_F_EC_KEY_SIMPLE_PRIV2OCT:260:ec_key_simple_priv2oct EC_F_EC_PKEY_CHECK:273:ec_pkey_check EC_F_EC_PKEY_PARAM_CHECK:274:ec_pkey_param_check EC_F_EC_POINTS_MAKE_AFFINE:136:EC_POINTs_make_affine +EC_F_EC_POINTS_MUL:290:EC_POINTs_mul EC_F_EC_POINT_ADD:112:EC_POINT_add EC_F_EC_POINT_BN2POINT:280:EC_POINT_bn2point EC_F_EC_POINT_CMP:113:EC_POINT_cmp @@ -630,6 +634,7 @@ EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP:126:\ EC_POINT_set_Jprojective_coordinates_GFp EC_F_EC_POINT_SET_TO_INFINITY:127:EC_POINT_set_to_infinity EC_F_EC_PRE_COMP_NEW:196:ec_pre_comp_new +EC_F_EC_SCALAR_MUL_LADDER:284:ec_scalar_mul_ladder EC_F_EC_WNAF_MUL:187:ec_wNAF_mul EC_F_EC_WNAF_PRECOMPUTE_MULT:188:ec_wNAF_precompute_mult EC_F_I2D_ECPARAMETERS:190:i2d_ECParameters @@ -2130,6 +2135,9 @@ EC_R_INVALID_PRIVATE_KEY:123:invalid private key EC_R_INVALID_TRINOMIAL_BASIS:137:invalid trinomial basis EC_R_KDF_PARAMETER_ERROR:148:kdf parameter error EC_R_KEYS_NOT_SET:140:keys not set +EC_R_LADDER_POST_FAILURE:136:ladder post failure +EC_R_LADDER_PRE_FAILURE:153:ladder pre failure +EC_R_LADDER_STEP_FAILURE:162:ladder step failure EC_R_MISSING_PARAMETERS:124:missing parameters EC_R_MISSING_PRIVATE_KEY:125:missing private key EC_R_NEED_NEW_SETUP_VALUES:157:need new setup values @@ -2144,12 +2152,14 @@ EC_R_PEER_KEY_ERROR:149:peer key error EC_R_PKPARAMETERS2GROUP_FAILURE:127:pkparameters2group failure EC_R_POINT_ARITHMETIC_FAILURE:155:point arithmetic failure EC_R_POINT_AT_INFINITY:106:point at infinity +EC_R_POINT_COORDINATES_BLIND_FAILURE:163:point coordinates blind failure EC_R_POINT_IS_NOT_ON_CURVE:107:point is not on curve EC_R_RANDOM_NUMBER_GENERATION_FAILED:158:random number generation failed EC_R_SHARED_INFO_ERROR:150:shared info error EC_R_SLOT_FULL:108:slot full EC_R_UNDEFINED_GENERATOR:113:undefined generator EC_R_UNDEFINED_ORDER:128:undefined order +EC_R_UNKNOWN_COFACTOR:164:unknown cofactor EC_R_UNKNOWN_GROUP:129:unknown group EC_R_UNKNOWN_ORDER:114:unknown order EC_R_UNSUPPORTED_FIELD:131:unsupported field diff --git a/crypto/include/internal/sm2err.h b/crypto/include/internal/sm2err.h index f32d26c..9a7e2b6 100644 --- a/crypto/include/internal/sm2err.h +++ b/crypto/include/internal/sm2err.h @@ -15,6 +15,9 @@ # ifndef OPENSSL_NO_SM2 +# ifdef __cplusplus +extern "C" +# endif int ERR_load_SM2_strings(void); /* diff --git a/include/internal/dsoerr.h b/include/internal/dsoerr.h index ac6bdcd..a54a185 100644 --- a/include/internal/dsoerr.h +++ b/include/internal/dsoerr.h @@ -15,6 +15,9 @@ # ifndef OPENSSL_NO_DSO +# ifdef __cplusplus +extern "C" +# endif int ERR_load_DSO_strings(void); /* diff --git a/include/openssl/ecerr.h b/include/openssl/ecerr.h index 8db7967..967d6e0 100644 --- a/include/openssl/ecerr.h +++ b/include/openssl/ecerr.h @@ -64,8 +64,11 @@ int ERR_load_EC_strings(void); # define EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY 208 # define EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT 159 # define EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE 195 +# define EC_F_EC_GF2M_SIMPLE_LADDER_POST 285 +# define EC_F_EC_GF2M_SIMPLE_LADDER_PRE 288 # define EC_F_EC_GF2M_SIMPLE_OCT2POINT 160 # define EC_F_EC_GF2M_SIMPLE_POINT2OCT 161 +# define EC_F_EC_GF2M_SIMPLE_POINTS_MUL 289 # define EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES 162 # define EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES 163 # define EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES 164 @@ -133,6 +136,7 @@ int ERR_load_EC_strings(void); # define EC_F_EC_PKEY_CHECK 273 # define EC_F_EC_PKEY_PARAM_CHECK 274 # define EC_F_EC_POINTS_MAKE_AFFINE 136 +# define EC_F_EC_POINTS_MUL 290 # define EC_F_EC_POINT_ADD 112 # define EC_F_EC_POINT_BN2POINT 280 # define EC_F_EC_POINT_CMP 113 @@ -156,6 +160,7 @@ int ERR_load_EC_strings(void); # define EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP 126 # define EC_F_EC_POINT_SET_TO_INFINITY 127 # define EC_F_EC_PRE_COMP_NEW 196 +# define EC_F_EC_SCALAR_MUL_LADDER 284 # define EC_F_EC_WNAF_MUL 187 # define EC_F_EC_WNAF_PRECOMPUTE_MULT 188 # define EC_F_I2D_ECPARAMETERS 190 @@ -183,12 +188,6 @@ int ERR_load_EC_strings(void); # define EC_F_PKEY_EC_KEYGEN 199 # define EC_F_PKEY_EC_PARAMGEN 219 # define EC_F_PKEY_EC_SIGN 218 -# define EC_F_PKEY_SM2_CTRL 284 -# define EC_F_PKEY_SM2_CTRL_STR 285 -# define EC_F_PKEY_SM2_INIT 287 -# define EC_F_PKEY_SM2_KEYGEN 288 -# define EC_F_PKEY_SM2_PARAMGEN 289 -# define EC_F_PKEY_SM2_SIGN 290 # define EC_F_VALIDATE_ECX_DERIVE 278 /* @@ -228,6 +227,9 @@ int ERR_load_EC_strings(void); # define EC_R_INVALID_TRINOMIAL_BASIS 137 # define EC_R_KDF_PARAMETER_ERROR 148 # define EC_R_KEYS_NOT_SET 140 +# define EC_R_LADDER_POST_FAILURE 136 +# define EC_R_LADDER_PRE_FAILURE 153 +# define EC_R_LADDER_STEP_FAILURE 162 # define EC_R_MISSING_PARAMETERS 124 # define EC_R_MISSING_PRIVATE_KEY 125 # define EC_R_NEED_NEW_SETUP_VALUES 157 @@ -242,12 +244,14 @@ int ERR_load_EC_strings(void); # define EC_R_PKPARAMETERS2GROUP_FAILURE 127 # define EC_R_POINT_ARITHMETIC_FAILURE 155 # define EC_R_POINT_AT_INFINITY 106 +# define EC_R_POINT_COORDINATES_BLIND_FAILURE 163 # define EC_R_POINT_IS_NOT_ON_CURVE 107 # define EC_R_RANDOM_NUMBER_GENERATION_FAILED 158 # define EC_R_SHARED_INFO_ERROR 150 # define EC_R_SLOT_FULL 108 # define EC_R_UNDEFINED_GENERATOR 113 # define EC_R_UNDEFINED_ORDER 128 +# define EC_R_UNKNOWN_COFACTOR 164 # define EC_R_UNKNOWN_GROUP 129 # define EC_R_UNKNOWN_ORDER 114 # define EC_R_UNSUPPORTED_FIELD 131 diff --git a/test/ectest.c b/test/ectest.c index ead23d7..2945cd7 100644 --- a/test/ectest.c +++ b/test/ectest.c @@ -31,6 +31,7 @@ static int group_order_tests(EC_GROUP *group) { BIGNUM *n1 = NULL, *n2 = NULL, *order = NULL; EC_POINT *P = NULL, *Q = NULL, *R = NULL, *S = NULL; + const EC_POINT *G = NULL; BN_CTX *ctx = NULL; int i = 0, r = 0; @@ -38,6 +39,7 @@ static int group_order_tests(EC_GROUP *group) || !TEST_ptr(n2 = BN_new()) || !TEST_ptr(order = BN_new()) || !TEST_ptr(ctx = BN_CTX_new()) + || !TEST_ptr(G = EC_GROUP_get0_generator(group)) || !TEST_ptr(P = EC_POINT_new(group)) || !TEST_ptr(Q = EC_POINT_new(group)) || !TEST_ptr(R = EC_POINT_new(group)) @@ -49,7 +51,15 @@ static int group_order_tests(EC_GROUP *group) || !TEST_true(EC_POINT_is_at_infinity(group, Q)) || !TEST_true(EC_GROUP_precompute_mult(group, ctx)) || !TEST_true(EC_POINT_mul(group, Q, order, NULL, NULL, ctx)) - || !TEST_true(EC_POINT_is_at_infinity(group, Q))) + || !TEST_true(EC_POINT_is_at_infinity(group, Q)) + || !TEST_true(EC_POINT_copy(P, G)) + || !TEST_true(BN_one(n1)) + || !TEST_true(EC_POINT_mul(group, Q, n1, NULL, NULL, ctx)) + || !TEST_int_eq(0, EC_POINT_cmp(group, Q, P, ctx)) + || !TEST_true(BN_sub(n1, order, n1)) + || !TEST_true(EC_POINT_mul(group, Q, n1, NULL, NULL, ctx)) + || !TEST_true(EC_POINT_invert(group, Q, ctx)) + || !TEST_int_eq(0, EC_POINT_cmp(group, Q, P, ctx))) goto err; for (i = 1; i <= 2; i++) { @@ -62,6 +72,7 @@ static int group_order_tests(EC_GROUP *group) * EC_GROUP_precompute_mult has set up precomputation. */ || !TEST_true(EC_POINT_mul(group, P, n1, NULL, NULL, ctx)) + || (i == 1 && !TEST_int_eq(0, EC_POINT_cmp(group, P, G, ctx))) || !TEST_true(BN_one(n1)) /* n1 = 1 - order */ || !TEST_true(BN_sub(n1, n1, order)) _____ openssl-commits mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-commits