Botan 2.1.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 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
201 inline secure_vector<uint8_t> strip_leading_zeros(const secure_vector<uint8_t>& in)
202 {
203 return strip_leading_zeros(in.data(), in.size());
204 }
205
206 }
207
208 }
209
210 #endif
Botan::CT::expand_top_bit
T expand_top_bit(T a)
Definition: ct_utils.h:167
Botan::CT::conditional_copy_mem
void conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:138
Botan::CT::is_less
T is_less(T x, T y)
Definition: ct_utils.h:122
Botan::CT::is_lte
T is_lte(T x, T y)
Definition: ct_utils.h:132
Botan::CT::poison
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
Botan::CT::is_equal
T is_equal(T x, T y)
Definition: ct_utils.h:116
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
Botan::CT::cond_zero_mem
void cond_zero_mem(T cond, T *array, size_t elems)
Definition: ct_utils.h:153
Botan::CT::expand_mask
T expand_mask(T x)
Definition: ct_utils.h:86
BOTAN_UNUSED
#define BOTAN_UNUSED(v)
Definition: assert.h:92
Botan::CT::select
T select(T mask, T from0, T from1)
Definition: ct_utils.h:98
Botan
Definition: alg_id.cpp:13
Botan::CT::max
T max(T a, T b)
Definition: ct_utils.h:173
Botan::CT::val_or_zero
ValT val_or_zero(PredT pred_val, ValT val)
Definition: ct_utils.h:104
Botan::CT::is_zero
T is_zero(T x)
Definition: ct_utils.h:110
Botan::CT::min
T min(T a, T b)
Definition: ct_utils.h:180
Botan::CT::unpoison
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
Botan::CT::strip_leading_zeros
secure_vector< uint8_t > strip_leading_zeros(const uint8_t in[], size_t length)
Definition: ct_utils.h:186