Add APIs to support RSA keys with large e. We cap e in RSA for DoS reasons. draft-amjad-cfrg-partially-blind-rsa needs to create RSA keys with very large e. To support this, add an API which disables this check. Also add some missing checks for negative n and negative e. (Already rejected by the parser, just not at this layer.) Change-Id: Ia996bb1b46fc8b73db704f492b3df72b254a15a4 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/59645 Auto-Submit: David Benjamin <davidben@google.com> Reviewed-by: Adam Langley <agl@google.com> Commit-Queue: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/rsa/rsa.c b/crypto/fipsmodule/rsa/rsa.c index 5b687b7..77ab6c6 100644 --- a/crypto/fipsmodule/rsa/rsa.c +++ b/crypto/fipsmodule/rsa/rsa.c
@@ -160,6 +160,49 @@ return rsa; } +RSA *RSA_new_public_key_large_e(const BIGNUM *n, const BIGNUM *e) { + RSA *rsa = RSA_new(); + if (rsa == NULL) { + return NULL; + } + + rsa->flags |= RSA_FLAG_LARGE_PUBLIC_EXPONENT; + if (!bn_dup_into(&rsa->n, n) || // + !bn_dup_into(&rsa->e, e) || // + !RSA_check_key(rsa)) { + RSA_free(rsa); + return NULL; + } + + return rsa; +} + +RSA *RSA_new_private_key_large_e(const BIGNUM *n, const BIGNUM *e, + const BIGNUM *d, const BIGNUM *p, + const BIGNUM *q, const BIGNUM *dmp1, + const BIGNUM *dmq1, const BIGNUM *iqmp) { + RSA *rsa = RSA_new(); + if (rsa == NULL) { + return NULL; + } + + rsa->flags |= RSA_FLAG_LARGE_PUBLIC_EXPONENT; + if (!bn_dup_into(&rsa->n, n) || // + !bn_dup_into(&rsa->e, e) || // + !bn_dup_into(&rsa->d, d) || // + !bn_dup_into(&rsa->p, p) || // + !bn_dup_into(&rsa->q, q) || // + !bn_dup_into(&rsa->dmp1, dmp1) || // + !bn_dup_into(&rsa->dmq1, dmq1) || // + !bn_dup_into(&rsa->iqmp, iqmp) || // + !RSA_check_key(rsa)) { + RSA_free(rsa); + return NULL; + } + + return rsa; +} + RSA *RSA_new(void) { return RSA_new_method(NULL); } RSA *RSA_new_method(const ENGINE *engine) {
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c index e9379d9..b907ae4 100644 --- a/crypto/fipsmodule/rsa/rsa_impl.c +++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -85,32 +85,44 @@ return 0; } - // RSA moduli must be odd. In addition to being necessary for RSA in general, - // we cannot setup Montgomery reduction with even moduli. - if (!BN_is_odd(rsa->n)) { + // RSA moduli must be positive and odd. In addition to being necessary for RSA + // in general, we cannot setup Montgomery reduction with even moduli. + if (!BN_is_odd(rsa->n) || BN_is_negative(rsa->n)) { OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_RSA_PARAMETERS); return 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 (rsa->e != NULL) { + // Reject e = 1, negative e, and even e. e must be odd to be relatively + // prime with phi(n). unsigned e_bits = BN_num_bits(rsa->e); - if (e_bits > kMaxExponentBits || - // Additionally reject e = 1 or even e. e must be odd to be relatively - // prime with phi(n). - e_bits < 2 || !BN_is_odd(rsa->e)) { + if (e_bits < 2 || BN_is_negative(rsa->e) || !BN_is_odd(rsa->e)) { OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE); return 0; } + if (rsa->flags & RSA_FLAG_LARGE_PUBLIC_EXPONENT) { + // The caller has requested disabling DoS protections. Still, e must be + // less than n. + if (BN_ucmp(rsa->n, rsa->e) <= 0) { + OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE); + return 0; + } + } else { + // 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 + if (e_bits > kMaxExponentBits) { + OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE); + return 0; + } + } } else if (!(rsa->flags & RSA_FLAG_NO_PUBLIC_EXPONENT)) { OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING); return 0;
diff --git a/crypto/rsa_extra/rsa_test.cc b/crypto/rsa_extra/rsa_test.cc index 4a450e5..48f48d8 100644 --- a/crypto/rsa_extra/rsa_test.cc +++ b/crypto/rsa_extra/rsa_test.cc
@@ -64,6 +64,7 @@ #include <openssl/bn.h> #include <openssl/bytestring.h> #include <openssl/crypto.h> +#include <openssl/digest.h> #include <openssl/err.h> #include <openssl/nid.h> @@ -1187,6 +1188,112 @@ kPlaintextLen, RSA_PKCS1_OAEP_PADDING)); } +TEST(RSATest, Negative) { + auto dup_neg = [](const BIGNUM *bn) -> bssl::UniquePtr<BIGNUM> { + bssl::UniquePtr<BIGNUM> ret(BN_dup(bn)); + if (!ret) { + return nullptr; + } + BN_set_negative(ret.get(), 1); + return ret; + }; + + bssl::UniquePtr<RSA> key( + RSA_private_key_from_bytes(kFIPSKey, sizeof(kFIPSKey) - 1)); + ASSERT_TRUE(key); + const BIGNUM *n = RSA_get0_n(key.get()); + bssl::UniquePtr<BIGNUM> neg_n = dup_neg(n); + ASSERT_TRUE(neg_n); + const BIGNUM *e = RSA_get0_e(key.get()); + bssl::UniquePtr<BIGNUM> neg_e = dup_neg(e); + ASSERT_TRUE(neg_e); + const BIGNUM *d = RSA_get0_d(key.get()); + bssl::UniquePtr<BIGNUM> neg_d = dup_neg(d); + ASSERT_TRUE(neg_d); + const BIGNUM *p = RSA_get0_p(key.get()); + bssl::UniquePtr<BIGNUM> neg_p = dup_neg(p); + ASSERT_TRUE(neg_p); + const BIGNUM *q = RSA_get0_q(key.get()); + bssl::UniquePtr<BIGNUM> neg_q = dup_neg(q); + ASSERT_TRUE(neg_q); + const BIGNUM *dmp1 = RSA_get0_dmp1(key.get()); + bssl::UniquePtr<BIGNUM> neg_dmp1 = dup_neg(dmp1); + ASSERT_TRUE(neg_dmp1); + const BIGNUM *dmq1 = RSA_get0_dmq1(key.get()); + bssl::UniquePtr<BIGNUM> neg_dmq1 = dup_neg(dmq1); + ASSERT_TRUE(neg_dmq1); + const BIGNUM *iqmp = RSA_get0_iqmp(key.get()); + bssl::UniquePtr<BIGNUM> neg_iqmp = dup_neg(iqmp); + ASSERT_TRUE(neg_iqmp); + + EXPECT_FALSE(RSA_new_public_key(neg_n.get(), e)); + EXPECT_FALSE(RSA_new_public_key(n, neg_e.get())); + EXPECT_FALSE(RSA_new_private_key(neg_n.get(), e, d, p, q, dmp1, dmq1, iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, neg_e.get(), d, p, q, dmp1, dmq1, iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, e, neg_d.get(), p, q, dmp1, dmq1, iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, e, d, neg_p.get(), q, dmp1, dmq1, iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, e, d, p, neg_q.get(), dmp1, dmq1, iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, e, d, p, q, neg_dmp1.get(), dmq1, iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, e, d, p, q, dmp1, neg_dmq1.get(), iqmp)); + EXPECT_FALSE(RSA_new_private_key(n, e, d, p, q, dmp1, dmq1, neg_iqmp.get())); +} + +TEST(RSATest, LargeE) { + // Test an RSA key with large e by swapping d and e in kFIPSKey. Since e is + // small, e mod (p-1) and e mod (q-1) will simply be e. + bssl::UniquePtr<RSA> key( + RSA_private_key_from_bytes(kFIPSKey, sizeof(kFIPSKey) - 1)); + ASSERT_TRUE(key); + const BIGNUM *n = RSA_get0_n(key.get()); + const BIGNUM *e = RSA_get0_e(key.get()); + const BIGNUM *d = RSA_get0_d(key.get()); + const BIGNUM *p = RSA_get0_p(key.get()); + const BIGNUM *q = RSA_get0_q(key.get()); + const BIGNUM *iqmp = RSA_get0_iqmp(key.get()); + + // By default, the large exponent is not allowed as e. + bssl::UniquePtr<RSA> pub(RSA_new_public_key(n, /*e=*/d)); + EXPECT_FALSE(pub); + bssl::UniquePtr<RSA> priv(RSA_new_private_key(n, /*e=*/d, /*d=*/e, p, q, + /*dmp1=*/e, /*dmq1=*/e, iqmp)); + EXPECT_FALSE(priv); + + // But the "large e" APIs tolerate it. + pub.reset(RSA_new_public_key_large_e(n, /*e=*/d)); + ASSERT_TRUE(pub); + priv.reset(RSA_new_private_key_large_e(n, /*e=*/d, /*d=*/e, p, q, /*dmp1=*/e, + /*dmq1=*/e, iqmp)); + ASSERT_TRUE(priv); + + // Test that operations work correctly. + static const uint8_t kDigest[32] = {0}; + std::vector<uint8_t> sig(RSA_size(priv.get())); + size_t len; + ASSERT_TRUE(RSA_sign_pss_mgf1(priv.get(), &len, sig.data(), sig.size(), + kDigest, sizeof(kDigest), EVP_sha256(), + EVP_sha256(), /*salt_len=*/32)); + sig.resize(len); + + EXPECT_TRUE(RSA_verify_pss_mgf1(pub.get(), kDigest, sizeof(kDigest), + EVP_sha256(), EVP_sha256(), /*salt_len=*/32, + sig.data(), sig.size())); + + // e = 1 is still invalid. + EXPECT_FALSE(RSA_new_public_key_large_e(n, BN_value_one())); + + // e must still be odd. + bssl::UniquePtr<BIGNUM> bad_e(BN_dup(d)); + ASSERT_TRUE(bad_e); + ASSERT_TRUE(BN_add_word(bad_e.get(), 1)); + EXPECT_FALSE(RSA_new_public_key_large_e(n, bad_e.get())); + + // e must still be bounded by n. + bad_e.reset(BN_dup(n)); + ASSERT_TRUE(bad_e); + ASSERT_TRUE(BN_add_word(bad_e.get(), 2)); // Preserve parity. + EXPECT_FALSE(RSA_new_public_key_large_e(n, bad_e.get())); +} + #if !defined(BORINGSSL_SHARED_LIBRARY) TEST(RSATest, SqrtTwo) { bssl::UniquePtr<BIGNUM> sqrt(BN_new()), pow2(BN_new());
diff --git a/include/openssl/rsa.h b/include/openssl/rsa.h index 49a6aa6..9b21d83 100644 --- a/include/openssl/rsa.h +++ b/include/openssl/rsa.h
@@ -620,6 +620,26 @@ // attacks. OPENSSL_EXPORT RSA *RSA_new_private_key_no_e(const BIGNUM *n, const BIGNUM *d); +// RSA_new_public_key_large_e behaves like |RSA_new_public_key| but allows any +// |e| up to |n|. +// +// BoringSSL typically bounds public exponents as a denial-of-service +// mitigation. Keys created by this function may perform worse than those +// created by |RSA_new_public_key|. +OPENSSL_EXPORT RSA *RSA_new_public_key_large_e(const BIGNUM *n, + const BIGNUM *e); + +// RSA_new_private_key_large_e behaves like |RSA_new_private_key| but allows any +// |e| up to |n|. +// +// BoringSSL typically bounds public exponents as a denial-of-service +// mitigation. Keys created by this function may perform worse than those +// created by |RSA_new_private_key|. +OPENSSL_EXPORT RSA *RSA_new_private_key_large_e( + const BIGNUM *n, const BIGNUM *e, const BIGNUM *d, const BIGNUM *p, + const BIGNUM *q, const BIGNUM *dmp1, const BIGNUM *dmq1, + const BIGNUM *iqmp); + // ex_data functions. // @@ -656,6 +676,12 @@ // |RSA_new_private_key_no_e| to construct such keys. #define RSA_FLAG_NO_PUBLIC_EXPONENT 0x40 +// RSA_FLAG_LARGE_PUBLIC_EXPONENT indicates that keys with a large public +// exponent are allowed. This is an internal constant. Use +// |RSA_new_public_key_large_e| and |RSA_new_private_key_large_e| to construct +// such keys. +#define RSA_FLAG_LARGE_PUBLIC_EXPONENT 0x80 + // RSA public exponent values.