From 66509ddbd00179e8be58d54cf5576fb6b74d0131 Mon Sep 17 00:00:00 2001 From: David Benjamin Date: Tue, 23 Jan 2018 13:46:53 -0500 Subject: [PATCH] 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 Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/5154) (cherry picked from commit 972c87dfc7e765bd28a4964519c362f0d3a58ca4) --- crypto/bn/bn_lib.c | 107 +++++++++++++++++---------------------------- 1 file changed, 40 insertions(+), 67 deletions(-) diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 10b78f5126..27b9bdbc3c 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -144,74 +144,47 @@ const BIGNUM *BN_value_one(void) int BN_num_bits_word(BN_ULONG l) { - static const unsigned char bits[256] = { - 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, - 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - }; - -#if defined(SIXTY_FOUR_BIT_LONG) - if (l & 0xffffffff00000000L) { - if (l & 0xffff000000000000L) { - if (l & 0xff00000000000000L) { - return (bits[(int)(l >> 56)] + 56); - } else - return (bits[(int)(l >> 48)] + 48); - } else { - if (l & 0x0000ff0000000000L) { - return (bits[(int)(l >> 40)] + 40); - } else - return (bits[(int)(l >> 32)] + 32); - } - } else -#else -# ifdef SIXTY_FOUR_BIT - if (l & 0xffffffff00000000LL) { - if (l & 0xffff000000000000LL) { - if (l & 0xff00000000000000LL) { - return (bits[(int)(l >> 56)] + 56); - } else - return (bits[(int)(l >> 48)] + 48); - } else { - if (l & 0x0000ff0000000000LL) { - return (bits[(int)(l >> 40)] + 40); - } else - return (bits[(int)(l >> 32)] + 32); - } - } else -# endif -#endif - { -#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) - if (l & 0xffff0000L) { - if (l & 0xff000000L) - return (bits[(int)(l >> 24L)] + 24); - else - return (bits[(int)(l >> 16L)] + 16); - } else + BN_ULONG x, mask; + int bits = (l != 0); + +#if BN_BITS2 > 32 + x = l >> 32; + mask = (0 - x) & BN_MASK2; + mask = (0 - (mask >> (BN_BITS2 - 1))); + bits += 32 & mask; + l ^= (x ^ l) & mask; #endif - { -#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) - if (l & 0xff00L) - return (bits[(int)(l >> 8)] + 8); - else -#endif - return (bits[(int)(l)]); - } - } + + x = l >> 16; + mask = (0 - x) & BN_MASK2; + mask = (0 - (mask >> (BN_BITS2 - 1))); + bits += 16 & mask; + l ^= (x ^ l) & mask; + + x = l >> 8; + mask = (0 - x) & BN_MASK2; + mask = (0 - (mask >> (BN_BITS2 - 1))); + bits += 8 & mask; + l ^= (x ^ l) & mask; + + x = l >> 4; + mask = (0 - x) & BN_MASK2; + mask = (0 - (mask >> (BN_BITS2 - 1))); + bits += 4 & mask; + l ^= (x ^ l) & mask; + + x = l >> 2; + mask = (0 - x) & BN_MASK2; + mask = (0 - (mask >> (BN_BITS2 - 1))); + bits += 2 & mask; + l ^= (x ^ l) & mask; + + x = l >> 1; + mask = (0 - x) & BN_MASK2; + mask = (0 - (mask >> (BN_BITS2 - 1))); + bits += 1 & mask; + + return bits; } int BN_num_bits(const BIGNUM *a) -- 2.25.1