diff options
Diffstat (limited to 'deps/openssl/openssl/crypto/bn/bn_exp.c')
-rw-r--r-- | deps/openssl/openssl/crypto/bn/bn_exp.c | 186 |
1 files changed, 99 insertions, 87 deletions
diff --git a/deps/openssl/openssl/crypto/bn/bn_exp.c b/deps/openssl/openssl/crypto/bn/bn_exp.c index a6ad475a0b..c026ffcb33 100644 --- a/deps/openssl/openssl/crypto/bn/bn_exp.c +++ b/deps/openssl/openssl/crypto/bn/bn_exp.c @@ -51,10 +51,7 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) } BN_CTX_start(ctx); - if ((r == a) || (r == p)) - rr = BN_CTX_get(ctx); - else - rr = r; + rr = ((r == a) || (r == p)) ? BN_CTX_get(ctx) : r; v = BN_CTX_get(ctx); if (rr == NULL || v == NULL) goto err; @@ -86,7 +83,7 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) err: BN_CTX_end(ctx); bn_check_top(r); - return (ret); + return ret; } int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, @@ -134,13 +131,6 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, #define RECP_MUL_MOD #ifdef MONT_MUL_MOD - /* - * I have finally been able to take out this pre-condition of the top bit - * being set. It was caused by an error in BN_div with negatives. There - * was also another problem when for a^b%m a >= m. eay 07-May-97 - */ - /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ - if (BN_is_odd(m)) { # ifdef MONT_EXP_WORD if (a->top == 1 && !a->neg @@ -165,7 +155,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, #endif bn_check_top(r); - return (ret); + return ret; } int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, @@ -201,7 +191,7 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX_start(ctx); aa = BN_CTX_get(ctx); val[0] = BN_CTX_get(ctx); - if (!aa || !val[0]) + if (val[0] == NULL) goto err; BN_RECP_CTX_init(&recp); @@ -300,7 +290,7 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX_end(ctx); BN_RECP_CTX_free(&recp); bn_check_top(r); - return (ret); + return ret; } int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, @@ -326,7 +316,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, if (!BN_is_odd(m)) { BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS); - return (0); + return 0; } bits = BN_num_bits(p); if (bits == 0) { @@ -344,7 +334,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, d = BN_CTX_get(ctx); r = BN_CTX_get(ctx); val[0] = BN_CTX_get(ctx); - if (!d || !r || !val[0]) + if (val[0] == NULL) goto err; /* @@ -366,11 +356,6 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, aa = val[0]; } else aa = a; - if (BN_is_zero(aa)) { - BN_zero(rr); - ret = 1; - goto err; - } if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx)) goto err; /* 1 */ @@ -481,10 +466,9 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, BN_MONT_CTX_free(mont); BN_CTX_end(ctx); bn_check_top(rr); - return (ret); + return ret; } -#if defined(SPARC_T4_MONT) static BN_ULONG bn_get_bits(const BIGNUM *a, int bitpos) { BN_ULONG ret = 0; @@ -503,7 +487,6 @@ static BN_ULONG bn_get_bits(const BIGNUM *a, int bitpos) return ret & BN_MASK2; } -#endif /* * BN_mod_exp_mont_consttime() stores the precomputed powers in a specific @@ -610,7 +593,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) { - int i, bits, ret = 0, window, wvalue; + int i, bits, ret = 0, window, wvalue, wmask, window0; int top; BN_MONT_CTX *mont = NULL; @@ -629,7 +612,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, if (!BN_is_odd(m)) { BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME, BN_R_CALLED_WITH_EVEN_MODULUS); - return (0); + return 0; } top = m->top; @@ -666,31 +649,33 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, } #ifdef RSAZ_ENABLED - /* - * If the size of the operands allow it, perform the optimized - * RSAZ exponentiation. For further information see - * crypto/bn/rsaz_exp.c and accompanying assembly modules. - */ - if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024) - && rsaz_avx2_eligible()) { - if (NULL == bn_wexpand(rr, 16)) + if (!a->neg) { + /* + * If the size of the operands allow it, perform the optimized + * RSAZ exponentiation. For further information see + * crypto/bn/rsaz_exp.c and accompanying assembly modules. + */ + if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024) + && rsaz_avx2_eligible()) { + if (NULL == bn_wexpand(rr, 16)) + goto err; + RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d, + mont->n0[0]); + rr->top = 16; + rr->neg = 0; + bn_correct_top(rr); + ret = 1; goto err; - RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d, - mont->n0[0]); - rr->top = 16; - rr->neg = 0; - bn_correct_top(rr); - ret = 1; - goto err; - } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) { - if (NULL == bn_wexpand(rr, 8)) + } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) { + if (NULL == bn_wexpand(rr, 8)) + goto err; + RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d); + rr->top = 8; + rr->neg = 0; + bn_correct_top(rr); + ret = 1; goto err; - RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d); - rr->top = 8; - rr->neg = 0; - bn_correct_top(rr); - ret = 1; - goto err; + } } #endif @@ -763,7 +748,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, /* prepare a^1 in Montgomery domain */ if (a->neg || BN_ucmp(a, m) >= 0) { - if (!BN_mod(&am, a, m, ctx)) + if (!BN_nnmod(&am, a, m, ctx)) goto err; if (!bn_to_mont_fixed_top(&am, &am, mont, ctx)) goto err; @@ -861,20 +846,27 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, top /= 2; bn_flip_t4(np, mont->N.d, top); - bits--; - for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--) - wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); + /* + * The exponent may not have a whole number of fixed-size windows. + * To simplify the main loop, the initial window has between 1 and + * full-window-size bits such that what remains is always a whole + * number of windows + */ + window0 = (bits - 1) % 5 + 1; + wmask = (1 << window0) - 1; + bits -= window0; + wvalue = bn_get_bits(p, bits) & wmask; bn_gather5_t4(tmp.d, top, powerbuf, wvalue); /* * Scan the exponent one window at a time starting from the most * significant bits. */ - while (bits >= 0) { + while (bits > 0) { if (bits < stride) - stride = bits + 1; + stride = bits; bits -= stride; - wvalue = bn_get_bits(p, bits + 1); + wvalue = bn_get_bits(p, bits); if ((*pwr5_worker) (tmp.d, np, n0, powerbuf, wvalue, stride)) continue; @@ -982,32 +974,36 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, bn_scatter5(tmp.d, top, powerbuf, i); } # endif - bits--; - for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--) - wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); + /* + * The exponent may not have a whole number of fixed-size windows. + * To simplify the main loop, the initial window has between 1 and + * full-window-size bits such that what remains is always a whole + * number of windows + */ + window0 = (bits - 1) % 5 + 1; + wmask = (1 << window0) - 1; + bits -= window0; + wvalue = bn_get_bits(p, bits) & wmask; bn_gather5(tmp.d, top, powerbuf, wvalue); /* * Scan the exponent one window at a time starting from the most * significant bits. */ - if (top & 7) - while (bits >= 0) { - for (wvalue = 0, i = 0; i < 5; i++, bits--) - wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); - + if (top & 7) { + while (bits > 0) { bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); bn_mul_mont_gather5(tmp.d, tmp.d, powerbuf, np, n0, top, - wvalue); + bn_get_bits5(p->d, bits -= 5)); + } } else { - while (bits >= 0) { - wvalue = bn_get_bits5(p->d, bits - 4); - bits -= 5; - bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue); + while (bits > 0) { + bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, + bn_get_bits5(p->d, bits -= 5)); } } @@ -1049,28 +1045,45 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, } } - bits--; - for (wvalue = 0, i = bits % window; i >= 0; i--, bits--) - wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); + /* + * The exponent may not have a whole number of fixed-size windows. + * To simplify the main loop, the initial window has between 1 and + * full-window-size bits such that what remains is always a whole + * number of windows + */ + window0 = (bits - 1) % window + 1; + wmask = (1 << window0) - 1; + bits -= window0; + wvalue = bn_get_bits(p, bits) & wmask; if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp, top, powerbuf, wvalue, window)) goto err; + wmask = (1 << window) - 1; /* * Scan the exponent one window at a time starting from the most * significant bits. */ - while (bits >= 0) { - wvalue = 0; /* The 'value' of the window */ + while (bits > 0) { - /* Scan the window, squaring the result as we go */ - for (i = 0; i < window; i++, bits--) { + /* Square the result window-size times */ + for (i = 0; i < window; i++) if (!bn_mul_mont_fixed_top(&tmp, &tmp, &tmp, mont, ctx)) goto err; - wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); - } /* + * Get a window's worth of bits from the exponent + * This avoids calling BN_is_bit_set for each bit, which + * is not only slower but also makes each bit vulnerable to + * EM (and likely other) side-channel attacks like One&Done + * (for details see "One&Done: A Single-Decryption EM-Based + * Attack on OpenSSL's Constant-Time Blinded RSA" by M. Alam, + * H. Khan, M. Dey, N. Sinha, R. Callan, A. Zajic, and + * M. Prvulovic, in USENIX Security'18) + */ + bits -= window; + wvalue = bn_get_bits(p, bits) & wmask; + /* * Fetch the appropriate pre-computed value from the pre-buf */ if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf, wvalue, @@ -1108,7 +1121,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, OPENSSL_free(powerbufFree); } BN_CTX_end(ctx); - return (ret); + return ret; } int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, @@ -1118,7 +1131,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, int b, bits, ret = 0; int r_is_one; BN_ULONG w, next_w; - BIGNUM *d, *r, *t; + BIGNUM *r, *t; BIGNUM *swap_tmp; #define BN_MOD_MUL_WORD(r, w, m) \ (BN_mul_word(r, (w)) && \ @@ -1149,7 +1162,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, if (!BN_is_odd(m)) { BNerr(BN_F_BN_MOD_EXP_MONT_WORD, BN_R_CALLED_WITH_EVEN_MODULUS); - return (0); + return 0; } if (m->top == 1) a %= m->d[0]; /* make sure that 'a' is reduced */ @@ -1172,10 +1185,9 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, } BN_CTX_start(ctx); - d = BN_CTX_get(ctx); r = BN_CTX_get(ctx); t = BN_CTX_get(ctx); - if (d == NULL || r == NULL || t == NULL) + if (t == NULL) goto err; if (in_mont != NULL) @@ -1256,7 +1268,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, BN_MONT_CTX_free(mont); BN_CTX_end(ctx); bn_check_top(rr); - return (ret); + return ret; } /* The old fallback, simple version :-) */ @@ -1292,7 +1304,7 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX_start(ctx); d = BN_CTX_get(ctx); val[0] = BN_CTX_get(ctx); - if (!d || !val[0]) + if (val[0] == NULL) goto err; if (!BN_nnmod(val[0], a, m, ctx)) @@ -1377,5 +1389,5 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, err: BN_CTX_end(ctx); bn_check_top(r); - return (ret); + return ret; } |