Add initial support for non-minimal BIGNUMs.

Thanks to Andres Erbsen for extremely helpful suggestions on how finally
plug this long-standing hole!

OpenSSL BIGNUMs are currently minimal-width, which means they cannot be
constant-time. We'll need to either excise BIGNUM from RSA and EC or
somehow fix BIGNUM. EC_SCALAR and later EC_FELEM work will excise it
from EC, but RSA's BIGNUMs are more transparent.  Teaching BIGNUM to
handle non-minimal word widths is probably simpler.

The main constraint is BIGNUM's large "calculator" API surface. One
could, in theory, do arbitrary math on RSA components, which means all
public functions must tolerate non-minimal inputs. This is also useful
for EC; https://boringssl-review.googlesource.com/c/boringssl/+/24445 is
silly.

As a first step, fix comparison-type functions that were assuming
minimal BIGNUMs. I've also added bn_resize_words, but it is testing-only
until the rest of the library is fixed.

bn->top is now a loose upper bound we carry around. It does not affect
numerical results, only performance and secrecy. This is a departure
from the original meaning, and compiler help in auditing everything is
nice, so the final change in this series will rename bn->top to
bn->width. Thus these new functions are named per "width", not "top".

Looking further ahead, how are output BIGNUM widths determined? There's
three notions of correctness here:

1. Do I compute the right answer for all widths?

2. Do I handle secret data in constant time?

3. Does my memory usage not balloon absurdly?

For (1), a BIGNUM function must give the same answer for all input
widths. BN_mod_add_quick may assume |a| < |m|, but |a| may still be
wider than |m| by way of leading zeres. The simplest approach is to
write code in a width-agnostic way and rely on functions to accept all
widths. Where functions need to look at bn->d, we'll a few helper
functions to smooth over funny widths.

For (2), (1) is little cumbersome. Consider constant-time modular
addition. A sane type system would guarantee input widths match. But C
is weak here, and bifurcating the internals is a lot of work. Thus, at
least for now, I do not propose we move RSA's internal computation out
of BIGNUM. (EC_SCALAR/EC_FELEM are valuable for EC because we get to
stack-allocate, curves were already specialized, and EC only has two
types with many operations on those types. None of these apply to RSA.
We've got numbers mod n, mod p, mod q, and their corresponding
exponents, each of which is used for basically one operation.)

Instead, constant-time BIGNUM functions will output non-minimal widths.
This is trivial for BN_bin2bn or modular arithmetic. But for BN_mul,
constant-time[*] would dictate r->top = a->top + b->top. A calculator
repeatedly multiplying by one would then run out of memory.  Those we'll
split into a private BN_mul_fixed for crypto, leaving BN_mul for
calculators. BN_mul is just BN_mul_fixed followed by bn_correct_top.

[*] BN_mul is not constant-time for other reasons, but that will be
fixed separately.

Bug: 232
Change-Id: Ide2258ae8c09a9a41bb71d6777908d1c27917069
Reviewed-on: https://boringssl-review.googlesource.com/25244
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/bn.c b/crypto/fipsmodule/bn/bn.c
index 4be4f21..70f98c8 100644
--- a/crypto/fipsmodule/bn/bn.c
+++ b/crypto/fipsmodule/bn/bn.c
@@ -227,13 +227,12 @@
 }
 
 unsigned BN_num_bits(const BIGNUM *bn) {
-  const int max = bn->top - 1;
-
-  if (BN_is_zero(bn)) {
+  const int width = bn_minimal_width(bn);
+  if (width == 0) {
     return 0;
   }
 
-  return max*BN_BITS2 + BN_num_bits_word(bn->d[max]);
+  return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]);
 }
 
 unsigned BN_num_bytes(const BIGNUM *bn) {
@@ -350,19 +349,39 @@
   return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
 }
 
-void bn_correct_top(BIGNUM *bn) {
-  BN_ULONG *ftl;
-  int tmp_top = bn->top;
-
-  if (tmp_top > 0) {
-    for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) {
-      if (*(ftl--)) {
-        break;
-      }
+int bn_resize_words(BIGNUM *bn, size_t words) {
+  if ((size_t)bn->top <= words) {
+    if (!bn_wexpand(bn, words)) {
+      return 0;
     }
-    bn->top = tmp_top;
+    OPENSSL_memset(bn->d + bn->top, 0, (words - bn->top) * sizeof(BN_ULONG));
+    bn->top = words;
+    return 1;
   }
 
+  // All words beyond the new width must be zero.
+  BN_ULONG mask = 0;
+  for (size_t i = words; i < (size_t)bn->top; i++) {
+    mask |= bn->d[i];
+  }
+  if (mask != 0) {
+    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
+    return 0;
+  }
+  bn->top = words;
+  return 1;
+}
+
+int bn_minimal_width(const BIGNUM *bn) {
+  int ret = bn->top;
+  while (ret > 0 && bn->d[ret - 1] == 0) {
+    ret--;
+  }
+  return ret;
+}
+
+void bn_correct_top(BIGNUM *bn) {
+  bn->top = bn_minimal_width(bn);
   if (bn->top == 0) {
     bn->neg = 0;
   }
diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index ca5f978..8e6f4eb 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -1883,4 +1883,61 @@
   EXPECT_EQ(0, bn_less_than_words(NULL, NULL, 0));
   EXPECT_EQ(0, bn_in_range_words(NULL, 0, NULL, 0));
 }
+
+TEST_F(BNTest, NonMinimal) {
+  bssl::UniquePtr<BIGNUM> ten(BN_new());
+  ASSERT_TRUE(ten);
+  ASSERT_TRUE(BN_set_word(ten.get(), 10));
+  bssl::UniquePtr<BIGNUM> ten_copy(BN_dup(ten.get()));
+  ASSERT_TRUE(ten_copy);
+  bssl::UniquePtr<BIGNUM> eight(BN_new());
+  ASSERT_TRUE(eight);
+  ASSERT_TRUE(BN_set_word(eight.get(), 8));
+
+  // Check some comparison functions on |ten|.
+  EXPECT_TRUE(BN_abs_is_word(ten.get(), 10));
+  EXPECT_TRUE(BN_is_word(ten.get(), 10));
+  EXPECT_EQ(10u, BN_get_word(ten.get()));
+  uint64_t v;
+  ASSERT_TRUE(BN_get_u64(ten.get(), &v));
+  EXPECT_EQ(10u, v);
+  EXPECT_TRUE(BN_equal_consttime(ten.get(), ten_copy.get()));
+  EXPECT_EQ(BN_cmp(ten.get(), ten_copy.get()), 0);
+  EXPECT_FALSE(BN_equal_consttime(ten.get(), eight.get()));
+  EXPECT_LT(BN_cmp(eight.get(), ten.get()), 0);
+  EXPECT_EQ(4u, BN_num_bits(ten.get()));
+  EXPECT_EQ(1u, BN_num_bytes(ten.get()));
+  EXPECT_FALSE(BN_is_pow2(ten.get()));
+
+  // Make a wider version of |ten|.
+  EXPECT_TRUE(bn_resize_words(ten.get(), 4));
+  EXPECT_EQ(4, ten->top);
+
+  // The same properties hold.
+  EXPECT_TRUE(BN_abs_is_word(ten.get(), 10));
+  EXPECT_TRUE(BN_is_word(ten.get(), 10));
+  EXPECT_EQ(10u, BN_get_word(ten.get()));
+  ASSERT_TRUE(BN_get_u64(ten.get(), &v));
+  EXPECT_EQ(10u, v);
+  EXPECT_TRUE(BN_equal_consttime(ten.get(), ten_copy.get()));
+  EXPECT_EQ(BN_cmp(ten.get(), ten_copy.get()), 0);
+  EXPECT_FALSE(BN_equal_consttime(ten.get(), eight.get()));
+  EXPECT_LT(BN_cmp(eight.get(), ten.get()), 0);
+  EXPECT_EQ(4u, BN_num_bits(ten.get()));
+  EXPECT_EQ(1u, BN_num_bytes(ten.get()));
+  EXPECT_FALSE(BN_is_pow2(ten.get()));
+
+  // |ten| may be resized back down to one word.
+  EXPECT_TRUE(bn_resize_words(ten.get(), 1));
+  EXPECT_EQ(1, ten->top);
+
+  // But not to zero words, which it does not fit.
+  EXPECT_FALSE(bn_resize_words(ten.get(), 0));
+
+  EXPECT_TRUE(BN_is_pow2(eight.get()));
+  EXPECT_TRUE(bn_resize_words(eight.get(), 4));
+  EXPECT_EQ(4, eight->top);
+  EXPECT_TRUE(BN_is_pow2(eight.get()));
+}
+
 #endif  // !BORINGSSL_SHARED_LIBRARY
diff --git a/crypto/fipsmodule/bn/bytes.c b/crypto/fipsmodule/bn/bytes.c
index 328d56e..887f526 100644
--- a/crypto/fipsmodule/bn/bytes.c
+++ b/crypto/fipsmodule/bn/bytes.c
@@ -240,7 +240,7 @@
 }
 
 BN_ULONG BN_get_word(const BIGNUM *bn) {
-  switch (bn->top) {
+  switch (bn_minimal_width(bn)) {
     case 0:
       return 0;
     case 1:
@@ -251,7 +251,7 @@
 }
 
 int BN_get_u64(const BIGNUM *bn, uint64_t *out) {
-  switch (bn->top) {
+  switch (bn_minimal_width(bn)) {
     case 0:
       *out = 0;
       return 1;
diff --git a/crypto/fipsmodule/bn/cmp.c b/crypto/fipsmodule/bn/cmp.c
index acc017f..3a5bbb2 100644
--- a/crypto/fipsmodule/bn/cmp.c
+++ b/crypto/fipsmodule/bn/cmp.c
@@ -64,19 +64,18 @@
 
 
 int BN_ucmp(const BIGNUM *a, const BIGNUM *b) {
-  int i;
-  BN_ULONG t1, t2, *ap, *bp;
-
-  i = a->top - b->top;
+  int a_width = bn_minimal_width(a);
+  int b_width = bn_minimal_width(b);
+  int i = a_width - b_width;
   if (i != 0) {
     return i;
   }
 
-  ap = a->d;
-  bp = b->d;
-  for (i = a->top - 1; i >= 0; i--) {
-    t1 = ap[i];
-    t2 = bp[i];
+  const BN_ULONG *ap = a->d;
+  const BN_ULONG *bp = b->d;
+  for (i = a_width - 1; i >= 0; i--) {
+    BN_ULONG t1 = ap[i];
+    BN_ULONG t2 = bp[i];
     if (t1 != t2) {
       return (t1 > t2) ? 1 : -1;
     }
@@ -114,14 +113,16 @@
     lt = 1;
   }
 
-  if (a->top > b->top) {
+  int a_width = bn_minimal_width(a);
+  int b_width = bn_minimal_width(b);
+  if (a_width > b_width) {
     return gt;
   }
-  if (a->top < b->top) {
+  if (a_width < b_width) {
     return lt;
   }
 
-  for (i = a->top - 1; i >= 0; i--) {
+  for (i = a_width - 1; i >= 0; i--) {
     t1 = a->d[i];
     t2 = b->d[i];
     if (t1 > t2) {
@@ -190,7 +191,7 @@
 }
 
 int BN_abs_is_word(const BIGNUM *bn, BN_ULONG w) {
-  switch (bn->top) {
+  switch (bn_minimal_width(bn)) {
     case 1:
       return bn->d[0] == w;
     case 0:
@@ -212,7 +213,7 @@
 }
 
 int BN_is_zero(const BIGNUM *bn) {
-  return bn->top == 0;
+  return bn_minimal_width(bn) == 0;
 }
 
 int BN_is_one(const BIGNUM *bn) {
@@ -228,27 +229,35 @@
 }
 
 int BN_is_pow2(const BIGNUM *bn) {
-  if (bn->top == 0 || bn->neg) {
+  int width = bn_minimal_width(bn);
+  if (width == 0 || bn->neg) {
     return 0;
   }
 
-  for (int i = 0; i < bn->top - 1; i++) {
+  for (int i = 0; i < width - 1; i++) {
     if (bn->d[i] != 0) {
       return 0;
     }
   }
 
-  return 0 == (bn->d[bn->top-1] & (bn->d[bn->top-1] - 1));
+  return 0 == (bn->d[width-1] & (bn->d[width-1] - 1));
 }
 
 int BN_equal_consttime(const BIGNUM *a, const BIGNUM *b) {
-  if (a->top != b->top) {
-    return 0;
+  BN_ULONG mask = 0;
+  // If |a| or |b| has more words than the other, all those words must be zero.
+  for (int i = a->top; i < b->top; i++) {
+    mask |= b->d[i];
   }
-
-  int limbs_are_equal =
-    CRYPTO_memcmp(a->d, b->d, (size_t)a->top * sizeof(a->d[0])) == 0;
-
-  return constant_time_select_int(constant_time_eq_int(a->neg, b->neg),
-                                  limbs_are_equal, 0);
+  for (int i = b->top; i < a->top; i++) {
+    mask |= a->d[i];
+  }
+  // Common words must match.
+  int min = a->top < b->top ? a->top : b->top;
+  for (int i = 0; i < min; i++) {
+    mask |= (a->d[i] ^ b->d[i]);
+  }
+  // The sign bit must match.
+  mask |= (a->neg ^ b->neg);
+  return mask == 0;
 }
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index 706e544..1a5dc1b 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -197,8 +197,12 @@
 #define Hw(t) ((BN_ULONG)((t) >> BN_BITS2))
 #endif
 
-// bn_correct_top decrements |bn->top| until |bn->d[top-1]| is non-zero or
-// until |top| is zero. If |bn| is zero, |bn->neg| is set to zero.
+// bn_minimal_width returns the minimal value of |bn->top| which fits the
+// value of |bn|.
+int bn_minimal_width(const BIGNUM *bn);
+
+// bn_correct_top decrements |bn->top| to |bn_minimal_width|. If |bn| is zero,
+// |bn->neg| is set to zero.
 void bn_correct_top(BIGNUM *bn);
 
 // bn_wexpand ensures that |bn| has at least |words| works of space without
@@ -210,6 +214,14 @@
 // than a number of words.
 int bn_expand(BIGNUM *bn, size_t bits);
 
+// bn_resize_words adjusts |bn->top| to be |words|. It returns one on success
+// and zero on allocation error or if |bn|'s value is too large.
+//
+// Do not call this function outside of unit tests. Most functions currently
+// require |BIGNUM|s be minimal. This function breaks that invariant. It is
+// introduced early so the invariant may be relaxed incrementally.
+int bn_resize_words(BIGNUM *bn, size_t words);
+
 // bn_set_words sets |bn| to the value encoded in the |num| words in |words|,
 // least significant word first.
 int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num);