Add |BN_mod_inverse_blinded| and use it in RSA blinding.

Yo dawg I herd you like blinding so I put inversion blinding in your
RSA blinding so you can randomly mask your random mask.

This improves upon the current situation where we pretend that
|BN_mod_inverse_no_branch| is constant-time, and it avoids the need to
exert a lot of effort to make a actually-constant-time modular
inversion function just for RSA blinding.

Note that if the random number generator weren't working correctly then
the blinding of the inversion wouldn't be very effective, but in that
case the RSA blinding itself would probably be completely busted, so
we're not really losing anything by relying on blinding to blind the
blinding.

Change-Id: I771100f0ad8ed3c24e80dd859ec22463ef2a194f
Reviewed-on: https://boringssl-review.googlesource.com/8923
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>

2 files changed, 70 insertions, 32 deletions

diff --git a/crypto/bn/gcd.c b/crypto/bn/gcd.c
index 52db5698..0cc18d91 100644
--- a/crypto/bn/gcd.c
+++ b/crypto/bn/gcd.c
@@ -227,17 +227,13 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *out, int *out_no_inverse,
                                         const BIGNUM *a, const BIGNUM *n,
                                         BN_CTX *ctx);
 
-BIGNUM *BN_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
-                          const BIGNUM *n, BN_CTX *ctx) {
+static BIGNUM *bn_mod_inverse_ex(BIGNUM *out, int *out_no_inverse,
+                                 const BIGNUM *a, const BIGNUM *n,
+                                 BN_CTX *ctx) {
   BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
   BIGNUM *ret = NULL;
   int sign;
 
-  if ((a->flags & BN_FLG_CONSTTIME) != 0 ||
-      (n->flags & BN_FLG_CONSTTIME) != 0) {
-    return BN_mod_inverse_no_branch(out, out_no_inverse, a, n, ctx);
-  }
-
   *out_no_inverse = 0;
 
   BN_CTX_start(ctx);
@@ -266,11 +262,6 @@ BIGNUM *BN_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
     goto err;
   }
   A->neg = 0;
-  if (B->neg || (BN_ucmp(B, A) >= 0)) {
-    if (!BN_nnmod(B, B, A, ctx)) {
-      goto err;
-    }
-  }
   sign = -1;
   /* From  B = a mod |n|,  A = |n|  it follows that
    *
@@ -543,7 +534,57 @@ err:
 BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n,
                        BN_CTX *ctx) {
   int no_inverse;
-  return BN_mod_inverse_ex(out, &no_inverse, a, n, ctx);
+
+  if ((a->flags & BN_FLG_CONSTTIME) != 0 ||
+      (n->flags & BN_FLG_CONSTTIME) != 0) {
+    return BN_mod_inverse_no_branch(out, &no_inverse, a, n, ctx);
+  }
+
+  if (!a->neg && BN_ucmp(a, n) < 0) {
+    return bn_mod_inverse_ex(out, &no_inverse, a, n, ctx);
+  }
+
+  BIGNUM a_reduced;
+  BN_init(&a_reduced);
+  BIGNUM *ret = NULL;
+
+  if (!BN_nnmod(&a_reduced, a, n, ctx)) {
+    goto err;
+  }
+
+  ret = bn_mod_inverse_ex(out, &no_inverse, &a_reduced, n, ctx);
+
+err:
+  BN_free(&a_reduced);
+  return ret;
+}
+
+int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
+                           const BN_MONT_CTX *mont, BN_CTX *ctx) {
+  *out_no_inverse = 0;
+
+  if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) {
+    OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
+    return 0;
+  }
+
+  int ret = 0;
+  BIGNUM blinding_factor;
+  BN_init(&blinding_factor);
+
+  if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) ||
+      !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) ||
+      bn_mod_inverse_ex(out, out_no_inverse, out, &mont->N, ctx) == NULL ||
+      !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) {
+    OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
+    goto err;
+  }
+
+  ret = 1;
+
+err:
+  BN_free(&blinding_factor);
+  return ret;
 }
 
 /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse.
diff --git a/crypto/rsa/blinding.c b/crypto/rsa/blinding.c
index 71f2e6f8..0a485ee9 100644
--- a/crypto/rsa/blinding.c
+++ b/crypto/rsa/blinding.c
@@ -216,9 +216,6 @@ int BN_BLINDING_invert(BIGNUM *n, const BN_BLINDING *b, BN_MONT_CTX *mont,
 
 static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
                                     const BN_MONT_CTX *mont, BN_CTX *ctx) {
-  BIGNUM mont_N_consttime;
-  BN_init(&mont_N_consttime);
-  BN_with_flags(&mont_N_consttime, &mont->N, BN_FLG_CONSTTIME);
   int retry_counter = 32;
 
   do {
@@ -227,30 +224,30 @@ static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
       return 0;
     }
 
-    /* |BN_from_montgomery| + |BN_mod_inverse_no_branch| is equivalent to, but
-     * more efficient than, |BN_mod_inverse_no_branch| + |BN_to_montgomery|. */
+    /* |BN_from_montgomery| + |BN_mod_inverse_blinded| is equivalent to, but
+     * more efficient than, |BN_mod_inverse_blinded| + |BN_to_montgomery|. */
     if (!BN_from_montgomery(b->Ai, b->A, mont, ctx)) {
       OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
       return 0;
     }
 
     int no_inverse;
-    if (BN_mod_inverse_ex(b->Ai, &no_inverse, b->Ai, &mont_N_consttime, ctx) ==
-        NULL) {
-      /* this should almost never happen for good RSA keys */
-      if (no_inverse) {
-        if (retry_counter-- == 0) {
-          OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
-          return 0;
-        }
-        ERR_clear_error();
-      } else {
-        OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
-        return 0;
-      }
-    } else {
+    if (BN_mod_inverse_blinded(b->Ai, &no_inverse, b->Ai, mont, ctx)) {
       break;
     }
+
+    if (!no_inverse) {
+      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
+      return 0;
+    }
+
+    /* For reasonably-sized RSA keys, it should almost never be the case that a
+     * random value doesn't have an inverse. */
+    if (retry_counter-- == 0) {
+      OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
+      return 0;
+    }
+    ERR_clear_error();
   } while (1);
 
   if (!BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont)) {