Merge GH #1606 Make Montgomery exponentation const time

7 files changed, 124 insertions, 60 deletions

diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index cf5f26003..b7d868cbf 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -1,9 +1,9 @@
 Side Channels
 =========================
 
-Many cryptographic systems can be broken by side channels. This document notes
-side channel protections which are currently implemented, as well as areas of
-the code which are known to be vulnerable to side channels. The latter are
+Many cryptographic systems can be easily broken by side channels. This document
+notes side channel protections which are currently implemented, as well as areas
+of the code which are known to be vulnerable to side channels. The latter are
 obviously all open for future improvement.
 
 The following text assumes the reader is already familiar with cryptographic
@@ -20,7 +20,7 @@ inverse with each decryption, both the mask and its inverse are simply squared
 to choose the next blinding factor. This is much faster than computing a fresh
 value each time, and the additional relation is thought to provide only minimal
 useful information for an attacker. Every BOTAN_BLINDING_REINIT_INTERVAL
-(default 32) operations, a new starting point is chosen.
+(default 64) operations, a new starting point is chosen.
 
 Exponent blinding uses new values for each signature.
 
@@ -109,17 +109,17 @@ Modular Exponentiation
 ------------------------
 
 Modular exponentiation uses a fixed window algorithm with Montgomery
-representation. A side channel silent table lookup is used to access the
-precomputed powers. See powm_mnt.cpp.
+representation. A side channel silent table lookup is used to access
+the precomputed powers. Currently the bit length of the exponent is
+leaked (with a granularity based on the window size, typically 4 bits)
+due to the number of loop iterations. See monty_exp.cpp
 
-The Karatsuba multiplication algorithm has some conditional branches that
-probably expose information through the branch predictor, but probably? does not
-expose a timing channel since the same amount of work is done on both sides of
-the conditional. There is certainly room for improvement here. See mp_karat.cpp
-for details.
+Karatsuba multiplication algorithm avoids any conditional branches; in
+cases where different operations must be performed it instead uses masked
+operations. See mp_karat.cpp for details.
 
-The Montgomery reduction is written (and tested) to run in constant time. See
-mp_monty.cpp.
+The Montgomery reduction is written (and tested) to run in constant time.
+The final reduction is handled with a masked subtraction. See mp_monty.cpp.
 
 ECC point decoding
 ----------------------
diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp
index b1add33a4..2ae65e508 100644
--- a/src/lib/math/mp/mp_core.cpp
+++ b/src/lib/math/mp/mp_core.cpp
@@ -92,6 +92,34 @@ word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
    return carry & mask;
    }
 
+void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
+   {
+   const size_t blocks = size - (size % 8);
+
+   word carry = 0;
+   word borrow = 0;
+
+   word t0[8] = { 0 };
+   word t1[8] = { 0 };
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      carry = word8_add3(t0, x + i, y + i, carry);
+      borrow = word8_sub3(t1, x + i, y + i, borrow);
+
+      for(size_t j = 0; j != 8; ++j)
+         x[i+j] = CT::select(mask, t0[j], t1[j]);
+      }
+
+   for(size_t i = blocks; i != size; ++i)
+      {
+      const word a = word_add(x[i], y[i], &carry);
+      const word s = word_sub(x[i], y[i], &borrow);
+
+      x[i] = CT::select(mask, a, s);
+      }
+   }
+
 void bigint_cnd_abs(word cnd, word x[], size_t size)
    {
    const word mask = CT::expand_mask(cnd);
@@ -211,18 +239,35 @@ void bigint_sub2_rev(word x[],  const word y[], size_t y_size)
    BOTAN_ASSERT(!borrow, "y must be greater than x");
    }
 
-int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t sz)
+word bigint_sub_abs(word z[],
+                    const word x[], const word y[], size_t N,
+                    word ws[])
    {
-   word borrow = bigint_sub3(z, x, sz, y, sz);
+   // Subtract in both direction then conditional copy out the result
+
+   word* ws0 = ws;
+   word* ws1 = ws + N;
+
+   word borrow0 = 0;
+   word borrow1 = 0;
 
-   CT::unpoison(borrow);
-   if(borrow)
+   const size_t blocks = N - (N % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
+      borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
+      }
+
+   for(size_t i = blocks; i != N; ++i)
       {
-      bigint_sub3(z, y, sz, x, sz);
-      return -1;
+      ws0[i] = word_sub(x[i], y[i], &borrow0);
+      ws1[i] = word_sub(y[i], x[i], &borrow1);
       }
 
-   return 1;
+   word mask = CT::conditional_copy_mem(borrow1, z, ws0, ws1, N);
+
+   return CT::select<word>(mask, 0, 1);
    }
 
 /*
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 4ae28f7bb..9430c3753 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -27,20 +27,29 @@ BOTAN_TEST_API
 void bigint_cnd_swap(word cnd, word x[], word y[], size_t size);
 
 /*
-* If cond > 0 adds x[0:size] to y[0:size] and returns carry
+* If cond > 0 adds x[0:size] and y[0:size] and returns carry
 * Runs in constant time
 */
 BOTAN_TEST_API
 word bigint_cnd_add(word cnd, word x[], const word y[], size_t size);
 
 /*
-* If cond > 0 subs x[0:size] to y[0:size] and returns borrow
+* If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
 * Runs in constant time
 */
 BOTAN_TEST_API
 word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
 
 /*
+* Equivalent to
+*   bigint_cnd_add( mask, x, y, size);
+*   bigint_cnd_sub(~mask, x, y, size);
+*
+* Mask must be either 0 or all 1 bits
+*/
+void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size);
+
+/*
 * 2s complement absolute value
 * If cond > 0 sets x to ~x + 1
 * Runs in constant time
@@ -100,9 +109,16 @@ word bigint_sub3(word z[],
 * Otherwise compute z = y - x
 * No borrow is possible since the result is always >= 0
 *
-* Returns 1 if x >= y or -1 if x < y
-*/
-int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t size);
+* Returns 1 if x >= y or 0 if x < y
+* @param z output array of at least N words
+* @param x input array of N words
+* @param y input array of N words
+* @param N length of x and y
+* @param ws array of at least 2*N words
+*/
+word bigint_sub_abs(word z[],
+                    const word x[], const word y[], size_t N,
+                    word ws[]);
 
 /*
 * Shift Operations
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 03a37ed8d..69e2ae665 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -1,6 +1,6 @@
 /*
 * Multiplication and Squaring
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2018 Jack Lloyd
 *     2016 Matthias Gierlings
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -8,6 +8,7 @@
 
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_asmi.h>
+#include <botan/internal/ct_utils.h>
 #include <botan/mem_ops.h>
 #include <botan/exceptn.h>
 
@@ -120,11 +121,10 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
    */
 
    // First compute (X_lo - X_hi)*(Y_hi - Y_lo)
-   const int32_t cmp0 = bigint_sub_abs(z0, x0, x1, N2);
-   const int32_t cmp1 = bigint_sub_abs(z1, y1, y0, N2);
+   const word cmp0 = bigint_sub_abs(z0, x0, x1, N2, workspace);
+   const word cmp1 = bigint_sub_abs(z1, y1, y0, N2, workspace);
 
    karatsuba_mul(ws0, z0, z1, N2, ws1);
-   const bool is_negative = cmp0 != cmp1;
 
    // Compute X_lo * Y_lo
    karatsuba_mul(z0, x0, y0, N2, ws1);
@@ -138,10 +138,11 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
    z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1);
    bigint_add2_nc(z + N + N2, N2, &z_carry, 1);
 
-   if(is_negative)
-      bigint_sub2(z + N2, 2*N-N2, ws0, N);
-   else
-      bigint_add2_nc(z + N2, 2*N-N2, ws0, N);
+   clear_mem(workspace + N, N2);
+
+   const word neg_mask = CT::is_equal<word>(cmp0, cmp1);
+
+   bigint_cnd_addsub(neg_mask, z + N2, workspace, 2*N-N2);
    }
 
 /*
@@ -178,7 +179,7 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[])
    clear_mem(workspace, 2*N);
 
    // See comment in karatsuba_mul
-   bigint_sub_abs(z0, x0, x1, N2);
+   bigint_sub_abs(z0, x0, x1, N2, workspace);
    karatsuba_sqr(ws0, z0, N2, ws1);
 
    karatsuba_sqr(z0, x0, N2, ws1);
diff --git a/src/lib/math/mp/mp_monty.cpp b/src/lib/math/mp/mp_monty.cpp
index cae113df0..e5dda705c 100644
--- a/src/lib/math/mp/mp_monty.cpp
+++ b/src/lib/math/mp/mp_monty.cpp
@@ -116,10 +116,6 @@ void bigint_monty_redc(word z[],
 
    BOTAN_ARG_CHECK(ws_size >= z_size, "workspace too small");
 
-   CT::poison(z, z_size);
-   CT::poison(p, p_size);
-   CT::poison(ws, 2*(p_size+1));
-
    if(p_size == 4)
       bigint_monty_redc_4(z, p, p_dash, ws);
    else if(p_size == 6)
@@ -134,10 +130,6 @@ void bigint_monty_redc(word z[],
       bigint_monty_redc_32(z, p, p_dash, ws);
    else
       bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws);
-
-   CT::unpoison(z, z_size);
-   CT::unpoison(p, p_size);
-   CT::unpoison(ws, 2*(p_size+1));
    }
 
 }
diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index b33fdf34c..0560cc59e 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -76,10 +76,13 @@ BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y,
    if(ws.size() < output_size)
       ws.resize(output_size);
 
+   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
+   BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
+
    BigInt z(BigInt::Positive, output_size);
    bigint_mul(z.mutable_data(), z.size(),
-              x.data(), x.size(), x.sig_words(),
-              y.data(), y.size(), y.sig_words(),
+              x.data(), x.size(), std::min(m_p_words, x.size()),
+              y.data(), y.size(), std::min(m_p_words, y.size()),
               ws.data(), ws.size());
 
    bigint_monty_redc(z.mutable_data(),
@@ -98,9 +101,11 @@ BigInt Montgomery_Params::mul(const BigInt& x,
       ws.resize(output_size);
    BigInt z(BigInt::Positive, output_size);
 
+   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
+
    bigint_mul(z.mutable_data(), z.size(),
-              x.data(), x.size(), x.sig_words(),
-              y.data(), y.size(), y.size(),
+              x.data(), x.size(), std::min(m_p_words, x.size()),
+              y.data(), y.size(), std::min(m_p_words, y.size()),
               ws.data(), ws.size());
 
    bigint_monty_redc(z.mutable_data(),
@@ -122,9 +127,11 @@ void Montgomery_Params::mul_by(BigInt& x,
    word* z_data = &ws[0];
    word* ws_data = &ws[output_size];
 
+   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
+
    bigint_mul(z_data, output_size,
-              x.data(), x.size(), x.sig_words(),
-              y.data(), y.size(), y.size(),
+              x.data(), x.size(), std::min(m_p_words, x.size()),
+              y.data(), y.size(), std::min(m_p_words, y.size()),
               ws_data, output_size);
 
    bigint_monty_redc(z_data,
@@ -148,9 +155,11 @@ void Montgomery_Params::mul_by(BigInt& x,
    word* z_data = &ws[0];
    word* ws_data = &ws[output_size];
 
+   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
+
    bigint_mul(z_data, output_size,
-              x.data(), x.size(), x.sig_words(),
-              y.data(), y.size(), y.sig_words(),
+              x.data(), x.size(), std::min(m_p_words, x.size()),
+              y.data(), y.size(), std::min(m_p_words, y.size()),
               ws_data, output_size);
 
    bigint_monty_redc(z_data,
@@ -171,13 +180,10 @@ BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const
 
    BigInt z(BigInt::Positive, output_size);
 
-   // assume x.sig_words() is at most p_words
    BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
 
-   const size_t x_words = (x.size() >= m_p_words) ? m_p_words : x.sig_words();
-
    bigint_sqr(z.mutable_data(), z.size(),
-              x.data(), x.size(), x_words,
+              x.data(), x.size(), std::min(m_p_words, x.size()),
               ws.data(), ws.size());
 
    bigint_monty_redc(z.mutable_data(),
@@ -198,8 +204,10 @@ void Montgomery_Params::square_this(BigInt& x,
    word* z_data = &ws[0];
    word* ws_data = &ws[output_size];
 
+   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
+
    bigint_sqr(z_data, output_size,
-              x.data(), x.size(), x.sig_words(),
+              x.data(), x.size(), std::min(m_p_words, x.size()),
               ws_data, output_size);
 
    bigint_monty_redc(z_data,
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 0356f9b39..f67fb8f10 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -139,11 +139,11 @@ inline T is_lte(T a, T b)
    }
 
 template<typename T>
-inline void conditional_copy_mem(T value,
-                                 T* to,
-                                 const T* from0,
-                                 const T* from1,
-                                 size_t elems)
+inline T conditional_copy_mem(T value,
+                              T* to,
+                              const T* from0,
+                              const T* from1,
+                              size_t elems)
    {
    const T mask = CT::expand_mask(value);
 
@@ -151,6 +151,8 @@ inline void conditional_copy_mem(T value,
       {
       to[i] = CT::select(mask, from0[i], from1[i]);
       }
+
+   return mask;
    }
 
 template<typename T>