Add a const-time division algorithm

It is stupid and slow (~50-100x slower than variable time version) but
still useful for protecting critical algorithms.

Not currently used, waiting for OSS-Fuzz to test it for a while before
we commit to it.

4 files changed, 69 insertions, 8 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index d64082476..0e0dfe0d5 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -241,7 +241,7 @@ uint32_t BigInt::to_u32bit() const
 /*
 * Set bit number n
 */
-void BigInt::set_bit(size_t n)
+void BigInt::conditionally_set_bit(size_t n, bool set_it)
    {
    const size_t which = n / BOTAN_MP_WORD_BITS;
 
@@ -250,7 +250,7 @@ void BigInt::set_bit(size_t n)
       grow_to(which + 1);
       }
 
-   const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
+   const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
    m_data.set_word_at(which, word_at(which) | mask);
    }
 
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 9b385348e..64f81765a 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -414,7 +414,20 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * Set bit at specified position
      * @param n bit position to set
      */
-     void set_bit(size_t n);
+     void set_bit(size_t n)
+        {
+        conditionally_set_bit(n, true);
+        }
+
+     /**
+     * Conditionally set bit at specified position. Note if set_it is
+     * false, nothing happens, and if the bit is already set, it
+     * remains set.
+     *
+     * @param n bit position to set
+     * @param set_it if the bit should be set
+     */
+     void conditionally_set_bit(size_t n, bool set_it);
 
      /**
      * Clear bit at specified position
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index 63326d655..64d1537ba 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -1,6 +1,6 @@
 /*
 * Division Algorithm
-* (C) 1999-2007,2012 Jack Lloyd
+* (C) 1999-2007,2012,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -8,6 +8,7 @@
 #include <botan/divide.h>
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_madd.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -52,6 +53,36 @@ bool division_check(word q, word y2, word y1,
 
 }
 
+void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
+   {
+   const size_t x_words = x.sig_words();
+   const size_t y_words = y.sig_words();
+
+   const size_t x_bits = x.bits();
+
+   BigInt q(BigInt::Positive, x_words);
+   BigInt r(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);
+
+      // y <= r -> r >= y
+      const auto r_gte_y = bigint_ct_is_lt(y.data(), y_words, r.data(), r.size(), true);
+
+      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);
+      }
+
+   sign_fixup(x, y, q, r);
+   r_out = r;
+   q_out = q;
+   }
+
 /*
 * Solve x = q * y + r
 */
@@ -84,7 +115,8 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
       y <<= shifts;
       r <<= shifts;
 
-      const size_t n = r.sig_words() - 1, t = y_words - 1;
+      const size_t n = r.sig_words() - 1;
+      const size_t t = y_words - 1;
 
       if(n < t)
          throw Internal_Error("BigInt division word sizes");
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index 03e5ff7c1..d7d72e200 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -20,9 +20,25 @@ namespace Botan {
 * @param r will be set to x % y
 */
 void BOTAN_PUBLIC_API(2,0) divide(const BigInt& x,
-                      const BigInt& y,
-                      BigInt& q,
-                      BigInt& r);
+                                  const BigInt& y,
+                                  BigInt& q,
+                                  BigInt& r);
+
+/**
+* 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
+*/
+void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
+                                     const BigInt& y,
+                                     BigInt& q,
+                                     BigInt& r);
 
 }