Direct-BT v3.3.0-1-gc2d430c
Direct-BT - Direct Bluetooth Programming.
ct_utils.hpp
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 * (C) 2024 Sven Gothel
11 *
12 * jaulib including this code is released under the MIT License (see COPYING)
13 * Botan itself is released under the Simplified BSD License (see COPYING)
14 */
15
16#ifndef JAU_CT_UTILS_HPP_
17#define JAU_CT_UTILS_HPP_
18
19#include <type_traits>
20#include <jau/int_math.hpp>
21
22#if defined(JAU_HAS_VALGRIND)
23 #include <valgrind/memcheck.h>
24#endif
25
26namespace jau::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*/
45template<typename T>
46inline void poison([[maybe_unused]] const T* p, [[maybe_unused]] size_t n)
47 {
48#if defined(JAU_HAS_VALGRIND)
49 VALGRIND_MAKE_MEM_UNDEFINED(p, n * sizeof(T));
50#endif
51 }
52
53template<typename T>
54inline void unpoison([[maybe_unused]] const T* p, [[maybe_unused]] size_t n)
55 {
56#if defined(JAU_HAS_VALGRIND)
57 VALGRIND_MAKE_MEM_DEFINED(p, n * sizeof(T));
58#endif
59 }
60
61template<typename T>
62inline void unpoison([[maybe_unused]] T& p)
63 {
64#if defined(JAU_HAS_VALGRIND)
65 VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
66#endif
67 }
68
69/**
70* A Mask type used for constant-time operations. A Mask<T> always has value
71* either 0 (all bits cleared) or ~0 (all bits set). All operations in a Mask<T>
72* are intended to compile to code which does not contain conditional jumps.
73* This must be verified with tooling (eg binary disassembly or using valgrind)
74* since you never know what a compiler might do.
75*
76 * @tparam T unsigned integral type
77 */
78template <typename T,
79 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T>, bool> = true>
80class Mask
81 {
82 public:
83 Mask(const Mask<T>& other) noexcept
84 : m_mask(other.m_mask) { }
85
86 Mask<T>& operator=(const Mask<T>& other) noexcept {
87 m_mask = other.m_mask;
88 return *this;
89 }
90
91 /**
92 * Derive a Mask from a Mask of a larger type
93 */
94 template<typename U>
95 Mask(Mask<U> o) noexcept : m_mask(static_cast<T>(o.value()))
96 {
97 static_assert(sizeof(U) > sizeof(T), "sizes ok");
98 }
99
100 /**
101 * Return a Mask<T> with all bits set
102 */
103 static Mask<T> set() noexcept
104 {
105 return Mask<T>(static_cast<T>(~0));
106 }
107
108 /**
109 * Return a Mask<T> with all bits cleared
110 */
111 static Mask<T> cleared() noexcept
112 {
113 return Mask<T>(0);
114 }
115
116 /**
117 * Return a Mask<T> which is set if v is != 0
118 */
119 static Mask<T> expand(T v) noexcept
120 {
121 return ~Mask<T>::is_zero(v);
122 }
123
124 /**
125 * Return a Mask<T> which is set if m is set
126 */
127 template<typename U>
128 static Mask<T> expand(Mask<U> m) noexcept
129 {
130 static_assert(sizeof(U) < sizeof(T), "sizes ok");
131 return ~Mask<T>::is_zero(m.value());
132 }
133
134 /**
135 * Return a Mask<T> which is set if v is == 0 or cleared otherwise
136 */
137 static Mask<T> is_zero(T x) noexcept
138 {
139 return Mask<T>(ct_is_zero<T>(x));
140 }
141
142 /**
143 * Return a Mask<T> which is set if x == y
144 */
145 static Mask<T> is_equal(T x, T y) noexcept
146 {
147 return Mask<T>::is_zero(static_cast<T>(x ^ y));
148 }
149
150 /**
151 * Return a Mask<T> which is set if x < y
152 */
153 static Mask<T> is_lt(T x, T y) noexcept
154 {
155 return Mask<T>(ct_expand_top_bit<T>(x^((x^y) | ((x-y)^x))));
156 }
157
158 /**
159 * Return a Mask<T> which is set if x > y
160 */
161 static Mask<T> is_gt(T x, T y) noexcept
162 {
163 return Mask<T>::is_lt(y, x);
164 }
165
166 /**
167 * Return a Mask<T> which is set if x <= y
168 */
169 static Mask<T> is_lte(T x, T y) noexcept
170 {
171 return ~Mask<T>::is_gt(x, y);
172 }
173
174 /**
175 * Return a Mask<T> which is set if x >= y
176 */
177 static Mask<T> is_gte(T x, T y) noexcept
178 {
179 return ~Mask<T>::is_lt(x, y);
180 }
181
182 static Mask<T> is_within_range(T v, T l, T u) noexcept
183 {
184 //return Mask<T>::is_gte(v, l) & Mask<T>::is_lte(v, u);
185
186 const T v_lt_l = v^((v^l) | ((v-l)^v));
187 const T v_gt_u = u^((u^v) | ((u-v)^u));
188 const T either = v_lt_l | v_gt_u;
189 return ~Mask<T>(ct_expand_top_bit(either));
190 }
191
192 static Mask<T> is_any_of(T v, std::initializer_list<T> accepted) noexcept
193 {
194 T accept = 0;
195
196 for(auto a: accepted)
197 {
198 const T diff = a ^ v;
199 const T eq_zero = ~diff & (diff - 1);
200 accept |= eq_zero;
201 }
202
203 return Mask<T>(ct_expand_top_bit(accept));
204 }
205
206 /**
207 * AND-combine two masks
208 */
210 {
211 m_mask &= o.value();
212 return (*this);
213 }
214
215 /**
216 * XOR-combine two masks
217 */
219 {
220 m_mask ^= o.value();
221 return (*this);
222 }
223
224 /**
225 * OR-combine two masks
226 */
228 {
229 m_mask |= o.value();
230 return (*this);
231 }
232
233 /**
234 * AND-combine two masks
235 */
236 friend Mask<T> operator&(Mask<T> x, Mask<T> y) noexcept
237 {
238 return Mask<T>(x.value() & y.value());
239 }
240
241 /**
242 * XOR-combine two masks
243 */
244 friend Mask<T> operator^(Mask<T> x, Mask<T> y) noexcept
245 {
246 return Mask<T>(x.value() ^ y.value());
247 }
248
249 /**
250 * OR-combine two masks
251 */
252 friend Mask<T> operator|(Mask<T> x, Mask<T> y) noexcept
253 {
254 return Mask<T>(x.value() | y.value());
255 }
256
257 /**
258 * Negate this mask
259 */
260 Mask<T> operator~() const noexcept
261 {
262 return Mask<T>(~value());
263 }
264
265 /**
266 * Return x if the mask is set, or otherwise zero
267 */
268 T if_set_return(T x) const noexcept
269 {
270 return m_mask & x;
271 }
272
273 /**
274 * Return x if the mask is cleared, or otherwise zero
275 */
276 T if_not_set_return(T x) const noexcept
277 {
278 return ~m_mask & x;
279 }
280
281 /**
282 * If this mask is set, return x, otherwise return y
283 */
284 T select(T x, T y) const noexcept
285 {
286 return ct_masked_merge(value(), x, y);
287 }
288
289 T select_and_unpoison(T x, T y) const noexcept
290 {
291 T r = this->select(x, y);
292 CT::unpoison(r);
293 return r;
294 }
295
296 /**
297 * If this mask is set, return x, otherwise return y
298 */
299 Mask<T> select_mask(Mask<T> x, Mask<T> y) const noexcept
300 {
301 return Mask<T>(select(x.value(), y.value()));
302 }
303
304 /**
305 * Conditionally set output to x or y, depending on if mask is set or
306 * cleared (resp)
307 */
308 void select_n(T output[], const T x[], const T y[], size_t len) const noexcept
309 {
310 for(size_t i = 0; i != len; ++i)
311 output[i] = this->select(x[i], y[i]);
312 }
313
314 /**
315 * If this mask is set, zero out buf, otherwise do nothing
316 */
317 void if_set_zero_out(T buf[], size_t elems) noexcept
318 {
319 for(size_t i = 0; i != elems; ++i)
320 {
321 buf[i] = this->if_not_set_return(buf[i]);
322 }
323 }
324
325 /**
326 * Return the value of the mask, unpoisoned
327 */
328 T unpoisoned_value() const noexcept
329 {
330 T r = value();
331 CT::unpoison(r);
332 return r;
333 }
334
335 /**
336 * Return true iff this mask is set
337 */
338 bool is_set() const noexcept
339 {
340 return unpoisoned_value() != 0;
341 }
342
343 /**
344 * Return the underlying value of the mask
345 */
346 T value() const noexcept
347 {
348 return m_mask;
349 }
350
351 private:
352 Mask(T m) noexcept : m_mask(m) {}
353
354 T m_mask;
355 };
356
357template<typename T>
359 T* to,
360 const T* from0,
361 const T* from1,
362 size_t elems) noexcept
363 {
364 const auto mask = CT::Mask<T>::expand(cnd);
365 mask.select_n(to, from0, from1, elems);
366 return mask;
367 }
368
369template<typename T>
370inline void conditional_swap(bool cnd, T& x, T& y) noexcept
371 {
372 const auto swap = CT::Mask<T>::expand(cnd);
373
374 T t0 = swap.select(y, x);
375 T t1 = swap.select(x, y);
376 x = t0;
377 y = t1;
378 }
379
380template<typename T>
381inline void conditional_swap_ptr(bool cnd, T& x, T& y) noexcept
382 {
383 uintptr_t xp = reinterpret_cast<uintptr_t>(x);
384 uintptr_t yp = reinterpret_cast<uintptr_t>(y);
385
386 conditional_swap<uintptr_t>(cnd, xp, yp);
387
388 x = reinterpret_cast<T>(xp);
389 y = reinterpret_cast<T>(yp);
390 }
391
392} // jau::ct
393
394#endif
A Mask type used for constant-time operations.
Definition: ct_utils.hpp:81
Mask< T > & operator^=(Mask< T > o) noexcept
XOR-combine two masks.
Definition: ct_utils.hpp:218
Mask(Mask< U > o) noexcept
Derive a Mask from a Mask of a larger type.
Definition: ct_utils.hpp:95
Mask< T > operator~() const noexcept
Negate this mask.
Definition: ct_utils.hpp:260
Mask< T > & operator&=(Mask< T > o) noexcept
AND-combine two masks.
Definition: ct_utils.hpp:209
static Mask< T > is_gte(T x, T y) noexcept
Return a Mask<T> which is set if x >= y.
Definition: ct_utils.hpp:177
T unpoisoned_value() const noexcept
Return the value of the mask, unpoisoned.
Definition: ct_utils.hpp:328
void select_n(T output[], const T x[], const T y[], size_t len) const noexcept
Conditionally set output to x or y, depending on if mask is set or cleared (resp)
Definition: ct_utils.hpp:308
static Mask< T > set() noexcept
Return a Mask<T> with all bits set.
Definition: ct_utils.hpp:103
static Mask< T > cleared() noexcept
Return a Mask<T> with all bits cleared.
Definition: ct_utils.hpp:111
static Mask< T > is_gt(T x, T y) noexcept
Return a Mask<T> which is set if x > y.
Definition: ct_utils.hpp:161
T select(T x, T y) const noexcept
If this mask is set, return x, otherwise return y.
Definition: ct_utils.hpp:284
static Mask< T > is_equal(T x, T y) noexcept
Return a Mask<T> which is set if x == y.
Definition: ct_utils.hpp:145
friend Mask< T > operator&(Mask< T > x, Mask< T > y) noexcept
AND-combine two masks.
Definition: ct_utils.hpp:236
void if_set_zero_out(T buf[], size_t elems) noexcept
If this mask is set, zero out buf, otherwise do nothing.
Definition: ct_utils.hpp:317
T if_not_set_return(T x) const noexcept
Return x if the mask is cleared, or otherwise zero.
Definition: ct_utils.hpp:276
bool is_set() const noexcept
Return true iff this mask is set.
Definition: ct_utils.hpp:338
static Mask< T > expand(T v) noexcept
Return a Mask<T> which is set if v is != 0.
Definition: ct_utils.hpp:119
static Mask< T > is_lte(T x, T y) noexcept
Return a Mask<T> which is set if x <= y.
Definition: ct_utils.hpp:169
T value() const noexcept
Return the underlying value of the mask.
Definition: ct_utils.hpp:346
Mask< T > & operator=(const Mask< T > &other) noexcept
Definition: ct_utils.hpp:86
Mask< T > select_mask(Mask< T > x, Mask< T > y) const noexcept
If this mask is set, return x, otherwise return y.
Definition: ct_utils.hpp:299
static Mask< T > is_within_range(T v, T l, T u) noexcept
Definition: ct_utils.hpp:182
T if_set_return(T x) const noexcept
Return x if the mask is set, or otherwise zero.
Definition: ct_utils.hpp:268
Mask< T > & operator|=(Mask< T > o) noexcept
OR-combine two masks.
Definition: ct_utils.hpp:227
Mask(const Mask< T > &other) noexcept
Definition: ct_utils.hpp:83
static Mask< T > is_zero(T x) noexcept
Return a Mask<T> which is set if v is == 0 or cleared otherwise.
Definition: ct_utils.hpp:137
static Mask< T > is_any_of(T v, std::initializer_list< T > accepted) noexcept
Definition: ct_utils.hpp:192
T select_and_unpoison(T x, T y) const noexcept
Definition: ct_utils.hpp:289
static Mask< T > expand(Mask< U > m) noexcept
Return a Mask<T> which is set if m is set.
Definition: ct_utils.hpp:128
friend Mask< T > operator^(Mask< T > x, Mask< T > y) noexcept
XOR-combine two masks.
Definition: ct_utils.hpp:244
friend Mask< T > operator|(Mask< T > x, Mask< T > y) noexcept
OR-combine two masks.
Definition: ct_utils.hpp:252
static Mask< T > is_lt(T x, T y) noexcept
Return a Mask<T> which is set if x < y.
Definition: ct_utils.hpp:153
constexpr T ct_expand_top_bit(T x)
Returns ~0 (2-complement) if top bit of arg is set, otherwise 0 (w/o branching) in O(1) and constant ...
constexpr T ct_masked_merge(T mask, T a_if_masked, T b_if_unmasked)
Returns merged a_if_masked bits selected by mask 1 bits and b_if_unmasked bits selected by mask 0 bit...
void swap(cow_darray< Value_type, Size_type, Alloc_type > &rhs, cow_darray< Value_type, Size_type, Alloc_type > &lhs) noexcept
Functions for constant time operations on data and testing of constant time annotations using valgrin...
Definition: ct_utils.hpp:26
void poison(const T *p, size_t n)
Use valgrind to mark the contents of memory as being undefined.
Definition: ct_utils.hpp:46
void unpoison(const T *p, size_t n)
Definition: ct_utils.hpp:54
void conditional_swap(bool cnd, T &x, T &y) noexcept
Definition: ct_utils.hpp:370
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems) noexcept
Definition: ct_utils.hpp:358
void conditional_swap_ptr(bool cnd, T &x, T &y) noexcept
Definition: ct_utils.hpp:381