Bound RSA and DSA key sizes better.
Most asymmetric operations scale superlinearly, which makes them
potential DoS vectors. This (and other problems) are mitigated with
fixed sizes, like RSA-2048, P-256, or curve25519.
In older algorithms like RSA and DSA, these sizes are conventions rather
than well-defined algorithms. "Everyone" uses RSA-2048, but code which
imports an RSA key may see an arbitrary key size, possibly from an
untrusted source. This is commonly a public key, so we bound RSA key
sizes in check_modulus_and_exponent_sizes.
However, some applications import external private keys, and may need
tighter bounds. These typically parse the key then check the result.
However, parsing itself can perform superlinear work (RSA_check_key or
recovering the DSA public key).
This CL does the following:
- Rename check_modulus_and_exponent_sizes to rsa_check_public_key and
additionally call it from RSA_check_key.
- Fix a bug where RSA_check_key, on CRT-less keys, did not bound d, and
bound p and q before multiplying (quadratic).
- Our DSA verifier had stricter checks on q (160-, 224-, and 256-bit
only) than our DSA signer (multiple of 8 bits). Aligner the signer to
the verifier's checks.
- Validate DSA group sizes on parse, as well as priv_key < q, to bound
the running time.
Ideally these invariants would be checked exactly once at construction,
but our RSA and DSA implementations suffer from some OpenSSL's API
mistakes (https://crbug.com/boringssl/316), which means it is hard to
consistently enforce invariants. This CL focuses on the parser, but
later I'd like to better rationalize the freeze_private_key logic.
Performance of parsing RSA and DSA keys, gathered on my laptop.
Did 15130 RSA-2048 parse operations in 5022458us (3012.5 ops/sec)
Did 4888 RSA-4096 parse operations in 5060606us (965.9 ops/sec)
Did 354 RSA-16384 parse operations in 5043565us (70.2 ops/sec)
Did 88 RSA-32768 parse operations in 5038293us (17.5 ops/sec) [rejected by this CL]
Did 35000 DSA-1024/256 parse operations in 5030447us (6957.6 ops/sec)
Did 11316 DSA-2048/256 parse operations in 5094664us (2221.1 ops/sec)
Did 5488 DSA-3072/256 parse operations in 5096032us (1076.9 ops/sec)
Did 3172 DSA-4096/256 parse operations in 5041220us (629.2 ops/sec)
Did 840 DSA-8192/256 parse operations in 5070616us (165.7 ops/sec)
Did 285 DSA-10000/256 parse operations in 5004033us (57.0 ops/sec)
Did 74 DSA-20000/256 parse operations in 5066299us (14.6 ops/sec) [rejected by this CL]
Update-Note: Some invalid or overly large RSA and DSA keys may
previously have been accepted that are now rejected at parse time. For
public keys, this only moves the error from verification to parsing. In
some private key cases, we would previously allow signing with those
keys, but the resulting signatures would not be accepted by BoringSSL
anyway. This CL makes us behave more consistently.
Bug: oss-fuzz:24730
Change-Id: I4ad2003ee61138b693e65d3da4c6aa00bc165251
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/42504
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/dsa/dsa.c b/crypto/dsa/dsa.c
index 5cd98f8..c869568 100644
--- a/crypto/dsa/dsa.c
+++ b/crypto/dsa/dsa.c
@@ -72,12 +72,11 @@
#include <openssl/sha.h>
#include <openssl/thread.h>
+#include "internal.h"
#include "../fipsmodule/bn/internal.h"
#include "../internal.h"
-#define OPENSSL_DSA_MAX_MODULUS_BITS 10000
-
// Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of
// Miller-Rabin.
#define DSS_prime_checks 50
@@ -568,23 +567,7 @@
}
DSA_SIG *DSA_do_sign(const uint8_t *digest, size_t digest_len, const DSA *dsa) {
- if (!dsa->p || !dsa->q || !dsa->g) {
- OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS);
- return NULL;
- }
-
- // Reject invalid parameters. In particular, the algorithm will infinite loop
- // if |g| is zero.
- if (BN_is_zero(dsa->p) || BN_is_zero(dsa->q) || BN_is_zero(dsa->g)) {
- OPENSSL_PUT_ERROR(DSA, DSA_R_INVALID_PARAMETERS);
- return NULL;
- }
-
- // We only support DSA keys that are a multiple of 8 bits. (This is a weaker
- // check than the one in |DSA_do_check_signature|, which only allows 160-,
- // 224-, and 256-bit keys.
- if (BN_num_bits(dsa->q) % 8 != 0) {
- OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE);
+ if (!dsa_check_parameters(dsa)) {
return NULL;
}
@@ -678,35 +661,17 @@
int DSA_do_check_signature(int *out_valid, const uint8_t *digest,
size_t digest_len, DSA_SIG *sig, const DSA *dsa) {
- BN_CTX *ctx;
- BIGNUM u1, u2, t1;
- int ret = 0;
- unsigned i;
-
*out_valid = 0;
-
- if (!dsa->p || !dsa->q || !dsa->g) {
- OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS);
+ if (!dsa_check_parameters(dsa)) {
return 0;
}
- i = BN_num_bits(dsa->q);
- // FIPS 186-3 allows only different sizes for q.
- if (i != 160 && i != 224 && i != 256) {
- OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE);
- return 0;
- }
-
- if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
- OPENSSL_PUT_ERROR(DSA, DSA_R_MODULUS_TOO_LARGE);
- return 0;
- }
-
+ int ret = 0;
+ BIGNUM u1, u2, t1;
BN_init(&u1);
BN_init(&u2);
BN_init(&t1);
-
- ctx = BN_CTX_new();
+ BN_CTX *ctx = BN_CTX_new();
if (ctx == NULL) {
goto err;
}
@@ -729,11 +694,12 @@
}
// save M in u1
- if (digest_len > (i >> 3)) {
+ unsigned q_bits = BN_num_bits(dsa->q);
+ if (digest_len > (q_bits >> 3)) {
// if the digest length is greater than the size of q use the
// BN_num_bits(dsa->q) leftmost bits of the digest, see
// fips 186-3, 4.2
- digest_len = (i >> 3);
+ digest_len = (q_bits >> 3);
}
if (BN_bin2bn(digest, digest_len, &u1) == NULL) {
diff --git a/crypto/dsa/dsa_asn1.c b/crypto/dsa/dsa_asn1.c
index 97fd07f..3f3bd48 100644
--- a/crypto/dsa/dsa_asn1.c
+++ b/crypto/dsa/dsa_asn1.c
@@ -61,9 +61,45 @@
#include <openssl/err.h>
#include <openssl/mem.h>
+#include "internal.h"
#include "../bytestring/internal.h"
+#define OPENSSL_DSA_MAX_MODULUS_BITS 10000
+
+// This function is in dsa_asn1.c rather than dsa.c because it is reachable from
+// |EVP_PKEY| parsers. This makes it easier for the static linker to drop most
+// of the DSA implementation.
+int dsa_check_parameters(const DSA *dsa) {
+ if (!dsa->p || !dsa->q || !dsa->g) {
+ OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS);
+ return 0;
+ }
+
+ // Reject invalid parameters. In particular, signing will infinite loop if |g|
+ // is zero.
+ if (BN_is_zero(dsa->p) || BN_is_zero(dsa->q) || BN_is_zero(dsa->g)) {
+ OPENSSL_PUT_ERROR(DSA, DSA_R_INVALID_PARAMETERS);
+ return 0;
+ }
+
+ // FIPS 186-4 allows only three different sizes for q.
+ unsigned q_bits = BN_num_bits(dsa->q);
+ if (q_bits != 160 && q_bits != 224 && q_bits != 256) {
+ OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE);
+ return 0;
+ }
+
+ // Bound |dsa->p| to avoid a DoS vector. Note this limit is much larger than
+ // the one in FIPS 186-4, which only allows L = 1024, 2048, and 3072.
+ if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
+ OPENSSL_PUT_ERROR(DSA, DSA_R_MODULUS_TOO_LARGE);
+ return 0;
+ }
+
+ return 1;
+}
+
static int parse_integer(CBS *cbs, BIGNUM **out) {
assert(*out == NULL);
*out = BN_new();
@@ -124,10 +160,16 @@
!parse_integer(&child, &ret->g) ||
CBS_len(&child) != 0) {
OPENSSL_PUT_ERROR(DSA, DSA_R_DECODE_ERROR);
- DSA_free(ret);
- return NULL;
+ goto err;
+ }
+ if (!dsa_check_parameters(ret)) {
+ goto err;
}
return ret;
+
+err:
+ DSA_free(ret);
+ return NULL;
}
int DSA_marshal_public_key(CBB *cbb, const DSA *dsa) {
@@ -156,10 +198,16 @@
!parse_integer(&child, &ret->g) ||
CBS_len(&child) != 0) {
OPENSSL_PUT_ERROR(DSA, DSA_R_DECODE_ERROR);
- DSA_free(ret);
- return NULL;
+ goto err;
+ }
+ if (!dsa_check_parameters(ret)) {
+ goto err;
}
return ret;
+
+err:
+ DSA_free(ret);
+ return NULL;
}
int DSA_marshal_parameters(CBB *cbb, const DSA *dsa) {
@@ -203,6 +251,9 @@
OPENSSL_PUT_ERROR(DSA, DSA_R_DECODE_ERROR);
goto err;
}
+ if (!dsa_check_parameters(ret)) {
+ goto err;
+ }
return ret;
err:
diff --git a/crypto/dsa/internal.h b/crypto/dsa/internal.h
new file mode 100644
index 0000000..2d86edb
--- /dev/null
+++ b/crypto/dsa/internal.h
@@ -0,0 +1,34 @@
+/* Copyright (c) 2020, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#ifndef OPENSSL_HEADER_DSA_INTERNAL_H
+#define OPENSSL_HEADER_DSA_INTERNAL_H
+
+#include <openssl/dsa.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+
+// dsa_check_parameters checks that |dsa|'s group is within DoS bounds. It
+// returns one on success and zero on error.
+int dsa_check_parameters(const DSA *dsa);
+
+
+#if defined(__cplusplus)
+} // extern C
+#endif
+
+#endif // OPENSSL_HEADER_DSA_INTERNAL_H
diff --git a/crypto/evp/p_dsa_asn1.c b/crypto/evp/p_dsa_asn1.c
index d50e0fc..ac91127 100644
--- a/crypto/evp/p_dsa_asn1.c
+++ b/crypto/evp/p_dsa_asn1.c
@@ -141,9 +141,13 @@
goto err;
}
- // Decode the key.
+ // Decode the key. To avoid DoS attacks when importing private keys, we bound
+ // |dsa->priv_key| against |dsa->q|, which itself bound by
+ // |DSA_parse_parameters|. (We cannot call |BN_num_bits| on |dsa->priv_key|.
+ // That would leak a secret bit width.)
if (!BN_parse_asn1_unsigned(key, dsa->priv_key) ||
- CBS_len(key) != 0) {
+ CBS_len(key) != 0 ||
+ BN_cmp(dsa->priv_key, dsa->q) >= 0) {
OPENSSL_PUT_ERROR(EVP, EVP_R_DECODE_ERROR);
goto err;
}
diff --git a/crypto/fipsmodule/rsa/internal.h b/crypto/fipsmodule/rsa/internal.h
index faa6fb7..d9d6fac 100644
--- a/crypto/fipsmodule/rsa/internal.h
+++ b/crypto/fipsmodule/rsa/internal.h
@@ -108,6 +108,10 @@
int RSA_padding_add_none(uint8_t *to, size_t to_len, const uint8_t *from,
size_t from_len);
+// rsa_check_public_key checks that |rsa|'s public modulus and exponent are
+// within DoS bounds.
+int rsa_check_public_key(const RSA *rsa);
+
// RSA_private_transform calls either the method-specific |private_transform|
// function (if given) or the generic one. See the comment for
// |private_transform| in |rsa_meth_st|.
diff --git a/crypto/fipsmodule/rsa/rsa.c b/crypto/fipsmodule/rsa/rsa.c
index 2929673..ae63e1a 100644
--- a/crypto/fipsmodule/rsa/rsa.c
+++ b/crypto/fipsmodule/rsa/rsa.c
@@ -661,6 +661,9 @@
return 1;
}
+ // Note |bn_mul_consttime| and |bn_div_consttime| do not scale linearly, but
+ // checking |ainv| is in range bounds the running time, assuming |m|'s bounds
+ // were checked by the caller.
BN_CTX_start(ctx);
BIGNUM *tmp = BN_CTX_get(ctx);
int ret = tmp != NULL &&
@@ -674,22 +677,35 @@
}
int RSA_check_key(const RSA *key) {
+ // TODO(davidben): RSA key initialization is spread across
+ // |rsa_check_public_key|, |RSA_check_key|, |freeze_private_key|, and
+ // |BN_MONT_CTX_set_locked| as a result of API issues. See
+ // https://crbug.com/boringssl/316. As a result, we inconsistently check RSA
+ // invariants. We should fix this and integrate that logic.
+
if (RSA_is_opaque(key)) {
// Opaque keys can't be checked.
return 1;
}
+ if (!rsa_check_public_key(key)) {
+ return 0;
+ }
+
if ((key->p != NULL) != (key->q != NULL)) {
OPENSSL_PUT_ERROR(RSA, RSA_R_ONLY_ONE_OF_P_Q_GIVEN);
return 0;
}
- if (!key->n || !key->e) {
- OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
+ // |key->d| must be bounded by |key->n|. This ensures bounds on |RSA_bits|
+ // translate to bounds on the running time of private key operations.
+ if (key->d != NULL &&
+ (BN_is_negative(key->d) || BN_cmp(key->d, key->n) >= 0)) {
+ OPENSSL_PUT_ERROR(RSA, RSA_R_D_OUT_OF_RANGE);
return 0;
}
- if (!key->d || !key->p) {
+ if (key->d == NULL || key->p == NULL) {
// For a public key, or without p and q, there's nothing that can be
// checked.
return 1;
@@ -709,24 +725,28 @@
BN_init(&qm1);
BN_init(&dmp1);
BN_init(&dmq1);
+
+ // Check that p * q == n. Before we multiply, we check that p and q are in
+ // bounds, to avoid a DoS vector in |bn_mul_consttime| below. Note that
+ // n was bound by |rsa_check_public_key|.
+ if (BN_is_negative(key->p) || BN_cmp(key->p, key->n) >= 0 ||
+ BN_is_negative(key->q) || BN_cmp(key->q, key->n) >= 0) {
+ OPENSSL_PUT_ERROR(RSA, RSA_R_N_NOT_EQUAL_P_Q);
+ goto out;
+ }
if (!bn_mul_consttime(&tmp, key->p, key->q, ctx)) {
OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
goto out;
}
-
if (BN_cmp(&tmp, key->n) != 0) {
OPENSSL_PUT_ERROR(RSA, RSA_R_N_NOT_EQUAL_P_Q);
goto out;
}
- if (BN_is_negative(key->d) || BN_cmp(key->d, key->n) >= 0) {
- OPENSSL_PUT_ERROR(RSA, RSA_R_D_OUT_OF_RANGE);
- goto out;
- }
-
// d must be an inverse of e mod the Carmichael totient, lcm(p-1, q-1), but it
// may be unreduced because other implementations use the Euler totient. We
- // simply check that d * e is one mod p-1 and mod q-1.
+ // simply check that d * e is one mod p-1 and mod q-1. Note d and e were bound
+ // by earlier checks in this function.
if (!bn_usub_consttime(&pm1, key->p, BN_value_one()) ||
!bn_usub_consttime(&qm1, key->q, BN_value_one()) ||
!bn_mul_consttime(&de, key->d, key->e, ctx) ||
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c
index 2d9a9c9..86ff2f3 100644
--- a/crypto/fipsmodule/rsa/rsa_impl.c
+++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -73,7 +73,12 @@
#include "../rand/fork_detect.h"
-static int check_modulus_and_exponent_sizes(const RSA *rsa) {
+int rsa_check_public_key(const RSA *rsa) {
+ if (rsa->n == NULL || rsa->e == NULL) {
+ OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
+ return 0;
+ }
+
unsigned rsa_bits = BN_num_bits(rsa->n);
if (rsa_bits > 16 * 1024) {
@@ -253,8 +258,7 @@
int RSA_encrypt(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);
+ if (!rsa_check_public_key(rsa)) {
return 0;
}
@@ -269,10 +273,6 @@
return 0;
}
- if (!check_modulus_and_exponent_sizes(rsa)) {
- return 0;
- }
-
ctx = BN_CTX_new();
if (ctx == NULL) {
goto err;
@@ -592,8 +592,7 @@
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);
+ if (!rsa_check_public_key(rsa)) {
return 0;
}
@@ -610,10 +609,6 @@
return 0;
}
- if (!check_modulus_and_exponent_sizes(rsa)) {
- return 0;
- }
-
BN_CTX *ctx = BN_CTX_new();
if (ctx == NULL) {
return 0;
@@ -1121,8 +1116,8 @@
// Reject excessively large public exponents. Windows CryptoAPI and Go don't
// support values larger than 32 bits, so match their limits for generating
- // keys. (|check_modulus_and_exponent_sizes| uses a slightly more conservative
- // value, but we don't need to support generating such keys.)
+ // keys. (|rsa_check_public_key| uses a slightly more conservative value, but
+ // we don't need to support generating such keys.)
// https://github.com/golang/go/issues/3161
// https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx
if (BN_num_bits(e_value) > 32) {
diff --git a/include/openssl/evp.h b/include/openssl/evp.h
index b305225..e647cdf 100644
--- a/include/openssl/evp.h
+++ b/include/openssl/evp.h
@@ -219,7 +219,9 @@
//
// The caller must check the type of the parsed private key to ensure it is
// suitable and validate other desired key properties such as RSA modulus size
-// or EC curve.
+// or EC curve. In particular, RSA private key operations scale cubicly, so
+// applications accepting RSA private keys from external sources may need to
+// bound key sizes (use |EVP_PKEY_bits| or |RSA_bits|) to avoid a DoS vector.
//
// A PrivateKeyInfo ends with an optional set of attributes. These are not
// processed and so this function will silently ignore any trailing data in the
