Fix comments now BN_mod_exp_mont_consttime is not cache-line-sensitive
BN_mod_exp_mont_consttime originally assumed accesses within a cache
line were indistinguishable and indexed into a cache line with secret
values. As a result, it required all of its tables, etc., to be
cache-line-aligned. Nowadays, the standard constant time memory model is
to assume the whole address leaks and not make these assumptions.
In particular, CacheBleed (CVE-2016-0702) showed this assumption was
false and which cache bank you accessed as leaked. OpenSSL's fix for the
assembly (mont5 and rsaz) appears to match the standard constant-time
model. However, its fix to the C code narrowed the assumption to cache
banks, so the alignment was still necessary.
After https://boringssl-review.googlesource.com/c/boringssl/+/33268, we
dropped this and use the standard model. All together, it should mean we
no longer make assumptions about cache lines. Update all the comments
and variable names accordingly.
Change-Id: I7bcb828eb2751a0167c3a3c8242b1b3971efc708
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/55227
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c
index a76d7cb..285c4dd 100644
--- a/crypto/fipsmodule/bn/exponentiation.c
+++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -863,28 +863,13 @@
// Window sizes optimized for fixed window size modular exponentiation
// algorithm (BN_mod_exp_mont_consttime).
//
-// To achieve the security goals of BN_mode_exp_mont_consttime, the maximum
-// size of the window must not exceed
-// log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH).
-//
-// Window size thresholds are defined for cache line sizes of 32 and 64, cache
-// line sizes where log_2(32)=5 and log_2(64)=6 respectively. A window size of
-// 7 should only be used on processors that have a 128 byte or greater cache
-// line size.
-#if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
-
+// TODO(davidben): These window sizes were originally set for 64-byte cache
+// lines with a cache-line-dependent constant-time mitigation. They can probably
+// be revised now that our implementation is no longer cache-time-dependent.
#define BN_window_bits_for_ctime_exponent_size(b) \
((b) > 937 ? 6 : (b) > 306 ? 5 : (b) > 89 ? 4 : (b) > 22 ? 3 : 1)
#define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6)
-#elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32
-
-#define BN_window_bits_for_ctime_exponent_size(b) \
- ((b) > 306 ? 5 : (b) > 89 ? 4 : (b) > 22 ? 3 : 1)
-#define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5)
-
-#endif
-
// This variant of |BN_mod_exp_mont| uses fixed windows and fixed memory access
// patterns to protect secret exponents (cf. the hyper-threading timing attacks
// pointed out by Colin Percival,
@@ -945,8 +930,7 @@
// paths. If we were to use separate static buffers for each then there is
// some chance that both large buffers would be allocated on the stack,
// causing the stack space requirement to be truly huge (~10KB).
- alignas(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH) BN_ULONG
- storage[MOD_EXP_CTIME_STORAGE_LEN];
+ alignas(MOD_EXP_CTIME_ALIGN) BN_ULONG storage[MOD_EXP_CTIME_STORAGE_LEN];
#endif
#if defined(RSAZ_ENABLED)
// If the size of the operands allow it, perform the optimized RSAZ
@@ -991,12 +975,11 @@
assert(powerbuf != NULL || top * BN_BITS2 > 1024);
#endif
if (powerbuf == NULL) {
- powerbufFree =
- OPENSSL_malloc(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH);
+ powerbufFree = OPENSSL_malloc(powerbufLen + MOD_EXP_CTIME_ALIGN);
if (powerbufFree == NULL) {
goto err;
}
- powerbuf = align_pointer(powerbufFree, MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH);
+ powerbuf = align_pointer(powerbufFree, MOD_EXP_CTIME_ALIGN);
}
OPENSSL_memset(powerbuf, 0, powerbufLen);
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index 9329ce7..f7adfe9 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -189,14 +189,20 @@
#define BN_CAN_USE_INLINE_ASM
#endif
-// |BN_mod_exp_mont_consttime| is based on the assumption that the L1 data
-// cache line width of the target processor is at least the following value.
-#define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH 64
+// MOD_EXP_CTIME_ALIGN is the alignment needed for |BN_mod_exp_mont_consttime|'s
+// tables.
+//
+// TODO(davidben): Historically, this alignment came from cache line
+// assumptions, which we've since removed. Is 64-byte alignment still necessary
+// or ideal? The true alignment requirement seems to now be 32 bytes, coming
+// from RSAZ's use of VMOVDQA to a YMM register. Non-x86_64 has even fewer
+// requirements.
+#define MOD_EXP_CTIME_ALIGN 64
-// The number of |BN_ULONG|s needed for the |BN_mod_exp_mont_consttime| stack-
-// allocated storage buffer. The buffer is just the right size for the RSAZ
-// and is about ~1KB larger than what's necessary (4480 bytes) for 1024-bit
-// inputs.
+// MOD_EXP_CTIME_STORAGE_LEN is the number of |BN_ULONG|s needed for the
+// |BN_mod_exp_mont_consttime| stack-allocated storage buffer. The buffer is
+// just the right size for the RSAZ and is about ~1KB larger than what's
+// necessary (4480 bytes) for 1024-bit inputs.
#define MOD_EXP_CTIME_STORAGE_LEN \
(((320u * 3u) + (32u * 9u * 16u)) / sizeof(BN_ULONG))
diff --git a/crypto/fipsmodule/bn/rsaz_exp.c b/crypto/fipsmodule/bn/rsaz_exp.c
index 7b455b5..da25030 100644
--- a/crypto/fipsmodule/bn/rsaz_exp.c
+++ b/crypto/fipsmodule/bn/rsaz_exp.c
@@ -40,8 +40,8 @@
const BN_ULONG m_norm[16], const BN_ULONG RR[16],
BN_ULONG k0,
BN_ULONG storage[MOD_EXP_CTIME_STORAGE_LEN]) {
- static_assert(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH % 64 == 0,
- "MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH is too small");
+ static_assert(MOD_EXP_CTIME_ALIGN % 64 == 0,
+ "MOD_EXP_CTIME_ALIGN is too small");
assert((uintptr_t)storage % 64 == 0);
BN_ULONG *a_inv, *m, *result, *table_s = storage + 40 * 3, *R2 = table_s;
diff --git a/crypto/fipsmodule/bn/rsaz_exp.h b/crypto/fipsmodule/bn/rsaz_exp.h
index 67f1cab..22ca3ec 100644
--- a/crypto/fipsmodule/bn/rsaz_exp.h
+++ b/crypto/fipsmodule/bn/rsaz_exp.h
@@ -32,8 +32,7 @@
// modulo |m_norm|. |base_norm| must be fully-reduced and |exponent| must have
// the high bit set (it is 1024 bits wide). |RR| and |k0| must be |RR| and |n0|,
// respectively, extracted from |m_norm|'s |BN_MONT_CTX|. |storage_words| is a
-// temporary buffer that must be aligned to |MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH|
-// bytes.
+// temporary buffer that must be aligned to |MOD_EXP_CTIME_ALIGN| bytes.
void RSAZ_1024_mod_exp_avx2(BN_ULONG result[16], const BN_ULONG base_norm[16],
const BN_ULONG exponent[16],
const BN_ULONG m_norm[16], const BN_ULONG RR[16],
