Source code
Revision control
Copy as Markdown
Other Tools
/*
* Functions for constant time operations on data and testing of
* constant time annotations using valgrind.
*
* For more information about constant time programming see
* Wagner, Molnar, et al "The Program Counter Security Model"
*
* (C) 2010 Falko Strenzke
* (C) 2015,2016,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#ifndef BOTAN_CT_UTILS_H_
#define BOTAN_CT_UTILS_H_
#include <botan/secmem.h>
#include <botan/internal/bit_ops.h>
#include <type_traits>
#include <vector>
#if defined(BOTAN_HAS_VALGRIND)
#include <valgrind/memcheck.h>
#endif
namespace Botan {
namespace CT {
/**
* Use valgrind to mark the contents of memory as being undefined.
* Valgrind will accept operations which manipulate undefined values,
* but will warn if an undefined value is used to decided a conditional
* jump or a load/store address. So if we poison all of our inputs we
* can confirm that the operations in question are truly const time
* when compiled by whatever compiler is in use.
*
* Even better, the VALGRIND_MAKE_MEM_* macros work even when the
* program is not run under valgrind (though with a few cycles of
* overhead, which is unfortunate in final binaries as these
* annotations tend to be used in fairly important loops).
*
* but calling the valgrind mecheck API directly works just as well and
* doesn't require a custom patched valgrind.
*/
template<typename T>
inline void poison(const T* p, size_t n)
{
#if defined(BOTAN_HAS_VALGRIND)
VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T));
#else
BOTAN_UNUSED(p);
BOTAN_UNUSED(n);
#endif
}
template<typename T>
inline void unpoison(const T* p, size_t n)
{
#if defined(BOTAN_HAS_VALGRIND)
VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T));
#else
BOTAN_UNUSED(p);
BOTAN_UNUSED(n);
#endif
}
template<typename T>
inline void unpoison(T& p)
{
#if defined(BOTAN_HAS_VALGRIND)
VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
#else
BOTAN_UNUSED(p);
#endif
}
/**
* 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>
class Mask
{
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(static_cast<T>(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>(static_cast<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 m is set
*/
template<typename U>
static Mask<T> expand(Mask<U> m)
{
static_assert(sizeof(U) < sizeof(T), "sizes ok");
return ~Mask<T>::is_zero(m.value());
}
/**
* Return a Mask<T> which is set if v is == 0 or cleared otherwise
*/
static Mask<T> is_zero(T x)
{
return Mask<T>(ct_is_zero<T>(x));
}
/**
* 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<T>(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);
}
static Mask<T> is_within_range(T v, T l, T u)
{
//return Mask<T>::is_gte(v, l) & Mask<T>::is_lte(v, u);
const T v_lt_l = v^((v^l) | ((v-l)^v));
const T v_gt_u = u^((u^v) | ((u-v)^u));
const T either = v_lt_l | v_gt_u;
return ~Mask<T>(expand_top_bit(either));
}
static Mask<T> is_any_of(T v, std::initializer_list<T> accepted)
{
T accept = 0;
for(auto a: accepted)
{
const T diff = a ^ v;
const T eq_zero = ~diff & (diff - 1);
accept |= eq_zero;
}
return Mask<T>(expand_top_bit(accept));
}
/**
* 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:
Mask(T m) : m_mask(m) {}
T m_mask;
};
template<typename T>
inline Mask<T> conditional_copy_mem(T cnd,
T* to,
const T* from0,
const T* from1,
size_t elems)
{
const auto mask = CT::Mask<T>::expand(cnd);
mask.select_n(to, from0, from1, elems);
return mask;
}
template<typename T>
inline void conditional_swap(bool cnd, T& x, T& y)
{
const auto swap = CT::Mask<T>::expand(cnd);
T t0 = swap.select(y, x);
T t1 = swap.select(x, y);
x = t0;
y = t1;
}
template<typename T>
inline void conditional_swap_ptr(bool cnd, T& x, T& y)
{
uintptr_t xp = reinterpret_cast<uintptr_t>(x);
uintptr_t yp = reinterpret_cast<uintptr_t>(y);
conditional_swap<uintptr_t>(cnd, xp, yp);
x = reinterpret_cast<T>(xp);
y = reinterpret_cast<T>(yp);
}
/**
* If bad_mask is unset, return in[delim_idx:input_length] copied to
* new buffer. If bad_mask is set, return an all zero vector of
* unspecified length.
*/
secure_vector<uint8_t> copy_output(CT::Mask<uint8_t> bad_input,
const uint8_t input[],
size_t input_length,
size_t delim_idx);
secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length);
inline secure_vector<uint8_t> strip_leading_zeros(const secure_vector<uint8_t>& in)
{
return strip_leading_zeros(in.data(), in.size());
}
}
}
#endif