summaryrefslogtreecommitdiffstats
path: root/comm/third_party/botan/src/lib/utils/ct_utils.h
diff options
context:
space:
mode:
Diffstat (limited to 'comm/third_party/botan/src/lib/utils/ct_utils.h')
-rw-r--r--comm/third_party/botan/src/lib/utils/ct_utils.h418
1 files changed, 418 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/utils/ct_utils.h b/comm/third_party/botan/src/lib/utils/ct_utils.h
new file mode 100644
index 0000000000..f2e7452931
--- /dev/null
+++ b/comm/third_party/botan/src/lib/utils/ct_utils.h
@@ -0,0 +1,418 @@
+/*
+* 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).
+*
+* This approach was first used in ctgrind (https://github.com/agl/ctgrind)
+* 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-02 20:14:02 +0000