/src/botan/build/include/botan/internal/ct_utils.h
Line | Count | Source (jump to first uncovered line) |
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 | | #if defined(BOTAN_HAS_VALGRIND) |
50 | | VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T)); |
51 | | #else |
52 | | BOTAN_UNUSED(p, n); |
53 | | #endif |
54 | | } |
55 | | |
56 | | template <typename T> |
57 | | inline void unpoison(const T* p, size_t n) { |
58 | | #if defined(BOTAN_HAS_VALGRIND) |
59 | | VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T)); |
60 | | #else |
61 | | BOTAN_UNUSED(p, n); |
62 | | #endif |
63 | | } |
64 | | |
65 | | template <typename T> |
66 | 771k | inline void unpoison(T& p) { |
67 | | #if defined(BOTAN_HAS_VALGRIND) |
68 | | VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T)); |
69 | | #else |
70 | 771k | BOTAN_UNUSED(p); |
71 | 771k | #endif |
72 | 771k | } void Botan::CT::unpoison<unsigned long>(unsigned long&) Line | Count | Source | 66 | 762k | inline void unpoison(T& p) { | 67 | | #if defined(BOTAN_HAS_VALGRIND) | 68 | | VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T)); | 69 | | #else | 70 | 762k | BOTAN_UNUSED(p); | 71 | 762k | #endif | 72 | 762k | } |
void Botan::CT::unpoison<unsigned long const>(unsigned long const&) Line | Count | Source | 66 | 9.23k | inline void unpoison(T& p) { | 67 | | #if defined(BOTAN_HAS_VALGRIND) | 68 | | VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T)); | 69 | | #else | 70 | 9.23k | BOTAN_UNUSED(p); | 71 | 9.23k | #endif | 72 | 9.23k | } |
|
73 | | |
74 | | /** |
75 | | * A Mask type used for constant-time operations. A Mask<T> always has value |
76 | | * either 0 (all bits cleared) or ~0 (all bits set). All operations in a Mask<T> |
77 | | * are intended to compile to code which does not contain conditional jumps. |
78 | | * This must be verified with tooling (eg binary disassembly or using valgrind) |
79 | | * since you never know what a compiler might do. |
80 | | */ |
81 | | template <typename T> |
82 | | requires std::is_unsigned<T>::value |
83 | | class Mask final { |
84 | | public: |
85 | | Mask(const Mask<T>& other) = default; |
86 | | Mask<T>& operator=(const Mask<T>& other) = default; |
87 | | |
88 | | /** |
89 | | * Derive a Mask from a Mask of a larger type |
90 | | */ |
91 | | template <typename U> |
92 | | Mask(Mask<U> o) : m_mask(static_cast<T>(o.value())) { |
93 | | static_assert(sizeof(U) > sizeof(T), "sizes ok"); |
94 | | } |
95 | | |
96 | | /** |
97 | | * Return a Mask<T> with all bits set |
98 | | */ |
99 | | static Mask<T> set() { return Mask<T>(static_cast<T>(~0)); } |
100 | | |
101 | | /** |
102 | | * Return a Mask<T> with all bits cleared |
103 | | */ |
104 | | static Mask<T> cleared() { return Mask<T>(0); } |
105 | | |
106 | | /** |
107 | | * Return a Mask<T> which is set if v is != 0 |
108 | | */ |
109 | 1.31M | static Mask<T> expand(T v) { return ~Mask<T>::is_zero(v); } Botan::CT::Mask<unsigned long>::expand(unsigned long) Line | Count | Source | 109 | 1.30M | static Mask<T> expand(T v) { return ~Mask<T>::is_zero(v); } |
Botan::CT::Mask<unsigned char>::expand(unsigned char) Line | Count | Source | 109 | 5.83k | static Mask<T> expand(T v) { return ~Mask<T>::is_zero(v); } |
|
110 | | |
111 | | /** |
112 | | * Return a Mask<T> which is set if m is set |
113 | | */ |
114 | | template <typename U> |
115 | | static Mask<T> expand(Mask<U> m) { |
116 | | static_assert(sizeof(U) < sizeof(T), "sizes ok"); |
117 | | return ~Mask<T>::is_zero(m.value()); |
118 | | } |
119 | | |
120 | | /** |
121 | | * Return a Mask<T> which is set if v is == 0 or cleared otherwise |
122 | | */ |
123 | 1.69M | static Mask<T> is_zero(T x) { return Mask<T>(ct_is_zero<T>(x)); } Botan::CT::Mask<unsigned long>::is_zero(unsigned long) Line | Count | Source | 123 | 1.68M | static Mask<T> is_zero(T x) { return Mask<T>(ct_is_zero<T>(x)); } |
Botan::CT::Mask<unsigned char>::is_zero(unsigned char) Line | Count | Source | 123 | 5.83k | static Mask<T> is_zero(T x) { return Mask<T>(ct_is_zero<T>(x)); } |
|
124 | | |
125 | | /** |
126 | | * Return a Mask<T> which is set if x == y |
127 | | */ |
128 | 371k | static Mask<T> is_equal(T x, T y) { return Mask<T>::is_zero(static_cast<T>(x ^ y)); } |
129 | | |
130 | | /** |
131 | | * Return a Mask<T> which is set if x < y |
132 | | */ |
133 | 964k | static Mask<T> is_lt(T x, T y) { return Mask<T>(expand_top_bit<T>(x ^ ((x ^ y) | ((x - y) ^ x)))); } Botan::CT::Mask<unsigned long>::is_lt(unsigned long, unsigned long) Line | Count | Source | 133 | 964k | static Mask<T> is_lt(T x, T y) { return Mask<T>(expand_top_bit<T>(x ^ ((x ^ y) | ((x - y) ^ x)))); } |
Unexecuted instantiation: Botan::CT::Mask<unsigned char>::is_lt(unsigned char, unsigned char) |
134 | | |
135 | | /** |
136 | | * Return a Mask<T> which is set if x > y |
137 | | */ |
138 | | static Mask<T> is_gt(T x, T y) { return Mask<T>::is_lt(y, x); } |
139 | | |
140 | | /** |
141 | | * Return a Mask<T> which is set if x <= y |
142 | | */ |
143 | | static Mask<T> is_lte(T x, T y) { return ~Mask<T>::is_gt(x, y); } |
144 | | |
145 | | /** |
146 | | * Return a Mask<T> which is set if x >= y |
147 | | */ |
148 | 608k | static Mask<T> is_gte(T x, T y) { return ~Mask<T>::is_lt(x, y); } |
149 | | |
150 | 0 | static Mask<T> is_within_range(T v, T l, T u) { |
151 | | //return Mask<T>::is_gte(v, l) & Mask<T>::is_lte(v, u); |
152 | |
|
153 | 0 | const T v_lt_l = v ^ ((v ^ l) | ((v - l) ^ v)); |
154 | 0 | const T v_gt_u = u ^ ((u ^ v) | ((u - v) ^ u)); |
155 | 0 | const T either = v_lt_l | v_gt_u; |
156 | 0 | return ~Mask<T>(expand_top_bit(either)); |
157 | 0 | } |
158 | | |
159 | 0 | static Mask<T> is_any_of(T v, std::initializer_list<T> accepted) { |
160 | 0 | T accept = 0; |
161 | |
|
162 | 0 | for(auto a : accepted) { |
163 | 0 | const T diff = a ^ v; |
164 | 0 | const T eq_zero = ~diff & (diff - 1); |
165 | 0 | accept |= eq_zero; |
166 | 0 | } |
167 | |
|
168 | 0 | return Mask<T>(expand_top_bit(accept)); |
169 | 0 | } |
170 | | |
171 | | /** |
172 | | * AND-combine two masks |
173 | | */ |
174 | 0 | Mask<T>& operator&=(Mask<T> o) { |
175 | 0 | m_mask &= o.value(); |
176 | 0 | return (*this); |
177 | 0 | } |
178 | | |
179 | | /** |
180 | | * XOR-combine two masks |
181 | | */ |
182 | | Mask<T>& operator^=(Mask<T> o) { |
183 | | m_mask ^= o.value(); |
184 | | return (*this); |
185 | | } |
186 | | |
187 | | /** |
188 | | * OR-combine two masks |
189 | | */ |
190 | 592 | Mask<T>& operator|=(Mask<T> o) { |
191 | 592 | m_mask |= o.value(); |
192 | 592 | return (*this); |
193 | 592 | } |
194 | | |
195 | | /** |
196 | | * AND-combine two masks |
197 | | */ |
198 | | friend Mask<T> operator&(Mask<T> x, Mask<T> y) { return Mask<T>(x.value() & y.value()); } |
199 | | |
200 | | /** |
201 | | * XOR-combine two masks |
202 | | */ |
203 | 5 | friend Mask<T> operator^(Mask<T> x, Mask<T> y) { return Mask<T>(x.value() ^ y.value()); } |
204 | | |
205 | | /** |
206 | | * OR-combine two masks |
207 | | */ |
208 | 608k | friend Mask<T> operator|(Mask<T> x, Mask<T> y) { return Mask<T>(x.value() | y.value()); } |
209 | | |
210 | | /** |
211 | | * Negate this mask |
212 | | */ |
213 | 1.92M | Mask<T> operator~() const { return Mask<T>(~value()); } Botan::CT::Mask<unsigned long>::operator~() const Line | Count | Source | 213 | 1.91M | Mask<T> operator~() const { return Mask<T>(~value()); } |
Botan::CT::Mask<unsigned char>::operator~() const Line | Count | Source | 213 | 5.83k | Mask<T> operator~() const { return Mask<T>(~value()); } |
|
214 | | |
215 | | /** |
216 | | * Return x if the mask is set, or otherwise zero |
217 | | */ |
218 | 722k | T if_set_return(T x) const { return m_mask & x; } |
219 | | |
220 | | /** |
221 | | * Return x if the mask is cleared, or otherwise zero |
222 | | */ |
223 | | T if_not_set_return(T x) const { return ~m_mask & x; } |
224 | | |
225 | | /** |
226 | | * If this mask is set, return x, otherwise return y |
227 | | */ |
228 | 31.3M | T select(T x, T y) const { return choose(value(), x, y); } Botan::CT::Mask<unsigned long>::select(unsigned long, unsigned long) const Line | Count | Source | 228 | 31.3M | T select(T x, T y) const { return choose(value(), x, y); } |
Botan::CT::Mask<unsigned char>::select(unsigned char, unsigned char) const Line | Count | Source | 228 | 5.83k | T select(T x, T y) const { return choose(value(), x, y); } |
|
229 | | |
230 | | T select_and_unpoison(T x, T y) const { |
231 | | T r = this->select(x, y); |
232 | | CT::unpoison(r); |
233 | | return r; |
234 | | } |
235 | | |
236 | | /** |
237 | | * If this mask is set, return x, otherwise return y |
238 | | */ |
239 | 96.4k | Mask<T> select_mask(Mask<T> x, Mask<T> y) const { return Mask<T>(select(x.value(), y.value())); } |
240 | | |
241 | | /** |
242 | | * Conditionally set output to x or y, depending on if mask is set or |
243 | | * cleared (resp) |
244 | | */ |
245 | 10 | void select_n(T output[], const T x[], const T y[], size_t len) const { |
246 | 182 | for(size_t i = 0; i != len; ++i) |
247 | 172 | output[i] = this->select(x[i], y[i]); |
248 | 10 | } |
249 | | |
250 | | /** |
251 | | * If this mask is set, zero out buf, otherwise do nothing |
252 | | */ |
253 | | void if_set_zero_out(T buf[], size_t elems) { |
254 | | for(size_t i = 0; i != elems; ++i) { |
255 | | buf[i] = this->if_not_set_return(buf[i]); |
256 | | } |
257 | | } |
258 | | |
259 | | /** |
260 | | * Return the value of the mask, unpoisoned |
261 | | */ |
262 | 646k | T unpoisoned_value() const { |
263 | 646k | T r = value(); |
264 | 646k | CT::unpoison(r); |
265 | 646k | return r; |
266 | 646k | } |
267 | | |
268 | | /** |
269 | | * Return true iff this mask is set |
270 | | */ |
271 | 646k | bool is_set() const { return unpoisoned_value() != 0; } |
272 | | |
273 | | /** |
274 | | * Return the underlying value of the mask |
275 | | */ |
276 | 35.3M | T value() const { return m_mask; } Botan::CT::Mask<unsigned long>::value() const Line | Count | Source | 276 | 35.3M | T value() const { return m_mask; } |
Botan::CT::Mask<unsigned char>::value() const Line | Count | Source | 276 | 11.6k | T value() const { return m_mask; } |
|
277 | | |
278 | | private: |
279 | 5.28M | Mask(T m) : m_mask(m) {} Botan::CT::Mask<unsigned long>::Mask(unsigned long) Line | Count | Source | 279 | 5.27M | Mask(T m) : m_mask(m) {} |
Botan::CT::Mask<unsigned char>::Mask(unsigned char) Line | Count | Source | 279 | 11.6k | Mask(T m) : m_mask(m) {} |
|
280 | | |
281 | | T m_mask; |
282 | | }; |
283 | | |
284 | | template <typename T> |
285 | 10 | inline Mask<T> conditional_copy_mem(T cnd, T* to, const T* from0, const T* from1, size_t elems) { |
286 | 10 | const auto mask = CT::Mask<T>::expand(cnd); |
287 | 10 | mask.select_n(to, from0, from1, elems); |
288 | 10 | return mask; |
289 | 10 | } |
290 | | |
291 | | template <typename T> |
292 | | inline Mask<T> conditional_assign_mem(T cnd, T* sink, const T* src, size_t elems) { |
293 | | const auto mask = CT::Mask<T>::expand(cnd); |
294 | | mask.select_n(sink, src, sink, elems); |
295 | | return mask; |
296 | | } |
297 | | |
298 | | template <typename T> |
299 | 0 | inline void conditional_swap(bool cnd, T& x, T& y) { |
300 | 0 | const auto swap = CT::Mask<T>::expand(cnd); |
301 | |
|
302 | 0 | T t0 = swap.select(y, x); |
303 | 0 | T t1 = swap.select(x, y); |
304 | 0 | x = t0; |
305 | 0 | y = t1; |
306 | 0 | } |
307 | | |
308 | | template <typename T> |
309 | 0 | inline void conditional_swap_ptr(bool cnd, T& x, T& y) { |
310 | 0 | uintptr_t xp = reinterpret_cast<uintptr_t>(x); |
311 | 0 | uintptr_t yp = reinterpret_cast<uintptr_t>(y); |
312 | |
|
313 | 0 | conditional_swap<uintptr_t>(cnd, xp, yp); |
314 | |
|
315 | 0 | x = reinterpret_cast<T>(xp); |
316 | 0 | y = reinterpret_cast<T>(yp); |
317 | 0 | } |
318 | | |
319 | | template <typename T> |
320 | | inline CT::Mask<T> all_zeros(const T elem[], size_t len) { |
321 | | T sum = 0; |
322 | | for(size_t i = 0; i != len; ++i) |
323 | | sum |= elem[i]; |
324 | | return CT::Mask<T>::is_zero(sum); |
325 | | } |
326 | | |
327 | | /** |
328 | | * If bad_input is unset, return input[offset:input_length] copied to new |
329 | | * buffer. If bad_input is set, return an empty vector. In all cases, the capacity |
330 | | * of the vector is equal to input_length |
331 | | * |
332 | | * This function attempts to avoid leaking the following: |
333 | | * - if bad_input was set or not |
334 | | * - the value of offset |
335 | | * - the values in input[] |
336 | | * |
337 | | * This function leaks the value of input_length |
338 | | */ |
339 | | BOTAN_TEST_API |
340 | | secure_vector<uint8_t> copy_output(CT::Mask<uint8_t> bad_input, |
341 | | const uint8_t input[], |
342 | | size_t input_length, |
343 | | size_t offset); |
344 | | |
345 | | secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length); |
346 | | |
347 | 0 | inline secure_vector<uint8_t> strip_leading_zeros(const secure_vector<uint8_t>& in) { |
348 | 0 | return strip_leading_zeros(in.data(), in.size()); |
349 | 0 | } |
350 | | |
351 | | } // namespace CT |
352 | | |
353 | | } // namespace Botan |
354 | | |
355 | | #endif |