Botan  2.18.2
Crypto and TLS for C++11
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>
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  */
272  T if_set_return(T x) const
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 
294  T select_and_unpoison(T x, T y) const
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 
362 template<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 
374 template<typename T>
375 inline 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 
385 template<typename T>
386 inline 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 
407 secure_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
static Mask< T > cleared()
Definition: ct_utils.h:115
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:386
friend Mask< T > operator^(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:248
void select_n(T output[], const T x[], const T y[], size_t len) const
Definition: ct_utils.h:313
Mask(const Mask< T > &other)=default
T value() const
Definition: ct_utils.h:351
static Mask< T > is_within_range(T v, T l, T u)
Definition: ct_utils.h:186
bool is_set() const
Definition: ct_utils.h:343
Mask< T > select_mask(Mask< T > x, Mask< T > y) const
Definition: ct_utils.h:304
static Mask< T > is_gte(T x, T y)
Definition: ct_utils.h:181
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition: ct_utils.cpp:66
Mask< T > & operator &=(Mask< T > o)
Definition: ct_utils.h:213
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
static Mask< T > expand(T v)
Definition: ct_utils.h:123
T expand_top_bit(T a)
Definition: bit_ops.h:23
T select(T x, T y) const
Definition: ct_utils.h:288
static Mask< T > expand(Mask< U > m)
Definition: ct_utils.h:132
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
Definition: alg_id.cpp:13
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:363
#define BOTAN_UNUSED(...)
Definition: assert.h:142
T if_not_set_return(T x) const
Definition: ct_utils.h:280
static Mask< T > is_any_of(T v, std::initializer_list< T > accepted)
Definition: ct_utils.h:196
Mask< T > operator~() const
Definition: ct_utils.h:264
T if_set_return(T x) const
Definition: ct_utils.h:272
Mask< T > & operator|=(Mask< T > o)
Definition: ct_utils.h:231
T select_and_unpoison(T x, T y) const
Definition: ct_utils.h:294
fe T
Definition: ge.cpp:37
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
Mask< T > & operator=(const Mask< T > &other)=default
friend Mask< T > operator|(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:256
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
Mask< T > & operator^=(Mask< T > o)
Definition: ct_utils.h:222
void if_set_zero_out(T buf[], size_t elems)
Definition: ct_utils.h:322
T unpoisoned_value() const
Definition: ct_utils.h:333
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
Mask(Mask< U > o)
Definition: ct_utils.h:99
static Mask< T > is_gt(T x, T y)
Definition: ct_utils.h:165
static Mask< T > is_lt(T x, T y)
Definition: ct_utils.h:157
void conditional_swap(bool cnd, T &x, T &y)
Definition: ct_utils.h:375