Make ec_GFp_simple_cmp constant-time.
We need a constant-time point equality for two reasons. First, although
multiplication results are usually public, their Jacobian Z coordinates
may be secret, or at least are not obviously public. Second, more
complex protocols will sometimes manipulate secret points, notably
PMBTokens.
While here I've renamed the inner function to points_equal without the
flipped return value, to be less confusing.
Update-Note: This does mean that we pay a 6M+2S Jacobian comparison
where comparing two publicly affine points should cost no field
operations at all. Code which compares two EC public keys for equality
will be slightly slower. I wouldn't expect this to matter (if you
actually use the public keys, you'll pay much much more) If it does, we
can restore this optimization by keeping better track of affine vs.
Jacobian forms. See https://crbug.com/boringssl/326.
Bug: 326, chromium:1014199
Change-Id: I67c9a56bc9b66f30c0b500a29e8bf90427d89061
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/40665
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 26e094d..e16a379 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -623,7 +623,7 @@
BN_cmp(&a->field, &b->field) != 0 ||
!ec_felem_equal(a, &a->a, &b->a) ||
!ec_felem_equal(a, &a->b, &b->b) ||
- ec_GFp_simple_cmp(a, &a->generator->raw, &b->generator->raw) != 0;
+ !ec_GFp_simple_points_equal(a, &a->generator->raw, &b->generator->raw);
}
const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group) {
@@ -786,7 +786,9 @@
OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
return -1;
}
- return ec_GFp_simple_cmp(group, &a->raw, &b->raw);
+
+ // Note |EC_POINT_cmp| returns zero for equality and non-zero for inequality.
+ return ec_GFp_simple_points_equal(group, &a->raw, &b->raw) ? 0 : 1;
}
int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group,
diff --git a/crypto/fipsmodule/ec/ec_key.c b/crypto/fipsmodule/ec/ec_key.c
index 0d9ce67..cd48c60 100644
--- a/crypto/fipsmodule/ec/ec_key.c
+++ b/crypto/fipsmodule/ec/ec_key.c
@@ -292,10 +292,6 @@
}
int EC_KEY_check_key(const EC_KEY *eckey) {
- int ok = 0;
- BN_CTX *ctx = NULL;
- EC_POINT *point = NULL;
-
if (!eckey || !eckey->group || !eckey->pub_key) {
OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
return 0;
@@ -303,41 +299,31 @@
if (EC_POINT_is_at_infinity(eckey->group, eckey->pub_key)) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
- goto err;
+ return 0;
}
- ctx = BN_CTX_new();
-
- if (ctx == NULL) {
- goto err;
- }
-
- // testing whether the pub_key is on the elliptic curve
- if (!EC_POINT_is_on_curve(eckey->group, eckey->pub_key, ctx)) {
+ // Test whether the public key is on the elliptic curve.
+ if (!EC_POINT_is_on_curve(eckey->group, eckey->pub_key, NULL)) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE);
- goto err;
+ return 0;
}
- // in case the priv_key is present :
- // check if generator * priv_key == pub_key
+
+ // Check the public and private keys match.
if (eckey->priv_key != NULL) {
- point = EC_POINT_new(eckey->group);
- if (point == NULL ||
- !ec_point_mul_scalar_base(eckey->group, &point->raw,
+ EC_RAW_POINT point;
+ if (!ec_point_mul_scalar_base(eckey->group, &point,
&eckey->priv_key->scalar)) {
OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
- goto err;
+ return 0;
}
- if (EC_POINT_cmp(eckey->group, point, eckey->pub_key, ctx) != 0) {
+ if (!ec_GFp_simple_points_equal(eckey->group, &point,
+ &eckey->pub_key->raw)) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_PRIVATE_KEY);
- goto err;
+ return 0;
}
}
- ok = 1;
-err:
- BN_CTX_free(ctx);
- EC_POINT_free(point);
- return ok;
+ return 1;
}
int EC_KEY_check_fips(const EC_KEY *key) {
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index e9a8623..9778efb 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -482,8 +482,8 @@
void ec_GFp_simple_invert(const EC_GROUP *, EC_RAW_POINT *);
int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_RAW_POINT *);
int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_RAW_POINT *);
-int ec_GFp_simple_cmp(const EC_GROUP *, const EC_RAW_POINT *a,
- const EC_RAW_POINT *b);
+int ec_GFp_simple_points_equal(const EC_GROUP *, const EC_RAW_POINT *a,
+ const EC_RAW_POINT *b);
void ec_simple_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
const EC_SCALAR *a);
diff --git a/crypto/fipsmodule/ec/simple.c b/crypto/fipsmodule/ec/simple.c
index ce72235..bd420b8 100644
--- a/crypto/fipsmodule/ec/simple.c
+++ b/crypto/fipsmodule/ec/simple.c
@@ -237,80 +237,51 @@
return 1 & ~(not_infinity & not_equal);
}
-int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_RAW_POINT *a,
- const EC_RAW_POINT *b) {
- // Note this function returns zero if |a| and |b| are equal and 1 if they are
- // not equal.
- if (ec_GFp_simple_is_at_infinity(group, a)) {
- return ec_GFp_simple_is_at_infinity(group, b) ? 0 : 1;
- }
+int ec_GFp_simple_points_equal(const EC_GROUP *group, const EC_RAW_POINT *a,
+ const EC_RAW_POINT *b) {
+ // This function is implemented in constant-time for two reasons. First,
+ // although EC points are usually public, their Jacobian Z coordinates may be
+ // secret, or at least are not obviously public. Second, more complex
+ // protocols will sometimes manipulate secret points.
+ //
+ // This does mean that we pay a 6M+2S Jacobian comparison when comparing two
+ // publicly affine points costs no field operations at all. If needed, we can
+ // restore this optimization by keeping better track of affine vs. Jacobian
+ // forms. See https://crbug.com/boringssl/326.
- if (ec_GFp_simple_is_at_infinity(group, b)) {
- return 1;
- }
-
- int a_Z_is_one = ec_felem_equal(group, &a->Z, &group->one);
- int b_Z_is_one = ec_felem_equal(group, &b->Z, &group->one);
-
- if (a_Z_is_one && b_Z_is_one) {
- return !ec_felem_equal(group, &a->X, &b->X) ||
- !ec_felem_equal(group, &a->Y, &b->Y);
- }
+ // If neither |a| or |b| is infinity, we have to decide whether
+ // (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
+ // or equivalently, whether
+ // (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
const EC_FELEM *b) = group->meth->felem_mul;
void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) =
group->meth->felem_sqr;
- // We have to decide whether
- // (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
- // or equivalently, whether
- // (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
-
EC_FELEM tmp1, tmp2, Za23, Zb23;
- const EC_FELEM *tmp1_, *tmp2_;
- if (!b_Z_is_one) {
- felem_sqr(group, &Zb23, &b->Z);
- felem_mul(group, &tmp1, &a->X, &Zb23);
- tmp1_ = &tmp1;
- } else {
- tmp1_ = &a->X;
- }
- if (!a_Z_is_one) {
- felem_sqr(group, &Za23, &a->Z);
- felem_mul(group, &tmp2, &b->X, &Za23);
- tmp2_ = &tmp2;
- } else {
- tmp2_ = &b->X;
- }
+ felem_sqr(group, &Zb23, &b->Z); // Zb23 = Z_b^2
+ felem_mul(group, &tmp1, &a->X, &Zb23); // tmp1 = X_a * Z_b^2
+ felem_sqr(group, &Za23, &a->Z); // Za23 = Z_a^2
+ felem_mul(group, &tmp2, &b->X, &Za23); // tmp2 = X_b * Z_a^2
+ ec_felem_sub(group, &tmp1, &tmp1, &tmp2);
+ const BN_ULONG x_not_equal = ec_felem_non_zero_mask(group, &tmp1);
- // Compare X_a*Z_b^2 with X_b*Z_a^2.
- if (!ec_felem_equal(group, tmp1_, tmp2_)) {
- return 1; // The points differ.
- }
+ felem_mul(group, &Zb23, &Zb23, &b->Z); // Zb23 = Z_b^3
+ felem_mul(group, &tmp1, &a->Y, &Zb23); // tmp1 = Y_a * Z_b^3
+ felem_mul(group, &Za23, &Za23, &a->Z); // Za23 = Z_a^3
+ felem_mul(group, &tmp2, &b->Y, &Za23); // tmp2 = Y_b * Z_a^3
+ ec_felem_sub(group, &tmp1, &tmp1, &tmp2);
+ const BN_ULONG y_not_equal = ec_felem_non_zero_mask(group, &tmp1);
+ const BN_ULONG x_and_y_equal = ~(x_not_equal | y_not_equal);
- if (!b_Z_is_one) {
- felem_mul(group, &Zb23, &Zb23, &b->Z);
- felem_mul(group, &tmp1, &a->Y, &Zb23);
- // tmp1_ = &tmp1
- } else {
- tmp1_ = &a->Y;
- }
- if (!a_Z_is_one) {
- felem_mul(group, &Za23, &Za23, &a->Z);
- felem_mul(group, &tmp2, &b->Y, &Za23);
- // tmp2_ = &tmp2
- } else {
- tmp2_ = &b->Y;
- }
+ const BN_ULONG a_not_infinity = ec_felem_non_zero_mask(group, &a->Z);
+ const BN_ULONG b_not_infinity = ec_felem_non_zero_mask(group, &b->Z);
+ const BN_ULONG a_and_b_infinity = ~(a_not_infinity | b_not_infinity);
- // Compare Y_a*Z_b^3 with Y_b*Z_a^3.
- if (!ec_felem_equal(group, tmp1_, tmp2_)) {
- return 1; // The points differ.
- }
-
- // The points are equal.
- return 0;
+ const BN_ULONG equal =
+ a_and_b_infinity | (a_not_infinity & b_not_infinity & x_and_y_equal);
+ return equal & 1;
}
int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p,
