Don't leak the exponent bit width in BN_mod_exp_mont_consttime.
authorDavid Benjamin <davidben@google.com>
Tue, 23 Jan 2018 18:57:10 +0000 (13:57 -0500)
committerAndy Polyakov <appro@openssl.org>
Thu, 1 Feb 2018 20:45:52 +0000 (21:45 +0100)
commit723183b5640e9b047acac189c7c7fb78575522d4
tree1ec4b537f34540e05daae459043c52c54ff65515
parent0b9373ce3c2d39d9a88634913b8191ad4f7a453c
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 <paul.dale@oracle.com>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/5154)

(cherry picked from commit 39eeb64f59ff838f976ad305de7d15747d47a41c)
crypto/bn/bn_exp.c