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.

1 files changed, 48 insertions, 71 deletions

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