From b9a380f78cd7dbb414bccb38f0904a32d8384fca Mon Sep 17 00:00:00 2001 From: Nicola Tuveri Date: Fri, 2 Aug 2019 02:08:34 +0300 Subject: [PATCH] Make BN_num_bits() consttime upon BN_FLG_CONSTTIME This issue was partially addressed by commit 972c87dfc7e765bd28a4964519c362f0d3a58ca4, which hardened its callee BN_num_bits_word() to avoid leaking the most-significant word of its argument via branching and memory access pattern. The commit message also reported: > There are a few places where BN_num_bits is called on an input where > the bit length is also secret. This does *not* fully resolve those > cases as we still only look at the top word. BN_num_bits() is called directly or indirectly (e.g., through BN_num_bytes() or BN_bn2binpad() ) in various parts of the `crypto/ec` code, notably in all the currently supported implementations of scalar multiplication (in the generic path through ec_scalar_mul_ladder() as well as in dedicated methods like ecp_nistp{224,256,521}.c and ecp_nistz256.c). Under the right conditions, a motivated SCA attacker could retrieve the secret bitlength of a secret nonce through this vulnerability, potentially leading, ultimately, to recover a long-term secret key. With this commit, exclusively for BIGNUMs that are flagged with BN_FLG_CONSTTIME, instead of accessing only bn->top, all the limbs of the BIGNUM are accessed up to bn->dmax and bitwise masking is used to avoid branching. Memory access pattern still leaks bn->dmax, the size of the lazily allocated buffer for representing the BIGNUM, which is inevitable with the current BIGNUM architecture: reading past bn->dmax would be an out-of-bound read. As such, it's the caller responsibility to ensure that bn->dmax does not leak secret information, by explicitly expanding the internal BIGNUM buffer to a public value sufficient to avoid any lazy reallocation while manipulating it: this should be already done at the top level alongside setting the BN_FLG_CONSTTIME. Thanks to David Schrammel and Samuel Weiser for reporting this issue through responsible disclosure. Reviewed-by: Matt Caswell Reviewed-by: Bernd Edlinger (Merged from https://github.com/openssl/openssl/pull/9511) (cherry picked from commit 8b44198b916015f77bef1befa26edb48ad8a0238) --- crypto/bn/bn_lib.c | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 279d9c2488..082abe220e 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -132,13 +132,57 @@ int BN_num_bits_word(BN_ULONG l) return bits; } +/* + * This function still leaks `a->dmax`: it's caller's responsibility to + * expand the input `a` in advance to a public length. + */ +static ossl_inline +int bn_num_bits_consttime(const BIGNUM *a) +{ + int j, ret; + unsigned int mask, past_i; + int i = a->top - 1; + bn_check_top(a); + + for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) { + mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */ + + ret += BN_BITS2 & (~mask & ~past_i); + ret += BN_num_bits_word(a->d[j]) & mask; + + past_i |= mask; /* past_i will become 0xff..ff after i==j */ + } + + /* + * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the + * final result. + */ + mask = ~(constant_time_eq_int(i, ((int)-1))); + + return ret & mask; +} + int BN_num_bits(const BIGNUM *a) { int i = a->top - 1; bn_check_top(a); + if (a->flags & BN_FLG_CONSTTIME) { + /* + * We assume that BIGNUMs flagged as CONSTTIME have also been expanded + * so that a->dmax is not leaking secret information. + * + * In other words, it's the caller's responsibility to ensure `a` has + * been preallocated in advance to a public length if we hit this + * branch. + * + */ + return bn_num_bits_consttime(a); + } + if (BN_is_zero(a)) return 0; + return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); } -- 2.25.1