external/boringssl: Sync to 21baf6421a7e1e03f85cf2243c3c2404f5765072.

This includes the following changes:

https://boringssl.googlesource.com/boringssl/+log/a5462d3050ac6a68ab488450bf5856475dbef992..21baf6421a7e1e03f85cf2243c3c2404f5765072

Test: BoringSSL CTS Presubmits
Change-Id: I7081a7bead0260f9790e3af70bc23dba42ddb156

1 files changed, 66 insertions, 43 deletions

diff --git a/src/crypto/fipsmodule/ecdsa/ecdsa.c b/src/crypto/fipsmodule/ecdsa/ecdsa.c
index 319a934e..6571c941 100644
--- a/src/crypto/fipsmodule/ecdsa/ecdsa.c
+++ b/src/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -66,10 +66,53 @@
 #include "../../internal.h"
 
 
+// EC_LOOSE_SCALAR is like |EC_SCALAR| but is bounded by 2^|BN_num_bits(order)|
+// rather than |order|.
+typedef union {
+  // bytes is the representation of the scalar in little-endian order.
+  uint8_t bytes[EC_MAX_SCALAR_BYTES];
+  BN_ULONG words[EC_MAX_SCALAR_WORDS];
+} EC_LOOSE_SCALAR;
+
+static void scalar_add_loose(const EC_GROUP *group, EC_LOOSE_SCALAR *r,
+                             const EC_LOOSE_SCALAR *a, const EC_SCALAR *b) {
+  // Add and subtract one copy of |order| if necessary. We have:
+  //   |a| + |b| < 2^BN_num_bits(order) + order
+  // so this leaves |r| < 2^BN_num_bits(order).
+  const BIGNUM *order = &group->order;
+  BN_ULONG carry = bn_add_words(r->words, a->words, b->words, order->top);
+  EC_LOOSE_SCALAR tmp;
+  BN_ULONG v = bn_sub_words(tmp.words, r->words, order->d, order->top) - carry;
+  v = 0u - v;
+  for (int i = 0; i < order->top; i++) {
+    OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
+                           crypto_word_t_too_small);
+    r->words[i] = constant_time_select_w(v, r->words[i], tmp.words[i]);
+  }
+}
+
+static int scalar_mod_mul_montgomery(const EC_GROUP *group, EC_SCALAR *r,
+                                     const EC_SCALAR *a, const EC_SCALAR *b) {
+  const BIGNUM *order = &group->order;
+  return bn_mod_mul_montgomery_small(r->words, order->top, a->words, order->top,
+                                     b->words, order->top, group->order_mont);
+}
+
+static int scalar_mod_mul_montgomery_loose(const EC_GROUP *group, EC_SCALAR *r,
+                                           const EC_LOOSE_SCALAR *a,
+                                           const EC_SCALAR *b) {
+  // Although |a| is loose, |bn_mod_mul_montgomery_small| only requires the
+  // product not exceed R * |order|. |b| is fully reduced and |a| <
+  // 2^BN_num_bits(order) <= R, so this holds.
+  const BIGNUM *order = &group->order;
+  return bn_mod_mul_montgomery_small(r->words, order->top, a->words, order->top,
+                                     b->words, order->top, group->order_mont);
+}
+
 // digest_to_scalar interprets |digest_len| bytes from |digest| as a scalar for
 // ECDSA. Note this value is not fully reduced modulo the order, only the
 // correct number of bits.
-static void digest_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
+static void digest_to_scalar(const EC_GROUP *group, EC_LOOSE_SCALAR *out,
                              const uint8_t *digest, size_t digest_len) {
   const BIGNUM *order = &group->order;
   size_t num_bits = BN_num_bits(order);
@@ -195,15 +238,12 @@ int ECDSA_do_verify(const uint8_t *digest, size_t digest_len,
     goto err;
   }
 
-  EC_SCALAR r, s, m, u1, u2, s_inv_mont;
+  EC_SCALAR r, s, u1, u2, s_inv_mont;
+  EC_LOOSE_SCALAR m;
   const BIGNUM *order = EC_GROUP_get0_order(group);
   if (BN_is_zero(sig->r) ||
-      BN_is_negative(sig->r) ||
-      BN_ucmp(sig->r, order) >= 0 ||
       !ec_bignum_to_scalar(group, &r, sig->r) ||
       BN_is_zero(sig->s) ||
-      BN_is_negative(sig->s) ||
-      BN_ucmp(sig->s, order) >= 0 ||
       !ec_bignum_to_scalar(group, &s, sig->s)) {
     OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE);
     goto err;
@@ -212,26 +252,21 @@ int ECDSA_do_verify(const uint8_t *digest, size_t digest_len,
   // the products below.
   int no_inverse;
   if (!BN_mod_inverse_odd(X, &no_inverse, sig->s, order, ctx) ||
-      !ec_bignum_to_scalar(group, &s_inv_mont, X) ||
+      // TODO(davidben): Add a words version of |BN_mod_inverse_odd| and write
+      // into |s_inv_mont| directly.
+      !ec_bignum_to_scalar_unchecked(group, &s_inv_mont, X) ||
       !bn_to_montgomery_small(s_inv_mont.words, order->top, s_inv_mont.words,
                               order->top, group->order_mont)) {
     goto err;
   }
-  // u1 = m * s_inv_mont mod order
-  // u2 = r * s_inv_mont mod order
+  // u1 = m * s^-1 mod order
+  // u2 = r * s^-1 mod order
   //
   // |s_inv_mont| is in Montgomery form while |m| and |r| are not, so |u1| and
-  // |u2| will be taken out of Montgomery form, as desired. Note that, although
-  // |m| is not fully reduced, |bn_mod_mul_montgomery_small| only requires the
-  // product not exceed R * |order|. |s_inv_mont| is fully reduced and |m| <
-  // 2^BN_num_bits(order) <= R, so this holds.
+  // |u2| will be taken out of Montgomery form, as desired.
   digest_to_scalar(group, &m, digest, digest_len);
-  if (!bn_mod_mul_montgomery_small(u1.words, order->top, m.words, order->top,
-                                   s_inv_mont.words, order->top,
-                                   group->order_mont) ||
-      !bn_mod_mul_montgomery_small(u2.words, order->top, r.words, order->top,
-                                   s_inv_mont.words, order->top,
-                                   group->order_mont)) {
+  if (!scalar_mod_mul_montgomery_loose(group, &u1, &m, &s_inv_mont) ||
+      !scalar_mod_mul_montgomery(group, &u2, &r, &s_inv_mont)) {
     goto err;
   }
 
@@ -368,14 +403,17 @@ ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len,
   int ok = 0;
   ECDSA_SIG *ret = ECDSA_SIG_new();
   BN_CTX *ctx = BN_CTX_new();
-  EC_SCALAR kinv_mont, priv_key, r_mont, s, tmp, m;
+  EC_SCALAR kinv_mont, priv_key, r_mont, s;
+  EC_LOOSE_SCALAR m, tmp;
   if (ret == NULL || ctx == NULL) {
     OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE);
     return NULL;
   }
 
   digest_to_scalar(group, &m, digest, digest_len);
-  if (!ec_bignum_to_scalar(group, &priv_key, priv_key_bn)) {
+  // TODO(davidben): Store the private key as an |EC_SCALAR| so this is obvious
+  // via the type system.
+  if (!ec_bignum_to_scalar_unchecked(group, &priv_key, priv_key_bn)) {
     goto err;
   }
   for (;;) {
@@ -385,36 +423,21 @@ ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len,
     }
 
     // Compute priv_key * r (mod order). Note if only one parameter is in the
-    // Montgomery domain, |bn_mod_mul_montgomery_small| will compute the answer
-    // in the normal domain.
+    // Montgomery domain, |scalar_mod_mul_montgomery| will compute the answer in
+    // the normal domain.
     if (!ec_bignum_to_scalar(group, &r_mont, ret->r) ||
         !bn_to_montgomery_small(r_mont.words, order->top, r_mont.words,
                                 order->top, group->order_mont) ||
-        !bn_mod_mul_montgomery_small(s.words, order->top, priv_key.words,
-                                     order->top, r_mont.words, order->top,
-                                     group->order_mont)) {
+        !scalar_mod_mul_montgomery(group, &s, &priv_key, &r_mont)) {
       goto err;
     }
 
-    // Compute s += m in constant time. Reduce one copy of |order| if necessary.
-    // Note this does not leave |s| fully reduced. We have
-    // |m| < 2^BN_num_bits(order), so subtracting |order| leaves
-    // 0 <= |s| < 2^BN_num_bits(order).
-    BN_ULONG carry = bn_add_words(s.words, s.words, m.words, order->top);
-    BN_ULONG v = bn_sub_words(tmp.words, s.words, order->d, order->top) - carry;
-    v = 0u - v;
-    for (int i = 0; i < order->top; i++) {
-      s.words[i] = constant_time_select_w(v, s.words[i], tmp.words[i]);
-    }
+    // Compute tmp = m + priv_key * r.
+    scalar_add_loose(group, &tmp, &m, &s);
 
     // Finally, multiply s by k^-1. That was retained in Montgomery form, so the
-    // same technique as the previous multiplication works. Although the
-    // previous step did not fully reduce |s|, |bn_mod_mul_montgomery_small|
-    // only requires the product not exceed R * |order|. |kinv_mont| is fully
-    // reduced and |s| < 2^BN_num_bits(order) <= R, so this holds.
-    if (!bn_mod_mul_montgomery_small(s.words, order->top, s.words, order->top,
-                                     kinv_mont.words, order->top,
-                                     group->order_mont) ||
+    // same technique as the previous multiplication works.
+    if (!scalar_mod_mul_montgomery_loose(group, &s, &tmp, &kinv_mont) ||
         !bn_set_words(ret->s, s.words, order->top)) {
       goto err;
     }