The branch OpenSSL_1_1_0-stable has been updated via 73bebc17a14da5278b01416b39e5c28a7d0c1861 (commit) via c5c6915fba3f1becfd78ed2be032caa38ecadef3 (commit) via db09fdc1a675bde167001a4f68e0f1e595e96dee (commit) via a6d8fe92a601728138e645302fa8bab7ca54fb58 (commit) from 5eee95a54de6854e60886c8e662a902184b12d04 (commit)
- Log ----------------------------------------------------------------- commit 73bebc17a14da5278b01416b39e5c28a7d0c1861 Author: Andy Polyakov <ap...@openssl.org> Date: Wed Aug 15 15:46:35 2018 +0200 bn/bn_lib.c: conceal even memmory access pattern in bn2binpad. (cherry picked from commit 324b95605225410763fe63f7cff36eb46ca54ee9) Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/6940) commit c5c6915fba3f1becfd78ed2be032caa38ecadef3 Author: Andy Polyakov <ap...@openssl.org> Date: Mon Aug 13 16:59:08 2018 +0200 bn/bn_blind.c: use Montgomery multiplication when possible. (cherry picked from commit e02c519cd32a55e6ad39a0cfbeeda775f9115f28) Resolved conflicts: crypto/bn/bn_blind.c Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/6940) commit db09fdc1a675bde167001a4f68e0f1e595e96dee Author: Andy Polyakov <ap...@openssl.org> Date: Fri Aug 10 19:46:03 2018 +0200 rsa/rsa_ossl.c: implement variant of "Smooth CRT-RSA." In [most common] case of p and q being of same width, it's possible to replace CRT modulo operations with Montgomery reductions. And those are even fixed-length Montgomery reductions... (cherry picked from commit 41bfd5e7c8ac3a0874a94e4d15c006ad5eb48e59) Resolved conflicts: crypto/rsa/rsa_ossl.c Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/6940) commit a6d8fe92a601728138e645302fa8bab7ca54fb58 Author: Andy Polyakov <ap...@openssl.org> Date: Fri Aug 10 19:31:22 2018 +0200 crypto/bn: add more fixed-top routines. Add bn_mul_fixed_top, bn_from_mont_fixed_top, bn_mod_sub_fixed_top. Switch to bn_{mul|sqr}_fixed_top in bn_mul_mont_fixed_top and remove memset in bn_from_montgomery_word. (cherry picked from commit fcc4ee09473cac511eca90faa003661c7786e4f9) Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/6940) ----------------------------------------------------------------------- Summary of changes: crypto/bn/bn_blind.c | 88 ++++++++++++++++---------- crypto/bn/bn_lib.c | 34 +++++++--- crypto/bn/bn_mod.c | 67 +++++++++++++++++++- crypto/bn/bn_mont.c | 27 +++++--- crypto/bn/bn_mul.c | 12 +++- crypto/bn/bn_sqr.c | 12 +++- crypto/include/internal/bn_int.h | 6 ++ crypto/rsa/rsa_ossl.c | 130 ++++++++++++++++++++++++++++----------- 8 files changed, 287 insertions(+), 89 deletions(-) diff --git a/crypto/bn/bn_blind.c b/crypto/bn/bn_blind.c index 24d1383..7a8237c 100644 --- a/crypto/bn/bn_blind.c +++ b/crypto/bn/bn_blind.c @@ -109,10 +109,15 @@ int BN_BLINDING_update(BN_BLINDING *b, BN_CTX *ctx) if (!BN_BLINDING_create_param(b, NULL, NULL, ctx, NULL, NULL)) goto err; } else if (!(b->flags & BN_BLINDING_NO_UPDATE)) { - if (!BN_mod_mul(b->A, b->A, b->A, b->mod, ctx)) - goto err; - if (!BN_mod_mul(b->Ai, b->Ai, b->Ai, b->mod, ctx)) - goto err; + if (b->m_ctx != NULL) { + if (!bn_mul_mont_fixed_top(b->Ai, b->Ai, b->Ai, b->m_ctx, ctx) + || !bn_mul_mont_fixed_top(b->A, b->A, b->A, b->m_ctx, ctx)) + goto err; + } else { + if (!BN_mod_mul(b->Ai, b->Ai, b->Ai, b->mod, ctx) + || !BN_mod_mul(b->A, b->A, b->A, b->mod, ctx)) + goto err; + } } ret = 1; @@ -144,13 +149,13 @@ int BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx) else if (!BN_BLINDING_update(b, ctx)) return (0); - if (r != NULL) { - if (!BN_copy(r, b->Ai)) - ret = 0; - } + if (r != NULL && (BN_copy(r, b->Ai) == NULL)) + return 0; - if (!BN_mod_mul(n, n, b->A, b->mod, ctx)) - ret = 0; + if (b->m_ctx != NULL) + ret = BN_mod_mul_montgomery(n, n, b->A, b->m_ctx, ctx); + else + ret = BN_mod_mul(n, n, b->A, b->mod, ctx); return ret; } @@ -167,14 +172,29 @@ int BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b, bn_check_top(n); - if (r != NULL) - ret = BN_mod_mul(n, n, r, b->mod, ctx); - else { - if (b->Ai == NULL) { - BNerr(BN_F_BN_BLINDING_INVERT_EX, BN_R_NOT_INITIALIZED); - return (0); + if (r == NULL && (r = b->Ai) == NULL) { + BNerr(BN_F_BN_BLINDING_INVERT_EX, BN_R_NOT_INITIALIZED); + return 0; + } + + if (b->m_ctx != NULL) { + /* ensure that BN_mod_mul_montgomery takes pre-defined path */ + if (n->dmax >= r->top) { + size_t i, rtop = r->top, ntop = n->top; + BN_ULONG mask; + + for (i = 0; i < rtop; i++) { + mask = (BN_ULONG)0 - ((i - ntop) >> (8 * sizeof(i) - 1)); + n->d[i] &= mask; + } + mask = (BN_ULONG)0 - ((rtop - ntop) >> (8 * sizeof(ntop) - 1)); + /* always true, if (rtop >= ntop) n->top = r->top; */ + n->top = (int)(rtop & ~mask) | (ntop & mask); + n->flags |= (BN_FLG_FIXED_TOP & ~mask); } - ret = BN_mod_mul(n, n, b->Ai, b->mod, ctx); + ret = BN_mod_mul_montgomery(n, n, r, b->m_ctx, ctx); + } else { + ret = BN_mod_mul(n, n, r, b->mod, ctx); } bn_check_top(n); @@ -253,31 +273,35 @@ BN_BLINDING *BN_BLINDING_create_param(BN_BLINDING *b, int rv; if (!BN_rand_range(ret->A, ret->mod)) goto err; - if (!int_bn_mod_inverse(ret->Ai, ret->A, ret->mod, ctx, &rv)) { - /* - * this should almost never happen for good RSA keys - */ - if (rv) { - if (retry_counter-- == 0) { - BNerr(BN_F_BN_BLINDING_CREATE_PARAM, - BN_R_TOO_MANY_ITERATIONS); - goto err; - } - } else - goto err; - } else + if (int_bn_mod_inverse(ret->Ai, ret->A, ret->mod, ctx, &rv)) break; + + /* + * this should almost never happen for good RSA keys + */ + if (!rv) + goto err; + + if (retry_counter-- == 0) { + BNerr(BN_F_BN_BLINDING_CREATE_PARAM, BN_R_TOO_MANY_ITERATIONS); + goto err; + } } while (1); if (ret->bn_mod_exp != NULL && ret->m_ctx != NULL) { - if (!ret->bn_mod_exp - (ret->A, ret->A, ret->e, ret->mod, ctx, ret->m_ctx)) + if (!ret->bn_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx, ret->m_ctx)) goto err; } else { if (!BN_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx)) goto err; } + if (ret->m_ctx != NULL) { + if (!bn_to_mont_fixed_top(ret->Ai, ret->Ai, ret->m_ctx, ctx) + || !bn_to_mont_fixed_top(ret->A, ret->A, ret->m_ctx, ctx)) + goto err; + } + return ret; err: if (b == NULL) { diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 25eac39..80f8599 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -503,26 +503,40 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) { int n; - size_t i, inc, lasti, j; + size_t i, lasti, j, atop, mask; BN_ULONG l; + /* + * In case |a| is fixed-top, BN_num_bytes can return bogus length, + * but it's assumed that fixed-top inputs ought to be "nominated" + * even for padded output, so it works out... + */ n = BN_num_bytes(a); - if (tolen == -1) + if (tolen == -1) { tolen = n; - else if (tolen < n) - return -1; + } else if (tolen < n) { /* uncommon/unlike case */ + BIGNUM temp = *a; - if (n == 0) { + bn_correct_top(&temp); + n = BN_num_bytes(&temp); + if (tolen < n) + return -1; + } + + /* Swipe through whole available data and don't give away padded zero. */ + atop = a->dmax * BN_BYTES; + if (atop == 0) { OPENSSL_cleanse(to, tolen); return tolen; } - lasti = n - 1; - for (i = 0, inc = 1, j = tolen; j > 0;) { + lasti = atop - 1; + atop = a->top * BN_BYTES; + for (i = 0, j = 0, to += tolen; j < (size_t)tolen; j++) { l = a->d[i / BN_BYTES]; - to[--j] = (unsigned char)(l >> (8 * (i % BN_BYTES)) & (0 - inc)); - inc = (i - lasti) >> (8 * sizeof(i) - 1); - i += inc; /* stay on top limb */ + mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); + *--to = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); + i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ } return tolen; diff --git a/crypto/bn/bn_mod.c b/crypto/bn/bn_mod.c index 2361094..2e98035 100644 --- a/crypto/bn/bn_mod.c +++ b/crypto/bn/bn_mod.c @@ -58,7 +58,7 @@ int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, if (mtop > sizeof(storage) / sizeof(storage[0]) && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL) - return 0; + return 0; ap = a->d != NULL ? a->d : tp; bp = b->d != NULL ? b->d : tp; @@ -83,6 +83,7 @@ int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, ((volatile BN_ULONG *)tp)[i] = 0; } r->top = mtop; + r->flags |= BN_FLG_FIXED_TOP; r->neg = 0; if (tp != storage) @@ -111,6 +112,70 @@ int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, } /* + * BN_mod_sub variant that may be used if both a and b are non-negative, + * a is less than m, while b is of same bit width as m. It's implemented + * as subtraction followed by two conditional additions. + * + * 0 <= a < m + * 0 <= b < 2^w < 2*m + * + * after subtraction + * + * -2*m < r = a - b < m + * + * Thus it takes up to two conditional additions to make |r| positive. + */ +int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m) +{ + size_t i, ai, bi, mtop = m->top; + BN_ULONG borrow, carry, ta, tb, mask, *rp; + const BN_ULONG *ap, *bp; + + if (bn_wexpand(r, mtop) == NULL) + return 0; + + rp = r->d; + ap = a->d != NULL ? a->d : rp; + bp = b->d != NULL ? b->d : rp; + + for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) { + mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); + ta = ap[ai] & mask; + + mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); + tb = bp[bi] & mask; + rp[i] = ta - tb - borrow; + if (ta != tb) + borrow = (ta < tb); + + i++; + ai += (i - a->dmax) >> (8 * sizeof(i) - 1); + bi += (i - b->dmax) >> (8 * sizeof(i) - 1); + } + ap = m->d; + for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) { + ta = ((ap[i] & mask) + carry) & BN_MASK2; + carry = (ta < carry); + rp[i] = (rp[i] + ta) & BN_MASK2; + carry += (rp[i] < ta); + } + borrow -= carry; + for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) { + ta = ((ap[i] & mask) + carry) & BN_MASK2; + carry = (ta < carry); + rp[i] = (rp[i] + ta) & BN_MASK2; + carry += (rp[i] < ta); + } + + r->top = mtop; + r->flags |= BN_FLG_FIXED_TOP; + r->neg = 0; + + return 1; +} + +/* * BN_mod_sub variant that may be used if both a and b are non-negative and * less than m */ diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index 3ccf8ea..4121433 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -64,10 +64,10 @@ int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, bn_check_top(tmp); if (a == b) { - if (!BN_sqr(tmp, a, ctx)) + if (!bn_sqr_fixed_top(tmp, a, ctx)) goto err; } else { - if (!BN_mul(tmp, a, b, ctx)) + if (!bn_mul_fixed_top(tmp, a, b, ctx)) goto err; } /* reduce from aRR to aR */ @@ -90,6 +90,7 @@ static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) BIGNUM *n; BN_ULONG *ap, *np, *rp, n0, v, carry; int nl, max, i; + unsigned int rtop; n = &(mont->N); nl = n->top; @@ -106,10 +107,10 @@ static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) np = n->d; rp = r->d; - /* clear the top words of T */ - i = max - r->top; - if (i) - memset(&rp[r->top], 0, sizeof(*rp) * i); + for (rtop = r->top, i = 0; i < max; i++) { + v = (BN_ULONG)0 - ((i - rtop) >> (8 * sizeof(rtop) - 1)); + rp[i] &= v; + } r->top = max; r->flags |= BN_FLG_FIXED_TOP; @@ -160,6 +161,18 @@ static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx) { + int retn; + + retn = bn_from_mont_fixed_top(ret, a, mont, ctx); + bn_correct_top(ret); + bn_check_top(ret); + + return retn; +} + +int bn_from_mont_fixed_top(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, + BN_CTX *ctx) +{ int retn = 0; #ifdef MONT_WORD BIGNUM *t; @@ -167,8 +180,6 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX_start(ctx); if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) { retn = bn_from_montgomery_word(ret, t, mont); - bn_correct_top(ret); - bn_check_top(ret); } BN_CTX_end(ctx); #else /* !MONT_WORD */ diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c index a1abc5b..a14f53f 100644 --- a/crypto/bn/bn_mul.c +++ b/crypto/bn/bn_mul.c @@ -833,6 +833,16 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { + int ret = bn_mul_fixed_top(r, a, b, ctx); + + bn_correct_top(r); + bn_check_top(r); + + return ret; +} + +int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) +{ int ret = 0; int top, al, bl; BIGNUM *rr; @@ -935,7 +945,7 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) end: #endif rr->neg = a->neg ^ b->neg; - bn_correct_top(rr); + rr->flags |= BN_FLG_FIXED_TOP; if (r != rr && BN_copy(r, rr) == NULL) goto err; diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c index 1f12a14..db72bf2 100644 --- a/crypto/bn/bn_sqr.c +++ b/crypto/bn/bn_sqr.c @@ -16,6 +16,16 @@ */ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { + int ret = bn_sqr_fixed_top(r, a, ctx); + + bn_correct_top(r); + bn_check_top(r); + + return ret; +} + +int bn_sqr_fixed_top(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) +{ int max, al; int ret = 0; BIGNUM *tmp, *rr; @@ -83,7 +93,7 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) rr->neg = 0; rr->top = max; - bn_correct_top(rr); + rr->flags |= BN_FLG_FIXED_TOP; if (r != rr && BN_copy(r, rr) == NULL) goto err; diff --git a/crypto/include/internal/bn_int.h b/crypto/include/internal/bn_int.h index 2fcdd0d..2be7fdd 100644 --- a/crypto/include/internal/bn_int.h +++ b/crypto/include/internal/bn_int.h @@ -85,8 +85,14 @@ int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx); int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx); +int bn_from_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, + BN_CTX *ctx); int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m); +int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m); +int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); +int bn_sqr_fixed_top(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); #ifdef __cplusplus } diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c index 36c4e42..5703411 100644 --- a/crypto/rsa/rsa_ossl.c +++ b/crypto/rsa/rsa_ossl.c @@ -127,8 +127,8 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, } if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) goto err; if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, @@ -312,8 +312,8 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) { + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) { BN_free(d); goto err; } @@ -435,8 +435,8 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) { + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) { BN_free(d); goto err; } @@ -541,8 +541,8 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, } if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) goto err; if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, @@ -583,7 +583,7 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) { BIGNUM *r1, *m1, *vrfy; - int ret = 0; + int ret = 0, smooth = 0; BN_CTX_start(ctx); @@ -593,43 +593,79 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) if (vrfy == NULL) goto err; - { - BIGNUM *p = BN_new(), *q = BN_new(); + if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { + BIGNUM *factor = BN_new(); + + if (factor == NULL) + goto err; /* * Make sure BN_mod_inverse in Montgomery initialization uses the * BN_FLG_CONSTTIME flag */ - if (p == NULL || q == NULL) { - BN_free(p); - BN_free(q); + if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME), + BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock, + factor, ctx)) + || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME), + BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock, + factor, ctx))) { + BN_free(factor); goto err; } - BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); - BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME); - - if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_p, rsa->lock, p, ctx) - || !BN_MONT_CTX_set_locked(&rsa->_method_mod_q, - rsa->lock, q, ctx)) { - BN_free(p); - BN_free(q); - goto err; - } - } /* - * We MUST free p and q before any further use of rsa->p and rsa->q + * We MUST free |factor| before any further use of the prime factors */ - BN_free(p); - BN_free(q); + BN_free(factor); + + smooth = (rsa->meth->bn_mod_exp == BN_mod_exp_mont) + && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p)); } if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) goto err; + if (smooth) { + /* + * Conversion from Montgomery domain, a.k.a. Montgomery reduction, + * accepts values in [0-m*2^w) range. w is m's bit width rounded up + * to limb width. So that at the very least if |I| is fully reduced, + * i.e. less than p*q, we can count on from-to round to perform + * below modulo operations on |I|. Unlike BN_mod it's constant time. + */ + if (/* m1 = I moq q */ + !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx) + || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx) + /* m1 = m1^dmq1 mod q */ + || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx, + rsa->_method_mod_q) + /* r1 = I mod p */ + || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx) + || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) + /* r1 = r1^dmp1 mod p */ + || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx, + rsa->_method_mod_p) + /* r1 = (r1 - m1) mod p */ + /* + * bn_mod_sub_fixed_top is not regular modular subtraction, + * it can tolerate subtrahend to be larger than modulus, but + * not bit-wise wider. This makes up for uncommon q>p case, + * when |m1| can be larger than |rsa->p|. + */ + || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p) + + /* r0 = r0 * iqmp mod p */ + || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) + || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p, + ctx) + || !bn_mul_fixed_top(r0, r1, rsa->q, ctx) + || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n)) + goto err; + + goto tail; + } + /* compute I mod q */ { BIGNUM *c = BN_new(); @@ -652,7 +688,7 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) /* compute r1^dmq1 mod q */ if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, - rsa->_method_mod_q)) { + rsa->_method_mod_q)) { BN_free(c); BN_free(dmq1); goto err; @@ -728,10 +764,18 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) if (!BN_add(r0, r1, m1)) goto err; + tail: if (rsa->e && rsa->n) { - if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, - rsa->_method_mod_n)) - goto err; + if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) { + if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx, + rsa->_method_mod_n)) + goto err; + } else { + bn_correct_top(r0); + if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, + rsa->_method_mod_n)) + goto err; + } /* * If 'I' was greater than (or equal to) rsa->n, the operation will * be equivalent to using 'I mod n'. However, the result of the @@ -740,6 +784,11 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) */ if (!BN_sub(vrfy, vrfy, I)) goto err; + if (BN_is_zero(vrfy)) { + bn_correct_top(r0); + ret = 1; + goto err; /* not actually error */ + } if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) goto err; if (BN_is_negative(vrfy)) @@ -766,6 +815,15 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) BN_free(d); } } + /* + * It's unfortunate that we have to bn_correct_top(r0). What hopefully + * saves the day is that correction is highly unlike, and private key + * operations are customarily performed on blinded message. Which means + * that attacker won't observe correlation with chosen plaintext. + * Secondly, remaining code would still handle it in same computational + * time and even conceal memory access pattern around corrected top. + */ + bn_correct_top(r0); ret = 1; err: BN_CTX_end(ctx); _____ openssl-commits mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-commits