Limit size of modulus for bn_mul_mont and BN_mod_exp_mont_consttime

Otherwise the alloca can cause an exception.

Issue reported by Jiayi Lin.

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Todd Short <todd.short@me.com>
(Merged from https://github.com/openssl/openssl/pull/20005)

3 files changed, 48 insertions, 8 deletions

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index c7b62232f3..22cbffa723 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -36,6 +36,15 @@
 /* maximum precomputation table size for *variable* sliding windows */
 #define TABLE_SIZE      32
 
+/*
+ * Beyond this limit the constant time code is disabled due to
+ * the possible overflow in the computation of powerbufLen in
+ * BN_mod_exp_mont_consttime.
+ * When this limit is exceeded, the computation will be done using
+ * non-constant time code, but it will take very long.
+ */
+#define BN_CONSTTIME_SIZE_LIMIT (INT_MAX / BN_BYTES / 256)
+
 /* this one works - simple but works */
 int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 {
@@ -303,12 +312,6 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     BIGNUM *val[TABLE_SIZE];
     BN_MONT_CTX *mont = NULL;
 
-    if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
-            || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
-            || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
-        return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
-    }
-
     bn_check_top(a);
     bn_check_top(p);
     bn_check_top(m);
@@ -317,6 +320,14 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         ERR_raise(ERR_LIB_BN, BN_R_CALLED_WITH_EVEN_MODULUS);
         return 0;
     }
+
+    if (m->top <= BN_CONSTTIME_SIZE_LIMIT
+        && (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
+            || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
+            || BN_get_flags(m, BN_FLG_CONSTTIME) != 0)) {
+        return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
+    }
+
     bits = BN_num_bits(p);
     if (bits == 0) {
         /* x**0 mod 1, or x**0 mod -1 is still zero. */
@@ -615,6 +626,11 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 
     top = m->top;
 
+    if (top > BN_CONSTTIME_SIZE_LIMIT) {
+        /* Prevent overflowing the powerbufLen computation below */
+        return BN_mod_exp_mont(rr, a, p, m, ctx, in_mont);
+    }
+
     /*
      * Use all bits stored in |p|, rather than |BN_num_bits|, so we do not leak
      * whether the top bits are zero.
@@ -694,7 +710,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     else
 #endif
 #if defined(OPENSSL_BN_ASM_MONT5)
-    if (window >= 5) {
+    if (window >= 5 && top <= BN_SOFT_LIMIT) {
         window = 5;             /* ~5% improvement for RSA2048 sign, and even
                                  * for RSA4096 */
         /* reserve space for mont->N.d[] copy */
@@ -755,6 +771,9 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     if (!bn_to_mont_fixed_top(&am, a, mont, ctx))
         goto err;
 
+    if (top > BN_SOFT_LIMIT)
+        goto fallback;
+
 #if defined(SPARC_T4_MONT)
     if (t4) {
         typedef int (*bn_pwr5_mont_f) (BN_ULONG *tp, const BN_ULONG *np,
@@ -1026,6 +1045,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     } else
 #endif
     {
+ fallback:
         if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, window))
             goto err;
         if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, window))
diff --git a/crypto/bn/bn_local.h b/crypto/bn/bn_local.h
index 1a3a48ff6c..322b0af89b 100644
--- a/crypto/bn/bn_local.h
+++ b/crypto/bn/bn_local.h
@@ -42,6 +42,26 @@
 #  include <openssl/rand.h>
 # endif
 
+/*
+ * This should limit the stack usage due to alloca to about 4K.
+ * BN_SOFT_LIMIT is a soft limit equivalent to 2*OPENSSL_RSA_MAX_MODULUS_BITS.
+ * Beyond that size bn_mul_mont is no longer used, and the constant time
+ * assembler code is disabled, due to the blatant alloca and bn_mul_mont usage.
+ * Note that bn_mul_mont does an alloca that is hidden away in assembly.
+ * It is not recommended to do computations with numbers exceeding this limit,
+ * since the result will be highly version dependent:
+ * While the current OpenSSL version will use non-optimized, but safe code,
+ * previous versions will use optimized code, that may crash due to unexpected
+ * stack overflow, and future versions may very well turn this into a hard
+ * limit.
+ * Note however, that it is possible to override the size limit using
+ * "./config -DBN_SOFT_LIMIT=<limit>" if necessary, and the O/S specific
+ * stack limit is known and taken into consideration.
+ */
+# ifndef BN_SOFT_LIMIT
+#  define BN_SOFT_LIMIT         (4096 / BN_BYTES)
+# endif
+
 # ifndef OPENSSL_SMALL_FOOTPRINT
 #  define BN_MUL_COMBA
 #  define BN_SQR_COMBA
diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c
index 1d0ee7f633..35565426af 100644
--- a/crypto/bn/bn_mont.c
+++ b/crypto/bn/bn_mont.c
@@ -42,7 +42,7 @@ int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
     int num = mont->N.top;
 
 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
-    if (num > 1 && a->top == num && b->top == num) {
+    if (num > 1 && num <= BN_SOFT_LIMIT && a->top == num && b->top == num) {
         if (bn_wexpand(r, num) == NULL)
             return 0;
         if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {