Remove cacheline striping in copy_from_prebuf. The standard computation model for constant-time code is that memory access patterns must be independent of secret data. BN_mod_exp_mont_consttime was previously written to a slightly weaker model: only cacheline access patterns must be independent of secret data. It assumed accesses within a cacheline were indistinguishable. The CacheBleed attack (https://eprint.iacr.org/2016/224.pdf) showed this assumption was false. Cache lines may be divided into cache banks, and the researchers were able to measure cache bank contention pre-Haswell. For Haswell, the researchers note "But, as Haswell does show timing variations that depend on low address bits [19], it may be vulnerable to similar attacks." OpenSSL's fix to CacheBleed was not to adopt the standard constant-time computation model. Rather, it now assumes accesses within a 16-byte cache bank are indistinguishable, at least in the C copy_from_prebuf path. These weaker models failed before with CacheBleed, so avoiding such assumptions seems prudent. (The [19] citation above notes a false dependence between memory addresses with a distance of 4k, which may be what the paper was referring to.) Moreover, the C path is largely unused on x86_64 (which uses mont5 asm), so it is especially questionable for the generic C code to make assumptions based on x86_64. Just walk the entire table in the C implementation. Doing so as-is comes with a performance hit, but the striped memory layout is, at that point, useless. We regain the performance loss (and then some) by using a more natural layout. Benchmarks below. This CL does not touch the mont5 assembly; I haven't figured out what it's doing yet. Pixel 3, aarch64: Before: Did 3146 RSA 2048 signing operations in 10009070us (314.3 ops/sec) Did 447 RSA 4096 signing operations in 10026666us (44.6 ops/sec) After: Did 3210 RSA 2048 signing operations in 10010712us (320.7 ops/sec) Did 456 RSA 4096 signing operations in 10063543us (45.3 ops/sec) Pixel 3, armv7: Before: Did 2688 RSA 2048 signing operations in 10002266us (268.7 ops/sec) Did 459 RSA 4096 signing operations in 10004785us (45.9 ops/sec) After: Did 2709 RSA 2048 signing operations in 10001299us (270.9 ops/sec) Did 459 RSA 4096 signing operations in 10063737us (45.6 ops/sec) x86_64 Broadwell, mont5 assembly disabled: (This configuration is not actually shipped anywhere, but seemed a useful data point.) Before: Did 14274 RSA 2048 signing operations in 10009130us (1426.1 ops/sec) Did 2448 RSA 4096 signing operations in 10046921us (243.7 ops/sec) After: Did 14706 RSA 2048 signing operations in 10037908us (1465.0 ops/sec) Did 2538 RSA 4096 signing operations in 10059986us (252.3 ops/sec) Change-Id: If41da911d4281433856a86c6c8eadf99cd33e2d8 Reviewed-on: https://boringssl-review.googlesource.com/c/33268 Reviewed-by: Adam Langley <agl@google.com> Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c index fa326a7..1b9680f 100644 --- a/crypto/fipsmodule/bn/exponentiation.c +++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -850,67 +850,25 @@ bn_mod_exp_mont_small(r, a, num, p_minus_two, num, mont); } - -// |BN_mod_exp_mont_consttime| stores the precomputed powers in a specific -// layout so that accessing any of these table values shows the same access -// pattern as far as cache lines are concerned. The following functions are -// used to transfer a BIGNUM from/to that table. - static void copy_to_prebuf(const BIGNUM *b, int top, BN_ULONG *table, int idx, int window) { - int i, j; - const int width = 1 << window; - if (top > b->width) { - top = b->width; // This works because |table| is explicitly zeroed. - } - - for (i = 0, j = idx; i < top; i++, j += width) { - table[j] = b->d[i]; - } + int ret = bn_copy_words(table + idx * top, top, b); + assert(ret); // |b| is guaranteed to fit. + (void)ret; } -static int copy_from_prebuf(BIGNUM *b, int top, const BN_ULONG *buf, int idx, +static int copy_from_prebuf(BIGNUM *b, int top, const BN_ULONG *table, int idx, int window) { - int i, j; - const int width = 1 << window; - volatile const BN_ULONG *table = (volatile const BN_ULONG *)buf; - if (!bn_wexpand(b, top)) { return 0; } - if (window <= 3) { - for (i = 0; i < top; i++, table += width) { - BN_ULONG acc = 0; - - for (j = 0; j < width; j++) { - acc |= table[j] & ((BN_ULONG)0 - (constant_time_eq_int(j, idx) & 1)); - } - - b->d[i] = acc; - } - } else { - int xstride = 1 << (window - 2); - BN_ULONG y0, y1, y2, y3; - - i = idx >> (window - 2); // equivalent of idx / xstride - idx &= xstride - 1; // equivalent of idx % xstride - - y0 = (BN_ULONG)0 - (constant_time_eq_int(i, 0) & 1); - y1 = (BN_ULONG)0 - (constant_time_eq_int(i, 1) & 1); - y2 = (BN_ULONG)0 - (constant_time_eq_int(i, 2) & 1); - y3 = (BN_ULONG)0 - (constant_time_eq_int(i, 3) & 1); - - for (i = 0; i < top; i++, table += width) { - BN_ULONG acc = 0; - - for (j = 0; j < xstride; j++) { - acc |= ((table[j + 0 * xstride] & y0) | (table[j + 1 * xstride] & y1) | - (table[j + 2 * xstride] & y2) | (table[j + 3 * xstride] & y3)) & - ((BN_ULONG)0 - (constant_time_eq_int(j, idx) & 1)); - } - - b->d[i] = acc; + OPENSSL_memset(b->d, 0, sizeof(BN_ULONG) * top); + const int width = 1 << window; + for (int i = 0; i < width; i++, table += top) { + BN_ULONG mask = constant_time_eq_int(i, idx); + for (int j = 0; j < top; j++) { + b->d[j] |= table[j] & mask; } } @@ -953,9 +911,8 @@ (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - \ (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) -// This variant of BN_mod_exp_mont() uses fixed windows and the special -// precomputation memory layout to limit data-dependency to a minimum -// to protect secret exponents (cf. the hyper-threading timing attacks +// 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, // http://www.daemonology.net/hyperthreading-considered-harmful/) int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,