Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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
26 namespace Botan {
27
28 namespace 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 */
47 template<typename T>
48 inline 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
58 template<typename T>
59 inline 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
69 template<typename T>
70 inline 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 */
86 template<typename T>
87 class 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 */
115 static Mask<T> cleared()
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>
132 static Mask<T> expand(Mask<U> m)
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 /**
187 * AND-combine two masks
188 */
189 Mask<T>& operator&=(Mask<T> o)
190 {
191 m_mask &= o.value();
192 return (*this);
193 }
194
195 /**
196 * XOR-combine two masks
197 */
198 Mask<T>& operator^=(Mask<T> o)
199 {
200 m_mask ^= o.value();
201 return (*this);
202 }
203
204 /**
205 * OR-combine two masks
206 */
207 Mask<T>& operator|=(Mask<T> o)
208 {
209 m_mask |= o.value();
210 return (*this);
211 }
212
213 /**
214 * AND-combine two masks
215 */
216 friend Mask<T> operator&(Mask<T> x, Mask<T> y)
217 {
218 return Mask<T>(x.value() & y.value());
219 }
220
221 /**
222 * XOR-combine two masks
223 */
224 friend Mask<T> operator^(Mask<T> x, Mask<T> y)
225 {
226 return Mask<T>(x.value() ^ y.value());
227 }
228
229 /**
230 * OR-combine two masks
231 */
232 friend Mask<T> operator|(Mask<T> x, Mask<T> y)
233 {
234 return Mask<T>(x.value() | y.value());
235 }
236
237 /**
238 * Negate this mask
239 */
240 Mask<T> operator~() const
241 {
242 return Mask<T>(~value());
243 }
244
245 /**
246 * Return x if the mask is set, or otherwise zero
247 */
248 T if_set_return(T x) const
249 {
250 return m_mask & x;
251 }
252
253 /**
254 * Return x if the mask is cleared, or otherwise zero
255 */
256 T if_not_set_return(T x) const
257 {
258 return ~m_mask & x;
259 }
260
261 /**
262 * If this mask is set, return x, otherwise return y
263 */
264 T select(T x, T y) const
265 {
266 // (x & value()) | (y & ~value())
267 return static_cast<T>(y ^ (value() & (x ^ y)));
268 }
269
270 T select_and_unpoison(T x, T y) const
271 {
272 T r = this->select(x, y);
273 CT::unpoison(r);
274 return r;
275 }
276
277 /**
278 * If this mask is set, return x, otherwise return y
279 */
280 Mask<T> select_mask(Mask<T> x, Mask<T> y) const
281 {
282 return Mask<T>(select(x.value(), y.value()));
283 }
284
285 /**
286 * Conditionally set output to x or y, depending on if mask is set or
287 * cleared (resp)
288 */
289 void select_n(T output[], const T x[], const T y[], size_t len) const
290 {
291 for(size_t i = 0; i != len; ++i)
292 output[i] = this->select(x[i], y[i]);
293 }
294
295 /**
296 * If this mask is set, zero out buf, otherwise do nothing
297 */
298 void if_set_zero_out(T buf[], size_t elems)
299 {
300 for(size_t i = 0; i != elems; ++i)
301 {
302 buf[i] = this->if_not_set_return(buf[i]);
303 }
304 }
305
306 /**
307 * Return the value of the mask, unpoisoned
308 */
309 T unpoisoned_value() const
310 {
311 T r = value();
312 CT::unpoison(r);
313 return r;
314 }
315
316 /**
317 * Return true iff this mask is set
318 */
319 bool is_set() const
320 {
321 return unpoisoned_value() != 0;
322 }
323
324 /**
325 * Return the underlying value of the mask
326 */
327 T value() const
328 {
329 return m_mask;
330 }
331
332 private:
333 Mask(T m) : m_mask(m) {}
334
335 T m_mask;
336 };
337
338 template<typename T>
339 inline Mask<T> conditional_copy_mem(T cnd,
340 T* to,
341 const T* from0,
342 const T* from1,
343 size_t elems)
344 {
345 const auto mask = CT::Mask<T>::expand(cnd);
346 mask.select_n(to, from0, from1, elems);
347 return mask;
348 }
349
350 template<typename T>
351 inline void conditional_swap(bool cnd, T& x, T& y)
352 {
353 const auto swap = CT::Mask<T>::expand(cnd);
354
355 T t0 = swap.select(y, x);
356 T t1 = swap.select(x, y);
357 x = t0;
358 y = t1;
359 }
360
361 template<typename T>
362 inline void conditional_swap_ptr(bool cnd, T& x, T& y)
363 {
364 uintptr_t xp = reinterpret_cast<uintptr_t>(x);
365 uintptr_t yp = reinterpret_cast<uintptr_t>(y);
366
367 conditional_swap<uintptr_t>(cnd, xp, yp);
368
369 x = reinterpret_cast<T>(xp);
370 y = reinterpret_cast<T>(yp);
371 }
372
373 /**
374 * If bad_mask is unset, return in[delim_idx:input_length] copied to
375 * new buffer. If bad_mask is set, return an all zero vector of
376 * unspecified length.
377 */
378 secure_vector<uint8_t> copy_output(CT::Mask<uint8_t> bad_input,
379 const uint8_t input[],
380 size_t input_length,
381 size_t delim_idx);
382
383 secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length);
384
385 inline secure_vector<uint8_t> strip_leading_zeros(const secure_vector<uint8_t>& in)
386 {
387 return strip_leading_zeros(in.data(), in.size());
388 }
389
390 }
391
392 }
393
394 #endif
Botan::CT::Mask::cleared
static Mask< T > cleared()
Definition: ct_utils.h:115
Botan::CT::conditional_swap_ptr
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:362
Botan::CT::Mask::operator^
friend Mask< T > operator^(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:224
Botan::CT::Mask::Mask
Mask(const Mask< T > &other)=default
Botan::CT::Mask::operator~
Mask< T > operator~() const
Definition: ct_utils.h:240
Botan::CT::Mask::select_n
void select_n(T output[], const T x[], const T y[], size_t len) const
Definition: ct_utils.h:289
Botan::CT::Mask
Definition: ct_utils.h:87
Botan::CT::Mask::is_gte
static Mask< T > is_gte(T x, T y)
Definition: ct_utils.h:181
Botan::CT::poison
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
Botan::CT::Mask::if_not_set_return
T if_not_set_return(T x) const
Definition: ct_utils.h:256
Botan::CT::Mask::if_set_return
T if_set_return(T x) const
Definition: ct_utils.h:248
Botan::CT::strip_leading_zeros
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition: ct_utils.cpp:65
Botan::CT::Mask::select
T select(T x, T y) const
Definition: ct_utils.h:264
Botan::CT::Mask::select_mask
Mask< T > select_mask(Mask< T > x, Mask< T > y) const
Definition: ct_utils.h:280
Botan::CT::Mask::is_lte
static Mask< T > is_lte(T x, T y)
Definition: ct_utils.h:173
Botan::CT::Mask::expand
static Mask< T > expand(T v)
Definition: ct_utils.h:123
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
Botan::CT::Mask::operator&
friend Mask< T > operator&(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:216
Botan::CT::Mask::expand
static Mask< T > expand(Mask< U > m)
Definition: ct_utils.h:132
Botan::CT::copy_output
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
Botan
Definition: alg_id.cpp:13
Botan::CT::conditional_copy_mem
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:339
BOTAN_UNUSED
#define BOTAN_UNUSED(...)
Definition: assert.h:142
Botan::CT::Mask::select_and_unpoison
T select_and_unpoison(T x, T y) const
Definition: ct_utils.h:270
Botan::CT::Mask::value
T value() const
Definition: ct_utils.h:327
Botan::CT::Mask::operator|=
Mask< T > & operator|=(Mask< T > o)
Definition: ct_utils.h:207
Botan::CT::Mask::is_set
bool is_set() const
Definition: ct_utils.h:319
T
fe T
Definition: ge.cpp:37
Botan::CT::unpoison
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
Botan::CT::Mask::set
static Mask< T > set()
Definition: ct_utils.h:107
Botan::CT::Mask::operator=
Mask< T > & operator=(const Mask< T > &other)=default
Botan::CT::Mask::unpoisoned_value
T unpoisoned_value() const
Definition: ct_utils.h:309
Botan::CT::Mask::operator|
friend Mask< T > operator|(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:232
Botan::CT::Mask::operator^=
Mask< T > & operator^=(Mask< T > o)
Definition: ct_utils.h:198
Botan::CT::Mask::if_set_zero_out
void if_set_zero_out(T buf[], size_t elems)
Definition: ct_utils.h:298
Botan::CT::Mask::is_zero
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
Botan::CT::Mask::is_equal
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
Botan::CT::Mask::operator&=
Mask< T > & operator&=(Mask< T > o)
Definition: ct_utils.h:189
Botan::CT::Mask::Mask
Mask(Mask< U > o)
Definition: ct_utils.h:99
Botan::CT::Mask::is_gt
static Mask< T > is_gt(T x, T y)
Definition: ct_utils.h:165
Botan::CT::Mask::is_lt
static Mask< T > is_lt(T x, T y)
Definition: ct_utils.h:157
Botan::CT::conditional_swap
void conditional_swap(bool cnd, T &x, T &y)
Definition: ct_utils.h:351