Make BN_num_bits_word constant-time.
authorDavid Benjamin <davidben@google.com>
Tue, 23 Jan 2018 18:46:53 +0000 (13:46 -0500)
committerAndy Polyakov <appro@openssl.org>
Thu, 1 Feb 2018 20:45:40 +0000 (21:45 +0100)
commit0b9373ce3c2d39d9a88634913b8191ad4f7a453c
treeb4e363504c9162fba064ff51a31f9227d882cabb
parentd8adfdcd2e5de23f3e1d1a1d10c2fda6f4a65c4a
Make BN_num_bits_word constant-time.

(This patch was written by Andy Polyakov. I only wrote the commit
message. Mistakes in the analysis are my fault.)

BN_num_bits, by way of BN_num_bits_word, currently leaks the
most-significant word of its argument via branching and memory access
pattern.

BN_num_bits is called on RSA prime factors in various places. These have
public bit lengths, but all bits beyond the high bit are secret. This
fully resolves those cases.

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. Today, that is guaranteed to be
non-zero, but only because of the long-standing bn_correct_top timing
leak. Once that is fixed, a constant-time BN_num_bits on such inputs
must count bits on each word.

Instead, those cases should not call BN_num_bits at all. In particular,
BN_mod_exp_mont_consttime uses the exponent bit width to pick windows,
but it should be using the maximum bit width. The next patch will fix
this.

Thanks to Dinghao Wu, Danfeng Zhang, Shuai Wang, Pei Wang, and Xiao Liu
for reporting this issue.

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 972c87dfc7e765bd28a4964519c362f0d3a58ca4)
crypto/bn/bn_lib.c