Make PKCS #1 and OAEP decoding constant time to avoid oracle attacks

via timing channels.

Add annotations for checking constant-time code using ctgrind to
PKCS #1 and OAEP, as well as IDEA and Curve25519 which were already
written as constant time code.

4 files changed, 209 insertions, 125 deletions

diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
new file mode 100644
index 000000000..02148001e
--- /dev/null
+++ b/src/lib/utils/ct_utils.h
@@ -0,0 +1,207 @@
+/*
+* 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
+
+/*
+* Constant time operations for 32 bit values:
+* mask, select, zero, equals, min, max
+*/
+
+/*
+* 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)
+   {
+   uint32_t r = x;
+   r |= r >> 1;
+   r |= r >> 2;
+   r |= r >> 4;
+   r |= r >> 8;
+   r |= r >> 16;
+   r &= 1;
+   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_select_cond_32(bool cond, uint32_t a, uint32_t b)
+   {
+   return ct_select_mask_32(ct_expand_mask_32(static_cast<uint32_t>(cond)), a, b);
+   }
+
+inline uint32_t ct_get_high_bit_32(uint32_t x)
+   {
+   return (x >> (8 * sizeof(x) - 1));
+   }
+
+/*
+* If x is zero, return 0xFFFF...
+* Otherwise returns zero
+*/
+inline uint32_t ct_is_zero_32(uint32_t x)
+   {
+   return ct_expand_mask_32(ct_get_high_bit_32(~x & (x-1)));
+   }
+
+inline uint32_t ct_is_equal_32(uint32_t x, uint32_t y)
+   {
+   return ct_is_zero_32(x ^ y);
+   }
+
+/**
+* Branch-free maximum
+* Note: assumes twos-complement signed representation
+* @param a an integer
+* @param b an integer
+* @return max(a,b)
+*/
+inline uint32_t ct_max_32(uint32_t a, uint32_t b)
+   {
+   const uint32_t s = b - a;
+   return ct_select_cond_32(ct_get_high_bit_32(s), a, b);
+   }
+
+/**
+* Branch-free minimum
+* Note: assumes twos-complement signed representation
+* @param a an integer
+* @param b an integer
+* @return min(a,b)
+*/
+inline uint32_t ct_min_32(uint32_t a, uint32_t b)
+   {
+   const uint32_t s = b - a;
+   return ct_select_cond_32(ct_get_high_bit_32(s), b, a);
+   }
+
+/*
+* Constant time operations for 16 bit values:
+* mask, select, zero, equals
+*/
+inline uint16_t ct_expand_mask_16(uint16_t x)
+   {
+   uint16_t r = x;
+   r |= r >> 1;
+   r |= r >> 2;
+   r |= r >> 4;
+   r |= r >> 8;
+   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_select_cond_16(bool cond, uint16_t a, uint16_t b)
+   {
+   return ct_select_mask_16(ct_expand_mask_16(static_cast<uint16_t>(cond)), a, b);
+   }
+
+inline uint16_t ct_get_high_bit_16(uint16_t x)
+   {
+   return (x >> (8 * sizeof(x) - 1));
+   }
+
+inline uint16_t ct_is_zero_16(uint16_t x)
+   {
+   //uint16_t z = x & (x - 1)
+   //return ct_expand_mask_16((~x & (x-1))
+   return ct_expand_mask_16(ct_get_high_bit_16(~x & (x-1)));
+   }
+
+inline uint16_t ct_is_equal_16(uint16_t x, uint16_t y)
+   {
+   return ct_is_zero_16(x ^ y);
+   }
+
+/*
+* Constant time operations for 8 bit values:
+* mask, select, zero, equals
+*/
+
+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_select_cond_8(bool cond, uint8_t a, uint8_t b)
+   {
+   return ct_select_mask_8(ct_expand_mask_8(static_cast<uint8_t>(cond)), a, b);
+   }
+
+inline uint8_t ct_get_high_bit_8(uint8_t x)
+   {
+   return (x >> (8 * sizeof(x) - 1));
+   }
+
+inline uint8_t ct_is_zero_8(uint8_t x)
+   {
+   return ct_expand_mask_8(ct_get_high_bit_8(~x & (x-1)));
+   }
+
+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