Merge GH #1762 Use const time divide/modulo

9 files changed, 110 insertions, 26 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index d35dc082e..6e858d272 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -324,7 +324,7 @@ 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 = size();
+      const size_t words = sig_words();
 
       /*
       * FIXME - if shift_words == 0 && the top shift_bits of the top word
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 0e0dfe0d5..ae3ab24b0 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -386,7 +386,16 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
    m_data.swap(reg);
    }
 
-void BigInt::ct_cond_assign(bool predicate, BigInt& other)
+void BigInt::ct_cond_swap(bool predicate, BigInt& other)
+   {
+   const size_t max_words = std::max(size(), other.size());
+   grow_to(max_words);
+   other.grow_to(max_words);
+
+   bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
+   }
+
+void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
    {
    const size_t t_words = size();
    const size_t o_words = other.size();
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 64f81765a..46e0cd250 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -681,7 +681,13 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * If predicate is true assign other to *this
      * Uses a masked operation to avoid side channels
      */
-     void ct_cond_assign(bool predicate, BigInt& other);
+     void ct_cond_assign(bool predicate, const BigInt& other);
+
+     /**
+     * If predicate is true swap *this and other
+     * Uses a masked operation to avoid side channels
+     */
+     void ct_cond_swap(bool predicate, BigInt& other);
 
 #if defined(BOTAN_HAS_VALGRIND)
      void const_time_poison() const;
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index a11e8b70b..2dfb7405e 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -20,13 +20,14 @@ namespace {
 */
 void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
    {
-   if(x.sign() == BigInt::Negative)
-      {
+   if(x.sign() != y.sign())
       q.flip_sign();
-      if(r.is_nonzero()) { --q; r = y.abs() - r; }
+
+   if(x.is_negative() && r.is_nonzero())
+      {
+      q -= 1;
+      r = y.abs() - r;
       }
-   if(y.sign() == BigInt::Negative)
-      q.flip_sign();
    }
 
 inline bool division_check(word q, word y2, word y1,
@@ -58,6 +59,7 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
 
    BigInt q(BigInt::Positive, x_words);
    BigInt r(BigInt::Positive, y_words);
+   BigInt t(BigInt::Positive, y_words); // a temporary
 
    for(size_t i = 0; i != x_bits; ++i)
       {
@@ -67,11 +69,10 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
       r *= 2;
       r.conditionally_set_bit(0, x_b);
 
-      // y <= r -> r >= y
-      const auto r_gte_y = bigint_ct_is_lt(y.data(), y_words, r.data(), r.size(), true);
+      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
 
-      q.conditionally_set_bit(b, r_gte_y.is_set());
-      bigint_cnd_sub(r_gte_y.value(), r.mutable_data(), r.size(), y.data(), y_words);
+      q.conditionally_set_bit(b, r_gte_y);
+      r.ct_cond_swap(r_gte_y, t);
       }
 
    sign_fixup(x, y, q, r);
@@ -83,7 +84,6 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
    {
    const size_t x_words = x.sig_words();
    const size_t x_bits = x.bits();
-   const size_t y_words = 1;
 
    BigInt q(BigInt::Positive, x_words);
    uint32_t r = 0;
@@ -102,7 +102,7 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
       r = r_gte_y.select(r - y, r);
       }
 
-   if(x.sign() == BigInt::Negative)
+   if(x.is_negative())
       {
       q.flip_sign();
       if(r != 0)
@@ -116,6 +116,42 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
    q_out = q;
    }
 
+BigInt ct_modulo(const BigInt& x, const BigInt& y)
+   {
+   if(y.is_negative() || y.is_zero())
+      throw Invalid_Argument("ct_modulo requires y > 0");
+
+   const size_t y_words = y.sig_words();
+
+   const size_t x_bits = x.bits();
+
+   BigInt r(BigInt::Positive, y_words);
+   BigInt t(BigInt::Positive, y_words);
+
+   for(size_t i = 0; i != x_bits; ++i)
+      {
+      const size_t b = x_bits - 1 - i;
+      const bool x_b = x.get_bit(b);
+
+      r *= 2;
+      r.conditionally_set_bit(0, x_b);
+
+      const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;
+
+      r.ct_cond_swap(r_gte_y, t);
+      }
+
+   if(x.is_negative())
+      {
+      if(r.is_nonzero())
+         {
+         r = y - r;
+         }
+      }
+
+   return r;
+   }
+
 /*
 * Solve x = q * y + r
 */
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index d83f4b695..e365dabb3 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -48,6 +48,23 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
 *
 * @param x an integer
 * @param y a non-zero integer
+* @return x/y with remainder discarded
+*/
+inline BigInt ct_divide(const BigInt& x, const BigInt& y)
+   {
+   BigInt q, r;
+   ct_divide(x, y, q, r);
+   return q;
+   }
+
+/**
+* BigInt division, const time variant
+*
+* This runs with control flow independent of the values of x/y.
+* Warning: the loop bounds still leak the sizes of x and y.
+*
+* @param x an integer
+* @param y a non-zero integer
 * @param q will be set to x / y
 * @param r will be set to x % y
 */
@@ -56,6 +73,19 @@ void BOTAN_PUBLIC_API(2,9) ct_divide_u8(const BigInt& x,
                                         BigInt& q,
                                         uint8_t& r);
 
+/**
+* BigInt modulo, const time variant
+*
+* Using this function is (slightly) cheaper than calling ct_divide and
+* using only the remainder.
+*
+* @param x a non-negative integer
+* @param modulo a positive integer
+* @return result x % modulo
+*/
+BigInt BOTAN_PUBLIC_API(2,9) ct_modulo(const BigInt& x,
+                                       const BigInt& modulo);
+
 }
 
 #endif
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 399a49cea..eba924b7c 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -9,6 +9,7 @@
 #include <botan/pow_mod.h>
 #include <botan/reducer.h>
 #include <botan/monty.h>
+#include <botan/divide.h>
 #include <botan/rng.h>
 #include <botan/internal/bit_ops.h>
 #include <botan/internal/mp_core.h>
@@ -83,7 +84,7 @@ BigInt gcd(const BigInt& a, const BigInt& b)
 */
 BigInt lcm(const BigInt& a, const BigInt& b)
    {
-   return ((a * b) / gcd(a, b));
+   return ct_divide(a * b, gcd(a, b));
    }
 
 /*
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index a5321c47c..0468d004b 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -7,6 +7,7 @@
 
 #include <botan/reducer.h>
 #include <botan/internal/ct_utils.h>
+#include <botan/divide.h>
 
 namespace Botan {
 
@@ -28,7 +29,7 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod)
 
       m_modulus_2 = Botan::square(m_modulus);
 
-      m_mu = BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words) / m_modulus;
+      m_mu = ct_divide(BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words), m_modulus);
       }
    }
 
@@ -51,8 +52,8 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
 
    if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
       {
-      // too big, fall back to normal division
-      t1 = x % m_modulus;
+      // too big, fall back to slow boat division
+      t1 = ct_modulo(x, m_modulus);
       return;
       }
 
diff --git a/src/lib/misc/fpe_fe1/fpe_fe1.cpp b/src/lib/misc/fpe_fe1/fpe_fe1.cpp
index 3bd01ce34..98ada495a 100644
--- a/src/lib/misc/fpe_fe1/fpe_fe1.cpp
+++ b/src/lib/misc/fpe_fe1/fpe_fe1.cpp
@@ -151,7 +151,7 @@ BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak
    BigInt L, R, Fi;
    for(size_t i = 0; i != m_rounds; ++i)
       {
-      divide(X, m_b, L, R);
+      ct_divide(X, m_b, L, R);
       Fi = F(R, i, tweak_mac, tmp);
       X = m_a * R + mod_a->reduce(L + Fi);
       }
@@ -169,7 +169,7 @@ BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak
    BigInt W, R, Fi;
    for(size_t i = 0; i != m_rounds; ++i)
       {
-      divide(X, m_a, R, W);
+      ct_divide(X, m_a, R, W);
 
       Fi = F(R, m_rounds-i-1, tweak_mac, tmp);
       X = m_b * mod_a->reduce(W - Fi) + R;
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index d7d6a939e..9334ff4cd 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -15,6 +15,7 @@
 #include <botan/ber_dec.h>
 #include <botan/pow_mod.h>
 #include <botan/monty.h>
+#include <botan/divide.h>
 #include <botan/internal/monty_exp.h>
 
 #if defined(BOTAN_HAS_OPENSSL)
@@ -125,8 +126,8 @@ RSA_PrivateKey::RSA_PrivateKey(const BigInt& prime1,
       m_d = inverse_mod(m_e, phi_n);
       }
 
-   m_d1 = m_d % (m_p - 1);
-   m_d2 = m_d % (m_q - 1);
+   m_d1 = ct_modulo(m_d, m_p - 1);
+   m_d2 = ct_modulo(m_d, m_q - 1);
    }
 
 /*
@@ -157,8 +158,8 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
    const BigInt phi_n = lcm(m_p - 1, m_q - 1);
    // FIXME: this uses binary ext gcd because phi_n is even
    m_d = inverse_mod(m_e, phi_n);
-   m_d1 = m_d % (m_p - 1);
-   m_d2 = m_d % (m_q - 1);
+   m_d1 = ct_modulo(m_d, m_p - 1);
+   m_d2 = ct_modulo(m_d, m_q - 1);
    m_c = inverse_mod(m_q, m_p);
    }
 
@@ -173,7 +174,7 @@ bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    if(m_d < 2 || m_p < 3 || m_q < 3 || m_p*m_q != m_n)
       return false;
 
-   if(m_d1 != m_d % (m_p - 1) || m_d2 != m_d % (m_q - 1) || m_c != inverse_mod(m_q, m_p))
+   if(m_d1 != ct_modulo(m_d, m_p - 1) || m_d2 != ct_modulo(m_d, m_q - 1) || m_c != inverse_mod(m_q, m_p))
       return false;
 
    const size_t prob = (strong) ? 128 : 12;
@@ -183,7 +184,7 @@ bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
 
    if(strong)
       {
-      if((m_e * m_d) % lcm(m_p - 1, m_q - 1) != 1)
+      if(ct_modulo(m_e * m_d, lcm(m_p - 1, m_q - 1)) != 1)
          return false;
 
       return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-256)");