Botan  2.1.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  r |= r >> i;
92  r &= 1;
93  r = ~(r - 1);
94  return r;
95  }
96 
97 template<typename T>
98 inline T select(T mask, T from0, T from1)
99  {
100  return (from0 & mask) | (from1 & ~mask);
101  }
102 
103 template<typename PredT, typename ValT>
104 inline ValT val_or_zero(PredT pred_val, ValT val)
105  {
106  return select(CT::expand_mask<ValT>(pred_val), val, static_cast<ValT>(0));
107  }
108 
109 template<typename T>
110 inline T is_zero(T x)
111  {
112  return ~expand_mask(x);
113  }
114 
115 template<typename T>
116 inline T is_equal(T x, T y)
117  {
118  return is_zero(x ^ y);
119  }
120 
121 template<typename T>
122 inline T is_less(T x, T y)
123  {
124  /*
125  This expands to a constant time sequence with GCC 5.2.0 on x86-64
126  but something more complicated may be needed for portable const time.
127  */
128  return expand_mask<T>(x < y);
129  }
130 
131 template<typename T>
132 inline T is_lte(T x, T y)
133  {
134  return expand_mask<T>(x <= y);
135  }
136 
137 template<typename T>
138 inline void conditional_copy_mem(T value,
139  T* to,
140  const T* from0,
141  const T* from1,
142  size_t elems)
143  {
144  const T mask = CT::expand_mask(value);
145 
146  for(size_t i = 0; i != elems; ++i)
147  {
148  to[i] = CT::select(mask, from0[i], from1[i]);
149  }
150  }
151 
152 template<typename T>
153 inline void cond_zero_mem(T cond,
154  T* array,
155  size_t elems)
156  {
157  const T mask = CT::expand_mask(cond);
158  const T zero(0);
159 
160  for(size_t i = 0; i != elems; ++i)
161  {
162  array[i] = CT::select(mask, zero, array[i]);
163  }
164  }
165 
166 template<typename T>
167 inline T expand_top_bit(T a)
168  {
169  return expand_mask<T>(a >> (sizeof(T)*8-1));
170  }
171 
172 template<typename T>
173 inline T max(T a, T b)
174  {
175  const T a_larger = b - a; // negative if a is larger
176  return select(expand_top_bit(a), a, b);
177  }
178 
179 template<typename T>
180 inline T min(T a, T b)
181  {
182  const T a_larger = b - a; // negative if a is larger
183  return select(expand_top_bit(b), b, a);
184  }
185 
186 inline secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length)
187  {
188  size_t leading_zeros = 0;
189 
190  uint8_t only_zeros = 0xFF;
191 
192  for(size_t i = 0; i != length; ++i)
193  {
194  only_zeros &= CT::is_zero(in[i]);
195  leading_zeros += CT::select<uint8_t>(only_zeros, 1, 0);
196  }
197 
198  return secure_vector<uint8_t>(in + leading_zeros, in + length);
199  }
200 
202  {
203  return strip_leading_zeros(in.data(), in.size());
204  }
205 
206 }
207 
208 }
209 
210 #endif
T expand_top_bit(T a)
Definition: ct_utils.h:167
void conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:138
T is_less(T x, T y)
Definition: ct_utils.h:122
T is_lte(T x, T y)
Definition: ct_utils.h:132
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
T is_equal(T x, T y)
Definition: ct_utils.h:116
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
void cond_zero_mem(T cond, T *array, size_t elems)
Definition: ct_utils.h:153
T expand_mask(T x)
Definition: ct_utils.h:86
#define BOTAN_UNUSED(v)
Definition: assert.h:92
T select(T mask, T from0, T from1)
Definition: ct_utils.h:98
Definition: alg_id.cpp:13
T max(T a, T b)
Definition: ct_utils.h:173
ValT val_or_zero(PredT pred_val, ValT val)
Definition: ct_utils.h:104
T is_zero(T x)
Definition: ct_utils.h:110
T min(T a, T b)
Definition: ct_utils.h:180
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition: ct_utils.h:186