Make PKCS #1 and OAEP decryption operations constant time.

9 files changed, 233 insertions, 174 deletions

diff --git a/src/lib/block/idea/idea.cpp b/src/lib/block/idea/idea.cpp
index ddfd8e5fb..c7706b372 100644
--- a/src/lib/block/idea/idea.cpp
+++ b/src/lib/block/idea/idea.cpp
@@ -1,12 +1,13 @@
 /*
 * IDEA
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/idea.h>
 #include <botan/loadstor.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -19,8 +20,7 @@ inline u16bit mul(u16bit x, u16bit y)
    {
    const u32bit P = static_cast<u32bit>(x) * y;
 
-   // P ? 0xFFFF : 0
-   const u16bit P_mask = !P - 1;
+   const u16bit Z_mask = static_cast<u16bit>(ct_expand_mask_32(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 (r_1 & P_mask) | (r_2 & ~P_mask);
+   return ct_select_mask_16(Z_mask, r_1, r_2);
    }
 
 /*
@@ -62,12 +62,16 @@ 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);
+
    for(size_t i = 0; i != blocks; ++i)
       {
-      u16bit X1 = load_be<u16bit>(in, 0);
-      u16bit X2 = load_be<u16bit>(in, 1);
-      u16bit X3 = load_be<u16bit>(in, 2);
-      u16bit X4 = load_be<u16bit>(in, 3);
+      u16bit X1 = load_be<u16bit>(in + BLOCK_SIZE*i, 0);
+      u16bit X2 = load_be<u16bit>(in + BLOCK_SIZE*i, 1);
+      u16bit X3 = load_be<u16bit>(in + BLOCK_SIZE*i, 2);
+      u16bit X4 = load_be<u16bit>(in + BLOCK_SIZE*i, 3);
 
       for(size_t j = 0; j != 8; ++j)
          {
@@ -94,11 +98,12 @@ void idea_op(const byte in[], byte out[], size_t blocks, const u16bit K[52])
       X3 += K[49];
       X4  = mul(X4, K[51]);
 
-      store_be(out, X1, X3, X2, X4);
-
-      in += BLOCK_SIZE;
-      out += BLOCK_SIZE;
+      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);
    }
 
 }
@@ -127,6 +132,10 @@ 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);
+
    for(size_t i = 0; i != 8; ++i)
       EK[i] = load_be<u16bit>(key, i);
 
@@ -158,6 +167,10 @@ void IDEA::key_schedule(const byte key[], size_t)
    DK[2] = -EK[50];
    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);
    }
 
 void IDEA::clear()
diff --git a/src/lib/block/idea_sse2/idea_sse2.cpp b/src/lib/block/idea_sse2/idea_sse2.cpp
index a2a54ac32..51b5e909b 100644
--- a/src/lib/block/idea_sse2/idea_sse2.cpp
+++ b/src/lib/block/idea_sse2/idea_sse2.cpp
@@ -7,6 +7,7 @@
 
 #include <botan/idea_sse2.h>
 #include <botan/cpuid.h>
+#include <botan/internal/ct_utils.h>
 #include <emmintrin.h>
 
 namespace Botan {
@@ -130,6 +131,10 @@ 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);
+
    const __m128i* in_mm = reinterpret_cast<const __m128i*>(in);
 
    __m128i B0 = _mm_loadu_si128(in_mm + 0);
@@ -153,7 +158,6 @@ void idea_op_8(const byte in[64], byte out[64], const u16bit EK[52])
       B3 = mul(B3, EK[6*i+3]);
 
       __m128i T0 = B2;
-
       B2 = _mm_xor_si128(B2, B0);
       B2 = mul(B2, EK[6*i+4]);
 
@@ -190,6 +194,10 @@ void idea_op_8(const byte in[64], byte out[64], const u16bit EK[52])
    _mm_storeu_si128(out_mm + 1, B2);
    _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);
    }
 
 }
diff --git a/src/lib/pk_pad/eme_oaep/oaep.cpp b/src/lib/pk_pad/eme_oaep/oaep.cpp
index f214c25d2..b114afb8b 100644
--- a/src/lib/pk_pad/eme_oaep/oaep.cpp
+++ b/src/lib/pk_pad/eme_oaep/oaep.cpp
@@ -1,13 +1,13 @@
 /*
 * OAEP
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/oaep.h>
 #include <botan/mgf1.h>
-#include <botan/mem_ops.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -61,7 +61,7 @@ secure_vector<byte> OAEP::pad(const byte in[], size_t in_length,
 * OAEP Unpad Operation
 */
 secure_vector<byte> OAEP::unpad(const byte in[], size_t in_length,
-                               size_t key_length) const
+                                size_t key_length) const
    {
    /*
    Must be careful about error messages here; if an attacker can
@@ -84,41 +84,43 @@ 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());
+
+   const size_t hlen = m_Phash.size();
+
    mgf1_mask(*m_hash,
-             &input[m_Phash.size()], input.size() - m_Phash.size(),
-             input.data(), m_Phash.size());
+             &input[hlen], input.size() - hlen,
+             input.data(), hlen);
 
    mgf1_mask(*m_hash,
-             input.data(), m_Phash.size(),
-             &input[m_Phash.size()], input.size() - m_Phash.size());
+             input.data(), hlen,
+             &input[hlen], input.size() - hlen);
 
-   bool waiting_for_delim = true;
-   bool bad_input = false;
-   size_t delim_idx = 2 * m_Phash.size();
+   size_t delim_idx = 2 * hlen;
+   byte waiting_for_delim = 0xFF;
+   byte bad_input = 0;
 
-   /*
-   * GCC 4.5 on x86-64 compiles this in a way that is still vunerable
-   * to timing analysis. Other compilers, or GCC on other platforms,
-   * may or may not.
-   */
    for(size_t i = delim_idx; i < input.size(); ++i)
       {
-      const bool zero_p = !input[i];
-      const bool one_p = input[i] == 0x01;
+      const byte zero_m = ct_is_zero_8(input[i]);
+      const byte one_m = ct_is_equal_8(input[i], 1);
 
-      const bool add_1 = waiting_for_delim && zero_p;
+      const byte add_m = waiting_for_delim & zero_m;
 
-      bad_input |= waiting_for_delim && !(zero_p || one_p);
+      bad_input |= waiting_for_delim & ~(zero_m | one_m);
 
-      delim_idx += add_1;
+      delim_idx += ct_select_mask_8(add_m, 1, 0);
 
-      waiting_for_delim &= zero_p;
+      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 |= !same_mem(&input[m_Phash.size()], m_Phash.data(), m_Phash.size());
+   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));
 
    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 65d29cd59..219e93251 100644
--- a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
+++ b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
@@ -1,11 +1,12 @@
 /*
-* PKCS1 EME
-* (C) 1999-2007 Jack Lloyd
+* PKCS #1 v1.5 Type 2 (encryption) padding
+* (C) 1999-2007,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/eme_pkcs.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -38,22 +39,39 @@ secure_vector<byte> EME_PKCS1v15::pad(const byte in[], size_t inlen,
 * PKCS1 Unpad Operation
 */
 secure_vector<byte> EME_PKCS1v15::unpad(const byte in[], size_t inlen,
-                                       size_t key_len) const
+                                        size_t key_len) const
    {
-   if(inlen != key_len / 8 || inlen < 10 || in[0] != 0x02)
+   if(inlen != key_len / 8 || inlen < 10)
       throw Decoding_Error("PKCS1::unpad");
 
-   size_t separator = 0;
-   for(size_t j = 0; j != inlen; ++j)
-      if(in[j] == 0)
-         {
-         separator = j;
-         break;
-         }
-   if(separator < 9)
-      throw Decoding_Error("PKCS1::unpad");
+   BOTAN_CONST_TIME_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);
+
+   for(size_t i = 1; i != inlen; ++i)
+      {
+      const byte is_zero_m = ct_is_zero_8(in[i]);
+
+      delim_idx += ct_select_mask_8(~seen_zero_m, 1, 0);
+
+      bad_input_m |= is_zero_m & ct_expand_mask_8(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));
+
+   if(bad_input_m)
+      throw Decoding_Error("Invalid PKCS #1 v1.5 encryption padding");
 
-   return secure_vector<byte>(&in[separator + 1], &in[inlen]);
+   return secure_vector<byte>(&in[delim_idx + 1], &in[inlen]);
    }
 
 /*
diff --git a/src/lib/pubkey/curve25519/donna.cpp b/src/lib/pubkey/curve25519/donna.cpp
index 4fab78cb8..ab9363761 100644
--- a/src/lib/pubkey/curve25519/donna.cpp
+++ b/src/lib/pubkey/curve25519/donna.cpp
@@ -30,6 +30,7 @@
 #include <botan/curve25519.h>
 #include <botan/mul128.h>
 #include <botan/internal/donna128.h>
+#include <botan/internal/ct_utils.h>
 #include <botan/loadstor.h>
 
 namespace Botan {
@@ -418,6 +419,10 @@ 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);
+
   limb bp[5], x[5], z[5], zmone[5];
   uint8_t e[32];
   int i;
@@ -432,6 +437,10 @@ curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
   crecip(zmone, z);
   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);
   return 0;
 }
 
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
new file mode 100644
index 000000000..4ae735330
--- /dev/null
+++ b/src/lib/utils/ct_utils.h
@@ -0,0 +1,132 @@
+/*
+* Functions for constant time operations on data and testing of
+* constant time annotations using ctgrind.
+*
+* For more information about constant time programming see
+* Wagner, Molnar, et al "The Program Counter Security Model"
+*
+* (C) 2010 Falko Strenzke
+* (C) 2015 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_TIMING_ATTACK_CM_H__
+#define BOTAN_TIMING_ATTACK_CM_H__
+
+#include <botan/types.h>
+#include <vector>
+
+#if defined(BOTAN_USE_CTGRIND)
+
+// These are external symbols from libctgrind.so
+extern "C" void ct_poison(const void* address, size_t length);
+extern "C" void ct_unpoison(const void* address, size_t length);
+
+#endif
+
+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)
+
+#else
+
+#define BOTAN_CONST_TIME_POISON(p, l)
+#define BOTAN_CONST_TIME_UNPOISON(p, l)
+
+#endif
+
+/*
+* Expand to a mask used for other operations
+* @param in an integer
+* @return 0 if in == 0 else 0xFFFFFFFF
+*/
+inline uint32_t ct_expand_mask_32(uint32_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;
+   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)
+   {
+   return (a & mask) | (b & ~mask);
+   }
+
+inline uint32_t ct_is_zero_32(uint32_t x)
+   {
+   return ~ct_expand_mask_32(x);
+   }
+
+inline uint32_t ct_is_equal_32(uint32_t x, uint32_t y)
+   {
+   return ct_is_zero_32(x ^ y);
+   }
+
+inline uint16_t ct_expand_mask_16(uint16_t x)
+   {
+   uint16_t r = x;
+   r |= r >> 8;
+   r |= r >> 4;
+   r |= r >> 2;
+   r |= r >> 1;
+   r &= 1;
+   r = ~(r - 1);
+   return r;
+   }
+
+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);
+   }
+
+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);
+   }
+
+}
+
+#endif
diff --git a/src/lib/utils/info.txt b/src/lib/utils/info.txt
index 79026d7a9..228fccd82 100644
--- a/src/lib/utils/info.txt
+++ b/src/lib/utils/info.txt
@@ -8,8 +8,8 @@ bswap.h
 calendar.h
 charset.h
 cpuid.h
-database.h
 data_src.h
+database.h
 exceptn.h
 loadstor.h
 mem_ops.h
@@ -22,11 +22,11 @@ version.h
 
 <header:internal>
 bit_ops.h
+ct_utils.h
 donna128.h
 filesystem.h
 prefetch.h
 rounding.h
 semaphore.h
 stl_util.h
-ta_utils.h
 </header:internal>
diff --git a/src/lib/utils/ta_utils.cpp b/src/lib/utils/ta_utils.cpp
deleted file mode 100644
index 8aee726ec..000000000
--- a/src/lib/utils/ta_utils.cpp
+++ /dev/null
@@ -1,66 +0,0 @@
-/*
-* Timing Attack Countermeasure Functions
-* (C) 2010 Falko Strenzke, Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#include <botan/internal/ta_utils.h>
-
-namespace Botan {
-
-namespace TA_CM {
-
-/*
-* We use volatile in these functions in an attempt to ensure that the
-* compiler doesn't optimize in a way that would create branching
-* operations.
-*
-* Note: this needs further testing; on at least x86-64 with GCC,
-* volatile is not required to get branch-free operations, it just
-* makes the functions much longer/slower. It may not be required
-* anywhere.
-*/
-
-namespace {
-
-template<typename T>
-T expand_mask(T x)
-   {
-   volatile T r = x;
-   for(size_t i = 1; i != sizeof(T) * 8; i *= 2)
-      r |= r >> i;
-   r &= 1;
-   r = ~(r - 1);
-   return r;
-   }
-
-}
-
-u32bit expand_mask_u32bit(u32bit in)
-   {
-   return expand_mask<u32bit>(in);
-   }
-
-u16bit expand_mask_u16bit(u16bit in)
-   {
-   return expand_mask<u16bit>(in);
-   }
-
-u32bit max_32(u32bit a, u32bit b)
-   {
-   const u32bit a_larger = b - a; /* negative if a larger */
-   const u32bit mask = expand_mask<u32bit>(a_larger >> 31);
-   return (a & mask) | (b & ~mask);
-   }
-
-u32bit min_32(u32bit a, u32bit b)
-   {
-   const u32bit a_larger = b - a; /* negative if a larger */
-   const u32bit mask = expand_mask<u32bit>(a_larger >> 31);
-   return (a & ~mask) | (b & mask);
-   }
-
-}
-
-}
diff --git a/src/lib/utils/ta_utils.h b/src/lib/utils/ta_utils.h
deleted file mode 100644
index 9353214b2..000000000
--- a/src/lib/utils/ta_utils.h
+++ /dev/null
@@ -1,57 +0,0 @@
-/*
-* Timing Attack Countermeasure Functions
-* (C) 2010 Falko Strenzke, Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_TIMING_ATTACK_CM_H__
-#define BOTAN_TIMING_ATTACK_CM_H__
-
-#include <botan/types.h>
-
-namespace Botan {
-
-namespace TA_CM {
-
-/**
-* Function used in timing attack countermeasures
-* See Wagner, Molnar, et al "The Program Counter Security Model"
-*
-* @param in an integer
-* @return 0 if in == 0 else 0xFFFFFFFF
-*/
-u32bit expand_mask_u32bit(u32bit in);
-
-
-/**
- * Expand an input to a bit mask depending on it being being zero or
- * non-zero
- * @ param in the input
- * @return the mask 0xFFFF if tst is non-zero and 0 otherwise
- */
-u16bit expand_mask_u16bit(u16bit in);
-
-/**
-* Branch-free maximum
-* Note: assumes twos-complement signed representation
-* @param a an integer
-* @param b an integer
-* @return max(a,b)
-*/
-u32bit max_32(u32bit a, u32bit b);
-
-/**
-* Branch-free minimum
-* Note: assumes twos-complement signed representation
-* @param a an integer
-* @param b an integer
-* @return min(a,b)
-*/
-u32bit min_32(u32bit a, u32bit b);
-
-}
-
-}
-
-#endif