diff options
-rw-r--r-- | crypto/bn/bn_exp.c | 34 | ||||
-rw-r--r-- | crypto/bn/bn_local.h | 20 | ||||
-rw-r--r-- | crypto/bn/bn_mont.c | 2 | ||||
-rw-r--r-- | test/exptest.c | 29 |
4 files changed, 77 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 3c8534e1f7..c9a7ecf298 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 735989d983..865c361515 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)) { diff --git a/test/exptest.c b/test/exptest.c index f6ff411ca1..9dadd4873f 100644 --- 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; |