Add constant time conditional swap, add, sub for bigint words

Not optimized and relies on asm support for const time word_add/word_sub
instructions.

Fix a bug introduced in 46e9a89 - unpoison needs to call the valgrind
API with the pointer rather than the reference. Caused values not to
be unpoisoned.

5 files changed, 233 insertions, 2 deletions

diff --git a/src/lib/math/mp/mp_asm.cpp b/src/lib/math/mp/mp_asm.cpp
index b7d90552e..6d60d7e77 100644
--- a/src/lib/math/mp/mp_asm.cpp
+++ b/src/lib/math/mp/mp_asm.cpp
@@ -1,6 +1,6 @@
 /*
 * MPI Add, Subtract, Word Multiply
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2016 Jack Lloyd
 *     2006 Luca Piccarreta
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -9,12 +9,91 @@
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_asmi.h>
 #include <botan/internal/mp_core.h>
+#include <botan/internal/ct_utils.h>
 #include <botan/exceptn.h>
 #include <botan/mem_ops.h>
 
 namespace Botan {
 
 /*
+* If cond == 0, does nothing.
+* If cond > 0, swaps x[0:size] with y[0:size]
+* Runs in constant time
+*/
+void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   CT::poison(x, size);
+   CT::poison(y, size);
+
+   for(size_t i = 0; i != size; ++i)
+      {
+      word a = x[i];
+      word b = y[i];
+      x[i] = CT::select(mask, b, a);
+      y[i] = CT::select(mask, a, b);
+      }
+
+   CT::unpoison(x, size);
+   CT::unpoison(y, size);
+   }
+
+/*
+* If cond > 0 adds x[0:size] to y[0:size] and returns carry
+* Runs in constant time
+*/
+word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   CT::poison(x, size);
+   CT::poison(y, size);
+
+   word carry = 0;
+   for(size_t i = 0; i != size; ++i)
+      {
+      /*
+      Here we are relying on asm version of word_add being
+      a single addcl or equivalent. Fix this.
+      */
+      const word z = word_add(x[i], y[i], &carry);
+      x[i] = CT::select(mask, z, x[i]);
+      }
+
+   CT::unpoison(x, size);
+   CT::unpoison(y, size);
+   CT::unpoison(carry);
+
+   return carry & mask;
+   }
+
+/*
+* If cond > 0 subs x[0:size] to y[0:size] and returns borrow
+* Runs in constant time
+*/
+word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   CT::poison(x, size);
+   CT::poison(y, size);
+
+   word carry = 0;
+   for(size_t i = 0; i != size; ++i)
+      {
+      const word z = word_sub(x[i], y[i], &carry);
+      x[i] = CT::select(mask, z, x[i]);
+      }
+
+   CT::unpoison(x, size);
+   CT::unpoison(y, size);
+   CT::unpoison(carry);
+
+   return carry & mask;
+   }
+
+/*
 * Two Operand Addition, No Carry
 */
 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 9921f1f07..86bc920cf 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -18,6 +18,28 @@ namespace Botan {
 */
 const size_t MP_WORD_BITS = BOTAN_MP_WORD_BITS;
 
+/*
+* If cond == 0, does nothing.
+* If cond > 0, swaps x[0:size] with y[0:size]
+* Runs in constant time
+*/
+BOTAN_DLL
+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
+* Runs in constant time
+*/
+BOTAN_DLL
+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
+* Runs in constant time
+*/
+BOTAN_DLL
+word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
+
 /**
 * Two operand addition
 * @param x the first operand (and output)
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 3d0d1ac86..401a53e86 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -68,7 +68,7 @@ template<typename T>
 inline void unpoison(T& p)
    {
 #if defined(BOTAN_HAS_VALGRIND)
-   VALGRIND_MAKE_MEM_DEFINED(p, sizeof(T));
+   VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
 #else
    BOTAN_UNUSED(p);
 #endif
diff --git a/src/tests/test_mp.cpp b/src/tests/test_mp.cpp
new file mode 100644
index 000000000..b52d93406
--- /dev/null
+++ b/src/tests/test_mp.cpp
@@ -0,0 +1,123 @@
+/*
+* (C) 2016 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "tests.h"
+
+#if defined(BOTAN_HAS_BIGINT_MP)
+  #include <botan/internal/mp_core.h>
+#endif
+
+namespace Botan_Tests {
+
+namespace {
+
+#if defined(BOTAN_HAS_BIGINT_MP)
+
+class MP_Unit_Tests : public Test
+   {
+   public:
+      std::vector<Test::Result> run() override
+         {
+         std::vector<Test::Result> results;
+
+         results.push_back(test_cnd_swap());
+         results.push_back(test_cnd_add());
+         results.push_back(test_cnd_sub());
+
+         return results;
+         }
+   private:
+      Result test_cnd_add()
+         {
+         Result result("bigint_cnd_add");
+
+         using namespace Botan;
+
+         const word max = MP_WORD_MAX;
+
+         word a = 2;
+         word c = bigint_cnd_add(0, &a, &max, 1);
+
+         result.test_int_eq(a, 2, "No op");
+         result.test_int_eq(c, 0, "No op");
+
+         c = bigint_cnd_add(1, &a, &max, 1);
+
+         result.test_int_eq(a, 1, "Add");
+         result.test_int_eq(c, 1, "Carry");
+
+         // TODO more tests
+
+         return result;
+         }
+
+      Result test_cnd_sub()
+         {
+         Result result("bigint_cnd_sub");
+
+         using namespace Botan;
+
+         word a = 2;
+         word b = 3;
+         word c = bigint_cnd_sub(0, &a, &b, 1);
+
+         result.test_int_eq(a, 2, "No op");
+         result.test_int_eq(c, 0, "No op");
+
+         c = bigint_cnd_sub(1, &a, &b, 1);
+
+         result.test_int_eq(a, MP_WORD_MAX, "Sub");
+         result.test_int_eq(c, 1, "Borrow");
+
+         return result;
+         }
+
+      Result test_cnd_swap()
+         {
+         Result result("bigint_cnd_swap");
+
+         using namespace Botan;
+
+         // null with zero length is ok
+         bigint_cnd_swap(0, nullptr, nullptr, 0);
+         bigint_cnd_swap(1, nullptr, nullptr, 0);
+
+         word x1 = 5, y1 = 9;
+
+         bigint_cnd_swap(0, &x1, &y1, 1);
+         result.test_int_eq(x1, 5, "No swap");
+         bigint_cnd_swap(1, &x1, &y1, 1);
+         result.test_int_eq(x1, 9, "Swap");
+
+         word x5[5] = { 0, 1, 2, 3, 4 };
+         word y5[5] = { 3, 2, 1, 0, 9 };
+
+         // Should only modify first four
+         bigint_cnd_swap(1, x5, y5, 4);
+
+         for(size_t i = 0; i != 4; ++i)
+            {
+            result.test_int_eq(x5[i], 3-i, "Swap x5");
+            }
+         result.test_int_eq(x5[4], 4, "Not touched");
+
+         for(size_t i = 0; i != 4; ++i)
+            {
+            result.test_int_eq(y5[i], i, "Swap y5");
+            }
+         result.test_int_eq(y5[4], 9, "Not touched");
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("mp_unit", MP_Unit_Tests);
+
+#endif
+
+}
+
+}
diff --git a/src/tests/tests.h b/src/tests/tests.h
index 5a075975d..0c561a7d3 100644
--- a/src/tests/tests.h
+++ b/src/tests/tests.h
@@ -174,6 +174,13 @@ class Test
             bool test_eq(const std::string& what, bool produced, bool expected);
 
             bool test_eq(const std::string& what, size_t produced, size_t expected);
+
+            template<typename I1, typename I2>
+            bool test_int_eq(I1 x, I2 y, const char* what)
+               {
+               return test_eq(what, static_cast<size_t>(x), static_cast<size_t>(y));
+               }
+
             bool test_lt(const std::string& what, size_t produced, size_t expected);
             bool test_gte(const std::string& what, size_t produced, size_t expected);