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.

2 files changed, 102 insertions, 1 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)