Add CT::Mask type

3 files changed, 288 insertions, 118 deletions

diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 63b8f4640..eb510baa2 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -6,13 +6,13 @@
 * Wagner, Molnar, et al "The Program Counter Security Model"
 *
 * (C) 2010 Falko Strenzke
-* (C) 2015,2016 Jack Lloyd
+* (C) 2015,2016,2018 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_
+#ifndef BOTAN_CT_UTILS_H_
+#define BOTAN_CT_UTILS_H_
 
 #include <botan/secmem.h>
 #include <type_traits>
@@ -75,130 +75,285 @@ inline void unpoison(T& p)
 #endif
    }
 
-/* Mask generation */
-
-template<typename T>
-inline constexpr T expand_top_bit(T a)
-   {
-   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
-   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
-   }
-
-template<typename T>
-inline constexpr T is_zero(T x)
-   {
-   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
-   return expand_top_bit<T>(~x & (x - 1));
-   }
-
-/*
-* T should be an unsigned machine integer type
-* Expand to a mask used for other operations
-* @param in an integer
-* @return If n is zero, returns zero. Otherwise
-* returns a T with all bits set for use as a mask with
-* select.
+/**
+* A Mask type used for constant-time operations. A Mask<T> always has value
+* either 0 (all bits cleared) or ~0 (all bits set). All operations in a Mask<T>
+* are intended to compile to code which does not contain conditional jumps.
+* This must be verified with tooling (eg binary disassembly or using valgrind)
+* since you never know what a compiler might do.
 */
 template<typename T>
-inline constexpr T expand_mask(T x)
+class Mask
    {
-   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
-   return ~is_zero(x);
-   }
-
-template<typename T>
-inline constexpr T select(T mask, T from0, T from1)
-   {
-   static_assert(std::is_unsigned<T>::value, "unsigned integer type required");
-   //return static_cast<T>((from0 & mask) | (from1 & ~mask));
-   return static_cast<T>(from1 ^ (mask & (from0 ^ from1)));
-   }
-
-template<typename T>
-inline constexpr T select2(T mask0, T val0, T mask1, T val1, T val2)
-   {
-   return select<T>(mask0, val0, select<T>(mask1, val1, val2));
-   }
-
-template<typename T>
-inline constexpr T select3(T mask0, T val0, T mask1, T val1, T mask2, T val2, T val3)
-   {
-   return select2<T>(mask0, val0, mask1, val1, select<T>(mask2, val2, val3));
-   }
-
-template<typename PredT, typename ValT>
-inline constexpr ValT val_or_zero(PredT pred_val, ValT val)
-   {
-   return select(CT::expand_mask<ValT>(pred_val), val, static_cast<ValT>(0));
-   }
+   public:
+      static_assert(std::is_unsigned<T>::value, "CT::Mask only defined for unsigned integer types");
+
+      Mask(const Mask<T>& other) = default;
+      Mask<T>& operator=(const Mask<T>& other) = default;
+
+      /**
+      * Derive a Mask from a Mask of a larger type
+      */
+      template<typename U>
+      Mask(Mask<U> o) : m_mask(o.value())
+         {
+         static_assert(sizeof(U) > sizeof(T), "sizes ok");
+         }
+
+      /**
+      * Return a Mask<T> with all bits set
+      */
+      static Mask<T> set()
+         {
+         return Mask<T>(~0);
+         }
+
+      /**
+      * Return a Mask<T> with all bits cleared
+      */
+      static Mask<T> cleared()
+         {
+         return Mask<T>(0);
+         }
+
+      /**
+      * Return a Mask<T> which is set if v is != 0
+      */
+      static Mask<T> expand(T v)
+         {
+         return ~Mask<T>::is_zero(v);
+         }
+
+      /**
+      * Return a Mask<T> which is set if v is == 0 or cleared otherwise
+      */
+      static Mask<T> is_zero(T x)
+         {
+         return Mask<T>(expand_top_bit(~x & (x - 1)));
+         }
+
+      /**
+      * Return a Mask<T> which is set if x == y
+      */
+      static Mask<T> is_equal(T x, T y)
+         {
+         return Mask<T>::is_zero(static_cast<T>(x ^ y));
+         }
+
+      /**
+      * Return a Mask<T> which is set if x < y
+      */
+      static Mask<T> is_lt(T x, T y)
+         {
+         return Mask<T>(expand_top_bit(x^((x^y) | ((x-y)^x))));
+         }
+
+      /**
+      * Return a Mask<T> which is set if x > y
+      */
+      static Mask<T> is_gt(T x, T y)
+         {
+         return Mask<T>::is_lt(y, x);
+         }
+
+      /**
+      * Return a Mask<T> which is set if x <= y
+      */
+      static Mask<T> is_lte(T x, T y)
+         {
+         return ~Mask<T>::is_gt(x, y);
+         }
+
+      /**
+      * Return a Mask<T> which is set if x >= y
+      */
+      static Mask<T> is_gte(T x, T y)
+         {
+         return ~Mask<T>::is_lt(x, y);
+         }
+
+      /**
+      * AND-combine two masks
+      */
+      Mask<T>& operator&=(Mask<T> o)
+         {
+         m_mask &= o.value();
+         return (*this);
+         }
+
+      /**
+      * XOR-combine two masks
+      */
+      Mask<T>& operator^=(Mask<T> o)
+         {
+         m_mask ^= o.value();
+         return (*this);
+         }
+
+      /**
+      * OR-combine two masks
+      */
+      Mask<T>& operator|=(Mask<T> o)
+         {
+         m_mask |= o.value();
+         return (*this);
+         }
+
+      /**
+      * AND-combine two masks
+      */
+      friend Mask<T> operator&(Mask<T> x, Mask<T> y)
+         {
+         return Mask<T>(x.value() & y.value());
+         }
+
+      /**
+      * XOR-combine two masks
+      */
+      friend Mask<T> operator^(Mask<T> x, Mask<T> y)
+         {
+         return Mask<T>(x.value() ^ y.value());
+         }
+
+      /**
+      * OR-combine two masks
+      */
+      friend Mask<T> operator|(Mask<T> x, Mask<T> y)
+         {
+         return Mask<T>(x.value() | y.value());
+         }
+
+      /**
+      * Negate this mask
+      */
+      Mask<T> operator~() const
+         {
+         return Mask<T>(~value());
+         }
+
+      /**
+      * Return x if the mask is set, or otherwise zero
+      */
+      T if_set_return(T x) const
+         {
+         return m_mask & x;
+         }
+
+      /**
+      * Return x if the mask is cleared, or otherwise zero
+      */
+      T if_not_set_return(T x) const
+         {
+         return ~m_mask & x;
+         }
+
+      /**
+      * If this mask is set, return x, otherwise return y
+      */
+      T select(T x, T y) const
+         {
+         // (x & value()) | (y & ~value())
+         return static_cast<T>(y ^ (value() & (x ^ y)));
+         }
+
+      T select_and_unpoison(T x, T y) const
+         {
+         T r = this->select(x, y);
+         CT::unpoison(r);
+         return r;
+         }
+
+      /**
+      * If this mask is set, return x, otherwise return y
+      */
+      Mask<T> select_mask(Mask<T> x, Mask<T> y) const
+         {
+         return Mask<T>(select(x.value(), y.value()));
+         }
+
+      /**
+      * Conditionally set output to x or y, depending on if mask is set or
+      * cleared (resp)
+      */
+      void select_n(T output[], const T x[], const T y[], size_t len) const
+         {
+         for(size_t i = 0; i != len; ++i)
+            output[i] = this->select(x[i], y[i]);
+         }
+
+      /**
+      * If this mask is set, zero out buf, otherwise do nothing
+      */
+      void if_set_zero_out(T buf[], size_t elems)
+         {
+         for(size_t i = 0; i != elems; ++i)
+            {
+            buf[i] = this->if_not_set_return(buf[i]);
+            }
+         }
+
+      /**
+      * Return the value of the mask, unpoisoned
+      */
+      T unpoisoned_value() const
+         {
+         T r = value();
+         CT::unpoison(r);
+         return r;
+         }
+
+      /**
+      * Return true iff this mask is set
+      */
+      bool is_set() const
+         {
+         return unpoisoned_value() != 0;
+         }
+
+      /**
+      * Return the underlying value of the mask
+      */
+      T value() const
+         {
+         return m_mask;
+         }
+
+   private:
+      /**
+      * If top bit of arg is set, return ~0. Otherwise return 0.
+      */
+      static T expand_top_bit(T a)
+         {
+         return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
+         }
+
+      Mask(T m) : m_mask(m) {}
+
+      T m_mask;
+   };
 
 template<typename T>
-inline constexpr T is_equal(T x, T y)
+inline Mask<T> conditional_copy_mem(T cnd,
+                                    T* to,
+                                    const T* from0,
+                                    const T* from1,
+                                    size_t elems)
    {
-   return is_zero<T>(x ^ y);
-   }
-
-template<typename T>
-inline constexpr T is_less(T a, T b)
-   {
-   return expand_top_bit<T>(a ^ ((a^b) | ((a-b)^a)));
-   }
-
-template<typename T>
-inline constexpr T is_lte(T a, T b)
-   {
-   return CT::is_less(a, b) | CT::is_equal(a, b);
-   }
-
-template<typename C, typename T>
-inline T conditional_return(C condvar, T left, T right)
-   {
-   const T val = CT::select(CT::expand_mask<T>(condvar), left, right);
-   CT::unpoison(val);
-   return val;
-   }
-
-template<typename T>
-inline T conditional_copy_mem(T value,
-                              T* to,
-                              const T* from0,
-                              const T* from1,
-                              size_t elems)
-   {
-   const T mask = CT::expand_mask(value);
-
-   for(size_t i = 0; i != elems; ++i)
-      {
-      to[i] = CT::select(mask, from0[i], from1[i]);
-      }
-
+   const auto mask = CT::Mask<T>::expand(cnd);
+   mask.select_n(to, from0, from1, elems);
    return mask;
    }
 
-template<typename T>
-inline void cond_zero_mem(T cond,
-                          T* array,
-                          size_t elems)
-   {
-   const T mask = CT::expand_mask(cond);
-   const T zero(0);
-
-   for(size_t i = 0; i != elems; ++i)
-      {
-      array[i] = CT::select(mask, zero, array[i]);
-      }
-   }
-
 inline secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length)
    {
    size_t leading_zeros = 0;
 
-   uint8_t only_zeros = 0xFF;
+   auto only_zeros = Mask<uint8_t>::set();
 
    for(size_t i = 0; i != length; ++i)
       {
-      only_zeros = only_zeros & CT::is_zero<uint8_t>(in[i]);
-      leading_zeros += CT::select<uint8_t>(only_zeros, 1, 0);
+      only_zeros &= CT::Mask<uint8_t>::is_zero(in[i]);
+      leading_zeros += only_zeros.if_set_return(1);
       }
 
    return secure_vector<uint8_t>(in + leading_zeros, in + length);
diff --git a/src/lib/utils/mem_ops.cpp b/src/lib/utils/mem_ops.cpp
index 668437e9f..460fc4b69 100644
--- a/src/lib/utils/mem_ops.cpp
+++ b/src/lib/utils/mem_ops.cpp
@@ -5,6 +5,7 @@
 */
 
 #include <botan/mem_ops.h>
+#include <botan/internal/ct_utils.h>
 #include <cstdlib>
 #include <new>
 
@@ -49,16 +50,16 @@ void initialize_allocator()
 #endif
    }
 
-bool constant_time_compare(const uint8_t x[],
-                           const uint8_t y[],
-                           size_t len)
+uint8_t ct_compare_u8(const uint8_t x[],
+                      const uint8_t y[],
+                      size_t len)
    {
    volatile uint8_t difference = 0;
 
    for(size_t i = 0; i != len; ++i)
       difference |= (x[i] ^ y[i]);
 
-   return difference == 0;
+   return CT::Mask<uint8_t>::is_zero(difference).value();
    }
 
 }
diff --git a/src/lib/utils/mem_ops.h b/src/lib/utils/mem_ops.h
index f0599c8b2..bff15e98a 100644
--- a/src/lib/utils/mem_ops.h
+++ b/src/lib/utils/mem_ops.h
@@ -65,11 +65,25 @@ BOTAN_PUBLIC_API(2,0) void secure_scrub_memory(void* ptr, size_t n);
 * @param x a pointer to an array
 * @param y a pointer to another array
 * @param len the number of Ts in x and y
+* @return 0xFF iff x[i] == y[i] forall i in [0...n) or 0x00 otherwise
+*/
+BOTAN_PUBLIC_API(2,9) uint8_t ct_compare_u8(const uint8_t x[],
+                                            const uint8_t y[],
+                                            size_t len);
+
+/**
+* Memory comparison, input insensitive
+* @param x a pointer to an array
+* @param y a pointer to another array
+* @param len the number of Ts in x and y
 * @return true iff x[i] == y[i] forall i in [0...n)
 */
-BOTAN_PUBLIC_API(2,3) bool constant_time_compare(const uint8_t x[],
-                                     const uint8_t y[],
-                                     size_t len);
+inline bool constant_time_compare(const uint8_t x[],
+                                  const uint8_t y[],
+                                  size_t len)
+   {
+   return ct_compare_u8(x, y, len) == 0xFF;
+   }
 
 /**
 * Zero out some bytes