Botan  2.10.0
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  /**
187  * AND-combine two masks
188  */
190  {
191  m_mask &= o.value();
192  return (*this);
193  }
194 
195  /**
196  * XOR-combine two masks
197  */
199  {
200  m_mask ^= o.value();
201  return (*this);
202  }
203 
204  /**
205  * OR-combine two masks
206  */
208  {
209  m_mask |= o.value();
210  return (*this);
211  }
212 
213  /**
214  * AND-combine two masks
215  */
217  {
218  return Mask<T>(x.value() & y.value());
219  }
220 
221  /**
222  * XOR-combine two masks
223  */
225  {
226  return Mask<T>(x.value() ^ y.value());
227  }
228 
229  /**
230  * OR-combine two masks
231  */
233  {
234  return Mask<T>(x.value() | y.value());
235  }
236 
237  /**
238  * Negate this mask
239  */
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  */
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  */
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  */
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>
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 */
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 
386  {
387  return strip_leading_zeros(in.data(), in.size());
388  }
389 
390 }
391 
392 }
393 
394 #endif
static Mask< T > cleared()
Definition: ct_utils.h:115
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:362
friend Mask< T > operator^(Mask< T > x, Mask< T > y)
Definition: ct_utils.h:224
void select_n(T output[], const T x[], const T y[], size_t len) const
Definition: ct_utils.h:289
Mask(const Mask< T > &other)=default
T value() const
Definition: ct_utils.h:327
bool is_set() const
Definition: ct_utils.h:319
Mask< T > select_mask(Mask< T > x, Mask< T > y) const
Definition: ct_utils.h:280
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:65
Mask< T > & operator &=(Mask< T > o)
Definition: ct_utils.h:189
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:216
static Mask< T > expand(T v)
Definition: ct_utils.h:123
T select(T x, T y) const
Definition: ct_utils.h:264
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:339
#define BOTAN_UNUSED(...)
Definition: assert.h:142
T if_not_set_return(T x) const
Definition: ct_utils.h:256
Mask< T > operator~() const
Definition: ct_utils.h:240
T if_set_return(T x) const
Definition: ct_utils.h:248
Mask< T > & operator|=(Mask< T > o)
Definition: ct_utils.h:207
T select_and_unpoison(T x, T y) const
Definition: ct_utils.h:270
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:232
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
Mask< T > & operator^=(Mask< T > o)
Definition: ct_utils.h:198
void if_set_zero_out(T buf[], size_t elems)
Definition: ct_utils.h:298
T unpoisoned_value() const
Definition: ct_utils.h:309
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:351