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.

3 files changed, 59 insertions, 87 deletions

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<word>::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<word>::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<word>::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<word>::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);
       }
    }