Use a side channel silent table look up in the Montgomery exponentiation

6 files changed, 93 insertions, 36 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 5bf91df23..126688de9 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -9,6 +9,7 @@
 #include <botan/internal/mp_core.h>
 #include <botan/internal/rounding.h>
 #include <botan/internal/bit_ops.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -293,4 +294,27 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
       m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
    }
 
+void BigInt::shrink_to_fit()
+   {
+   m_reg.resize(sig_words());
+   }
+
+void BigInt::const_time_lookup(secure_vector<word>& output,
+                               const std::vector<BigInt>& vec,
+                               size_t idx)
+   {
+   const size_t words = output.size();
+
+   clear_mem(output.data(), output.size());
+
+   for(size_t i = 0; i != vec.size(); ++i)
+      {
+      BOTAN_ASSERT(vec[i].size() >= words,
+                   "Word size as expected in const_time_lookup");
+
+      for(size_t w = 0; w != words; ++w)
+         output[w] |= CT::select<word>(CT::is_equal(i, idx), vec[i].word_at(w), 0);
+      }
+   }
+
 }
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 9455a869b..e33adcf68 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -435,6 +435,8 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void grow_to(size_t n);
 
+     void shrink_to_fit();
+
      /**
      * Fill BigInt with a random number with size of bitsize
      *
@@ -577,6 +579,15 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes);
 
+     /**
+     * Set output = vec[idx].m_reg in constant time
+     * All words of vec must have the same size
+     */
+     static void const_time_lookup(
+        secure_vector<word>& output,
+        const std::vector<BigInt>& vec,
+        size_t idx);
+
    private:
       secure_vector<word> m_reg;
       Sign m_signedness = Positive;
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 06b0c6f7f..15b71d03f 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -183,6 +183,11 @@ void bigint_comba_sqr16(word out[32], const word in[16]);
 */
 void bigint_mul(BigInt& z, const BigInt& x, const BigInt& y, word workspace[]);
 
+void bigint_mul(word z[], size_t z_size,
+                const word x[], size_t x_size, size_t x_sw,
+                const word y[], size_t y_size, size_t y_sw,
+                word workspace[]);
+
 void bigint_sqr(word z[], size_t z_size, word workspace[],
                 const word x[], size_t x_size, size_t x_sw);
 
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 5082e38db..60924fb86 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -251,58 +251,66 @@ size_t karatsuba_size(size_t z_size, size_t x_size, size_t x_sw)
 */
 void bigint_mul(BigInt& z, const BigInt& x, const BigInt& y, word workspace[])
    {
-   const size_t x_sig_words = x.sig_words();
-   const size_t y_sig_words = y.sig_words();
+   return bigint_mul(z.mutable_data(), z.size(),
+                     x.data(), x.size(), x.sig_words(),
+                     y.data(), y.size(), y.sig_words(),
+                     workspace);
+   }
 
-   clear_mem(z.mutable_data(), z.size());
+void bigint_mul(word z[], size_t z_size,
+                const word x[], size_t x_size, size_t x_sw,
+                const word y[], size_t y_size, size_t y_sw,
+                word workspace[])
+   {
+   clear_mem(z, z_size);
 
-   if(x_sig_words == 1)
+   if(x_sw == 1)
       {
-      bigint_linmul3(z.mutable_data(), y.data(), y_sig_words, x.data()[0]);
+      bigint_linmul3(z, y, y_sw, x[0]);
       }
-   else if(y_sig_words == 1)
+   else if(y_sw == 1)
       {
-      bigint_linmul3(z.mutable_data(), x.data(), x_sig_words, y.data()[0]);
+      bigint_linmul3(z, x, x_sw, y[0]);
       }
-   else if(x_sig_words <= 4 && x.size() >= 4 &&
-           y_sig_words <= 4 && y.size() >= 4 && z.size() >= 8)
+   else if(x_sw <= 4 && x_size >= 4 &&
+           y_sw <= 4 && y_size >= 4 && z_size >= 8)
       {
-      bigint_comba_mul4(z.mutable_data(), x.data(), y.data());
+      bigint_comba_mul4(z, x, y);
       }
-   else if(x_sig_words <= 6 && x.size() >= 6 &&
-           y_sig_words <= 6 && y.size() >= 6 && z.size() >= 12)
+   else if(x_sw <= 6 && x_size >= 6 &&
+           y_sw <= 6 && y_size >= 6 && z_size >= 12)
       {
-      bigint_comba_mul6(z.mutable_data(), x.data(), y.data());
+      bigint_comba_mul6(z, x, y);
       }
-   else if(x_sig_words <= 8 && x.size() >= 8 &&
-           y_sig_words <= 8 && y.size() >= 8 && z.size() >= 16)
+   else if(x_sw <= 8 && x_size >= 8 &&
+           y_sw <= 8 && y_size >= 8 && z_size >= 16)
       {
-      bigint_comba_mul8(z.mutable_data(), x.data(), y.data());
+      bigint_comba_mul8(z, x, y);
       }
-   else if(x_sig_words <= 9 && x.size() >= 9 &&
-           y_sig_words <= 9 && y.size() >= 9 && z.size() >= 18)
+   else if(x_sw <= 9 && x_size >= 9 &&
+           y_sw <= 9 && y_size >= 9 && z_size >= 18)
       {
-      bigint_comba_mul9(z.mutable_data(), x.data(), y.data());
+      bigint_comba_mul9(z, x, y);
       }
-   else if(x_sig_words <= 16 && x.size() >= 16 &&
-           y_sig_words <= 16 && y.size() >= 16 && z.size() >= 32)
+   else if(x_sw <= 16 && x_size >= 16 &&
+           y_sw <= 16 && y_size >= 16 && z_size >= 32)
       {
-      bigint_comba_mul16(z.mutable_data(), x.data(), y.data());
+      bigint_comba_mul16(z, x, y);
       }
-   else if(x_sig_words < KARATSUBA_MULTIPLY_THRESHOLD ||
-           y_sig_words < KARATSUBA_MULTIPLY_THRESHOLD ||
+   else if(x_sw < KARATSUBA_MULTIPLY_THRESHOLD ||
+           y_sw < KARATSUBA_MULTIPLY_THRESHOLD ||
            !workspace)
       {
-      basecase_mul(z.mutable_data(), x.data(), x_sig_words, y.data(), y_sig_words);
+      basecase_mul(z, x, x_sw, y, y_sw);
       }
    else
       {
-      const size_t N = karatsuba_size(z.size(), x.size(), x_sig_words, y.size(), y_sig_words);
+      const size_t N = karatsuba_size(z_size, x_size, x_sw, y_size, y_sw);
 
       if(N)
-         karatsuba_mul(z.mutable_data(), x.data(), y.data(), N, workspace);
+         karatsuba_mul(z, x, y, N, workspace);
       else
-         basecase_mul(z.mutable_data(), x.data(), x_sig_words, y.data(), y_sig_words);
+         basecase_mul(z, x, x_sw, y, y_sw);
       }
    }
 
diff --git a/src/lib/math/mp/mp_monty.cpp b/src/lib/math/mp/mp_monty.cpp
index 88b5de715..2599266b0 100644
--- a/src/lib/math/mp/mp_monty.cpp
+++ b/src/lib/math/mp/mp_monty.cpp
@@ -101,9 +101,8 @@ void bigint_monty_mul(BigInt& z, const BigInt& x, const BigInt& y,
    bigint_mul(z, x, y, &ws[0]);
 
    bigint_monty_redc(z.mutable_data(),
-                     &p[0], p_size, p_dash,
-                     &ws[0]);
-
+                     p, p_size, p_dash,
+                     ws);
    }
 
 void bigint_monty_sqr(BigInt& z, const BigInt& x, const word p[],
@@ -113,8 +112,8 @@ void bigint_monty_sqr(BigInt& z, const BigInt& x, const word p[],
               x.data(), x.size(), x.sig_words());
 
    bigint_monty_redc(z.mutable_data(),
-                     &p[0], p_size, p_dash,
-                     &ws[0]);
+                     p, p_size, p_dash,
+                     ws);
    }
 
 }
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index 7e5c0be55..cd385e7ec 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -58,6 +58,8 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
                        workspace.data());
 
       m_g[i] = z;
+      m_g[i].shrink_to_fit();
+      m_g[i].grow_to(m_mod_words);
       }
    }
 
@@ -74,6 +76,7 @@ BigInt Montgomery_Exponentiator::execute() const
 
    BigInt z(BigInt::Positive, z_size);
    secure_vector<word> workspace(z.size());
+   secure_vector<word> e(m_mod_words);
 
    for(size_t i = exp_nibbles; i > 0; --i)
       {
@@ -87,9 +90,16 @@ BigInt Montgomery_Exponentiator::execute() const
 
       const uint32_t nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits);
 
-      bigint_monty_mul(z, x, m_g[nibble],
-                       m_modulus.data(), m_mod_words, m_mod_prime,
-                       workspace.data());
+      BigInt::const_time_lookup(e, m_g, nibble);
+
+      bigint_mul(z.mutable_data(), z.size(),
+                 x.data(), x.size(), x.sig_words(),
+                 e.data(), m_mod_words, m_mod_words,
+                 workspace.data());
+
+      bigint_monty_redc(z.mutable_data(),
+                        m_modulus.data(), m_mod_words, m_mod_prime,
+                        workspace.data());
 
       x = z;
       }