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);
