Add a value barrier when checking for point doubling.
Many of our point addition functions internally check for the doubling
case and branch because the addition formulas are incomplete. This
branch is fine because the multiplication formulas are arranged to not
hit this case. However, we don't want to leak the couple of intermedate
values that determine whether to branch. Previously, we ran into this
with https://boringssl-review.googlesource.com/c/boringssl/+/36465.
This wasn't sufficient. The compiler understands if (a & b) enough to
compile into two branches. Thanks to Moritz Schneider, Nicolas Dutly,
Daniele Lain, Ivan Puddu, and Srdjan Capkun for reporting this!
Fix the leak by adding a value barrier on the final value. As we're also
intentionally leaking the result of otherwise secret data flow, I've
used the constant_time_declassify functions, which feed into our
valgrind-based constant-time validation and double as barriers.
Accordingly, I've also added some CONSTTIME_SECRET markers around the
ECDSA nonce value, so we can check with valgrind the fix worked. The
marker really should be at a lower level, at ec_random_nonzero_scalar or
further (maybe RAND_bytes?), but for now I've just marked the nonce.
To then clear valgrind, add constant_time_declassify in a few other
places, like trying to convert infinity to affine coordinates. (ECDH
deals with secret points, but it is public that the point isn't
infinity.)
Valgrind now says this code is constant-time, at least up to compilation
differences introduced by the annotations. I've also inspected the
compiler output. This seems to be fine, though neither test is quite
satisfying. Ideally we could add annotations in ways that don't
influence compiler output.
Change-Id: Idfc413a75d92514717520404a0f5424903cb4453
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/60225
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
Auto-Submit: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 2195d06..04f2a98 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -1074,8 +1074,10 @@
group->meth->mul_base(group, r, scalar);
// Check the result is on the curve to defend against fault attacks or bugs.
- // This has negligible cost compared to the multiplication.
- if (!ec_GFp_simple_is_on_curve(group, r)) {
+ // This has negligible cost compared to the multiplication. This can only
+ // happen on bug or CPU fault, so it okay to leak this. The alternative would
+ // be to proceed with bad data.
+ if (!constant_time_declassify_int(ec_GFp_simple_is_on_curve(group, r))) {
OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
return 0;
}
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c
index eeaee64..78e0507 100644
--- a/crypto/fipsmodule/ec/ec_montgomery.c
+++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -177,7 +177,8 @@
static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group,
const EC_JACOBIAN *point,
EC_FELEM *x, EC_FELEM *y) {
- if (ec_GFp_simple_is_at_infinity(group, point)) {
+ if (constant_time_declassify_int(
+ ec_GFp_simple_is_at_infinity(group, point))) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
return 0;
}
@@ -317,7 +318,7 @@
// This case will never occur in the constant-time |ec_GFp_mont_mul|.
BN_ULONG is_nontrivial_double = ~xneq & ~yneq & z1nz & z2nz;
- if (is_nontrivial_double) {
+ if (constant_time_declassify_w(is_nontrivial_double)) {
ec_GFp_mont_dbl(group, out, a);
return;
}
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 8532026..bb41815 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -479,7 +479,8 @@
// point_get_affine_coordinates sets |*x| and |*y| to the affine coordinates
// of |p|. Either |x| or |y| may be NULL to omit it. It returns one on success
- // and zero if |p| is the point at infinity.
+ // and zero if |p| is the point at infinity. It leaks whether |p| was the
+ // point at infinity, but otherwise treats |p| as secret.
int (*point_get_affine_coordinates)(const EC_GROUP *, const EC_JACOBIAN *p,
EC_FELEM *x, EC_FELEM *y);
diff --git a/crypto/fipsmodule/ec/p224-64.c b/crypto/fipsmodule/ec/p224-64.c
index ef83b29..b646e82 100644
--- a/crypto/fipsmodule/ec/p224-64.c
+++ b/crypto/fipsmodule/ec/p224-64.c
@@ -734,8 +734,8 @@
// tmp[i] < 2^116 + 2^64 + 8 < 2^117
p224_felem_reduce(ftmp, tmp);
- // the formulae are incorrect if the points are equal
- // so we check for this and do doubling if this happens
+ // The formulae are incorrect if the points are equal, so we check for this
+ // and do doubling if this happens.
x_equal = p224_felem_is_zero(ftmp);
y_equal = p224_felem_is_zero(ftmp3);
z1_is_zero = p224_felem_is_zero(z1);
@@ -743,7 +743,7 @@
// In affine coordinates, (X_1, Y_1) == (X_2, Y_2)
p224_limb is_nontrivial_double =
x_equal & y_equal & (1 - z1_is_zero) & (1 - z2_is_zero);
- if (is_nontrivial_double) {
+ if (constant_time_declassify_w(is_nontrivial_double)) {
p224_point_double(x3, y3, z3, x1, y1, z1);
return;
}
@@ -862,7 +862,8 @@
static int ec_GFp_nistp224_point_get_affine_coordinates(
const EC_GROUP *group, const EC_JACOBIAN *point, EC_FELEM *x,
EC_FELEM *y) {
- if (ec_GFp_simple_is_at_infinity(group, point)) {
+ if (constant_time_declassify_int(
+ ec_GFp_simple_is_at_infinity(group, point))) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
return 0;
}
diff --git a/crypto/fipsmodule/ec/p256-nistz.c b/crypto/fipsmodule/ec/p256-nistz.c
index dfde2f4..85343fd 100644
--- a/crypto/fipsmodule/ec/p256-nistz.c
+++ b/crypto/fipsmodule/ec/p256-nistz.c
@@ -422,7 +422,8 @@
static int ecp_nistz256_get_affine(const EC_GROUP *group,
const EC_JACOBIAN *point, EC_FELEM *x,
EC_FELEM *y) {
- if (ec_GFp_simple_is_at_infinity(group, point)) {
+ if (constant_time_declassify_int(
+ ec_GFp_simple_is_at_infinity(group, point))) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
return 0;
}
diff --git a/crypto/fipsmodule/ec/p256.c b/crypto/fipsmodule/ec/p256.c
index af211be..76e865f 100644
--- a/crypto/fipsmodule/ec/p256.c
+++ b/crypto/fipsmodule/ec/p256.c
@@ -324,7 +324,7 @@
fiat_p256_limb_t is_nontrivial_double = constant_time_is_zero_w(xneq | yneq) &
~constant_time_is_zero_w(z1nz) &
~constant_time_is_zero_w(z2nz);
- if (is_nontrivial_double) {
+ if (constant_time_declassify_w(is_nontrivial_double)) {
fiat_p256_point_double(x3, y3, z3, x1, y1, z1);
return;
}
@@ -416,7 +416,8 @@
static int ec_GFp_nistp256_point_get_affine_coordinates(
const EC_GROUP *group, const EC_JACOBIAN *point, EC_FELEM *x_out,
EC_FELEM *y_out) {
- if (ec_GFp_simple_is_at_infinity(group, point)) {
+ if (constant_time_declassify_int(
+ ec_GFp_simple_is_at_infinity(group, point))) {
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
return 0;
}
diff --git a/crypto/fipsmodule/ecdsa/ecdsa.c b/crypto/fipsmodule/ecdsa/ecdsa.c
index be19540..1be147f 100644
--- a/crypto/fipsmodule/ecdsa/ecdsa.c
+++ b/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -223,7 +223,7 @@
return NULL;
}
- if (ec_scalar_is_zero(group, &r)) {
+ if (constant_time_declassify_int(ec_scalar_is_zero(group, &r))) {
*out_retry = 1;
return NULL;
}
@@ -250,11 +250,13 @@
ec_scalar_inv0_montgomery(group, &tmp, k); // tmp = k^-1 R^2
ec_scalar_from_montgomery(group, &tmp, &tmp); // tmp = k^-1 R
ec_scalar_mul_montgomery(group, &s, &s, &tmp);
- if (ec_scalar_is_zero(group, &s)) {
+ if (constant_time_declassify_int(ec_scalar_is_zero(group, &s))) {
*out_retry = 1;
return NULL;
}
+ CONSTTIME_DECLASSIFY(r.words, sizeof(r.words));
+ CONSTTIME_DECLASSIFY(s.words, sizeof(r.words));
ECDSA_SIG *ret = ECDSA_SIG_new();
if (ret == NULL || //
!bn_set_words(ret->r, r.words, order->width) ||
@@ -347,6 +349,10 @@
goto out;
}
+ // TODO(davidben): Move this inside |ec_random_nonzero_scalar| or lower, so
+ // that all scalars we generate are, by default, secret.
+ CONSTTIME_SECRET(k.words, sizeof(k.words));
+
int retry;
ret = ecdsa_sign_impl(group, &retry, priv_key, &k, digest, digest_len);
if (ret != NULL || !retry) {
