diff options
author | Nicola Tuveri <nic.tuv@gmail.com> | 2019-08-02 02:08:34 +0300 |
---|---|---|
committer | Nicola Tuveri <nic.tuv@gmail.com> | 2019-09-07 02:06:29 +0300 |
commit | 8b44198b916015f77bef1befa26edb48ad8a0238 (patch) | |
tree | d46a094a6235c0f8ed97f0c5b23127426bdc13a3 /crypto/bn | |
parent | 805315d3a20f7274195eed75b06c391dacf3b197 (diff) |
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 <matt@openssl.org>
Reviewed-by: Bernd Edlinger <bernd.edlinger@hotmail.de>
(Merged from https://github.com/openssl/openssl/pull/9511)
Diffstat (limited to 'crypto/bn')
-rw-r--r-- | crypto/bn/bn_lib.c | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 5719a00ebf..f2d74d96d3 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])); } |