Botan 2.19.1
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 {
27
28namespace CT {
29
30/**
31* Use valgrind to mark the contents of memory as being undefined.
32* Valgrind will accept operations which manipulate undefined values,
33* but will warn if an undefined value is used to decided a conditional
34* jump or a load/store address. So if we poison all of our inputs we
35* can confirm that the operations in question are truly const time
36* when compiled by whatever compiler is in use.
37*
38* Even better, the VALGRIND_MAKE_MEM_* macros work even when the
39* program is not run under valgrind (though with a few cycles of
40* overhead, which is unfortunate in final binaries as these
41* annotations tend to be used in fairly important loops).
42*
43* This approach was first used in ctgrind (https://github.com/agl/ctgrind)
44* but calling the valgrind mecheck API directly works just as well and
45* doesn't require a custom patched valgrind.
46*/
47template<typename T>
48inline void poison(const T* p, size_t n)
49 {
50#if defined(BOTAN_HAS_VALGRIND)
51 VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T));
52#else
53 BOTAN_UNUSED(p);
54 BOTAN_UNUSED(n);
55#endif
56 }
57
58template<typename T>
59inline void unpoison(const T* p, size_t n)
60 {
61#if defined(BOTAN_HAS_VALGRIND)
62 VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T));
63#else
64 BOTAN_UNUSED(p);
65 BOTAN_UNUSED(n);
66#endif
67 }
68
69template<typename T>
70inline void unpoison(T& p)
71 {
72#if defined(BOTAN_HAS_VALGRIND)
73 VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
74#else
75 BOTAN_UNUSED(p);
76#endif
77 }
78
79/**
80* A Mask type used for constant-time operations. A Mask<T> always has value
81* either 0 (all bits cleared) or ~0 (all bits set). All operations in a Mask<T>
82* are intended to compile to code which does not contain conditional jumps.
83* This must be verified with tooling (eg binary disassembly or using valgrind)
84* since you never know what a compiler might do.
85*/
86template<typename T>
87class Mask
88 {
89 public:
90 static_assert(std::is_unsigned<T>::value, "CT::Mask only defined for unsigned integer types");
91
92 Mask(const Mask<T>& other) = default;
93 Mask<T>& operator=(const Mask<T>& other) = default;
94
95 /**
96 * Derive a Mask from a Mask of a larger type
97 */
98 template<typename U>
99 Mask(Mask<U> o) : m_mask(static_cast<T>(o.value()))
100 {
101 static_assert(sizeof(U) > sizeof(T), "sizes ok");
102 }
103
104 /**
105 * Return a Mask<T> with all bits set
106 */
107 static Mask<T> set()
108 {
109 return Mask<T>(static_cast<T>(~0));
110 }
111
112 /**
113 * Return a Mask<T> with all bits cleared
114 */
116 {
117 return Mask<T>(0);
118 }
119
120 /**
121 * Return a Mask<T> which is set if v is != 0
122 */
123 static Mask<T> expand(T v)
124 {
125 return ~Mask<T>::is_zero(v);
126 }
127
128 /**
129 * Return a Mask<T> which is set if m is set
130 */
131 template<typename U>
133 {
134 static_assert(sizeof(U) < sizeof(T), "sizes ok");
135 return ~Mask<T>::is_zero(m.value());
136 }
137
138 /**
139 * Return a Mask<T> which is set if v is == 0 or cleared otherwise
140 */
141 static Mask<T> is_zero(T x)
142 {
143 return Mask<T>(ct_is_zero<T>(x));
144 }
145
146 /**
147 * Return a Mask<T> which is set if x == y
148 */
149 static Mask<T> is_equal(T x, T y)
150 {
151 return Mask<T>::is_zero(static_cast<T>(x ^ y));
152 }
153
154 /**
155 * Return a Mask<T> which is set if x < y
156 */
157 static Mask<T> is_lt(T x, T y)
158 {
159 return Mask<T>(expand_top_bit<T>(x^((x^y) | ((x-y)^x))));
160 }
161
162 /**
163 * Return a Mask<T> which is set if x > y
164 */
165 static Mask<T> is_gt(T x, T y)
166 {
167 return Mask<T>::is_lt(y, x);
168 }
169
170 /**
171 * Return a Mask<T> which is set if x <= y
172 */
173 static Mask<T> is_lte(T x, T y)
174 {
175 return ~Mask<T>::is_gt(x, y);
176 }
177
178 /**
179 * Return a Mask<T> which is set if x >= y
180 */
181 static Mask<T> is_gte(T x, T y)
182 {
183 return ~Mask<T>::is_lt(x, y);
184 }
185
186 static Mask<T> is_within_range(T v, T l, T u)
187 {
188 //return Mask<T>::is_gte(v, l) & Mask<T>::is_lte(v, u);
189
190 const T v_lt_l = v^((v^l) | ((v-l)^v));
191 const T v_gt_u = u^((u^v) | ((u-v)^u));
192 const T either = v_lt_l | v_gt_u;
193 return ~Mask<T>(expand_top_bit(either));
194 }
195
196 static Mask<T> is_any_of(T v, std::initializer_list<T> accepted)
197 {
198 T accept = 0;
199
200 for(auto a: accepted)
201 {
202 const T diff = a ^ v;
203 const T eq_zero = ~diff & (diff - 1);
204 accept |= eq_zero;
205 }
206
207 return Mask<T>(expand_top_bit(accept));
208 }
209
210 /**
211 * AND-combine two masks
212 */
214 {
215 m_mask &= o.value();
216 return (*this);
217 }
218
219 /**
220 * XOR-combine two masks
221 */
223 {
224 m_mask ^= o.value();
225 return (*this);
226 }
227
228 /**
229 * OR-combine two masks
230 */
232 {
233 m_mask |= o.value();
234 return (*this);
235 }
236
237 /**
238 * AND-combine two masks
239 */
241 {
242 return Mask<T>(x.value() & y.value());
243 }
244
245 /**
246 * XOR-combine two masks
247 */
249 {
250 return Mask<T>(x.value() ^ y.value());
251 }
252
253 /**
254 * OR-combine two masks
255 */
257 {
258 return Mask<T>(x.value() | y.value());
259 }
260
261 /**
262 * Negate this mask
263 */
265 {
266 return Mask<T>(~value());
267 }
268
269 /**
270 * Return x if the mask is set, or otherwise zero
271 */
273 {
274 return m_mask & x;
275 }
276
277 /**
278 * Return x if the mask is cleared, or otherwise zero
279 */
281 {
282 return ~m_mask & x;
283 }
284
285 /**
286 * If this mask is set, return x, otherwise return y
287 */
288 T select(T x, T y) const
289 {
290 // (x & value()) | (y & ~value())
291 return static_cast<T>(y ^ (value() & (x ^ y)));
292 }
293
295 {
296 T r = this->select(x, y);
297 CT::unpoison(r);
298 return r;
299 }
300
301 /**
302 * If this mask is set, return x, otherwise return y
303 */
305 {
306 return Mask<T>(select(x.value(), y.value()));
307 }
308
309 /**
310 * Conditionally set output to x or y, depending on if mask is set or
311 * cleared (resp)
312 */
313 void select_n(T output[], const T x[], const T y[], size_t len) const
314 {
315 for(size_t i = 0; i != len; ++i)
316 output[i] = this->select(x[i], y[i]);
317 }
318
319 /**
320 * If this mask is set, zero out buf, otherwise do nothing
321 */
322 void if_set_zero_out(T buf[], size_t elems)
323 {
324 for(size_t i = 0; i != elems; ++i)
325 {
326 buf[i] = this->if_not_set_return(buf[i]);
327 }
328 }
329
330 /**
331 * Return the value of the mask, unpoisoned
332 */
334 {
335 T r = value();
336 CT::unpoison(r);
337 return r;
338 }
339
340 /**
341 * Return true iff this mask is set
342 */
343 bool is_set() const
344 {
345 return unpoisoned_value() != 0;
346 }
347
348 /**
349 * Return the underlying value of the mask
350 */
351 T value() const
352 {
353 return m_mask;
354 }
355
356 private:
357 Mask(T m) : m_mask(m) {}
358
359 T m_mask;
360 };
361
362template<typename T>
364 T* to,
365 const T* from0,
366 const T* from1,
367 size_t elems)
368 {
369 const auto mask = CT::Mask<T>::expand(cnd);
370 mask.select_n(to, from0, from1, elems);
371 return mask;
372 }
373
374template<typename T>
375inline void conditional_swap(bool cnd, T& x, T& y)
376 {
377 const auto swap = CT::Mask<T>::expand(cnd);
378
379 T t0 = swap.select(y, x);
380 T t1 = swap.select(x, y);
381 x = t0;
382 y = t1;
383 }
384
385template<typename T>
386inline void conditional_swap_ptr(bool cnd, T& x, T& y)
387 {
388 uintptr_t xp = reinterpret_cast<uintptr_t>(x);
389 uintptr_t yp = reinterpret_cast<uintptr_t>(y);
390
391 conditional_swap<uintptr_t>(cnd, xp, yp);
392
393 x = reinterpret_cast<T>(xp);
394 y = reinterpret_cast<T>(yp);
395 }
396
397/**
398* If bad_mask is unset, return in[delim_idx:input_length] copied to
399* new buffer. If bad_mask is set, return an all zero vector of
400* unspecified length.
401*/
403 const uint8_t input[],
404 size_t input_length,
405 size_t delim_idx);
406
407secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length);
408
410 {
411 return strip_leading_zeros(in.data(), in.size());
412 }
413
414}
415
416}
417
418#endif
#define BOTAN_UNUSED(...)
Definition: assert.h:142
Mask< T > select_mask(Mask< T > x, Mask< T > y) const
Definition: ct_utils.h:304
void if_set_zero_out(T buf[], size_t elems)
Definition: ct_utils.h:322
bool is_set() const
Definition: ct_utils.h:343
static Mask< T > is_gt(T x, T y)
Definition: ct_utils.h:165
T value() const
Definition: ct_utils.h:351
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
friend Mask< T > operator|(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:256
Mask< T > & operator^=(Mask< T > o)
Definition: ct_utils.h:222
T if_not_set_return(T x) const
Definition: ct_utils.h:280
friend Mask< T > operator^(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:248
T select(T x, T y) const
Definition: ct_utils.h:288
void select_n(T output[], const T x[], const T y[], size_t len) const
Definition: ct_utils.h:313
static Mask< T > expand(Mask< U > m)
Definition: ct_utils.h:132
static Mask< T > expand(T v)
Definition: ct_utils.h:123
T unpoisoned_value() const
Definition: ct_utils.h:333
T if_set_return(T x) const
Definition: ct_utils.h:272
Mask< T > & operator=(const Mask< T > &other)=default
static Mask< T > set()
Definition: ct_utils.h:107
Mask(const Mask< T > &other)=default
Mask< T > & operator&=(Mask< T > o)
Definition: ct_utils.h:213
Mask(Mask< U > o)
Definition: ct_utils.h:99
T select_and_unpoison(T x, T y) const
Definition: ct_utils.h:294
Mask< T > operator~() const
Definition: ct_utils.h:264
static Mask< T > is_any_of(T v, std::initializer_list< T > accepted)
Definition: ct_utils.h:196
Mask< T > & operator|=(Mask< T > o)
Definition: ct_utils.h:231
static Mask< T > is_gte(T x, T y)
Definition: ct_utils.h:181
static Mask< T > is_lt(T x, T y)
Definition: ct_utils.h:157
static Mask< T > cleared()
Definition: ct_utils.h:115
static Mask< T > is_within_range(T v, T l, T u)
Definition: ct_utils.h:186
static Mask< T > is_lte(T x, T y)
Definition: ct_utils.h:173
friend Mask< T > operator&(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:240
fe T
Definition: ge.cpp:37
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:386
void conditional_swap(bool cnd, T &x, T &y)
Definition: ct_utils.h:375
secure_vector< uint8_t > copy_output(CT::Mask< uint8_t > bad_input, const uint8_t input[], size_t input_length, size_t offset)
Definition: ct_utils.cpp:13
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition: ct_utils.cpp:66
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:363
Definition: alg_id.cpp:13
T expand_top_bit(T a)
Definition: bit_ops.h:23
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65