From f345b1f39d9b4e4c9ef07e7522e9b2a870c9ca09 Mon Sep 17 00:00:00 2001 From: David Benjamin Date: Wed, 31 Jan 2018 14:47:41 -0500 Subject: [PATCH] Fix timing leak in BN_from_montgomery_word. BN_from_montgomery_word doesn't have a constant memory access pattern. Replace the pointer trick with a constant-time select. There is, of course, still the bn_correct_top leak pervasive in BIGNUM itself. See also https://boringssl-review.googlesource.com/22904 from BoringSSL. Reviewed-by: Andy Polyakov Reviewed-by: Kurt Roeckx (Merged from https://github.com/openssl/openssl/pull/5228) --- crypto/bn/bn_mont.c | 57 ++++++++++++++++----------------------------- 1 file changed, 20 insertions(+), 37 deletions(-) diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index 2119bfa331..6357c60c77 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -101,6 +101,11 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) r->top = max; n0 = mont->n0[0]; + /* + * Add multiples of |n| to |r| until R = 2^(nl * BN_BITS2) divides it. On + * input, we had |r| < |n| * R, so now |r| < 2 * |n| * R. Note that |r| + * includes |carry| which is stored separately. + */ for (carry = 0, i = 0; i < nl; i++, rp++) { v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2); v = (v + carry + rp[nl]) & BN_MASK2; @@ -115,46 +120,24 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) ret->neg = r->neg; rp = ret->d; - ap = &(r->d[nl]); -# define BRANCH_FREE 1 -# if BRANCH_FREE - { - BN_ULONG *nrp; - size_t m; + /* + * Shift |nl| words to divide by R. We have |ap| < 2 * |n|. Note that |ap| + * includes |carry| which is stored separately. + */ + ap = &(r->d[nl]); - v = bn_sub_words(rp, ap, np, nl) - carry; - /* - * if subtraction result is real, then trick unconditional memcpy - * below to perform in-place "refresh" instead of actual copy. - */ - m = (0 - (size_t)v); - nrp = - (BN_ULONG *)(((PTR_SIZE_INT) rp & ~m) | ((PTR_SIZE_INT) ap & m)); - - for (i = 0, nl -= 4; i < nl; i += 4) { - BN_ULONG t1, t2, t3, t4; - - t1 = nrp[i + 0]; - t2 = nrp[i + 1]; - t3 = nrp[i + 2]; - ap[i + 0] = 0; - t4 = nrp[i + 3]; - ap[i + 1] = 0; - rp[i + 0] = t1; - ap[i + 2] = 0; - rp[i + 1] = t2; - ap[i + 3] = 0; - rp[i + 2] = t3; - rp[i + 3] = t4; - } - for (nl += 4; i < nl; i++) - rp[i] = nrp[i], ap[i] = 0; + /* + * |v| is one if |ap| - |np| underflowed or zero if it did not. Note |v| + * cannot be -1. That would imply the subtraction did not fit in |nl| words, + * and we know at most one subtraction is needed. + */ + v = bn_sub_words(rp, ap, np, nl) - carry; + v = 0 - v; + for (i = 0; i < nl; i++) { + rp[i] = (v & ap[i]) | (~v & rp[i]); + ap[i] = 0; } -# else - if (bn_sub_words(rp, ap, np, nl) - carry) - memcpy(rp, ap, nl * sizeof(BN_ULONG)); -# endif bn_correct_top(r); bn_correct_top(ret); bn_check_top(ret); -- 2.25.1