Merge pull request #6 from randombit/master

Bring up to date with random bit/botan

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);
-   }
+}
 
 }