Push BIGNUM out of the cmp_x_coordinate interface. This removes the failure cases for cmp_x_coordinate, this clearing our earlier dilemma. Change-Id: I057f705e49b0fb5c3fc9616ee8962a3024097b24 Reviewed-on: https://boringssl-review.googlesource.com/c/33065 Reviewed-by: Adam Langley <agl@google.com> Commit-Queue: David Benjamin <davidben@google.com> CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c index ba101fe..5d25550 100644 --- a/crypto/fipsmodule/ec/ec.c +++ b/crypto/fipsmodule/ec/ec.c
@@ -919,12 +919,21 @@ return 1; } -int ec_cmp_x_coordinate(int *out_result, const EC_GROUP *group, - const EC_POINT *p, const BIGNUM *r, BN_CTX *ctx) { - return group->meth->cmp_x_coordinate(out_result, group, p, r, ctx); +int ec_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p, + const EC_SCALAR *r) { + return group->meth->cmp_x_coordinate(group, p, r); } -int ec_field_element_to_scalar(const EC_GROUP *group, BIGNUM *r) { +int ec_get_x_coordinate_as_scalar(const EC_GROUP *group, EC_SCALAR *out, + const EC_RAW_POINT *p) { + EC_FELEM x; + // For simplicity, in case of width mismatches between |group->field| and + // |group->order|, zero any untouched words in |x|. + OPENSSL_memset(&x, 0, sizeof(x)); + if (!group->meth->point_get_affine_coordinates(group, p, &x, NULL)) { + return 0; + } + // We must have p < 2×order, assuming p is not tiny (p >= 17). Thus rather we // can reduce by performing at most one subtraction. // @@ -940,19 +949,14 @@ // // Additionally, one can manually check this property for built-in curves. It // is enforced for legacy custom curves in |EC_GROUP_set_generator|. - // - // TODO(davidben): Introduce |EC_FIELD_ELEMENT|, make this a function from - // |EC_FIELD_ELEMENT| to |EC_SCALAR|, and cut out the |BIGNUM|. Does this need - // to be constant-time for signing? |r| is the x-coordinate for kG, which is - // public unless k was rerolled because |s| was zero. - assert(!BN_is_negative(r)); - assert(BN_cmp(r, &group->field) < 0); - if (BN_cmp(r, &group->order) >= 0 && - !BN_sub(r, r, &group->order)) { - return 0; - } - assert(!BN_is_negative(r)); - assert(BN_cmp(r, &group->order) < 0); + + // The above does not guarantee |group->field| is not one word larger than + // |group->order|, so read one extra carry word. + BN_ULONG carry = group->order.width < EC_MAX_SCALAR_WORDS + ? x.words[group->order.width] + : 0; + bn_reduce_once(out->words, x.words, carry, group->order.d, + group->order.width); return 1; }
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h index 4afaef9..d604f4d 100644 --- a/crypto/fipsmodule/ec/internal.h +++ b/crypto/fipsmodule/ec/internal.h
@@ -186,10 +186,10 @@ const EC_SCALAR *in); // cmp_x_coordinate compares the x (affine) coordinate of |p|, mod the group - // order, with |r|. On error it returns zero. Otherwise it sets |*out_result| - // to one iff the values match. - int (*cmp_x_coordinate)(int *out_result, const EC_GROUP *group, - const EC_POINT *p, const BIGNUM *r, BN_CTX *ctx); + // order, with |r|. It returns one if the values match and zero if |p| is the + // point at infinity of the values do not match. + int (*cmp_x_coordinate)(const EC_GROUP *group, const EC_RAW_POINT *p, + const EC_SCALAR *r); } /* EC_METHOD */; const EC_METHOD *EC_GFp_mont_method(void); @@ -273,6 +273,14 @@ int ec_random_nonzero_scalar(const EC_GROUP *group, EC_SCALAR *out, const uint8_t additional_data[32]); +// ec_scalar_equal_vartime returns one if |a| and |b| are equal and zero +// otherwise. Both values are treated as public. +int ec_scalar_equal_vartime(const EC_GROUP *group, const EC_SCALAR *a, + const EC_SCALAR *b); + +// ec_scalar_is_zero returns one if |a| is zero and zero otherwise. +int ec_scalar_is_zero(const EC_GROUP *group, const EC_SCALAR *a); + // ec_scalar_add sets |r| to |a| + |b|. void ec_scalar_add(const EC_GROUP *group, EC_SCALAR *r, const EC_SCALAR *a, const EC_SCALAR *b); @@ -315,11 +323,17 @@ const EC_GROUP *group, EC_POINT *r, const EC_SCALAR *g_scalar, const EC_POINT *p, const EC_SCALAR *p_scalar, BN_CTX *ctx); -// ec_cmp_x_coordinate compares the x (affine) coordinate of |p| with |r|. It -// returns zero on error. Otherwise it sets |*out_result| to one iff the values -// match. -int ec_cmp_x_coordinate(int *out_result, const EC_GROUP *group, - const EC_POINT *p, const BIGNUM *r, BN_CTX *ctx); +// ec_cmp_x_coordinate compares the x (affine) coordinate of |p|, mod the group +// order, with |r|. It returns one if the values match and zero if |p| is the +// point at infinity of the values do not match. +int ec_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p, + const EC_SCALAR *r); + +// ec_get_x_coordinate_as_scalar sets |*out| to |p|'s x-coordinate, modulo +// |group->order|. It returns one on success and zero if |p| is the point at +// infinity. +int ec_get_x_coordinate_as_scalar(const EC_GROUP *group, EC_SCALAR *out, + const EC_RAW_POINT *p); // ec_field_element_to_scalar reduces |r| modulo |group->order|. |r| must // previously have been reduced modulo |group->field|. @@ -371,12 +385,8 @@ int ec_GFp_simple_mont_inv_mod_ord_vartime(const EC_GROUP *group, EC_SCALAR *r, const EC_SCALAR *a); -// ec_GFp_simple_cmp_x_coordinate compares the x (affine) coordinate of |p|, mod -// the group order, with |r|. It returns zero on error. Otherwise it sets -// |*out_result| to one iff the values match. -int ec_GFp_simple_cmp_x_coordinate(int *out_result, const EC_GROUP *group, - const EC_POINT *p, const BIGNUM *r, - BN_CTX *ctx); +int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p, + const EC_SCALAR *r); // method functions in montgomery.c int ec_GFp_mont_group_init(EC_GROUP *);
diff --git a/crypto/fipsmodule/ec/p256-x86_64.c b/crypto/fipsmodule/ec/p256-x86_64.c index e7f4909..3053e2d 100644 --- a/crypto/fipsmodule/ec/p256-x86_64.c +++ b/crypto/fipsmodule/ec/p256-x86_64.c
@@ -600,18 +600,10 @@ return 1; } -static int ecp_nistz256_cmp_x_coordinate(int *out_result, const EC_GROUP *group, - const EC_POINT *p, const BIGNUM *r, - BN_CTX *ctx) { - *out_result = 0; - - if (ec_GFp_simple_is_at_infinity(group, &p->raw)) { - OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); - return 0; - } - - BN_ULONG r_words[P256_LIMBS]; - if (!bn_copy_words(r_words, P256_LIMBS, r)) { +static int ecp_nistz256_cmp_x_coordinate(const EC_GROUP *group, + const EC_RAW_POINT *p, + const EC_SCALAR *r) { + if (ec_GFp_simple_is_at_infinity(group, p)) { return 0; } @@ -619,12 +611,11 @@ // r*Z^2. Note that X and Z are represented in Montgomery form, while r is // not. BN_ULONG r_Z2[P256_LIMBS], Z2_mont[P256_LIMBS], X[P256_LIMBS]; - ecp_nistz256_mul_mont(Z2_mont, p->raw.Z.words, p->raw.Z.words); - ecp_nistz256_mul_mont(r_Z2, r_words, Z2_mont); - ecp_nistz256_from_mont(X, p->raw.X.words); + ecp_nistz256_mul_mont(Z2_mont, p->Z.words, p->Z.words); + ecp_nistz256_mul_mont(r_Z2, r->words, Z2_mont); + ecp_nistz256_from_mont(X, p->X.words); if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) { - *out_result = 1; return 1; } @@ -639,18 +630,16 @@ TOBN(0x0c46353d, 0x039cdaae), TOBN(0x43190553, 0x58e8617b), TOBN(0x00000000, 0x00000000), TOBN(0x00000000, 0x00000000)}; - if (bn_less_than_words(r_words, P_MINUS_ORDER, P256_LIMBS)) { - // We can add in-place, ignoring the carry, because: r + group_order < p < - // 2^256 - bn_add_words(r_words, r_words, P256_ORDER, P256_LIMBS); - ecp_nistz256_mul_mont(r_Z2, r_words, Z2_mont); + if (bn_less_than_words(r->words, P_MINUS_ORDER, P256_LIMBS)) { + // We can ignore the carry because: r + group_order < p < 2^256. + bn_add_words(r_Z2, r->words, P256_ORDER, P256_LIMBS); + ecp_nistz256_mul_mont(r_Z2, r_Z2, Z2_mont); if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) { - *out_result = 1; return 1; } } - return 1; + return 0; } DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_nistz256_method) {
diff --git a/crypto/fipsmodule/ec/scalar.c b/crypto/fipsmodule/ec/scalar.c index 88678a9..35e3765 100644 --- a/crypto/fipsmodule/ec/scalar.c +++ b/crypto/fipsmodule/ec/scalar.c
@@ -18,6 +18,7 @@ #include "internal.h" #include "../bn/internal.h" +#include "../../internal.h" int ec_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out, @@ -30,6 +31,20 @@ return 1; } +int ec_scalar_equal_vartime(const EC_GROUP *group, const EC_SCALAR *a, + const EC_SCALAR *b) { + return OPENSSL_memcmp(a->words, b->words, + group->order.width * sizeof(BN_ULONG)) == 0; +} + +int ec_scalar_is_zero(const EC_GROUP *group, const EC_SCALAR *a) { + BN_ULONG mask = 0; + for (int i = 0; i < group->order.width; i++) { + mask |= a->words[i]; + } + return mask == 0; +} + int ec_random_nonzero_scalar(const EC_GROUP *group, EC_SCALAR *out, const uint8_t additional_data[32]) { return bn_rand_range_words(out->words, 1, group->order.d, group->order.width,
diff --git a/crypto/fipsmodule/ec/simple.c b/crypto/fipsmodule/ec/simple.c index 8b862ff..c418c4e 100644 --- a/crypto/fipsmodule/ec/simple.c +++ b/crypto/fipsmodule/ec/simple.c
@@ -366,36 +366,15 @@ return 1; } -// Compares the x (affine) coordinate of the point p with x. -// Return 1 on success 0 otherwise -int ec_GFp_simple_cmp_x_coordinate(int *out_result, const EC_GROUP *group, - const EC_POINT *p, const BIGNUM *r, - BN_CTX *ctx) { - *out_result = 0; - int ret = 0; - BN_CTX_start(ctx); - - BIGNUM *X = BN_CTX_get(ctx); - if (X == NULL) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); - goto out; +int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p, + const EC_SCALAR *r) { + if (ec_GFp_simple_is_at_infinity(group, p)) { + // |ec_get_x_coordinate_as_scalar| will check this internally, but this way + // we do not push to the error queue. + return 0; } - if (!EC_POINT_get_affine_coordinates_GFp(group, p, X, NULL, ctx)) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); - goto out; - } - - if (!ec_field_element_to_scalar(group, X)) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); - goto out; - } - - // The signature is correct iff |X| is equal to |r|. - *out_result = (BN_ucmp(X, r) == 0); - ret = 1; - -out: - BN_CTX_end(ctx); - return ret; + EC_SCALAR x; + return ec_get_x_coordinate_as_scalar(group, &x, p) && + ec_scalar_equal_vartime(group, &x, r); }
diff --git a/crypto/fipsmodule/ecdsa/ecdsa.c b/crypto/fipsmodule/ecdsa/ecdsa.c index 80371c3..96f9dc5 100644 --- a/crypto/fipsmodule/ecdsa/ecdsa.c +++ b/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -152,21 +152,13 @@ return 0; } - BN_CTX *ctx = BN_CTX_new(); - if (!ctx) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); - return 0; - } - int ret = 0; - EC_POINT *point = NULL; - EC_SCALAR r, s, u1, u2, s_inv_mont, m; if (BN_is_zero(sig->r) || !ec_bignum_to_scalar(group, &r, sig->r) || BN_is_zero(sig->s) || !ec_bignum_to_scalar(group, &s, sig->s)) { OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE); - goto err; + return 0; } // s_inv_mont = s^-1 in the Montgomery domain. This is @@ -181,7 +173,13 @@ ec_scalar_mul_montgomery(group, &u1, &m, &s_inv_mont); ec_scalar_mul_montgomery(group, &u2, &r, &s_inv_mont); - point = EC_POINT_new(group); + BN_CTX *ctx = BN_CTX_new(); + if (!ctx) { + OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); + return 0; + } + int ret = 0; + EC_POINT *point = EC_POINT_new(group); if (point == NULL) { OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); goto err; @@ -191,13 +189,7 @@ goto err; } - int match; - if (!ec_cmp_x_coordinate(&match, group, point, sig->r, ctx)) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); - goto err; - } - - if (!match) { + if (!ec_cmp_x_coordinate(group, &point->raw, &r)) { OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE); goto err; } @@ -211,29 +203,23 @@ } static int ecdsa_sign_setup(const EC_KEY *eckey, BN_CTX *ctx, - EC_SCALAR *out_kinv_mont, BIGNUM **rp, + EC_SCALAR *out_kinv_mont, EC_SCALAR *out_r, const uint8_t *digest, size_t digest_len, const EC_SCALAR *priv_key) { - EC_POINT *tmp_point = NULL; - int ret = 0; - EC_SCALAR k; - BIGNUM *r = BN_new(); // this value is later returned in *rp - if (r == NULL) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); - goto err; - } - const EC_GROUP *group = EC_KEY_get0_group(eckey); - const BIGNUM *order = EC_GROUP_get0_order(group); - tmp_point = EC_POINT_new(group); - if (tmp_point == NULL) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); - goto err; - } - // Check that the size of the group order is FIPS compliant (FIPS 186-4 // B.5.2). + const EC_GROUP *group = EC_KEY_get0_group(eckey); + const BIGNUM *order = EC_GROUP_get0_order(group); if (BN_num_bits(order) < 160) { OPENSSL_PUT_ERROR(ECDSA, EC_R_INVALID_GROUP_ORDER); + return 0; + } + + int ret = 0; + EC_SCALAR k; + EC_POINT *tmp_point = EC_POINT_new(group); + if (tmp_point == NULL) { + OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); goto err; } @@ -268,24 +254,15 @@ // Compute r, the x-coordinate of generator * k. if (!ec_point_mul_scalar(group, tmp_point, &k, NULL, NULL, ctx) || - !EC_POINT_get_affine_coordinates_GFp(group, tmp_point, r, NULL, - ctx)) { + !ec_get_x_coordinate_as_scalar(group, out_r, &tmp_point->raw)) { goto err; } + } while (ec_scalar_is_zero(group, out_r)); - if (!ec_field_element_to_scalar(group, r)) { - goto err; - } - } while (BN_is_zero(r)); - - BN_clear_free(*rp); - *rp = r; - r = NULL; ret = 1; err: OPENSSL_cleanse(&k, sizeof(k)); - BN_clear_free(r); EC_POINT_free(tmp_point); return ret; } @@ -316,17 +293,15 @@ digest_to_scalar(group, &m, digest, digest_len); for (;;) { - if (!ecdsa_sign_setup(eckey, ctx, &kinv_mont, &ret->r, digest, digest_len, - priv_key)) { + if (!ecdsa_sign_setup(eckey, ctx, &kinv_mont, &r_mont, digest, digest_len, + priv_key) || + !bn_set_words(ret->r, r_mont.words, order->width)) { goto err; } // Compute priv_key * r (mod order). Note if only one parameter is in the - // Montgomery domain, |scalar_mod_mul_montgomery| will compute the answer in - // the normal domain. - if (!ec_bignum_to_scalar(group, &r_mont, ret->r)) { - goto err; - } + // Montgomery domain, |ec_scalar_mod_mul_montgomery| will compute the answer + // in the normal domain. ec_scalar_to_montgomery(group, &r_mont, &r_mont); ec_scalar_mul_montgomery(group, &s, priv_key, &r_mont);