Merge GH #1540 Progress towards const-time RSA

10 files changed, 112 insertions, 47 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index fd967e66e..8874195af 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -335,6 +335,18 @@ void BigInt::shrink_to_fit(size_t min_size)
    m_reg.resize(words);
    }
 
+#if defined(BOTAN_HAS_VALGRIND)
+void BigInt::const_time_poison() const
+   {
+   CT::poison(m_reg.data(), m_reg.size());
+   }
+
+void BigInt::const_time_unpoison() const
+   {
+   CT::unpoison(m_reg.data(), m_reg.size());
+   }
+#endif
+
 void BigInt::const_time_lookup(secure_vector<word>& output,
                                const std::vector<BigInt>& vec,
                                size_t idx)
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 44177de96..eec7f6176 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -565,6 +565,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void encode_words(word out[], size_t size) const;
 
+#if defined(BOTAN_HAS_VALGRIND)
+     void const_time_poison() const;
+     void const_time_unpoison() const;
+#else
+     void const_time_poison() const {}
+     void const_time_unpoison() const {}
+#endif
+
      /**
      * @param rng a random number generator
      * @param min the minimum value
diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp
index 52ad3a4d4..b1add33a4 100644
--- a/src/lib/math/mp/mp_core.cpp
+++ b/src/lib/math/mp/mp_core.cpp
@@ -157,8 +157,7 @@ word bigint_add3_nc(word z[], const word x[], size_t x_size,
 */
 void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
    {
-   if(bigint_add2_nc(x, x_size, y, y_size))
-      x[x_size] += 1;
+   x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
    }
 
 /*
@@ -212,6 +211,20 @@ 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 borrow = bigint_sub3(z, x, sz, y, sz);
+
+   CT::unpoison(borrow);
+   if(borrow)
+      {
+      bigint_sub3(z, y, sz, x, sz);
+      return -1;
+      }
+
+   return 1;
+   }
+
 /*
 * Three Operand Subtraction
 */
@@ -396,7 +409,7 @@ void bigint_shr2(word y[], const word x[], size_t x_size,
 * Compare two MP integers
 */
 int32_t bigint_cmp(const word x[], size_t x_size,
-                  const word y[], size_t y_size)
+                   const word y[], size_t y_size)
    {
    if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
 
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index a2c39bafa..1fae33987 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -95,6 +95,15 @@ word bigint_sub3(word z[],
                  const word x[], size_t x_size,
                  const word y[], size_t y_size);
 
+/**
+* Return abs(x-y), ie if x >= y, then compute z = x - y
+* 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);
+
 /*
 * Shift Operations
 */
@@ -134,10 +143,10 @@ void bigint_monty_redc(word z[],
                        size_t ws_size);
 
 /**
-* Compare x and y
+* Compare x and y returning early
 */
 int32_t bigint_cmp(const word x[], size_t x_size,
-                  const word y[], size_t y_size);
+                   const word y[], size_t y_size);
 
 /**
 * Compute ((n1<<bits) + n0) / d
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 7322b1c4b..2ac03ac1e 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -101,9 +101,6 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
    word* z0 = z;
    word* z1 = z + N;
 
-   const int32_t cmp0 = bigint_cmp(x0, N2, x1, N2);
-   const int32_t cmp1 = bigint_cmp(y1, N2, y0, N2);
-
    clear_mem(workspace, 2*N);
 
    /*
@@ -115,22 +112,17 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
    * subtractions and recursively multiply to avoid the timing channel.
    */
 
-   //if(cmp0 && cmp1)
-      {
-      if(cmp0 > 0)
-         bigint_sub3(z0, x0, N2, x1, N2);
-      else
-         bigint_sub3(z0, x1, N2, x0, N2);
-
-      if(cmp1 > 0)
-         bigint_sub3(z1, y1, N2, y0, N2);
-      else
-         bigint_sub3(z1, y0, N2, y1, N2);
+   // 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);
 
-      karatsuba_mul(workspace, z0, z1, N2, workspace+N);
-      }
+   karatsuba_mul(workspace, z0, z1, N2, workspace+N);
+   const bool is_negative = cmp0 != cmp1;
 
+   // Compute X_lo * Y_lo
    karatsuba_mul(z0, x0, y0, N2, workspace+N);
+
+   // Compute X_hi * Y_hi
    karatsuba_mul(z1, x1, y1, N2, workspace+N);
 
    const word ws_carry = bigint_add3_nc(workspace + N, z0, N, z1, N);
@@ -139,10 +131,10 @@ 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((cmp0 == cmp1) || (cmp0 == 0) || (cmp1 == 0))
-      bigint_add2(z + N2, 2*N-N2, workspace, N);
-   else
+   if(is_negative)
       bigint_sub2(z + N2, 2*N-N2, workspace, N);
+   else
+      bigint_add2_nc(z + N2, 2*N-N2, workspace, N);
    }
 
 /*
@@ -169,21 +161,11 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[])
    word* z0 = z;
    word* z1 = z + N;
 
-   const int32_t cmp = bigint_cmp(x0, N2, x1, N2);
-
    clear_mem(workspace, 2*N);
 
    // See comment in karatsuba_mul
-
-   //if(cmp)
-      {
-      if(cmp > 0)
-         bigint_sub3(z0, x0, N2, x1, N2);
-      else
-         bigint_sub3(z0, x1, N2, x0, N2);
-
-      karatsuba_sqr(workspace, z0, N2, workspace+N);
-      }
+   bigint_sub_abs(z0, x0, x1, N2);
+   karatsuba_sqr(workspace, z0, N2, workspace+N);
 
    karatsuba_sqr(z0, x0, N2, workspace+N);
    karatsuba_sqr(z1, x1, N2, workspace+N);
@@ -195,9 +177,9 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[])
    bigint_add2_nc(z + N + N2, N2, &z_carry, 1);
 
    /*
-   * This is only actually required if cmp is != 0, however
-   * if cmp==0 then workspace[0:N] == 0 and avoiding the jump
-   * hides a timing channel.
+   * This is only actually required if cmp (result of bigint_sub_abs) is != 0,
+   * however if cmp==0 then workspace[0:N] == 0 and avoiding the jump hides a
+   * timing channel.
    */
    bigint_sub2(z + N2, 2*N-N2, workspace, N);
    }
diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h
index 9f369f1a5..2af655230 100644
--- a/src/lib/math/numbertheory/monty.h
+++ b/src/lib/math/numbertheory/monty.h
@@ -100,6 +100,9 @@ class Montgomery_Int final
 
       Montgomery_Int& mul_by_8(secure_vector<word>& ws);
 
+      void const_time_poison() const { m_v.const_time_poison(); }
+      void const_time_unpoison() const { return m_v.const_time_unpoison(); }
+
    private:
       std::shared_ptr<const Montgomery_Params> m_params;
       BigInt m_v;
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index 4bf281fa9..b32a7ab4c 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -20,7 +20,8 @@ class Montgomery_Exponentation_State
    public:
       Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
                                      const BigInt& g,
-                                     size_t window_bits);
+                                     size_t window_bits,
+                                     bool const_time);
 
       BigInt exponentiation(const BigInt& k) const;
 
@@ -29,13 +30,16 @@ class Montgomery_Exponentation_State
       std::shared_ptr<const Montgomery_Params> m_params;
       std::vector<Montgomery_Int> m_g;
       size_t m_window_bits;
+      bool m_const_time;
    };
 
 Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
                                                                const BigInt& g,
-                                                               size_t window_bits) :
+                                                               size_t window_bits,
+                                                               bool const_time) :
    m_params(params),
-   m_window_bits(window_bits == 0 ? 4 : window_bits)
+   m_window_bits(window_bits == 0 ? 4 : window_bits),
+   m_const_time(const_time)
    {
    if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ...
       throw Invalid_Argument("Invalid window bits for Montgomery exponentiation");
@@ -59,6 +63,8 @@ Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<c
    for(size_t i = 0; i != window_size; ++i)
       {
       m_g[i].fix_size();
+      if(const_time)
+         m_g[i].const_time_poison();
       }
    }
 
@@ -91,6 +97,7 @@ void const_time_lookup(secure_vector<word>& output,
 BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) const
    {
    const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
+   CT::unpoison(exp_nibbles);
 
    Montgomery_Int x(m_params, m_params->R1(), false);
 
@@ -111,11 +118,14 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) cons
       x.mul_by(e_bits, ws);
       }
 
+   x.const_time_unpoison();
    return x.value();
    }
 
 BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const
    {
+   BOTAN_ASSERT_NOMSG(m_const_time == false);
+
    const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
 
    Montgomery_Int x(m_params, m_params->R1(), false);
@@ -135,15 +145,17 @@ BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scal
          x.mul_by(m_g[nibble], ws);
       }
 
+   x.const_time_unpoison();
    return x.value();
    }
 
 std::shared_ptr<const Montgomery_Exponentation_State>
 monty_precompute(std::shared_ptr<const Montgomery_Params> params,
                  const BigInt& g,
-                 size_t window_bits)
+                 size_t window_bits,
+                 bool const_time)
    {
-   return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits);
+   return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time);
    }
 
 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
index 6eeb88e7f..61da258cc 100644
--- a/src/lib/math/numbertheory/monty_exp.h
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -24,7 +24,8 @@ class Montgomery_Exponentation_State;
 std::shared_ptr<const Montgomery_Exponentation_State>
 monty_precompute(std::shared_ptr<const Montgomery_Params> params_p,
                  const BigInt& g,
-                 size_t window_bits);
+                 size_t window_bits,
+                 bool const_time = true);
 
 /*
 * Return g^x mod p
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 69d7052dc..df639be58 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -356,7 +356,7 @@ class RSA_Public_Operation
 
          const size_t powm_window = 1;
 
-         auto powm_m_n = monty_precompute(m_monty_n, m, powm_window);
+         auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false);
          return monty_execute_vartime(*powm_m_n, m_e);
          }
 
diff --git a/src/lib/utils/bit_ops.h b/src/lib/utils/bit_ops.h
index aa41db391..c7e401492 100644
--- a/src/lib/utils/bit_ops.h
+++ b/src/lib/utils/bit_ops.h
@@ -107,11 +107,36 @@ inline size_t ctz(T n)
 template<>
 inline size_t ctz(uint32_t n)
    {
+   if(n == 0)
+      return 32;
    return __builtin_ctz(n);
    }
 
-#endif
+template<>
+inline size_t ctz(uint64_t n)
+   {
+   if(n == 0)
+      return 64;
+   return __builtin_ctzll(n);
+   }
 
+template<>
+inline size_t high_bit(uint32_t x)
+   {
+   if(x == 0)
+      return 0;
+   return (32 - __builtin_clz(x));
+   }
+
+template<>
+inline size_t high_bit(uint64_t x)
+   {
+   if(x == 0)
+      return 0;
+   return (64 - __builtin_clzll(x));
+   }
+
+#endif
 
 template<typename T>
 size_t ceil_log2(T x)