From a58a6d90c7fa6ece9183c620ed89abddbd00699d Mon Sep 17 00:00:00 2001
From: tb <>
Date: Mon, 17 Jun 2019 17:11:48 +0000
Subject: Make BN_num_bits_word() constant time.

Previously, this function would leak the most significant word of its
argument due to branching and memory access pattern.  This patch is
enough to fix the use of BN_num_bits() on RSA prime factors in the
library.

The diff is a simplified and more readable (but perhaps less efficient)
version of https://github.com/openssl/openssl/commit/972c87df
by Andy Polyakov and David Benjamin (pre license change). Consult that
commit message for details. Subsequent fixes to follow in the near future.

Issue pointed out by David Schrammel and Samuel Weiser as part of
a larger report.

tests & ok inoguchi, ok jsing
---
 src/lib/libcrypto/bn/bn_lib.c | 66 ++++++++++++-------------------------------
 1 file changed, 18 insertions(+), 48 deletions(-)

diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c
index 0025cf52ef..1a91b9e60c 100644
--- a/src/lib/libcrypto/bn/bn_lib.c
+++ b/src/lib/libcrypto/bn/bn_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_lib.c,v 1.46 2019/03/23 18:48:15 beck Exp $ */
+/* $OpenBSD: bn_lib.c,v 1.47 2019/06/17 17:11:48 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -151,53 +151,23 @@ 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,
-	};
-
-#ifdef _LP64
-	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
-#endif
-	{
-		if (l & 0xffff0000L) {
-			if (l & 0xff000000L)
-				return (bits[(int)(l >> 24L)] + 24);
-			else
-				return (bits[(int)(l >> 16L)] + 16);
-		} else {
-			if (l & 0xff00L)
-				return (bits[(int)(l >> 8)] + 8);
-			else
-				return (bits[(int)(l)]);
-		}
-	}
+	BN_ULONG x, mask;
+	int bits;
+	unsigned int shift;
+
+	/* Constant time calculation of floor(log2(l)) + 1. */
+	bits = (l != 0);
+	shift = BN_BITS4;	/* On _LP64 this is 32, otherwise 16. */
+	do {
+		x = l >> shift;
+		/* If x is 0, set mask to 0, otherwise set it to all 1s. */
+		mask = ((~x & (x - 1)) >> (BN_BITS2 - 1)) - 1;
+		bits += shift & mask;
+		/* If x is 0, leave l alone, otherwise set l = x. */
+		l ^= (x ^ l) & mask;
+	} while ((shift /= 2) != 0);
+
+	return bits;
 }
 
 int
-- 
cgit v1.2.3-55-g6feb