Botan 3.2.0
Crypto and TLS for C&
ct_utils.h
Go to the documentation of this file.
1/*
2* Functions for constant time operations on data and testing of
3* constant time annotations using valgrind.
4*
5* For more information about constant time programming see
6* Wagner, Molnar, et al "The Program Counter Security Model"
7*
8* (C) 2010 Falko Strenzke
9* (C) 2015,2016,2018 Jack Lloyd
10*
11* Botan is released under the Simplified BSD License (see license.txt)
12*/
13
14#ifndef BOTAN_CT_UTILS_H_
15#define BOTAN_CT_UTILS_H_
16
17#include <botan/secmem.h>
18#include <botan/internal/bit_ops.h>
19#include <type_traits>
20#include <vector>
21
22#if defined(BOTAN_HAS_VALGRIND)
23 #include <valgrind/memcheck.h>
24#endif
25
26namespace Botan::CT {
27
28/**
29* Use valgrind to mark the contents of memory as being undefined.
30* Valgrind will accept operations which manipulate undefined values,
31* but will warn if an undefined value is used to decided a conditional
32* jump or a load/store address. So if we poison all of our inputs we
33* can confirm that the operations in question are truly const time
34* when compiled by whatever compiler is in use.
35*
36* Even better, the VALGRIND_MAKE_MEM_* macros work even when the
37* program is not run under valgrind (though with a few cycles of
38* overhead, which is unfortunate in final binaries as these
39* annotations tend to be used in fairly important loops).
40*
41* This approach was first used in ctgrind (https://github.com/agl/ctgrind)
42* but calling the valgrind mecheck API directly works just as well and
43* doesn't require a custom patched valgrind.
44*/
45template <typename T>
46inline void poison(const T* p, size_t n) {
47#if defined(BOTAN_HAS_VALGRIND)
48 VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T));
49#else
50 BOTAN_UNUSED(p, n);
51#endif
52}
53
54template <typename T>
55inline void unpoison(const T* p, size_t n) {
56#if defined(BOTAN_HAS_VALGRIND)
57 VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T));
58#else
59 BOTAN_UNUSED(p, n);
60#endif
61}
62
63template <typename T>
64inline void unpoison(T& p) {
65#if defined(BOTAN_HAS_VALGRIND)
66 VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
67#else
68 BOTAN_UNUSED(p);
69#endif
70}
71
72/**
73* A Mask type used for constant-time operations. A Mask<T> always has value
74* either 0 (all bits cleared) or ~0 (all bits set). All operations in a Mask<T>
75* are intended to compile to code which does not contain conditional jumps.
76* This must be verified with tooling (eg binary disassembly or using valgrind)
77* since you never know what a compiler might do.
78*/
79template <typename T>
80 requires(std::is_unsigned<T>::value && !std::is_same<bool, T>::value)
81class Mask final {
82 public:
83 Mask(const Mask<T>& other) = default;
84 Mask<T>& operator=(const Mask<T>& other) = default;
85
86 /**
87 * Derive a Mask from a Mask of a larger type
88 */
89 template <typename U>
90 Mask(Mask<U> o) : m_mask(static_cast<T>(o.value())) {
91 static_assert(sizeof(U) > sizeof(T), "sizes ok");
92 }
93
94 /**
95 * Return a Mask<T> with all bits set
96 */
97 static Mask<T> set() { return Mask<T>(static_cast<T>(~0)); }
98
99 /**
100 * Return a Mask<T> with all bits cleared
101 */
102 static Mask<T> cleared() { return Mask<T>(0); }
103
104 /**
105 * Return a Mask<T> which is set if v is != 0
106 */
107 static Mask<T> expand(T v) { return ~Mask<T>::is_zero(v); }
108
109 /**
110 * Return a Mask<T> which is set if m is set
111 */
112 template <typename U>
114 static_assert(sizeof(U) < sizeof(T), "sizes ok");
115 return ~Mask<T>::is_zero(m.value());
116 }
117
118 /**
119 * Return a Mask<T> which is set if v is == 0 or cleared otherwise
120 */
121 static Mask<T> is_zero(T x) { return Mask<T>(ct_is_zero<T>(x)); }
122
123 /**
124 * Return a Mask<T> which is set if x == y
125 */
126 static Mask<T> is_equal(T x, T y) { return Mask<T>::is_zero(static_cast<T>(x ^ y)); }
127
128 /**
129 * Return a Mask<T> which is set if x < y
130 */
131 static Mask<T> is_lt(T x, T y) { return Mask<T>(expand_top_bit<T>(x ^ ((x ^ y) | ((x - y) ^ x)))); }
132
133 /**
134 * Return a Mask<T> which is set if x > y
135 */
136 static Mask<T> is_gt(T x, T y) { return Mask<T>::is_lt(y, x); }
137
138 /**
139 * Return a Mask<T> which is set if x <= y
140 */
141 static Mask<T> is_lte(T x, T y) { return ~Mask<T>::is_gt(x, y); }
142
143 /**
144 * Return a Mask<T> which is set if x >= y
145 */
146 static Mask<T> is_gte(T x, T y) { return ~Mask<T>::is_lt(x, y); }
147
148 static Mask<T> is_within_range(T v, T l, T u) {
149 //return Mask<T>::is_gte(v, l) & Mask<T>::is_lte(v, u);
150
151 const T v_lt_l = v ^ ((v ^ l) | ((v - l) ^ v));
152 const T v_gt_u = u ^ ((u ^ v) | ((u - v) ^ u));
153 const T either = v_lt_l | v_gt_u;
154 return ~Mask<T>(expand_top_bit(either));
155 }
156
157 static Mask<T> is_any_of(T v, std::initializer_list<T> accepted) {
158 T accept = 0;
159
160 for(auto a : accepted) {
161 const T diff = a ^ v;
162 const T eq_zero = ~diff & (diff - 1);
163 accept |= eq_zero;
164 }
165
166 return Mask<T>(expand_top_bit(accept));
167 }
168
169 /**
170 * AND-combine two masks
171 */
173 m_mask &= o.value();
174 return (*this);
175 }
176
177 /**
178 * XOR-combine two masks
179 */
181 m_mask ^= o.value();
182 return (*this);
183 }
184
185 /**
186 * OR-combine two masks
187 */
189 m_mask |= o.value();
190 return (*this);
191 }
192
193 /**
194 * AND-combine two masks
195 */
196 friend Mask<T> operator&(Mask<T> x, Mask<T> y) { return Mask<T>(x.value() & y.value()); }
197
198 /**
199 * XOR-combine two masks
200 */
201 friend Mask<T> operator^(Mask<T> x, Mask<T> y) { return Mask<T>(x.value() ^ y.value()); }
202
203 /**
204 * OR-combine two masks
205 */
206 friend Mask<T> operator|(Mask<T> x, Mask<T> y) { return Mask<T>(x.value() | y.value()); }
207
208 /**
209 * Negate this mask
210 */
211 Mask<T> operator~() const { return Mask<T>(~value()); }
212
213 /**
214 * Return x if the mask is set, or otherwise zero
215 */
216 T if_set_return(T x) const { return m_mask & x; }
217
218 /**
219 * Return x if the mask is cleared, or otherwise zero
220 */
221 T if_not_set_return(T x) const { return ~m_mask & x; }
222
223 /**
224 * If this mask is set, return x, otherwise return y
225 */
226 T select(T x, T y) const { return choose(value(), x, y); }
227
228 T select_and_unpoison(T x, T y) const {
229 T r = this->select(x, y);
230 CT::unpoison(r);
231 return r;
232 }
233
234 /**
235 * If this mask is set, return x, otherwise return y
236 */
237 Mask<T> select_mask(Mask<T> x, Mask<T> y) const { return Mask<T>(select(x.value(), y.value())); }
238
239 /**
240 * Conditionally set output to x or y, depending on if mask is set or
241 * cleared (resp)
242 */
243 void select_n(T output[], const T x[], const T y[], size_t len) const {
244 for(size_t i = 0; i != len; ++i) {
245 output[i] = this->select(x[i], y[i]);
246 }
247 }
248
249 /**
250 * If this mask is set, zero out buf, otherwise do nothing
251 */
252 void if_set_zero_out(T buf[], size_t elems) {
253 for(size_t i = 0; i != elems; ++i) {
254 buf[i] = this->if_not_set_return(buf[i]);
255 }
256 }
257
258 /**
259 * Return the value of the mask, unpoisoned
260 */
262 T r = value();
263 CT::unpoison(r);
264 return r;
265 }
266
267 /**
268 * Return true iff this mask is set
269 */
270 bool is_set() const { return unpoisoned_value() != 0; }
271
272 /**
273 * Return the underlying value of the mask
274 */
275 T value() const { return m_mask; }
276
277 private:
278 Mask(T m) : m_mask(m) {}
279
280 T m_mask;
281};
282
283template <typename T>
284inline Mask<T> conditional_copy_mem(T cnd, T* to, const T* from0, const T* from1, size_t elems) {
285 const auto mask = CT::Mask<T>::expand(cnd);
286 mask.select_n(to, from0, from1, elems);
287 return mask;
288}
289
290template <typename T>
291inline Mask<T> conditional_assign_mem(T cnd, T* sink, const T* src, size_t elems) {
292 const auto mask = CT::Mask<T>::expand(cnd);
293 mask.select_n(sink, src, sink, elems);
294 return mask;
295}
296
297template <typename T>
298inline void conditional_swap(bool cnd, T& x, T& y) {
299 const auto swap = CT::Mask<T>::expand(cnd);
300
301 T t0 = swap.select(y, x);
302 T t1 = swap.select(x, y);
303 x = t0;
304 y = t1;
305}
306
307template <typename T>
308inline void conditional_swap_ptr(bool cnd, T& x, T& y) {
309 uintptr_t xp = reinterpret_cast<uintptr_t>(x);
310 uintptr_t yp = reinterpret_cast<uintptr_t>(y);
311
312 conditional_swap<uintptr_t>(cnd, xp, yp);
313
314 x = reinterpret_cast<T>(xp);
315 y = reinterpret_cast<T>(yp);
316}
317
318template <typename T>
319inline CT::Mask<T> all_zeros(const T elem[], size_t len) {
320 T sum = 0;
321 for(size_t i = 0; i != len; ++i) {
322 sum |= elem[i];
323 }
324 return CT::Mask<T>::is_zero(sum);
325}
326
327/**
328* If bad_input is unset, return input[offset:input_length] copied to new
329* buffer. If bad_input is set, return an empty vector. In all cases, the capacity
330* of the vector is equal to input_length
331*
332* This function attempts to avoid leaking the following:
333* - if bad_input was set or not
334* - the value of offset
335* - the values in input[]
336*
337* This function leaks the value of input_length
338*/
341 const uint8_t input[],
342 size_t input_length,
343 size_t offset);
344
345secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length);
346
348 return strip_leading_zeros(in.data(), in.size());
349}
350
351} // namespace Botan::CT
352
353#endif
#define BOTAN_UNUSED
Definition assert.h:118
Mask< T > select_mask(Mask< T > x, Mask< T > y) const
Definition ct_utils.h:237
void if_set_zero_out(T buf[], size_t elems)
Definition ct_utils.h:252
bool is_set() const
Definition ct_utils.h:270
static Mask< T > is_gt(T x, T y)
Definition ct_utils.h:136
T value() const
Definition ct_utils.h:275
static Mask< T > is_equal(T x, T y)
Definition ct_utils.h:126
static Mask< T > is_zero(T x)
Definition ct_utils.h:121
friend Mask< T > operator|(Mask< T > x, Mask< T > y)
Definition ct_utils.h:206
Mask< T > & operator^=(Mask< T > o)
Definition ct_utils.h:180
T if_not_set_return(T x) const
Definition ct_utils.h:221
friend Mask< T > operator^(Mask< T > x, Mask< T > y)
Definition ct_utils.h:201
T select(T x, T y) const
Definition ct_utils.h:226
void select_n(T output[], const T x[], const T y[], size_t len) const
Definition ct_utils.h:243
static Mask< T > expand(Mask< U > m)
Definition ct_utils.h:113
static Mask< T > expand(T v)
Definition ct_utils.h:107
T unpoisoned_value() const
Definition ct_utils.h:261
T if_set_return(T x) const
Definition ct_utils.h:216
Mask< T > & operator=(const Mask< T > &other)=default
static Mask< T > set()
Definition ct_utils.h:97
Mask(const Mask< T > &other)=default
Mask< T > & operator&=(Mask< T > o)
Definition ct_utils.h:172
Mask(Mask< U > o)
Definition ct_utils.h:90
T select_and_unpoison(T x, T y) const
Definition ct_utils.h:228
Mask< T > operator~() const
Definition ct_utils.h:211
static Mask< T > is_any_of(T v, std::initializer_list< T > accepted)
Definition ct_utils.h:157
Mask< T > & operator|=(Mask< T > o)
Definition ct_utils.h:188
static Mask< T > is_gte(T x, T y)
Definition ct_utils.h:146
static Mask< T > is_lt(T x, T y)
Definition ct_utils.h:131
static Mask< T > cleared()
Definition ct_utils.h:102
static Mask< T > is_within_range(T v, T l, T u)
Definition ct_utils.h:148
static Mask< T > is_lte(T x, T y)
Definition ct_utils.h:141
friend Mask< T > operator&(Mask< T > x, Mask< T > y)
Definition ct_utils.h:196
#define BOTAN_TEST_API
Definition compiler.h:40
FE_25519 T
Definition ge.cpp:34
void poison(const T *p, size_t n)
Definition ct_utils.h:46
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition ct_utils.h:308
void conditional_swap(bool cnd, T &x, T &y)
Definition ct_utils.h:298
secure_vector< uint8_t > copy_output(CT::Mask< uint8_t > bad_input_u8, const uint8_t input[], size_t input_length, size_t offset)
Definition ct_utils.cpp:11
Mask< T > conditional_assign_mem(T cnd, T *sink, const T *src, size_t elems)
Definition ct_utils.h:291
void unpoison(const T *p, size_t n)
Definition ct_utils.h:55
CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:319
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition ct_utils.cpp:84
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition ct_utils.h:284
constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:180
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr T expand_top_bit(T a)
Definition bit_ops.h:23