From 6276f596482da34f5535bc94841e85798ba21139 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 6 Dec 2018 21:52:24 -0500 Subject: Const time the behavior of shifts [WIP] They would previously leak for example if the requested shift was 0. However, that should only happen in two situations: very dumb code explicitly requested a shift of zero (in which case we don't care if performance is poor, your code is dumb) or a variable shift that just happens to be zero, in which case the variable may be a secret, for instance this can be seen in the GCD computation. --- src/lib/math/bigint/big_ops2.cpp | 38 +++++++-------- src/lib/math/bigint/big_ops3.cpp | 9 ---- src/lib/math/mp/mp_core.h | 99 +++++++++++++++++----------------------- 3 files changed, 59 insertions(+), 87 deletions(-) (limited to 'src') diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp index 0dc3c7715..6b8be1238 100644 --- a/src/lib/math/bigint/big_ops2.cpp +++ b/src/lib/math/bigint/big_ops2.cpp @@ -318,23 +318,20 @@ word BigInt::operator%=(word mod) */ BigInt& BigInt::operator<<=(size_t shift) { - if(shift) - { - const size_t shift_words = shift / BOTAN_MP_WORD_BITS; - const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; - const size_t words = sig_words(); + const size_t shift_words = shift / BOTAN_MP_WORD_BITS; + const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; + const size_t words = sig_words(); - /* - * FIXME - if shift_words == 0 && the top shift_bits of the top word - * are zero then we know that no additional word is needed and can - * skip the allocation. - */ - const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0); + /* + * FIXME - if shift_words == 0 && the top shift_bits of the top word + * are zero then we know that no additional word is needed and can + * skip the allocation. + */ + const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0); - m_data.grow_to(needed_size); + m_data.grow_to(needed_size); - bigint_shl1(m_data.mutable_data(), words, shift_words, shift_bits); - } + bigint_shl1(m_data.mutable_data(), words, shift_words, shift_bits); return (*this); } @@ -344,16 +341,13 @@ BigInt& BigInt::operator<<=(size_t shift) */ BigInt& BigInt::operator>>=(size_t shift) { - if(shift) - { - const size_t shift_words = shift / BOTAN_MP_WORD_BITS; - const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; + const size_t shift_words = shift / BOTAN_MP_WORD_BITS; + const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; - bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); + bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); - if(is_negative() && is_zero()) - set_sign(Positive); - } + if(is_negative() && is_zero()) + set_sign(Positive); return (*this); } diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp index e6c745dca..30b27c87b 100644 --- a/src/lib/math/bigint/big_ops3.cpp +++ b/src/lib/math/bigint/big_ops3.cpp @@ -152,9 +152,6 @@ word operator%(const BigInt& n, word mod) */ BigInt operator<<(const BigInt& x, size_t shift) { - if(shift == 0) - return x; - const size_t shift_words = shift / BOTAN_MP_WORD_BITS, shift_bits = shift % BOTAN_MP_WORD_BITS; @@ -170,16 +167,10 @@ BigInt operator<<(const BigInt& x, size_t shift) */ BigInt operator>>(const BigInt& x, size_t shift) { - if(shift == 0) - return x; - const size_t shift_words = shift / BOTAN_MP_WORD_BITS; const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; const size_t x_sw = x.sig_words(); - if(shift_words >= x_sw) - return 0; - BigInt y(x.sign(), x_sw - shift_words); bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index f586285bd..0d9c6a6a3 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -411,89 +411,76 @@ bigint_sub_abs(word z[], inline void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift) { - if(word_shift) - { - copy_mem(x + word_shift, x, x_size); - clear_mem(x, word_shift); - } + copy_mem(x + word_shift, x, x_size); + clear_mem(x, word_shift); - if(bit_shift) + const auto carry_mask = CT::Mask::expand(bit_shift); + const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); + + word carry = 0; + for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) { - word carry = 0; - for(size_t j = word_shift; j != x_size + word_shift + 1; ++j) - { - word temp = x[j]; - x[j] = (temp << bit_shift) | carry; - carry = (temp >> (BOTAN_MP_WORD_BITS - bit_shift)); - } + const word w = x[i]; + x[i] = (w << bit_shift) | carry; + carry = carry_mask.if_set_return(w >> carry_shift); } } inline void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift) { - if(x_size < word_shift) - { - clear_mem(x, x_size); - return; - } + const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0; - if(word_shift) - { - copy_mem(x, x + word_shift, x_size - word_shift); - clear_mem(x + x_size - word_shift, word_shift); - } + copy_mem(x, x + word_shift, top); + clear_mem(x + top, std::min(word_shift, x_size)); - if(bit_shift) - { - word carry = 0; - - size_t top = x_size - word_shift; + const auto carry_mask = CT::Mask::expand(bit_shift); + const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); - while(top) - { - word w = x[top-1]; - x[top-1] = (w >> bit_shift) | carry; - carry = (w << (BOTAN_MP_WORD_BITS - bit_shift)); + word carry = 0; - top--; - } + for(size_t i = 0; i != top; ++i) + { + const word w = x[top - i - 1]; + x[top-i-1] = (w >> bit_shift) | carry; + carry = carry_mask.if_set_return(w << carry_shift); } } inline void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift) { - for(size_t j = 0; j != x_size; ++j) - y[j + word_shift] = x[j]; - if(bit_shift) + copy_mem(y + word_shift, x, x_size); + + const auto carry_mask = CT::Mask::expand(bit_shift); + const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); + + word carry = 0; + for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) { - word carry = 0; - for(size_t j = word_shift; j != x_size + word_shift + 1; ++j) - { - word w = y[j]; - y[j] = (w << bit_shift) | carry; - carry = (w >> (BOTAN_MP_WORD_BITS - bit_shift)); - } + const word w = y[i]; + y[i] = (w << bit_shift) | carry; + carry = carry_mask.if_set_return(w >> carry_shift); } } inline void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift) { - if(x_size < word_shift) return; + if(x_size < word_shift) // XXX + return; + + copy_mem(y, x + word_shift, x_size - word_shift); + + const auto carry_mask = CT::Mask::expand(bit_shift); + const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); - for(size_t j = 0; j != x_size - word_shift; ++j) - y[j] = x[j + word_shift]; - if(bit_shift) + word carry = 0; + for(size_t i = x_size - word_shift; i > 0; --i) { - word carry = 0; - for(size_t j = x_size - word_shift; j > 0; --j) - { - word w = y[j-1]; - y[j-1] = (w >> bit_shift) | carry; - carry = (w << (BOTAN_MP_WORD_BITS - bit_shift)); - } + word w = y[i-1]; + y[i-1] = (w >> bit_shift) | carry; + carry = carry_mask.if_set_return(w << carry_shift); } } -- cgit v1.2.3 From 63fefbcc6ea922bdd14909e025ded5322bdb9578 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Fri, 7 Dec 2018 11:45:48 -0500 Subject: Fix bug and avoid allocations in left shift --- src/lib/math/bigint/big_ops2.cpp | 15 ++++++--------- src/lib/math/bigint/bigint.cpp | 27 ++++++++++++++++++--------- src/lib/math/bigint/bigint.h | 7 +++++++ src/lib/math/bigint/divide.cpp | 3 ++- src/lib/math/mp/mp_core.h | 6 +++--- 5 files changed, 36 insertions(+), 22 deletions(-) (limited to 'src') diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp index 6b8be1238..c42bf16e9 100644 --- a/src/lib/math/bigint/big_ops2.cpp +++ b/src/lib/math/bigint/big_ops2.cpp @@ -320,18 +320,15 @@ BigInt& BigInt::operator<<=(size_t shift) { const size_t shift_words = shift / BOTAN_MP_WORD_BITS; const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; - const size_t words = sig_words(); + const size_t size = sig_words(); - /* - * FIXME - if shift_words == 0 && the top shift_bits of the top word - * are zero then we know that no additional word is needed and can - * skip the allocation. - */ - const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0); + const size_t bits_free = top_bits_free(); + + const size_t new_size = size + shift_words + (bits_free < shift); - m_data.grow_to(needed_size); + m_data.grow_to(new_size); - bigint_shl1(m_data.mutable_data(), words, shift_words, shift_bits); + bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); return (*this); } diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index dd5ee6ac3..37a0fd0d4 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -273,9 +273,20 @@ size_t BigInt::bytes() const return round_up(bits(), 8) / 8; } -/* -* Count how many bits are being used -*/ +size_t BigInt::top_bits_free() const + { + const size_t words = sig_words(); + + const word top_word = word_at(words - 1); + + // Need to unpoison due to high_bit not being const time + CT::unpoison(top_word); + + const size_t bits_used = high_bit(top_word); + + return BOTAN_MP_WORD_BITS - bits_used; + } + size_t BigInt::bits() const { const size_t words = sig_words(); @@ -283,12 +294,10 @@ size_t BigInt::bits() const if(words == 0) return 0; - const size_t full_words = words - 1; - const word top_word = word_at(full_words); - // Need to unpoison due to high_bit not being const time - CT::unpoison(top_word); - const size_t bits = (full_words * BOTAN_MP_WORD_BITS + high_bit(top_word)); - return bits; + const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS; + const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free(); + + return full_words + top_bits; } /* diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index 31eee4c3c..ade70ba68 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -591,6 +591,13 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ size_t bits() const; + /** + * Get the number of high bits unset in the top (allocated) word + * of this integer. Returns BOTAN_MP_WORD_BITS only iff *this is + * zero. Ignores sign. + */ + size_t top_bits_free() const; + /** * Return a mutable pointer to the register * @result a pointer to the start of the internal register diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp index be47c6b5d..fdb920241 100644 --- a/src/lib/math/bigint/divide.cpp +++ b/src/lib/math/bigint/divide.cpp @@ -175,7 +175,7 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) y.set_sign(BigInt::Positive); // Calculate shifts needed to normalize y with high bit set - const size_t shifts = BOTAN_MP_WORD_BITS - high_bit(y.word_at(y_words-1)); + const size_t shifts = y.top_bits_free(); y <<= shifts; r <<= shifts; @@ -197,6 +197,7 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) const word y_t0 = y.word_at(t); const word y_t1 = y.word_at(t-1); + BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1); for(size_t j = n; j != t; --j) { diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index 0d9c6a6a3..9caacf9fb 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -408,17 +408,17 @@ bigint_sub_abs(word z[], /* * Shift Operations */ -inline void bigint_shl1(word x[], size_t x_size, +inline void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift) { - copy_mem(x + word_shift, x, x_size); + copy_mem(x + word_shift, x, x_words); clear_mem(x, word_shift); const auto carry_mask = CT::Mask::expand(bit_shift); const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); word carry = 0; - for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) + for(size_t i = word_shift; i != x_size; ++i) { const word w = x[i]; x[i] = (w << bit_shift) | carry; -- cgit v1.2.3 From 9ea9ebe5cb72656717eea35836b0fb827a5cee86 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Fri, 7 Dec 2018 12:09:50 -0500 Subject: Avoid early exit --- src/lib/math/mp/mp_core.h | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index 9caacf9fb..1ac6f7173 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -467,16 +467,15 @@ inline void bigint_shl2(word y[], const word x[], size_t x_size, inline void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift) { - if(x_size < word_shift) // XXX - return; + const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift); - copy_mem(y, x + word_shift, x_size - word_shift); + copy_mem(y, x + word_shift, new_size); const auto carry_mask = CT::Mask::expand(bit_shift); const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift); word carry = 0; - for(size_t i = x_size - word_shift; i > 0; --i) + for(size_t i = new_size; i > 0; --i) { word w = y[i-1]; y[i-1] = (w >> bit_shift) | carry; -- cgit v1.2.3