Make ec_GFp_simple_is_on_curve constant-time.
This function (by way of EC_POINT_is_on_curve) is used by callers in two
places:
- To check the affine result of decoding a point. (This is no longer
necessary because we'll always do it internally, but folks still do
it.)
- To check the Jacobian result of a multiplication as fault protection.
(Tink does this. We should probably do it in the library.)
That function's implementations of affine and Jacobian checks are mostly
constant-time, but branching between the two isn't. Since the difference
is small (2S + 1M vs 2S + 3M) compared to what one would be doing with
an affine point (point multiplication), this probably isn't worth
worrying about. Conservatively do the Jacobian check so folks like Tink
aren't accidentally introducing side channels.
Change-Id: I3140167868e027004906293df547add43ae40552
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/40590
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/ec/ec_test.cc b/crypto/fipsmodule/ec/ec_test.cc
index f7827c5..7ab7f5f 100644
--- a/crypto/fipsmodule/ec/ec_test.cc
+++ b/crypto/fipsmodule/ec/ec_test.cc
@@ -493,9 +493,6 @@
ASSERT_TRUE(key);
ASSERT_TRUE(EC_KEY_generate_key(key.get()));
- EXPECT_TRUE(EC_POINT_is_on_curve(group(), EC_KEY_get0_public_key(key.get()),
- nullptr));
-
// Get the public key's coordinates.
bssl::UniquePtr<BIGNUM> x(BN_new());
ASSERT_TRUE(x);
@@ -533,6 +530,30 @@
EC_KEY_set_public_key_affine_coordinates(key.get(), x.get(), y.get()));
}
+TEST_P(ECCurveTest, IsOnCurve) {
+ bssl::UniquePtr<EC_KEY> key(EC_KEY_new_by_curve_name(GetParam().nid));
+ ASSERT_TRUE(key);
+ ASSERT_TRUE(EC_KEY_generate_key(key.get()));
+
+ // The generated point is on the curve.
+ EXPECT_TRUE(EC_POINT_is_on_curve(group(), EC_KEY_get0_public_key(key.get()),
+ nullptr));
+
+ bssl::UniquePtr<EC_POINT> p(EC_POINT_new(group()));
+ ASSERT_TRUE(p);
+ ASSERT_TRUE(EC_POINT_copy(p.get(), EC_KEY_get0_public_key(key.get())));
+
+ // This should never happen outside of a bug, but |EC_POINT_is_on_curve|
+ // rejects points not on the curve.
+ OPENSSL_memset(&p->raw.X, 0, sizeof(p->raw.X));
+ EXPECT_FALSE(EC_POINT_is_on_curve(group(), p.get(), nullptr));
+
+ // The point at infinity is always on the curve.
+ ASSERT_TRUE(EC_POINT_copy(p.get(), EC_KEY_get0_public_key(key.get())));
+ OPENSSL_memset(&p->raw.Z, 0, sizeof(p->raw.Z));
+ EXPECT_TRUE(EC_POINT_is_on_curve(group(), p.get(), nullptr));
+}
+
TEST_P(ECCurveTest, GenerateFIPS) {
// Generate an EC_KEY.
bssl::UniquePtr<EC_KEY> key(EC_KEY_new_by_curve_name(GetParam().nid));
diff --git a/crypto/fipsmodule/ec/simple.c b/crypto/fipsmodule/ec/simple.c
index 19e9ad5..ce72235 100644
--- a/crypto/fipsmodule/ec/simple.c
+++ b/crypto/fipsmodule/ec/simple.c
@@ -182,10 +182,6 @@
int ec_GFp_simple_is_on_curve(const EC_GROUP *group,
const EC_RAW_POINT *point) {
- if (ec_GFp_simple_is_at_infinity(group, point)) {
- return 1;
- }
-
// We have a curve defined by a Weierstrass equation
// y^2 = x^3 + a*x + b.
// The point to consider is given in Jacobian projective coordinates
@@ -194,6 +190,9 @@
// into
// Y^2 = X^3 + a*X*Z^4 + b*Z^6.
// To test this, we add up the right-hand side in 'rh'.
+ //
+ // This function may be used when double-checking the secret result of a point
+ // multiplication, so we proceed in constant-time.
void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
const EC_FELEM *b) = group->meth->felem_mul;
@@ -205,37 +204,37 @@
felem_sqr(group, &rh, &point->X);
EC_FELEM tmp, Z4, Z6;
- if (!ec_felem_equal(group, &point->Z, &group->one)) {
- felem_sqr(group, &tmp, &point->Z);
- felem_sqr(group, &Z4, &tmp);
- felem_mul(group, &Z6, &Z4, &tmp);
+ felem_sqr(group, &tmp, &point->Z);
+ felem_sqr(group, &Z4, &tmp);
+ felem_mul(group, &Z6, &Z4, &tmp);
- // rh := (rh + a*Z^4)*X
- if (group->a_is_minus3) {
- ec_felem_add(group, &tmp, &Z4, &Z4);
- ec_felem_add(group, &tmp, &tmp, &Z4);
- ec_felem_sub(group, &rh, &rh, &tmp);
- felem_mul(group, &rh, &rh, &point->X);
- } else {
- felem_mul(group, &tmp, &Z4, &group->a);
- ec_felem_add(group, &rh, &rh, &tmp);
- felem_mul(group, &rh, &rh, &point->X);
- }
-
- // rh := rh + b*Z^6
- felem_mul(group, &tmp, &group->b, &Z6);
- ec_felem_add(group, &rh, &rh, &tmp);
+ // rh := rh + a*Z^4
+ if (group->a_is_minus3) {
+ ec_felem_add(group, &tmp, &Z4, &Z4);
+ ec_felem_add(group, &tmp, &tmp, &Z4);
+ ec_felem_sub(group, &rh, &rh, &tmp);
} else {
- // rh := (rh + a)*X
- ec_felem_add(group, &rh, &rh, &group->a);
- felem_mul(group, &rh, &rh, &point->X);
- // rh := rh + b
- ec_felem_add(group, &rh, &rh, &group->b);
+ felem_mul(group, &tmp, &Z4, &group->a);
+ ec_felem_add(group, &rh, &rh, &tmp);
}
+ // rh := (rh + a*Z^4)*X
+ felem_mul(group, &rh, &rh, &point->X);
+
+ // rh := rh + b*Z^6
+ felem_mul(group, &tmp, &group->b, &Z6);
+ ec_felem_add(group, &rh, &rh, &tmp);
+
// 'lh' := Y^2
felem_sqr(group, &tmp, &point->Y);
- return ec_felem_equal(group, &tmp, &rh);
+
+ ec_felem_sub(group, &tmp, &tmp, &rh);
+ BN_ULONG not_equal = ec_felem_non_zero_mask(group, &tmp);
+
+ // If Z = 0, the point is infinity, which is always on the curve.
+ BN_ULONG not_infinity = ec_felem_non_zero_mask(group, &point->Z);
+
+ return 1 & ~(not_infinity & not_equal);
}
int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_RAW_POINT *a,
