From fe2d3975880e6a89702f18ec58881307bf862542 Mon Sep 17 00:00:00 2001 From: Billy Brumley Date: Tue, 24 Apr 2018 16:00:08 +0300 Subject: [PATCH] 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 Reviewed-by: Andy Polyakov Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/6070) --- CHANGES | 4 ++++ crypto/ec/ec_lcl.h | 17 +++++++++++++++++ crypto/ec/ec_mult.c | 4 ++-- crypto/ec/ecdsa_ossl.c | 17 ----------------- doc/man3/EC_POINT_add.pod | 8 +++++--- 5 files changed, 28 insertions(+), 22 deletions(-) diff --git a/CHANGES b/CHANGES index a13183f9e8..08586c09d3 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,10 @@ Changes between 1.1.0h and 1.1.1 [xx XXX xxxx] + *) Remove ECDSA nonce padding: EC_POINT_mul is now responsible for + constant time fixed point multiplication. + [Billy Bob Brumley] + *) Updated CONTRIBUTING [Rich Salz] diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index 413a906883..5b306dbefa 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 *); diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c index 6b5553c9b2..1f34329182 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 2c9e5a88cf..7842851778 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 3c047e1ab0..21abf46b84 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 provides the number of points in the array B to be forced. -EC_POINT_mul calculates the value generator * B + B * B and stores the result in B. The value B may be NULL in which case the result is just B * B. +EC_POINT_mul is a convenient interface to EC_POINTs_mul: it calculates the value generator * B + B * B and stores the result in B. +The value B may be NULL in which case the result is just B * B (variable point multiplication). Alternatively, both B and B may be NULL, and B non-NULL, in which case the result is just generator * B (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 or B) is in the range [0, ec_group_order). -EC_POINTs_mul calculates the value generator * B + B * B + ... + B * B. As for EC_POINT_mul the value -B may be NULL. +EC_POINTs_mul calculates the value generator * B + B * B + ... + B * B. As for EC_POINT_mul the value B may be NULL or B may be zero. +When performing a fixed point multiplication (B is non-NULL and B is 0) or a variable point multiplication (B is NULL and B is 1), the underlying implementation uses a constant time algorithm, when the input scalar (either B or B) 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 for information -- 2.25.1