Fix allocation size in BN_mod_exp_mont_consttime.
powerbuf's layout is:
- num_powers values mod m, stored transposed
- one value mod m, tmp
- one value mod m, am
- (mont5-only) an extra copy of m
powerbuf_len broadly computed this, but where tmp + am would be
sizeof(BN_ULONG) * top * 2, it used
sizeof(BN_ULONG) * max(top * 2, num_powers).
(In the actual code it's written as a ternary op and some
multiplications are factored out.)
That is, it allocated enough room for tmp + am OR an extra row in the
num_powers table, as if each entry were top + 1 words long instead of
top, with the space overlapping. This expression dates to upstream's
https://github.com/openssl/openssl/commit/361512da0d900ba276096cbd152e304d402aca65,
though the exact layout has shifted over the years as mont5 evolved.
(Originally, it only contained one extra value mod m.)
At the time, this was necessary because bn_mul_mont_gather5 actually
overreads the table by one row! Although it only uses top * 32 words, it
requires the table to have (top + 1) * 32 words. This is because the
computation was scheduled so that the .Louter4x loop would read and mask
off the next iteration's value while incorporating the previous
iteration:
There were masked reads from $bp into XMM registers at the start of the
loop:
https://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L541
The XMM logic is interleaved throughout and does not move to a
general-purpose register, $m0, until much later. $m is not read again
until after the jump.
https://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L700
Meanwhile, the loop is already reading $m0 at the start of the
iteration.
https://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L551
The whole thing is bootstrapped by similar code just above it:
https://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L531
In the final iteration, we read one extra row into $m0 but never use it.
That is the overread.
I also confirmed this by rewinding our x86_64-mont5.pl to this state,
hacking things up until it built, and then hacking up
BN_mod_exp_mont_consttime to place the table in its own allocation, with
no extra slop using C11 aligned_alloc. This was so valgrind could
accurately instrument the bounds. When I did that, valgrind was clean if
I allocated (top + 1) * num_powers, but flagged an out-of-bounds read at
top * num_powers.
This no longer applies. After
https://github.com/openssl/openssl/commit/25d14c6c29b53907bf614b9964d43cd98401a7fc,
bn_mul_mont_gather5's scheduling is far less complicated. .Louter4x now
begins with a masked read, setting up $m0, and then it incorporates $m0
into the product. The same valgrind strategy confirmed this. Thus, I
don't believe this extra row is needed and we can allocate the buffer
straightforwardly.
Change-Id: I6c1ee8d5ebdb66eb4e5fec63d2140814c13ae146
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/55231
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: Bob Beck <bbe@google.com>
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c
index 2903ede..afa8e71 100644
--- a/crypto/fipsmodule/bn/exponentiation.c
+++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -961,9 +961,7 @@
// Allocate a buffer large enough to hold all of the pre-computed
// powers of |am|, |am| itself, and |tmp|.
int num_powers = 1 << window;
- powerbuf_len +=
- sizeof(m->d[0]) *
- (top * num_powers + ((2 * top) > num_powers ? (2 * top) : num_powers));
+ powerbuf_len += sizeof(m->d[0]) * top * (num_powers + 2);
#if defined(OPENSSL_BN_ASM_MONT5)
if (powerbuf_len <= sizeof(storage)) {
