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: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/19735)

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index e21dcff027c5d3295f13b615e4ae0bd0d70da214..31043c8bc23c825a070ff933f0fa013add4a3ac4 100644 (file)
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -37,6 +37,15 @@ extern unsigned int OPENSSL_sparcv9cap_P[];
 /* 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)
 {
@@ -305,12 +314,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);
@@ -319,6 +322,14 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         BNerr(BN_F_BN_MOD_EXP_MONT, 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. */
@@ -618,6 +629,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.
@@ -697,7 +713,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 */
@@ -758,6 +774,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,
@@ -1029,6 +1048,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 8ad69ccd3639edd7331cc183f700540a14f0c145..62a969b134d68a39207f452abffa9eab73cca929 100644 (file)
--- a/crypto/bn/bn_local.h
+++ b/crypto/bn/bn_local.h
@@ -35,6 +35,26 @@
 /* #define BN_DEBUG */
 /* #define BN_DEBUG_RAND */
 
+/*
+ * 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 1e5045a010bb70cf91e66aba4ff9022d79db97b9..3d4a1bda45c677d42689289742137281558a4d61 100644 (file)
--- 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)) {

diff --git a/test/exptest.c b/test/exptest.c
index a327773ec433d8ef0a52e382a31d2213695cbccc..5cab57c8514a2fc751ff03b7b9578d800b1077c4 100644 (file)
--- a/test/exptest.c
+++ b/test/exptest.c
@@ -50,6 +50,7 @@ static int test_mod_exp_zero(void)
     BN_ULONG one_word = 1;
     BN_CTX *ctx = BN_CTX_new();
     int ret = 0, failed = 0;
+    BN_MONT_CTX *mont = NULL;
 
     if (!TEST_ptr(m = BN_new())
         || !TEST_ptr(a = BN_new())
@@ -94,6 +95,33 @@ static int test_mod_exp_zero(void)
     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a)))
         failed = 1;
 
+    if (!TEST_ptr(mont = BN_MONT_CTX_new()))
+        goto err;
+
+    ERR_set_mark();
+    /* mont is not set but passed in */
+    if (!TEST_false(BN_mod_exp_mont_consttime(r, p, a, m, ctx, mont)))
+        goto err;
+    if (!TEST_false(BN_mod_exp_mont(r, p, a, m, ctx, mont)))
+        goto err;
+    ERR_pop_to_mark();
+
+    if (!TEST_true(BN_MONT_CTX_set(mont, m, ctx)))
+        goto err;
+
+    /* we compute 0 ** a mod 1 here, to execute code that uses mont */
+    if (!TEST_true(BN_mod_exp_mont_consttime(r, p, a, m, ctx, mont)))
+        goto err;
+
+    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a)))
+        failed = 1;
+
+    if (!TEST_true(BN_mod_exp_mont(r, p, a, m, ctx, mont)))
+        goto err;
+
+    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont", r, a)))
+        failed = 1;
+
     /*
      * A different codepath exists for single word multiplication
      * in non-constant-time only.
@@ -114,6 +142,7 @@ static int test_mod_exp_zero(void)
     BN_free(a);
     BN_free(p);
     BN_free(m);
+    BN_MONT_CTX_free(mont);
     BN_CTX_free(ctx);
 
     return ret;