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