Clear some false positives in constant-time validation
These were flagged when patching the PRNG to return data marked secret.
This CL doesn't include that part (I didn't run all tests, and other
tests likely require further annotations), but it does include some of
the declassifications necessary to do that later.
Broadly:
- Whenever we compute public keys from private keys, we must tell
valgrind the public key is now public. (Valgrind does not know
that cryptography works.)
- Whenever we compute signatures from private keys, we must tell
valgrind the signature is now public. (Ditto.)
- Whenever we pass a secret value but check it is fully reduced, we must
tell valgrind the comparison may be leaked. (Valgrind doesn't know
these values are always within range... that we have to check at all
is a consequence of OpenSSL's API and/or defensive coding.)
- Valgrind does not know about the randomizing properties of blinding.
We actually aim to be constant-time without RSA blinding, so that
doesn't need an annotation, but the blinded inversion step in the
process of computing the RSA blinding factor does.
Bug: 676
Change-Id: Ic3a47adddb23a61fe452b9be27b214eec2ea5235
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/65367
Auto-Submit: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
diff --git a/crypto/curve25519/curve25519.c b/crypto/curve25519/curve25519.c
index d1677a6..581d740 100644
--- a/crypto/curve25519/curve25519.c
+++ b/crypto/curve25519/curve25519.c
@@ -1906,6 +1906,8 @@
x25519_sc_reduce(hram);
sc_muladd(out_sig + 32, hram, az, nonce);
+ // The signature is computed from the private key, but is public.
+ CONSTTIME_DECLASSIFY(out_sig, 64);
return 1;
}
@@ -1983,6 +1985,8 @@
ge_p3 A;
x25519_ge_scalarmult_base(&A, az);
ge_p3_tobytes(out_public_key, &A);
+ // The public key is derived from the private key, but it is public.
+ CONSTTIME_DECLASSIFY(out_public_key, 32);
OPENSSL_memcpy(out_private_key, seed, 32);
OPENSSL_memcpy(out_private_key + 32, out_public_key, 32);
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c
index 632771e..7b24d89 100644
--- a/crypto/fipsmodule/bn/exponentiation.c
+++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -898,7 +898,9 @@
OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
return 0;
}
- if (a->neg || BN_ucmp(a, m) >= 0) {
+ // |a| is secret, but it is required to be in range, so these comparisons may
+ // be leaked.
+ if (a->neg || constant_time_declassify_int(BN_ucmp(a, m) >= 0)) {
OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
return 0;
}
diff --git a/crypto/fipsmodule/bn/gcd.c b/crypto/fipsmodule/bn/gcd.c
index df12569..7aa0043 100644
--- a/crypto/fipsmodule/bn/gcd.c
+++ b/crypto/fipsmodule/bn/gcd.c
@@ -327,7 +327,10 @@
const BN_MONT_CTX *mont, BN_CTX *ctx) {
*out_no_inverse = 0;
- if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) {
+ // |a| is secret, but it is required to be in range, so these comparisons may
+ // be leaked.
+ if (BN_is_negative(a) ||
+ constant_time_declassify_int(BN_cmp(a, &mont->N) >= 0)) {
OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
return 0;
}
@@ -336,11 +339,29 @@
BIGNUM blinding_factor;
BN_init(&blinding_factor);
- if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) ||
- !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) ||
- !BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) ||
+ // |BN_mod_inverse_odd| is leaky, so generate a secret blinding factor and
+ // blind |a|. This works because (ar)^-1 * r = a^-1, supposing r is
+ // invertible. If r is not invertible, this function will fail. However, we
+ // only use this in RSA, where stumbling on an uninvertible element means
+ // stumbling on the key's factorization. That is, if this function fails, the
+ // RSA key was not actually a product of two large primes.
+ //
+ // TODO(crbug.com/boringssl/677): When the PRNG output is marked secret by
+ // default, the explicit |bn_secret| call can be removed.
+ if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N)) {
+ goto err;
+ }
+ bn_secret(&blinding_factor);
+ if (!BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx)) {
+ goto err;
+ }
+
+ // Once blinded, |out| is no longer secret, so it may be passed to a leaky
+ // mod inverse function. Note |blinding_factor| is secret, so |out| will be
+ // secret again after multiplying.
+ bn_declassify(out);
+ if (!BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) ||
!BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) {
- OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
goto err;
}
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index 06ebe16..a2292b4 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -269,6 +269,18 @@
// validation.
void bn_assert_fits_in_bytes(const BIGNUM *bn, size_t num);
+// bn_secret marks |bn|'s contents, but not its width or sign, as secret. See
+// |CONSTTIME_SECRET| for details.
+OPENSSL_INLINE void bn_secret(BIGNUM *bn) {
+ CONSTTIME_SECRET(bn->d, bn->width * sizeof(BN_ULONG));
+}
+
+// bn_declassify marks |bn|'s value as public. See |CONSTTIME_DECLASSIFY| for
+// details.
+OPENSSL_INLINE void bn_declassify(BIGNUM *bn) {
+ CONSTTIME_DECLASSIFY(bn->d, bn->width * sizeof(BN_ULONG));
+}
+
// bn_mul_add_words multiples |ap| by |w|, adds the result to |rp|, and places
// the result in |rp|. |ap| and |rp| must both be |num| words long. It returns
// the carry word of the operation. |ap| and |rp| may be equal but otherwise may
diff --git a/crypto/fipsmodule/bn/random.c b/crypto/fipsmodule/bn/random.c
index 2500cc1..06de274 100644
--- a/crypto/fipsmodule/bn/random.c
+++ b/crypto/fipsmodule/bn/random.c
@@ -281,8 +281,14 @@
out[words - 1] &= mask;
// If out >= max_exclusive or out < min_inclusive, retry. This implements
- // the equivalent of steps 6 and 7 without leaking the value of |out|.
- } while (!bn_in_range_words(out, min_inclusive, max_exclusive, words));
+ // the equivalent of steps 6 and 7 without leaking the value of |out|. The
+ // result of this comparison may be treated as public. It only reveals how
+ // many attempts were needed before we found a value in range. This is
+ // independent of the final secret output, and has a distribution that
+ // depends only on |min_inclusive| and |max_exclusive|, both of which are
+ // public.
+ } while (!constant_time_declassify_int(
+ bn_in_range_words(out, min_inclusive, max_exclusive, words)));
return 1;
}
diff --git a/crypto/fipsmodule/ec/ec_key.c b/crypto/fipsmodule/ec/ec_key.c
index d42566a..c75d90b 100644
--- a/crypto/fipsmodule/ec/ec_key.c
+++ b/crypto/fipsmodule/ec/ec_key.c
@@ -314,8 +314,10 @@
OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
return 0;
}
- if (!ec_GFp_simple_points_equal(eckey->group, &point,
- &eckey->pub_key->raw)) {
+ // Leaking this comparison only leaks whether |eckey|'s public key was
+ // correct.
+ if (!constant_time_declassify_int(ec_GFp_simple_points_equal(
+ eckey->group, &point, &eckey->pub_key->raw))) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_PRIVATE_KEY);
return 0;
}
@@ -500,6 +502,14 @@
return 0;
}
+ // The public key is derived from the private key, but it is public.
+ //
+ // TODO(crbug.com/boringssl/677): This isn't quite right. While |pub_key|
+ // represents a public point, it is still in Jacobian form and the exact
+ // Jacobian representation is secret. We need to make it affine first. See
+ // discussion in the bug.
+ CONSTTIME_DECLASSIFY(&pub_key->raw, sizeof(pub_key->raw));
+
ec_wrapped_scalar_free(key->priv_key);
key->priv_key = priv_key;
EC_POINT_free(key->pub_key);
diff --git a/crypto/fipsmodule/ecdsa/ecdsa_test.cc b/crypto/fipsmodule/ecdsa/ecdsa_test.cc
index 39ad0a2..5876935 100644
--- a/crypto/fipsmodule/ecdsa/ecdsa_test.cc
+++ b/crypto/fipsmodule/ecdsa/ecdsa_test.cc
@@ -181,7 +181,9 @@
// Fill digest values with some random data.
uint8_t digest[20], wrong_digest[20];
ASSERT_TRUE(RAND_bytes(digest, 20));
+ CONSTTIME_DECLASSIFY(digest, 20);
ASSERT_TRUE(RAND_bytes(wrong_digest, 20));
+ CONSTTIME_DECLASSIFY(wrong_digest, 20);
static const struct {
int nid;
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c
index e847f93..f2dc7fe 100644
--- a/crypto/fipsmodule/rsa/rsa_impl.c
+++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -155,7 +155,7 @@
return 0;
}
*out = copy;
- CONSTTIME_SECRET(copy->d, sizeof(BN_ULONG) * width);
+ bn_secret(copy);
return 1;
}
@@ -259,8 +259,7 @@
goto err;
}
rsa->iqmp_mont = iqmp_mont;
- CONSTTIME_SECRET(rsa->iqmp_mont->d,
- sizeof(BN_ULONG) * rsa->iqmp_mont->width);
+ bn_secret(rsa->iqmp_mont);
}
}
}
@@ -622,7 +621,9 @@
goto err;
}
- if (BN_ucmp(f, rsa->n) >= 0) {
+ // The input to the RSA private transform may be secret, but padding is
+ // expected to construct a value within range, so we can leak this comparison.
+ if (constant_time_declassify_int(BN_ucmp(f, rsa->n) >= 0)) {
// Usually the padding functions would catch this.
OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
goto err;
diff --git a/crypto/rsa_extra/rsa_crypt.c b/crypto/rsa_extra/rsa_crypt.c
index c9d29fc..742284d 100644
--- a/crypto/rsa_extra/rsa_crypt.c
+++ b/crypto/rsa_extra/rsa_crypt.c
@@ -75,7 +75,9 @@
RAND_bytes(out, len);
for (size_t i = 0; i < len; i++) {
- while (out[i] == 0) {
+ // Zero values are replaced, and the distribution of zero and non-zero bytes
+ // is public, so leaking this is safe.
+ while (constant_time_declassify_int(out[i] == 0)) {
RAND_bytes(out + i, 1);
}
}
