Make Montgomery reduction constant time.

It was already close, but the carry loop would break early and
selecting which value to copy out was indexed on the borrow bit. Have
the carry loop run through, and add a const-time conditional copy
operation and use that to copy the output.

Convert ct_utils to CT namespace. Templatize the utils, which I was
hesitant to do initially but is pretty useful when dealing with
arbitrary word sizes.

Remove the poison macros, replace with inline funcs which reads
cleaner at the call site.

9 files changed, 115 insertions, 123 deletions

diff --git a/doc/news.rst b/doc/news.rst
index 00a102427..72ab4ad9f 100644
--- a/doc/news.rst
+++ b/doc/news.rst
@@ -14,12 +14,16 @@ Version 1.11.22, Not Yet Released
   By writing the code such that it does not depend on secret inputs for branch
   or memory indexes, such a side channel would be much less likely to exist.
 
+  The OAEP code has previously made an attempt at constant time operation, but
+  it used a construct which many compilers converted into a conditional jump.
+
 * Add support for using ctgrind (https://github.com/agl/ctgrind) to test that
   sections of code do not use secret inputs to decide branches or memory indexes.
   The testing relies on dynamic checking using valgrind.
 
-  So far PKCS #1 decoding, OAEP decoding, IDEA, and Curve25519 have been notated
-  and confirmed to be constant time.
+  So far PKCS #1 decoding, OAEP decoding, Montgomery reduction, IDEA, and
+  Curve25519 have been notated and confirmed to be constant time on Linux/x86-64
+  when compiled by gcc.
 
 * Public key operations can now be used with specified providers by passing an
   additional parameter to the constructor of the PK operation.
diff --git a/src/lib/block/idea/idea.cpp b/src/lib/block/idea/idea.cpp
index c7706b372..8069e16f7 100644
--- a/src/lib/block/idea/idea.cpp
+++ b/src/lib/block/idea/idea.cpp
@@ -20,7 +20,7 @@ inline u16bit mul(u16bit x, u16bit y)
    {
    const u32bit P = static_cast<u32bit>(x) * y;
 
-   const u16bit Z_mask = static_cast<u16bit>(ct_expand_mask_32(P) & 0xFFFF);
+   const u16bit Z_mask = static_cast<u16bit>(CT::expand_mask(P) & 0xFFFF);
 
    const u32bit P_hi = P >> 16;
    const u32bit P_lo = P & 0xFFFF;
@@ -28,7 +28,7 @@ inline u16bit mul(u16bit x, u16bit y)
    const u16bit r_1 = (P_lo - P_hi) + (P_lo < P_hi);
    const u16bit r_2 = 1 - x - y;
 
-   return ct_select_mask_16(Z_mask, r_1, r_2);
+   return CT::select(Z_mask, r_1, r_2);
    }
 
 /*
@@ -62,9 +62,9 @@ void idea_op(const byte in[], byte out[], size_t blocks, const u16bit K[52])
    {
    const size_t BLOCK_SIZE = 8;
 
-   BOTAN_CONST_TIME_POISON(in, blocks * 8);
-   BOTAN_CONST_TIME_POISON(out, blocks * 8);
-   BOTAN_CONST_TIME_POISON(K, 52 * 2);
+   CT::poison(in, blocks * 8);
+   CT::poison(out, blocks * 8);
+   CT::poison(K, 52);
 
    for(size_t i = 0; i != blocks; ++i)
       {
@@ -101,9 +101,9 @@ void idea_op(const byte in[], byte out[], size_t blocks, const u16bit K[52])
       store_be(out + BLOCK_SIZE*i, X1, X3, X2, X4);
       }
 
-   BOTAN_CONST_TIME_UNPOISON(in, blocks * 8);
-   BOTAN_CONST_TIME_UNPOISON(out, blocks * 8);
-   BOTAN_CONST_TIME_UNPOISON(K, 52 * 2);
+   CT::unpoison(in, blocks * 8);
+   CT::unpoison(out, blocks * 8);
+   CT::unpoison(K, 52);
    }
 
 }
@@ -132,9 +132,9 @@ void IDEA::key_schedule(const byte key[], size_t)
    EK.resize(52);
    DK.resize(52);
 
-   BOTAN_CONST_TIME_POISON(key, 16);
-   BOTAN_CONST_TIME_POISON(EK.data(), 52 * 2);
-   BOTAN_CONST_TIME_POISON(DK.data(), 52 * 2);
+   CT::poison(key, 16);
+   CT::poison(EK.data(), 52);
+   CT::poison(DK.data(), 52);
 
    for(size_t i = 0; i != 8; ++i)
       EK[i] = load_be<u16bit>(key, i);
@@ -168,9 +168,9 @@ void IDEA::key_schedule(const byte key[], size_t)
    DK[1] = -EK[49];
    DK[0] = mul_inv(EK[48]);
 
-   BOTAN_CONST_TIME_UNPOISON(key, 16);
-   BOTAN_CONST_TIME_UNPOISON(EK.data(), 52 * 2);
-   BOTAN_CONST_TIME_UNPOISON(DK.data(), 52 * 2);
+   CT::unpoison(key, 16);
+   CT::unpoison(EK.data(), 52);
+   CT::unpoison(DK.data(), 52);
    }
 
 void IDEA::clear()
diff --git a/src/lib/block/idea_sse2/idea_sse2.cpp b/src/lib/block/idea_sse2/idea_sse2.cpp
index 51b5e909b..c7d846e8b 100644
--- a/src/lib/block/idea_sse2/idea_sse2.cpp
+++ b/src/lib/block/idea_sse2/idea_sse2.cpp
@@ -131,9 +131,9 @@ void transpose_out(__m128i& B0, __m128i& B1, __m128i& B2, __m128i& B3)
 */
 void idea_op_8(const byte in[64], byte out[64], const u16bit EK[52])
    {
-   BOTAN_CONST_TIME_POISON(in, 64);
-   BOTAN_CONST_TIME_POISON(out, 64);
-   BOTAN_CONST_TIME_POISON(EK, 52*2);
+   CT::poison(in, 64);
+   CT::poison(out, 64);
+   CT::poison(EK, 52);
 
    const __m128i* in_mm = reinterpret_cast<const __m128i*>(in);
 
@@ -195,9 +195,9 @@ void idea_op_8(const byte in[64], byte out[64], const u16bit EK[52])
    _mm_storeu_si128(out_mm + 2, B1);
    _mm_storeu_si128(out_mm + 3, B3);
 
-   BOTAN_CONST_TIME_UNPOISON(in, 64);
-   BOTAN_CONST_TIME_UNPOISON(out, 64);
-   BOTAN_CONST_TIME_UNPOISON(EK, 52*2);
+   CT::unpoison(in, 64);
+   CT::unpoison(out, 64);
+   CT::unpoison(EK, 52);
    }
 
 }
diff --git a/src/lib/math/mp/mp_monty.cpp b/src/lib/math/mp/mp_monty.cpp
index 820f41e6c..7e427b540 100644
--- a/src/lib/math/mp/mp_monty.cpp
+++ b/src/lib/math/mp/mp_monty.cpp
@@ -9,6 +9,7 @@
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_madd.h>
 #include <botan/internal/mp_asmi.h>
+#include <botan/internal/ct_utils.h>
 #include <botan/mem_ops.h>
 
 namespace Botan {
@@ -22,6 +23,10 @@ void bigint_monty_redc(word z[],
    {
    const size_t z_size = 2*(p_size+1);
 
+   CT::poison(z, z_size);
+   CT::poison(p, p_size);
+   CT::poison(ws, 2*(p_size+1));
+
    const size_t blocks_of_8 = p_size - (p_size % 8);
 
    for(size_t i = 0; i != p_size; ++i)
@@ -47,10 +52,10 @@ void bigint_monty_redc(word z[],
       carry = (z_sum < z_i[p_size]);
       z_i[p_size] = z_sum;
 
-      for(size_t j = p_size + 1; carry && j != z_size - i; ++j)
+      for(size_t j = p_size + 1; j < z_size - i; ++j)
          {
-         ++z_i[j];
-         carry = !z_i[j];
+         z_i[j] += carry;
+         carry = carry & !z_i[j];
          }
       }
 
@@ -73,12 +78,18 @@ void bigint_monty_redc(word z[],
 
    ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
 
-   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow");
-
    copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
 
-   copy_mem(z, ws + borrow*(p_size+1), p_size + 1);
+   CT::conditional_copy_mem(borrow, z, ws + (p_size + 1), ws, (p_size + 1));
    clear_mem(z + p_size + 1, z_size - p_size - 1);
+
+   CT::unpoison(z, z_size);
+   CT::unpoison(p, p_size);
+   CT::unpoison(ws, 2*(p_size+1));
+
+   // This check comes after we've used it but that's ok here
+   CT::unpoison(&borrow, 1);
+   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow");
    }
 
 void bigint_monty_mul(word z[], size_t z_size,
diff --git a/src/lib/pk_pad/eme_oaep/oaep.cpp b/src/lib/pk_pad/eme_oaep/oaep.cpp
index b114afb8b..370a9fe45 100644
--- a/src/lib/pk_pad/eme_oaep/oaep.cpp
+++ b/src/lib/pk_pad/eme_oaep/oaep.cpp
@@ -84,7 +84,7 @@ secure_vector<byte> OAEP::unpad(const byte in[], size_t in_length,
    secure_vector<byte> input(key_length);
    buffer_insert(input, key_length - in_length, in, in_length);
 
-   BOTAN_CONST_TIME_POISON(input.data(), input.size());
+   CT::poison(input.data(), input.size());
 
    const size_t hlen = m_Phash.size();
 
@@ -102,25 +102,25 @@ secure_vector<byte> OAEP::unpad(const byte in[], size_t in_length,
 
    for(size_t i = delim_idx; i < input.size(); ++i)
       {
-      const byte zero_m = ct_is_zero_8(input[i]);
-      const byte one_m = ct_is_equal_8(input[i], 1);
+      const byte zero_m = CT::is_zero<byte>(input[i]);
+      const byte one_m = CT::is_equal<byte>(input[i], 1);
 
       const byte add_m = waiting_for_delim & zero_m;
 
       bad_input |= waiting_for_delim & ~(zero_m | one_m);
 
-      delim_idx += ct_select_mask_8(add_m, 1, 0);
+      delim_idx += CT::select<byte>(add_m, 1, 0);
 
       waiting_for_delim &= zero_m;
       }
 
    // If we never saw any non-zero byte, then it's not valid input
    bad_input |= waiting_for_delim;
-   bad_input |= ct_expand_mask_8(!same_mem(&input[hlen], m_Phash.data(), hlen));
+   bad_input |= CT::expand_mask<byte>(!same_mem(&input[hlen], m_Phash.data(), hlen));
 
-   BOTAN_CONST_TIME_UNPOISON(input.data(), input.size());
-   BOTAN_CONST_TIME_UNPOISON(&bad_input, sizeof(bad_input));
-   BOTAN_CONST_TIME_UNPOISON(&delim_idx, sizeof(delim_idx));
+   CT::unpoison(input.data(), input.size());
+   CT::unpoison(&bad_input, 1);
+   CT::unpoison(&delim_idx, 1);
 
    if(bad_input)
       throw Decoding_Error("Invalid OAEP encoding");
diff --git a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
index 219e93251..6b3bce0aa 100644
--- a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
+++ b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
@@ -44,29 +44,29 @@ secure_vector<byte> EME_PKCS1v15::unpad(const byte in[], size_t inlen,
    if(inlen != key_len / 8 || inlen < 10)
       throw Decoding_Error("PKCS1::unpad");
 
-   BOTAN_CONST_TIME_POISON(in, inlen);
+   CT::poison(in, inlen);
 
    byte bad_input_m = 0;
    byte seen_zero_m = 0;
    size_t delim_idx = 0;
 
-   bad_input_m |= ~ct_is_equal_8(in[0], 2);
+   bad_input_m |= ~CT::is_equal<byte>(in[0], 2);
 
    for(size_t i = 1; i != inlen; ++i)
       {
-      const byte is_zero_m = ct_is_zero_8(in[i]);
+      const byte is_zero_m = CT::is_zero<byte>(in[i]);
 
-      delim_idx += ct_select_mask_8(~seen_zero_m, 1, 0);
+      delim_idx += CT::select<byte>(~seen_zero_m, 1, 0);
 
-      bad_input_m |= is_zero_m & ct_expand_mask_8(i < 9);
+      bad_input_m |= is_zero_m & CT::expand_mask<byte>(i < 9);
       seen_zero_m |= is_zero_m;
       }
 
    bad_input_m |= ~seen_zero_m;
 
-   BOTAN_CONST_TIME_UNPOISON(in, inlen);
-   BOTAN_CONST_TIME_UNPOISON(&bad_input_m, sizeof(bad_input_m));
-   BOTAN_CONST_TIME_UNPOISON(&delim_idx, sizeof(delim_idx));
+   CT::unpoison(in, inlen);
+   CT::unpoison(&bad_input_m, 1);
+   CT::unpoison(&delim_idx, 1);
 
    if(bad_input_m)
       throw Decoding_Error("Invalid PKCS #1 v1.5 encryption padding");
diff --git a/src/lib/pubkey/curve25519/donna.cpp b/src/lib/pubkey/curve25519/donna.cpp
index ab9363761..78966f745 100644
--- a/src/lib/pubkey/curve25519/donna.cpp
+++ b/src/lib/pubkey/curve25519/donna.cpp
@@ -420,8 +420,8 @@ crecip(felem out, const felem z) {
 int
 curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
 
-  BOTAN_CONST_TIME_POISON(secret, 32);
-  BOTAN_CONST_TIME_POISON(basepoint, 32);
+  CT::poison(secret, 32);
+  CT::poison(basepoint, 32);
 
   limb bp[5], x[5], z[5], zmone[5];
   uint8_t e[32];
@@ -438,9 +438,9 @@ curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
   fmul(z, x, zmone);
   fcontract(mypublic, z);
 
-  BOTAN_CONST_TIME_UNPOISON(secret, 32);
-  BOTAN_CONST_TIME_UNPOISON(basepoint, 32);
-  BOTAN_CONST_TIME_UNPOISON(mypublic, 32);
+  CT::unpoison(secret, 32);
+  CT::unpoison(basepoint, 32);
+  CT::unpoison(mypublic, 32);
   return 0;
 }
 
diff --git a/src/lib/pubkey/pk_keys.cpp b/src/lib/pubkey/pk_keys.cpp
index f92492fa9..635934037 100644
--- a/src/lib/pubkey/pk_keys.cpp
+++ b/src/lib/pubkey/pk_keys.cpp
@@ -31,7 +31,7 @@ OID Public_Key::get_oid() const
 void Public_Key::load_check(RandomNumberGenerator& rng) const
    {
    if(!check_key(rng, BOTAN_PUBLIC_KEY_STRONG_CHECKS_ON_LOAD))
-      throw Invalid_Argument(algo_name() + ": Invalid public key");
+      throw Invalid_Argument("Invalid public key");
    }
 
 /*
@@ -40,7 +40,7 @@ void Public_Key::load_check(RandomNumberGenerator& rng) const
 void Private_Key::load_check(RandomNumberGenerator& rng) const
    {
    if(!check_key(rng, BOTAN_PRIVATE_KEY_STRONG_CHECKS_ON_LOAD))
-      throw Invalid_Argument(algo_name() + ": Invalid private key");
+      throw Invalid_Argument("Invalid private key");
    }
 
 /*
@@ -49,7 +49,7 @@ void Private_Key::load_check(RandomNumberGenerator& rng) const
 void Private_Key::gen_check(RandomNumberGenerator& rng) const
    {
    if(!check_key(rng, BOTAN_PRIVATE_KEY_STRONG_CHECKS_ON_GENERATE))
-      throw Self_Test_Failure(algo_name() + " private key generation failed");
+      throw Self_Test_Failure("Private key generation failed");
    }
 
 }
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 4ae735330..52a3bc388 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -27,105 +27,82 @@ extern "C" void ct_unpoison(const void* address, size_t length);
 
 namespace Botan {
 
-#if defined(BOTAN_USE_CTGRIND)
-
-#define BOTAN_CONST_TIME_POISON(p, l) ct_poison(p, l)
-#define BOTAN_CONST_TIME_UNPOISON(p, l) ct_unpoison(p, l)
+namespace CT {
 
+template<typename T>
+inline void poison(T* p, size_t n)
+   {
+#if defined(BOTAN_USE_CTGRIND)
+   ct_poison(p, sizeof(T)*n);
 #else
+   BOTAN_UNUSED(p);
+   BOTAN_UNUSED(n);
+#endif
+   }
 
-#define BOTAN_CONST_TIME_POISON(p, l)
-#define BOTAN_CONST_TIME_UNPOISON(p, l)
-
+template<typename T>
+inline void unpoison(T* p, size_t n)
+   {
+#if defined(BOTAN_USE_CTGRIND)
+   ct_unpoison(p, sizeof(T)*n);
+#else
+   BOTAN_UNUSED(p);
+   BOTAN_UNUSED(n);
 #endif
+   }
 
 /*
+* T should be an unsigned machine integer type
 * Expand to a mask used for other operations
 * @param in an integer
-* @return 0 if in == 0 else 0xFFFFFFFF
+* @return If n is zero, returns zero. Otherwise
+* returns a T with all bits set for use as a mask with
+* select.
 */
-inline uint32_t ct_expand_mask_32(uint32_t x)
+template<typename T>
+inline T expand_mask(T x)
    {
-   // First fold x down to a single bit:
-   uint32_t r = x;
-   r |= r >> 16;
-   r |= r >> 8;
-   r |= r >> 4;
-   r |= r >> 2;
-   r |= r >> 1;
+   T r = x;
+   // First fold r down to a single bit
+   for(size_t i = 1; i != sizeof(T)*8; i *= 2)
+      r |= r >> i;
    r &= 1;
-   // assumes 2s complement signed representation
    r = ~(r - 1);
    return r;
    }
 
-inline uint32_t ct_select_mask_32(uint32_t mask, uint32_t a, uint32_t b)
+template<typename T>
+inline T select(T mask, T from0, T from1)
    {
-   return (a & mask) | (b & ~mask);
+   return (from0 & mask) | (from1 & ~mask);
    }
 
-inline uint32_t ct_is_zero_32(uint32_t x)
+template<typename T>
+inline T is_zero(T x)
    {
-   return ~ct_expand_mask_32(x);
+   return ~expand_mask(x);
    }
 
-inline uint32_t ct_is_equal_32(uint32_t x, uint32_t y)
+template<typename T>
+inline T is_equal(T x, T y)
    {
-   return ct_is_zero_32(x ^ y);
+   return is_zero(x ^ y);
    }
 
-inline uint16_t ct_expand_mask_16(uint16_t x)
+template<typename T>
+inline void conditional_copy_mem(T value,
+                                 T* to,
+                                 const T* from0,
+                                 const T* from1,
+                                 size_t bytes)
    {
-   uint16_t r = x;
-   r |= r >> 8;
-   r |= r >> 4;
-   r |= r >> 2;
-   r |= r >> 1;
-   r &= 1;
-   r = ~(r - 1);
-   return r;
-   }
+   const T mask = CT::expand_mask(value);
 
-inline uint16_t ct_select_mask_16(uint16_t mask, uint16_t a, uint16_t b)
-   {
-   return (a & mask) | (b & ~mask);
-   }
-
-inline uint16_t ct_is_zero_16(uint16_t x)
-   {
-   return ~ct_expand_mask_16(x);
+   for(size_t i = 0; i != bytes; ++i)
+      to[i] = CT::select(mask, from0[i], from1[i]);
    }
 
-inline uint16_t ct_is_equal_16(uint16_t x, uint16_t y)
-   {
-   return ct_is_zero_16(x ^ y);
-   }
-
-inline uint8_t ct_expand_mask_8(uint8_t x)
-   {
-   uint8_t r = x;
-   r |= r >> 4;
-   r |= r >> 2;
-   r |= r >> 1;
-   r &= 1;
-   r = ~(r - 1);
-   return r;
-   }
-
-inline uint8_t ct_select_mask_8(uint8_t mask, uint8_t a, uint8_t b)
-   {
-   return (a & mask) | (b & ~mask);
-   }
-
-inline uint8_t ct_is_zero_8(uint8_t x)
-   {
-   return ~ct_expand_mask_8(x);
-   }
-
-inline uint8_t ct_is_equal_8(uint8_t x, uint8_t y)
-   {
-   return ct_is_zero_8(x ^ y);
-   }
+}
 
 }