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/9793)

1 files changed, 45 insertions, 0 deletions

diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c
index 2a84698af8..8d9d8b32de 100644
--- a/crypto/bn/bn_lib.c
+++ b/crypto/bn/bn_lib.c
@@ -66,6 +66,7 @@
 #include <stdio.h>
 #include "cryptlib.h"
 #include "bn_lcl.h"
+#include "constant_time_locl.h"
 
 const char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT;
 
@@ -187,13 +188,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 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]));
 }