Botan  2.6.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 Jack Lloyd
10 *
11 * Botan is released under the Simplified BSD License (see license.txt)
12 */
13 
14 #ifndef BOTAN_TIMING_ATTACK_CM_H_
15 #define BOTAN_TIMING_ATTACK_CM_H_
16 
17 #include <botan/secmem.h>
18 #include <vector>
19 
20 #if defined(BOTAN_HAS_VALGRIND)
21  #include <valgrind/memcheck.h>
22 #endif
23 
24 namespace Botan {
25 
26 namespace CT {
27 
28 /**
29 * Use valgrind to mark the contents of memory as being undefined.
30 * Valgrind will accept operations which manipulate undefined values,
31 * but will warn if an undefined value is used to decided a conditional
32 * jump or a load/store address. So if we poison all of our inputs we
33 * can confirm that the operations in question are truly const time
34 * when compiled by whatever compiler is in use.
35 *
36 * Even better, the VALGRIND_MAKE_MEM_* macros work even when the
37 * program is not run under valgrind (though with a few cycles of
38 * overhead, which is unfortunate in final binaries as these
39 * annotations tend to be used in fairly important loops).
40 *
41 * This approach was first used in ctgrind (https://github.com/agl/ctgrind)
42 * but calling the valgrind mecheck API directly works just as well and
43 * doesn't require a custom patched valgrind.
44 */
45 template<typename T>
46 inline void poison(const T* p, size_t n)
47  {
48 #if defined(BOTAN_HAS_VALGRIND)
49  VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T));
50 #else
51  BOTAN_UNUSED(p);
52  BOTAN_UNUSED(n);
53 #endif
54  }
55 
56 template<typename T>
57 inline void unpoison(const T* p, size_t n)
58  {
59 #if defined(BOTAN_HAS_VALGRIND)
60  VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T));
61 #else
62  BOTAN_UNUSED(p);
63  BOTAN_UNUSED(n);
64 #endif
65  }
66 
67 template<typename T>
68 inline 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 * T should be an unsigned machine integer type
79 * Expand to a mask used for other operations
80 * @param in an integer
81 * @return If n is zero, returns zero. Otherwise
82 * returns a T with all bits set for use as a mask with
83 * select.
84 */
85 template<typename T>
86 inline T expand_mask(T x)
87  {
88  T r = x;
89  // First fold r down to a single bit
90  for(size_t i = 1; i != sizeof(T)*8; i *= 2)
91  {
92  r = r | static_cast<T>(r >> i);
93  }
94  r &= 1;
95  r = static_cast<T>(~(r - 1));
96  return r;
97  }
98 
99 template<typename T>
100 inline T expand_top_bit(T a)
101  {
102  return expand_mask<T>(a >> (sizeof(T)*8-1));
103  }
104 
105 template<typename T>
106 inline T select(T mask, T from0, T from1)
107  {
108  return static_cast<T>((from0 & mask) | (from1 & ~mask));
109  }
110 
111 template<typename PredT, typename ValT>
112 inline ValT val_or_zero(PredT pred_val, ValT val)
113  {
114  return select(CT::expand_mask<ValT>(pred_val), val, static_cast<ValT>(0));
115  }
116 
117 template<typename T>
118 inline T is_zero(T x)
119  {
120  return static_cast<T>(~expand_mask(x));
121  }
122 
123 template<typename T>
124 inline T is_equal(T x, T y)
125  {
126  return is_zero<T>(x ^ y);
127  }
128 
129 template<typename T>
130 inline T is_less(T a, T b)
131  {
132  return expand_top_bit<T>(a ^ ((a^b) | ((a-b)^a)));
133  }
134 
135 template<typename T>
136 inline T is_lte(T a, T b)
137  {
138  return CT::is_less(a, b) | CT::is_equal(a, b);
139  }
140 
141 template<typename T>
142 inline void conditional_copy_mem(T value,
143  T* to,
144  const T* from0,
145  const T* from1,
146  size_t elems)
147  {
148  const T mask = CT::expand_mask(value);
149 
150  for(size_t i = 0; i != elems; ++i)
151  {
152  to[i] = CT::select(mask, from0[i], from1[i]);
153  }
154  }
155 
156 template<typename T>
157 inline void cond_zero_mem(T cond,
158  T* array,
159  size_t elems)
160  {
161  const T mask = CT::expand_mask(cond);
162  const T zero(0);
163 
164  for(size_t i = 0; i != elems; ++i)
165  {
166  array[i] = CT::select(mask, zero, array[i]);
167  }
168  }
169 
170 inline secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length)
171  {
172  size_t leading_zeros = 0;
173 
174  uint8_t only_zeros = 0xFF;
175 
176  for(size_t i = 0; i != length; ++i)
177  {
178  only_zeros = only_zeros & CT::is_zero<uint8_t>(in[i]);
179  leading_zeros += CT::select<uint8_t>(only_zeros, 1, 0);
180  }
181 
182  return secure_vector<uint8_t>(in + leading_zeros, in + length);
183  }
184 
186  {
187  return strip_leading_zeros(in.data(), in.size());
188  }
189 
190 }
191 
192 }
193 
194 #endif
T is_lte(T a, T b)
Definition: ct_utils.h:136
T expand_top_bit(T a)
Definition: ct_utils.h:100
void conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:142
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
T is_equal(T x, T y)
Definition: ct_utils.h:124
T is_less(T a, T b)
Definition: ct_utils.h:130
void cond_zero_mem(T cond, T *array, size_t elems)
Definition: ct_utils.h:157
T expand_mask(T x)
Definition: ct_utils.h:86
T select(T mask, T from0, T from1)
Definition: ct_utils.h:106
Definition: alg_id.cpp:13
#define BOTAN_UNUSED(...)
Definition: assert.h:117
ValT val_or_zero(PredT pred_val, ValT val)
Definition: ct_utils.h:112
T is_zero(T x)
Definition: ct_utils.h:118
fe T
Definition: ge.cpp:37
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition: ct_utils.h:170