Decrease BN_MONTGOMERY_MAX_WORDS to 16384 bits I'm not sure where I got the original value (I think it was when I was trying to set a limit for all of BIGNUM) but 8 KiB is still a fairly large stack allocation. I also missed that some of the bn_mul_mont implementations seem to alloca 2 * num words, so that's actually 16 KiB of stack used. We only support up to 16384-bit RSA, so we only need BN_MONT_CTX to work with that. Lower the limit accordingly. Ideally we'd get down to 8192 (see crbug.com/402677800). While we have to allow giant BIGNUMs for some non-cryptography callers, this means that Montgomery reduction and all the cryptography code can assume one integer fits in 2 KiB (lowering the RSA limit could bring us down to 1 KiB). I'm hoping this is small enough that all our Montgomery multiplication codepaths can just stack-allocate their temporaries. (We already believe it's small enough for bn_mul_mont, just other codepaths still allocate.) That should remove the main load-bearing use of BN_CTX. Update-Note: BN_MONT_CTX now only works for 16834-bit moduli or lower. This has no impact on cryptographic primitives supported by BoringSSL, which were already capped at that size. Bug: 42290433, 402677800 Change-Id: Iaaf8ba34eabeb3b90f4219e0faa5b74c4b1de4b8 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/77507 Reviewed-by: Bob Beck <bbe@google.com> Auto-Submit: David Benjamin <davidben@google.com> Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/dsa/dsa.cc b/crypto/dsa/dsa.cc index 958be93..c9566b1 100644 --- a/crypto/dsa/dsa.cc +++ b/crypto/dsa/dsa.cc
@@ -33,6 +33,10 @@ #include "internal.h" +static_assert(OPENSSL_DSA_MAX_MODULUS_BITS <= + BN_MONTGOMERY_MAX_WORDS * BN_BITS2, + "Max DSA size too big for Montgomery arithmetic"); + // Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of // Miller-Rabin. #define DSS_prime_checks 50
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h index 6ce2cc7..9e14fed 100644 --- a/crypto/fipsmodule/bn/internal.h +++ b/crypto/fipsmodule/bn/internal.h
@@ -263,11 +263,15 @@ int bn_rand_secret_range(BIGNUM *r, int *out_is_uniform, BN_ULONG min_inclusive, const BIGNUM *max_exclusive); -// BN_MONTGOMERY_MAX_WORDS is the maximum numer of words allowed in a |BIGNUM| +// BN_MONTGOMERY_MAX_WORDS is the maximum number of words allowed in a |BIGNUM| // used with Montgomery reduction. Ideally this limit would be applied to all // |BIGNUM|s, in |bn_wexpand|, but the exactfloat library needs to create 8 MiB // values for other operations. -#define BN_MONTGOMERY_MAX_WORDS (8 * 1024 / sizeof(BN_ULONG)) +// +// TODO(crbug.com/402677800): This is not quite tight enough to limit the +// |bn_mul_mont| allocation to under a page. Lower the maximum RSA key and then +// lower this to match. +#define BN_MONTGOMERY_MAX_WORDS (16384 / BN_BITS2) #if !defined(OPENSSL_NO_ASM) && \ (defined(OPENSSL_X86) || defined(OPENSSL_X86_64) || \ @@ -280,9 +284,9 @@ // If at least one of |ap| or |bp| is fully reduced, |rp| will be fully reduced. // If neither is fully-reduced, the output may not be either. // -// This function allocates |num| words on the stack, so |num| should be at most -// |BN_MONTGOMERY_MAX_WORDS|. Additionally, |num| must be at least 128 / -// |BN_BITS2|. +// This function allocates up to 2 * |num| words (plus a constant allocation) on +// the stack, so |num| should be at most |BN_MONTGOMERY_MAX_WORDS|. +// Additionally, |num| must be at least 128 / |BN_BITS2|. // // TODO(davidben): The x86_64 implementation expects a 32-bit input and masks // off upper bits. The aarch64 implementation expects a 64-bit input and does
diff --git a/crypto/fipsmodule/dh/check.cc.inc b/crypto/fipsmodule/dh/check.cc.inc index 19beb31..c15b858 100644 --- a/crypto/fipsmodule/dh/check.cc.inc +++ b/crypto/fipsmodule/dh/check.cc.inc
@@ -17,9 +17,14 @@ #include <openssl/bn.h> #include <openssl/err.h> +#include "../bn/internal.h" #include "internal.h" +static_assert(OPENSSL_DH_MAX_MODULUS_BITS <= + BN_MONTGOMERY_MAX_WORDS * BN_BITS2, + "Max DH size too big for Montgomery arithmetic"); + int dh_check_params_fast(const DH *dh) { // Most operations scale with p and q. if (BN_is_negative(dh->p) || !BN_is_odd(dh->p) ||
diff --git a/crypto/fipsmodule/rsa/rsa_impl.cc.inc b/crypto/fipsmodule/rsa/rsa_impl.cc.inc index 79e2789..5aad8e9 100644 --- a/crypto/fipsmodule/rsa/rsa_impl.cc.inc +++ b/crypto/fipsmodule/rsa/rsa_impl.cc.inc
@@ -31,6 +31,10 @@ #include "internal.h" +static_assert(OPENSSL_RSA_MAX_MODULUS_BITS <= + BN_MONTGOMERY_MAX_WORDS * BN_BITS2, + "Max RSA size too big for Montgomery arithmetic"); + int rsa_check_public_key(const RSA *rsa) { if (rsa->n == NULL) { OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
diff --git a/include/openssl/rsa.h b/include/openssl/rsa.h index f090927..21ef6c1 100644 --- a/include/openssl/rsa.h +++ b/include/openssl/rsa.h
@@ -71,7 +71,7 @@ // OPENSSL_RSA_MAX_MODULUS_BITS is the maximum supported RSA modulus, in bits. // -// TODO(davidben): Reduce this to 8192. +// TODO(crbug.com/402677800): Reduce this to 8192. #define OPENSSL_RSA_MAX_MODULUS_BITS 16384 // RSA_bits returns the size of |rsa|, in bits.