Merge GH #1757 Add a constant time division algorithm

9 files changed, 145 insertions, 16 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index ec6db5c86..59771fb65 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -26,6 +26,7 @@
 
 #if defined(BOTAN_HAS_BIGINT)
    #include <botan/bigint.h>
+   #include <botan/divide.h>
 #endif
 
 #if defined(BOTAN_HAS_BLOCK_CIPHER)
@@ -653,6 +654,10 @@ class Speed final : public Command
                {
                bench_mp_mul(msec);
                }
+            else if(algo == "mp_div")
+               {
+               bench_mp_div(msec);
+               }
 #endif
 
 #if defined(BOTAN_HAS_NUMBERTHEORY)
@@ -1263,6 +1268,46 @@ class Speed final : public Command
 
          }
 
+      void bench_mp_div(const std::chrono::milliseconds runtime)
+         {
+         std::chrono::milliseconds runtime_per_size = runtime;
+
+         for(size_t n_bits : { 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096 })
+            {
+            const size_t q_bits = n_bits / 2;
+            const std::string bit_descr = std::to_string(n_bits) + "/" + std::to_string(q_bits);
+
+            std::unique_ptr<Timer> div_timer = make_timer("BigInt div " + bit_descr);
+            std::unique_ptr<Timer> ct_div_timer = make_timer("BigInt ct_div " + bit_descr);
+
+            Botan::BigInt y;
+            Botan::BigInt x;
+            Botan::secure_vector<Botan::word> ws;
+
+            Botan::BigInt q1, r1, q2, r2;
+
+            while(ct_div_timer->under(runtime_per_size))
+               {
+               x.randomize(rng(), n_bits);
+               y.randomize(rng(), q_bits);
+
+               div_timer->start();
+               Botan::divide(x, y, q1, r1);
+               div_timer->stop();
+
+               ct_div_timer->start();
+               Botan::ct_divide(x, y, q2, r2);
+               ct_div_timer->stop();
+
+               BOTAN_ASSERT_EQUAL(q1, q2, "Quotient ok");
+               BOTAN_ASSERT_EQUAL(r1, r2, "Remainder ok");
+               }
+
+            record_result(div_timer);
+            record_result(ct_div_timer);
+            }
+         }
+
 #endif
 
 #if defined(BOTAN_HAS_DL_GROUP)
diff --git a/src/fuzzer/divide.cpp b/src/fuzzer/divide.cpp
index 01ec14e28..c0c86f051 100644
--- a/src/fuzzer/divide.cpp
+++ b/src/fuzzer/divide.cpp
@@ -1,5 +1,5 @@
 /*
-* (C) 2015,2016 Jack Lloyd
+* (C) 2015,2016,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -25,5 +25,11 @@ void fuzz(const uint8_t in[], size_t len)
    Botan::BigInt z = q*y + r;
 
    FUZZER_ASSERT_EQUAL(z, x);
+
+   Botan::BigInt ct_q, ct_r;
+   Botan::ct_divide(x, y, ct_q, ct_r);
+
+   FUZZER_ASSERT_EQUAL(q, ct_q);
+   FUZZER_ASSERT_EQUAL(r, ct_r);
    }
 
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);
 
 }
 
diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py
index 98423d8de..6445a3669 100755
--- a/src/scripts/test_cli.py
+++ b/src/scripts/test_cli.py
@@ -656,7 +656,7 @@ def cli_speed_tests():
         if format_re.match(line) is None:
             logging.error("Unexpected line %s", line)
 
-    math_ops = ['mp_mul', 'modexp', 'random_prime', 'inverse_mod', 'rfc3394', 'fpe_fe1',
+    math_ops = ['mp_mul', 'mp_div', 'modexp', 'random_prime', 'inverse_mod', 'rfc3394', 'fpe_fe1',
                 'bn_redc', 'nistp_redc', 'ecc_mult', 'ecc_ops', 'os2ecp', 'primality_test',
                 'bcrypt', 'passhash9']
 
diff --git a/src/tests/data/bn/divide.vec b/src/tests/data/bn/divide.vec
index a5470f41d..f1220561e 100644
--- a/src/tests/data/bn/divide.vec
+++ b/src/tests/data/bn/divide.vec
@@ -1,8 +1,16 @@
 [Division]
+In1 = 0
+In2 = 5
+Output = 0
+
 In1 = 0x1234567
 In2 = 0x103
 Output = 73701
 
+In1 = -0x1234567
+In2 = 0x103
+Output = -73702
+
 In1 = 0x100000000000000000000000000000000000000000000000000000000000000000000000
 In2 = 0x1000000000000000000000000000000000000000000000000000000000000000000000
 Output = 0x100
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index c7b95b89a..9d8a88497 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -9,6 +9,7 @@
 #if defined(BOTAN_HAS_NUMBERTHEORY)
    #include <botan/bigint.h>
    #include <botan/numthry.h>
+   #include <botan/divide.h>
    #include <botan/internal/primality.h>
    #include <botan/reducer.h>
    #include <botan/pow_mod.h>
@@ -404,6 +405,10 @@ class BigInt_Div_Test final : public Text_Based_Test
          e /= b;
          result.test_eq("a /= b", e, c);
 
+         Botan::BigInt ct_q, ct_r;
+         Botan::ct_divide(a, b, ct_q, ct_r);
+         result.test_eq("ct_divide q", ct_q, c);
+
          return result;
          }
    };
@@ -421,16 +426,16 @@ class BigInt_Mod_Test final : public Text_Based_Test
 
          const BigInt a = vars.get_req_bn("In1");
          const BigInt b = vars.get_req_bn("In2");
-         const BigInt c = vars.get_req_bn("Output");
+         const BigInt expected = vars.get_req_bn("Output");
 
-         result.test_eq("a % b", a % b, c);
+         result.test_eq("a % b", a % b, expected);
 
          BigInt e = a;
          e %= b;
-         result.test_eq("a %= b", e, c);
+         result.test_eq("a %= b", e, expected);
 
          const Botan::Modular_Reducer mod_b(b);
-         result.test_eq("Barrett", mod_b.reduce(a), c);
+         result.test_eq("Barrett", mod_b.reduce(a), expected);
 
          // if b fits into a Botan::word test %= operator for words
          if(b.sig_words() == 1)
@@ -439,11 +444,15 @@ class BigInt_Mod_Test final : public Text_Based_Test
 
             e = a;
             e %= b_word;
-            result.test_eq("a %= b (as word)", e, c);
+            result.test_eq("a %= b (as word)", e, expected);
 
-            result.test_eq("a % b (as word)", a % b_word, c);
+            result.test_eq("a % b (as word)", a % b_word, expected);
             }
 
+         Botan::BigInt ct_q, ct_r;
+         Botan::ct_divide(a, b, ct_q, ct_r);
+         result.test_eq("ct_divide r", ct_r, expected);
+
          return result;
          }
    };