1 files changed, 133 insertions, 120 deletions

diff --git a/crypto/rsa/rsa_impl.c b/crypto/rsa/rsa_impl.c
index ba310739..af44a3d5 100644
--- a/crypto/rsa/rsa_impl.c
+++ b/crypto/rsa/rsa_impl.c
@@ -56,6 +56,7 @@
 
 #include <openssl/rsa.h>
 
+#include <assert.h>
 #include <string.h>
 
 #include <openssl/bn.h>
@@ -69,21 +70,37 @@
 
 static int check_modulus_and_exponent_sizes(const RSA *rsa) {
   unsigned rsa_bits = BN_num_bits(rsa->n);
+
   if (rsa_bits > 16 * 1024) {
     OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
     return 0;
   }
 
-  if (BN_ucmp(rsa->n, rsa->e) <= 0) {
+  /* Mitigate DoS attacks by limiting the exponent size. 33 bits was chosen as
+   * the limit based on the recommendations in [1] and [2]. Windows CryptoAPI
+   * doesn't support values larger than 32 bits [3], so it is unlikely that
+   * exponents larger than 32 bits are being used for anything Windows commonly
+   * does.
+   *
+   * [1] https://www.imperialviolet.org/2012/03/16/rsae.html
+   * [2] https://www.imperialviolet.org/2012/03/17/rsados.html
+   * [3] https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx */
+  static const unsigned kMaxExponentBits = 33;
+
+  if (BN_num_bits(rsa->e) > kMaxExponentBits) {
     OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
     return 0;
   }
 
-  /* For large moduli only, enforce exponent limit. */
-  if (rsa_bits > 3072 && BN_num_bits(rsa->e) > 64) {
-    OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
+  /* Verify |n > e|. Comparing |rsa_bits| to |kMaxExponentBits| is a small
+   * shortcut to comparing |n| and |e| directly. In reality, |kMaxExponentBits|
+   * is much smaller than the minimum RSA key size that any application should
+   * accept. */
+  if (rsa_bits <= kMaxExponentBits) {
+    OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
     return 0;
   }
+  assert(BN_ucmp(rsa->n, rsa->e) > 0);
 
   return 1;
 }
@@ -154,13 +171,8 @@ int rsa_default_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
     goto err;
   }
 
-  if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
-    if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) == NULL) {
-      goto err;
-    }
-  }
-
-  if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
+  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
+      !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
     goto err;
   }
 
@@ -201,6 +213,9 @@ err:
  * |*index_used| and must be passed to |rsa_blinding_release| when finished. */
 static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
                                      BN_CTX *ctx) {
+  assert(ctx != NULL);
+  assert(rsa->mont_n != NULL);
+
   BN_BLINDING *ret = NULL;
   BN_BLINDING **new_blindings;
   uint8_t *new_blindings_inuse;
@@ -219,7 +234,7 @@ static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
   }
 
   if (ret != NULL) {
-    CRYPTO_MUTEX_unlock(&rsa->lock);
+    CRYPTO_MUTEX_unlock_write(&rsa->lock);
     return ret;
   }
 
@@ -228,8 +243,8 @@ static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
   /* We didn't find a free BN_BLINDING to use so increase the length of
    * the arrays by one and use the newly created element. */
 
-  CRYPTO_MUTEX_unlock(&rsa->lock);
-  ret = rsa_setup_blinding(rsa, ctx);
+  CRYPTO_MUTEX_unlock_write(&rsa->lock);
+  ret = BN_BLINDING_new();
   if (ret == NULL) {
     return NULL;
   }
@@ -266,14 +281,14 @@ static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
   rsa->blindings_inuse = new_blindings_inuse;
   rsa->num_blindings++;
 
-  CRYPTO_MUTEX_unlock(&rsa->lock);
+  CRYPTO_MUTEX_unlock_write(&rsa->lock);
   return ret;
 
 err2:
   OPENSSL_free(new_blindings);
 
 err1:
-  CRYPTO_MUTEX_unlock(&rsa->lock);
+  CRYPTO_MUTEX_unlock_write(&rsa->lock);
   BN_BLINDING_free(ret);
   return NULL;
 }
@@ -290,7 +305,7 @@ static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
 
   CRYPTO_MUTEX_lock_write(&rsa->lock);
   rsa->blindings_inuse[blinding_index] = 0;
-  CRYPTO_MUTEX_unlock(&rsa->lock);
+  CRYPTO_MUTEX_unlock_write(&rsa->lock);
 }
 
 /* signing */
@@ -409,33 +424,49 @@ err:
   return ret;
 }
 
-int rsa_default_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out,
-                           size_t max_out, const uint8_t *in, size_t in_len,
-                           int padding) {
+static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx);
+
+int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
+                   const uint8_t *in, size_t in_len, int padding) {
+  if (rsa->n == NULL || rsa->e == NULL) {
+    OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
+    return 0;
+  }
+
   const unsigned rsa_size = RSA_size(rsa);
   BIGNUM *f, *result;
-  int ret = 0;
   int r = -1;
-  uint8_t *buf = NULL;
-  BN_CTX *ctx = NULL;
 
   if (max_out < rsa_size) {
     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
     return 0;
   }
 
+  if (in_len != rsa_size) {
+    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
+    return 0;
+  }
+
   if (!check_modulus_and_exponent_sizes(rsa)) {
     return 0;
   }
 
-  ctx = BN_CTX_new();
+  BN_CTX *ctx = BN_CTX_new();
   if (ctx == NULL) {
-    goto err;
+    return 0;
   }
 
+  int ret = 0;
+  uint8_t *buf = NULL;
+
   BN_CTX_start(ctx);
   f = BN_CTX_get(ctx);
   result = BN_CTX_get(ctx);
+  if (f == NULL || result == NULL) {
+    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
+    goto err;
+  }
+
   if (padding == RSA_NO_PADDING) {
     buf = out;
   } else {
@@ -446,15 +477,6 @@ int rsa_default_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out,
       goto err;
     }
   }
-  if (!f || !result) {
-    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
-    goto err;
-  }
-
-  if (in_len != rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
-    goto err;
-  }
 
   if (BN_bin2bn(in, in_len, f) == NULL) {
     goto err;
@@ -465,13 +487,8 @@ int rsa_default_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out,
     goto err;
   }
 
-  if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
-    if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) == NULL) {
-      goto err;
-    }
-  }
-
-  if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
+  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
+      !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
     goto err;
   }
 
@@ -500,12 +517,9 @@ int rsa_default_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out,
   }
 
 err:
-  if (ctx != NULL) {
-    BN_CTX_end(ctx);
-    BN_CTX_free(ctx);
-  }
-  if (padding != RSA_NO_PADDING && buf != NULL) {
-    OPENSSL_cleanse(buf, rsa_size);
+  BN_CTX_end(ctx);
+  BN_CTX_free(ctx);
+  if (buf != out) {
     OPENSSL_free(buf);
   }
   return ret;
@@ -542,21 +556,38 @@ int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
     goto err;
   }
 
-  if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
+  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {
+    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
+    goto err;
+  }
+
+  /* We cannot do blinding or verification without |e|, and continuing without
+   * those countermeasures is dangerous. However, the Java/Android RSA API
+   * requires support for keys where only |d| and |n| (and not |e|) are known.
+   * The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|. */
+  int disable_security = (rsa->flags & RSA_FLAG_NO_BLINDING) && rsa->e == NULL;
+
+  if (!disable_security) {
+    /* Keys without public exponents must have blinding explicitly disabled to
+     * be used. */
+    if (rsa->e == NULL) {
+      OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);
+      goto err;
+    }
+
     blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
     if (blinding == NULL) {
       OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
       goto err;
     }
-    if (!BN_BLINDING_convert(f, blinding, ctx)) {
+    if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {
       goto err;
     }
   }
 
-  if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
-      ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) &&
-       (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
-    if (!rsa->meth->mod_exp(result, f, rsa, ctx)) {
+  if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&
+      rsa->dmq1 != NULL && rsa->iqmp != NULL) {
+    if (!mod_exp(result, f, rsa, ctx)) {
       goto err;
     }
   } else {
@@ -567,20 +598,30 @@ int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
     d = &local_d;
     BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 
-    if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
-      if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ==
-          NULL) {
-        goto err;
-      }
+    if (!BN_mod_exp_mont_consttime(result, f, d, rsa->n, ctx, rsa->mont_n)) {
+      goto err;
     }
+  }
 
-    if (!rsa->meth->bn_mod_exp(result, f, d, rsa->n, ctx, rsa->mont_n)) {
+  /* Verify the result to protect against fault attacks as described in the
+   * 1997 paper "On the Importance of Checking Cryptographic Protocols for
+   * Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some
+   * implementations do this only when the CRT is used, but we do it in all
+   * cases. Section 6 of the aforementioned paper describes an attack that
+   * works when the CRT isn't used. That attack is much less likely to succeed
+   * than the CRT attack, but there have likely been improvements since 1997.
+   *
+   * This check is cheap assuming |e| is small; it almost always is. */
+  if (!disable_security) {
+    BIGNUM *vrfy = BN_CTX_get(ctx);
+    if (vrfy == NULL ||
+        !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||
+        !BN_equal_consttime(vrfy, f)) {
+      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
       goto err;
     }
-  }
 
-  if (blinding) {
-    if (!BN_BLINDING_invert(result, blinding, ctx)) {
+    if (!BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {
       goto err;
     }
   }
@@ -605,6 +646,17 @@ err:
 }
 
 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
+  assert(ctx != NULL);
+
+  assert(rsa->n != NULL);
+  assert(rsa->e != NULL);
+  assert(rsa->d != NULL);
+  assert(rsa->p != NULL);
+  assert(rsa->q != NULL);
+  assert(rsa->dmp1 != NULL);
+  assert(rsa->dmq1 != NULL);
+  assert(rsa->iqmp != NULL);
+
   BIGNUM *r1, *m1, *vrfy;
   BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
   BIGNUM *dmp1, *dmq1, *c, *pr1;
@@ -619,6 +671,11 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
   r1 = BN_CTX_get(ctx);
   m1 = BN_CTX_get(ctx);
   vrfy = BN_CTX_get(ctx);
+  if (r1 == NULL ||
+      m1 == NULL ||
+      vrfy == NULL) {
+    goto err;
+  }
 
   {
     BIGNUM local_p, local_q;
@@ -634,20 +691,14 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
     q = &local_q;
     BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
 
-    if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
-      if (BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, p, ctx) == NULL) {
-        goto err;
-      }
-      if (BN_MONT_CTX_set_locked(&rsa->mont_q, &rsa->lock, q, ctx) == NULL) {
-        goto err;
-      }
+    if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, p, ctx) ||
+        !BN_MONT_CTX_set_locked(&rsa->mont_q, &rsa->lock, q, ctx)) {
+      goto err;
     }
   }
 
-  if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
-    if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) == NULL) {
-      goto err;
-    }
+  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {
+    goto err;
   }
 
   /* compute I mod q */
@@ -660,7 +711,7 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
   /* compute r1^dmq1 mod q */
   dmq1 = &local_dmq1;
   BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
-  if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, rsa->mont_q)) {
+  if (!BN_mod_exp_mont_consttime(m1, r1, dmq1, rsa->q, ctx, rsa->mont_q)) {
     goto err;
   }
 
@@ -674,7 +725,7 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
   /* compute r1^dmp1 mod p */
   dmp1 = &local_dmp1;
   BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
-  if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, rsa->mont_p)) {
+  if (!BN_mod_exp_mont_consttime(r0, r1, dmp1, rsa->p, ctx, rsa->mont_p)) {
     goto err;
   }
 
@@ -734,12 +785,8 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
       goto err;
     }
 
-    if ((rsa->flags & RSA_FLAG_CACHE_PRIVATE) &&
-        !BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, prime, ctx)) {
-      goto err;
-    }
-
-    if (!rsa->meth->bn_mod_exp(m1, r1, exp, prime, ctx, ap->mont)) {
+    if (!BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, prime, ctx) ||
+        !BN_mod_exp_mont_consttime(m1, r1, exp, prime, ctx, ap->mont)) {
       goto err;
     }
 
@@ -755,40 +802,6 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
     }
   }
 
-  if (rsa->e && rsa->n) {
-    if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, rsa->mont_n)) {
-      goto err;
-    }
-    /* If 'I' was greater than (or equal to) rsa->n, the operation
-     * will be equivalent to using 'I mod n'. However, the result of
-     * the verify will *always* be less than 'n' so we don't check
-     * for absolute equality, just congruency. */
-    if (!BN_sub(vrfy, vrfy, I)) {
-      goto err;
-    }
-    if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) {
-      goto err;
-    }
-    if (BN_is_negative(vrfy)) {
-      if (!BN_add(vrfy, vrfy, rsa->n)) {
-        goto err;
-      }
-    }
-    if (!BN_is_zero(vrfy)) {
-      /* 'I' and 'vrfy' aren't congruent mod n. Don't leak
-       * miscalculated CRT output, just do a raw (slower)
-       * mod_exp and return that instead. */
-
-      BIGNUM local_d;
-      BIGNUM *d = NULL;
-
-      d = &local_d;
-      BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
-      if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, rsa->mont_n)) {
-        goto err;
-      }
-    }
-  }
   ret = 1;
 
 err:
@@ -1090,9 +1103,9 @@ int rsa_default_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
                                         cb);
 }
 
-/* Many of these methods are NULL to more easily drop unused functions. The
- * wrapper functions will select the appropriate |rsa_default_*| for all
- * methods. */
+/* All of the methods are NULL to make it easier for the compiler/linker to drop
+ * unused functions. The wrapper functions will select the appropriate
+ * |rsa_default_*| implementation. */
 const RSA_METHOD RSA_default_method = {
   {
     0 /* references */,
@@ -1115,8 +1128,8 @@ const RSA_METHOD RSA_default_method = {
 
   NULL /* private_transform (defaults to rsa_default_private_transform) */,
 
-  mod_exp,
-  BN_mod_exp_mont /* bn_mod_exp */,
+  NULL /* mod_exp (ignored) */,
+  NULL /* bn_mod_exp (ignored) */,
 
   RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,