Start making asserts constant-time too
We've historically settled on treating asserts as not in scope for our
constant-time goals. Production binaries are expected to be optimized
builds, with debug assertions turned off. (We have a handful of
assertions in perf-sensitive code that you definitely do not want to run
with.) Secret data has invariants too, so it is useful to be able to
write debug assertions on them.
However, combined with our default CMake build being a debug build, this
seems to cause some confusion with researchers sometimes. Also, if we
ever get language-level constant-time support, we would need to resolve
this mismatch anyway. (I assume any language support would put enough
into the type system to force us to declassify any intentional branches
on secret-by-data-flow bools, notably those we assert on.) So I'm
inclined to just make our asserts constant-time.
There are two issues around asserts, at least with our valgrind-based
validation:
The first is that a couple of asserts over secret data compute their
condition leakily. We can just fix these. The only such ones I found
were in bn_reduce_once and bn_gcd_consttime.
The second is that almost every assert over secret data will be flagged
as an invalid branch by valgrind. However, presuming the condition
itself was computed in constant time, this branch is actually safe. If
we were willing to abort the process when false, the assert is clearly
publicly true. We just need to declassify the boolean to assert on it.
assert(constant_time_declassify_int(expr)) is really long, so I made an
internal wrapper macro declassify_assert(expr). Not sure if that's the
best name. constant_time_declassify_assert(expr) is kinda long.
constant_time_assert(expr) fits with the rest of that namespace, but
reads as if we're somehow running an assert without branching, when the
whole point is that we *are* branching and need to explicitly say it's
okay to.
Fixed: 339
Change-Id: Ie33b99bf9a269b11d2c48d246cc4934be7e239ff
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/65467
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/CMakeLists.txt b/CMakeLists.txt
index fe90240..59623e0 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -356,8 +356,6 @@
if(CONSTANT_TIME_VALIDATION)
add_definitions(-DBORINGSSL_CONSTANT_TIME_VALIDATION)
- # Asserts will often test secret data.
- add_definitions(-DNDEBUG)
endif()
if(MALLOC_FAILURE_TESTING)
diff --git a/crypto/cipher_extra/tls_cbc.c b/crypto/cipher_extra/tls_cbc.c
index ac6ca43..ddbe4f2 100644
--- a/crypto/cipher_extra/tls_cbc.c
+++ b/crypto/cipher_extra/tls_cbc.c
@@ -121,8 +121,8 @@
size_t mac_end = in_len;
size_t mac_start = mac_end - md_size;
- assert(orig_len >= in_len);
- assert(in_len >= md_size);
+ declassify_assert(orig_len >= in_len);
+ declassify_assert(in_len >= md_size);
assert(md_size <= EVP_MAX_MD_SIZE);
assert(md_size > 0);
diff --git a/crypto/curve25519/curve25519.c b/crypto/curve25519/curve25519.c
index 581d740..761af4c 100644
--- a/crypto/curve25519/curve25519.c
+++ b/crypto/curve25519/curve25519.c
@@ -81,7 +81,7 @@
#define assert_fe(f) \
do { \
for (unsigned _assert_fe_i = 0; _assert_fe_i < 5; _assert_fe_i++) { \
- assert(f[_assert_fe_i] <= UINT64_C(0x8cccccccccccc)); \
+ declassify_assert(f[_assert_fe_i] <= UINT64_C(0x8cccccccccccc)); \
} \
} while (0)
@@ -98,7 +98,7 @@
#define assert_fe_loose(f) \
do { \
for (unsigned _assert_fe_i = 0; _assert_fe_i < 5; _assert_fe_i++) { \
- assert(f[_assert_fe_i] <= UINT64_C(0x1a666666666664)); \
+ declassify_assert(f[_assert_fe_i] <= UINT64_C(0x1a666666666664)); \
} \
} while (0)
@@ -120,8 +120,8 @@
#define assert_fe(f) \
do { \
for (unsigned _assert_fe_i = 0; _assert_fe_i < 10; _assert_fe_i++) { \
- assert(f[_assert_fe_i] <= \
- ((_assert_fe_i & 1) ? 0x2333333u : 0x4666666u)); \
+ declassify_assert(f[_assert_fe_i] <= \
+ ((_assert_fe_i & 1) ? 0x2333333u : 0x4666666u)); \
} \
} while (0)
@@ -138,8 +138,8 @@
#define assert_fe_loose(f) \
do { \
for (unsigned _assert_fe_i = 0; _assert_fe_i < 10; _assert_fe_i++) { \
- assert(f[_assert_fe_i] <= \
- ((_assert_fe_i & 1) ? 0x6999999u : 0xd333332u)); \
+ declassify_assert(f[_assert_fe_i] <= \
+ ((_assert_fe_i & 1) ? 0x6999999u : 0xd333332u)); \
} \
} while (0)
@@ -150,7 +150,7 @@
static void fe_frombytes_strict(fe *h, const uint8_t s[32]) {
// |fiat_25519_from_bytes| requires the top-most bit be clear.
- assert((s[31] & 0x80) == 0);
+ declassify_assert((s[31] & 0x80) == 0);
fiat_25519_from_bytes(h->v, s);
assert_fe(h->v);
}
diff --git a/crypto/fipsmodule/bn/bytes.c b/crypto/fipsmodule/bn/bytes.c
index d7f70da..dcb0afc 100644
--- a/crypto/fipsmodule/bn/bytes.c
+++ b/crypto/fipsmodule/bn/bytes.c
@@ -186,7 +186,7 @@
void bn_words_to_big_endian(uint8_t *out, size_t out_len, const BN_ULONG *in,
size_t in_len) {
// The caller should have selected an output length without truncation.
- assert(fits_in_bytes(in, in_len, out_len));
+ declassify_assert(fits_in_bytes(in, in_len, out_len));
// We only support little-endian platforms, so the internal representation is
// also little-endian as bytes. We can simply copy it in reverse.
diff --git a/crypto/fipsmodule/bn/div.c b/crypto/fipsmodule/bn/div.c
index 6c13716..f524f89 100644
--- a/crypto/fipsmodule/bn/div.c
+++ b/crypto/fipsmodule/bn/div.c
@@ -425,7 +425,7 @@
//
// Although |carry| may be one if it was one on input and |bn_sub_words|
// returns zero, this would give |r| > |m|, violating our input assumptions.
- assert(carry == 0 || carry == (BN_ULONG)-1);
+ declassify_assert(carry + 1 <= 1);
bn_select_words(r, carry, a /* r < 0 */, r /* r >= 0 */, num);
return carry;
}
@@ -434,7 +434,7 @@
BN_ULONG *tmp, size_t num) {
// See |bn_reduce_once| for why this logic works.
carry -= bn_sub_words(tmp, r, m, num);
- assert(carry == 0 || carry == (BN_ULONG)-1);
+ declassify_assert(carry + 1 <= 1);
bn_select_words(r, carry, r /* tmp < 0 */, tmp /* tmp >= 0 */, num);
return carry;
}
@@ -504,7 +504,7 @@
// |divisor_min_bits| bits, the top |divisor_min_bits - 1| can be incorporated
// without reductions. This significantly speeds up |RSA_check_key|. For
// simplicity, we round down to a whole number of words.
- assert(divisor_min_bits <= BN_num_bits(divisor));
+ declassify_assert(divisor_min_bits <= BN_num_bits(divisor));
int initial_words = 0;
if (divisor_min_bits > 0) {
initial_words = (divisor_min_bits - 1) / BN_BITS2;
diff --git a/crypto/fipsmodule/bn/div_extra.c b/crypto/fipsmodule/bn/div_extra.c
index 141f7da..f75c914 100644
--- a/crypto/fipsmodule/bn/div_extra.c
+++ b/crypto/fipsmodule/bn/div_extra.c
@@ -39,7 +39,7 @@
// Multiply and subtract to get the remainder.
n -= d * t;
- assert(n < d);
+ declassify_assert(n < d);
return n;
}
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c
index 7b24d89..53c6142 100644
--- a/crypto/fipsmodule/bn/exponentiation.c
+++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -1013,7 +1013,7 @@
// Prepare a^1 in the Montgomery domain.
assert(!a->neg);
- assert(BN_ucmp(a, m) < 0);
+ declassify_assert(BN_ucmp(a, m) < 0);
if (!BN_to_montgomery(&am, a, mont, ctx) ||
!bn_resize_words(&am, top)) {
goto err;
diff --git a/crypto/fipsmodule/bn/gcd_extra.c b/crypto/fipsmodule/bn/gcd_extra.c
index 76f337c..531ff59 100644
--- a/crypto/fipsmodule/bn/gcd_extra.c
+++ b/crypto/fipsmodule/bn/gcd_extra.c
@@ -93,7 +93,7 @@
// At least one of |u| and |v| is now even.
BN_ULONG u_is_odd = word_is_odd_mask(u->d[0]);
BN_ULONG v_is_odd = word_is_odd_mask(v->d[0]);
- assert(!(u_is_odd & v_is_odd));
+ declassify_assert(!(u_is_odd & v_is_odd));
// If both are even, the final GCD gains a factor of two.
shift += 1 & (~u_is_odd & ~v_is_odd);
@@ -106,7 +106,7 @@
// One of |u| or |v| is zero at this point. The algorithm usually makes |u|
// zero, unless |y| was already zero on input. Fix this by combining the
// values.
- assert(BN_is_zero(u) || BN_is_zero(v));
+ declassify_assert(BN_is_zero(u) | BN_is_zero(v));
for (size_t i = 0; i < width; i++) {
v->d[i] |= u->d[i];
}
@@ -289,7 +289,7 @@
// and |v| is now even.
BN_ULONG u_is_even = ~word_is_odd_mask(u->d[0]);
BN_ULONG v_is_even = ~word_is_odd_mask(v->d[0]);
- assert(u_is_even != v_is_even);
+ declassify_assert(u_is_even != v_is_even);
// Halve the even one and adjust the corresponding coefficient.
maybe_rshift1_words(u->d, u_is_even, tmp->d, n_width);
@@ -313,7 +313,7 @@
maybe_rshift1_words_carry(D->d, D_carry, v_is_even, tmp->d, a_width);
}
- assert(BN_is_zero(v));
+ declassify_assert(BN_is_zero(v));
// While the inputs and output are secret, this function considers whether the
// input was invertible to be public. It is used as part of RSA key
// generation, where inputs are chosen to already be invertible.
diff --git a/crypto/fipsmodule/bn/montgomery_inv.c b/crypto/fipsmodule/bn/montgomery_inv.c
index 068d00b..499665a 100644
--- a/crypto/fipsmodule/bn/montgomery_inv.c
+++ b/crypto/fipsmodule/bn/montgomery_inv.c
@@ -153,7 +153,7 @@
// The invariant now shows that u*r - v*n == 1 since r == 2 * alpha.
#if BN_BITS2 == 64 && defined(BN_ULLONG)
- assert(1 == ((BN_ULLONG)u * 2 * alpha) - ((BN_ULLONG)v * beta));
+ declassify_assert(1 == ((BN_ULLONG)u * 2 * alpha) - ((BN_ULLONG)v * beta));
#endif
return v;
diff --git a/crypto/fipsmodule/bn/mul.c b/crypto/fipsmodule/bn/mul.c
index 7537899..07612c5 100644
--- a/crypto/fipsmodule/bn/mul.c
+++ b/crypto/fipsmodule/bn/mul.c
@@ -292,7 +292,7 @@
}
// The product should fit without carries.
- assert(c == 0);
+ declassify_assert(c == 0);
}
// bn_mul_part_recursive sets |r| to |a| * |b|, using |t| as scratch space. |r|
@@ -406,7 +406,7 @@
}
// The product should fit without carries.
- assert(c == 0);
+ declassify_assert(c == 0);
}
// bn_mul_impl implements |BN_mul| and |bn_mul_consttime|. Note this function
diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index 5af6387..4722f80 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -773,7 +773,7 @@
}
}
- assert(uniform_iterations >= (crypto_word_t)checks);
+ declassify_assert(uniform_iterations >= (crypto_word_t)checks);
*out_is_probably_prime = 1;
ret = 1;
diff --git a/crypto/fipsmodule/bn/random.c b/crypto/fipsmodule/bn/random.c
index 06de274..f57d1c6 100644
--- a/crypto/fipsmodule/bn/random.c
+++ b/crypto/fipsmodule/bn/random.c
@@ -339,7 +339,8 @@
// If the value is not in range, force it to be in range.
r->d[0] |= constant_time_select_w(in_range, 0, min_inclusive);
r->d[words - 1] &= constant_time_select_w(in_range, BN_MASK2, mask >> 1);
- assert(bn_in_range_words(r->d, min_inclusive, max_exclusive->d, words));
+ declassify_assert(
+ bn_in_range_words(r->d, min_inclusive, max_exclusive->d, words));
r->neg = 0;
r->width = (int)words;
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c
index 6f9c3bb..099bc02 100644
--- a/crypto/fipsmodule/rsa/rsa_impl.c
+++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -795,7 +795,7 @@
// This is a pre-condition for |mod_montgomery|. It was already checked by the
// caller.
- assert(BN_ucmp(I, n) < 0);
+ declassify_assert(BN_ucmp(I, n) < 0);
if (// |m1| is the result modulo |q|.
!mod_montgomery(r1, I, q, rsa->mont_q, p, ctx) ||
@@ -831,7 +831,7 @@
// bound the width slightly higher, so fix it. This trips constant-time checks
// because a naive data flow analysis does not realize the excess words are
// publicly zero.
- assert(BN_cmp(r0, n) < 0);
+ declassify_assert(BN_cmp(r0, n) < 0);
bn_assert_fits_in_bytes(r0, BN_num_bytes(n));
if (!bn_resize_words(r0, n->width)) {
goto err;
diff --git a/crypto/internal.h b/crypto/internal.h
index aa1436e..a77102d 100644
--- a/crypto/internal.h
+++ b/crypto/internal.h
@@ -609,6 +609,12 @@
return value_barrier_u32(v);
}
+// declassify_assert behaves like |assert| but declassifies the result of
+// evaluating |expr|. This allows the assertion to branch on the (presumably
+// public) result, but still ensures that values leading up to the computation
+// were secret.
+#define declassify_assert(expr) assert(constant_time_declassify_int(expr))
+
// Thread-safe initialisation.
@@ -1180,13 +1186,13 @@
static inline uint32_t CRYPTO_addc_u32(uint32_t x, uint32_t y, uint32_t carry,
uint32_t *out_carry) {
- assert(carry <= 1);
+ declassify_assert(carry <= 1);
return CRYPTO_GENERIC_ADDC(x, y, carry, out_carry);
}
static inline uint64_t CRYPTO_addc_u64(uint64_t x, uint64_t y, uint64_t carry,
uint64_t *out_carry) {
- assert(carry <= 1);
+ declassify_assert(carry <= 1);
return CRYPTO_GENERIC_ADDC(x, y, carry, out_carry);
}
@@ -1194,7 +1200,7 @@
static inline uint32_t CRYPTO_addc_u32(uint32_t x, uint32_t y, uint32_t carry,
uint32_t *out_carry) {
- assert(carry <= 1);
+ declassify_assert(carry <= 1);
uint64_t ret = carry;
ret += (uint64_t)x + y;
*out_carry = (uint32_t)(ret >> 32);
@@ -1203,7 +1209,7 @@
static inline uint64_t CRYPTO_addc_u64(uint64_t x, uint64_t y, uint64_t carry,
uint64_t *out_carry) {
- assert(carry <= 1);
+ declassify_assert(carry <= 1);
#if defined(BORINGSSL_HAS_UINT128)
uint128_t ret = carry;
ret += (uint128_t)x + y;
@@ -1232,13 +1238,13 @@
static inline uint32_t CRYPTO_subc_u32(uint32_t x, uint32_t y, uint32_t borrow,
uint32_t *out_borrow) {
- assert(borrow <= 1);
+ declassify_assert(borrow <= 1);
return CRYPTO_GENERIC_SUBC(x, y, borrow, out_borrow);
}
static inline uint64_t CRYPTO_subc_u64(uint64_t x, uint64_t y, uint64_t borrow,
uint64_t *out_borrow) {
- assert(borrow <= 1);
+ declassify_assert(borrow <= 1);
return CRYPTO_GENERIC_SUBC(x, y, borrow, out_borrow);
}
@@ -1246,7 +1252,7 @@
static inline uint32_t CRYPTO_subc_u32(uint32_t x, uint32_t y, uint32_t borrow,
uint32_t *out_borrow) {
- assert(borrow <= 1);
+ declassify_assert(borrow <= 1);
uint32_t ret = x - y - borrow;
*out_borrow = (x < y) | ((x == y) & borrow);
return ret;
@@ -1254,7 +1260,7 @@
static inline uint64_t CRYPTO_subc_u64(uint64_t x, uint64_t y, uint64_t borrow,
uint64_t *out_borrow) {
- assert(borrow <= 1);
+ declassify_assert(borrow <= 1);
uint64_t ret = x - y - borrow;
*out_borrow = (x < y) | ((x == y) & borrow);
return ret;
