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.
