From 4981e6fc1da4aec6775fc248643c91dd1e87e0b7 Mon Sep 17 00:00:00 2001 From: David Benjamin Date: Tue, 23 Jan 2018 13:57:10 -0500 Subject: [PATCH] Don't leak the exponent bit width in BN_mod_exp_mont_consttime. The exponent here is one of d, dmp1, or dmq1 for RSA. This value and its bit length are both secret. The only public upper bound is the bit width of the corresponding modulus (RSA n, p, and q, respectively). Although BN_num_bits is constant-time (sort of; see bn_correct_top notes in preceding patch), this does not fix the root problem, which is that the windows are based on the minimal bit width, not the upper bound. We could use BN_num_bits(m), but BN_mod_exp_mont_consttime is public API and may be called with larger exponents. Instead, use all top*BN_BITS2 bits in the BIGNUM. This is still sensitive to the long-standing bn_correct_top leak, but we need to fix that regardless. This may cause us to do a handful of extra multiplications for RSA keys which are just above a whole number of words, but that is not a standard RSA key size. Reviewed-by: Paul Dale Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/5154) (cherry picked from commit 39eeb64f59ff838f976ad305de7d15747d47a41c) --- crypto/bn/bn_exp.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c index c4b63e44ba..9fc545a524 100644 --- a/crypto/bn/bn_exp.c +++ b/crypto/bn/bn_exp.c @@ -727,7 +727,11 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, top = m->top; - bits = BN_num_bits(p); + /* + * Use all bits stored in |p|, rather than |BN_num_bits|, so we do not leak + * whether the top bits are zero. + */ + bits = p->top * BN_BITS2; if (bits == 0) { /* x**0 mod 1 is still zero. */ if (BN_is_one(m)) { -- 2.25.1