Line data Source code
1 : /**
2 : * Constant-time functions
3 : *
4 : * Copyright The Mbed TLS Contributors
5 : * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 : */
7 :
8 : #ifndef MBEDTLS_CONSTANT_TIME_IMPL_H
9 : #define MBEDTLS_CONSTANT_TIME_IMPL_H
10 :
11 : #include <stddef.h>
12 :
13 : #include "common.h"
14 :
15 : #if defined(MBEDTLS_BIGNUM_C)
16 : #include "mbedtls/bignum.h"
17 : #endif
18 :
19 : /*
20 : * To improve readability of constant_time_internal.h, the static inline
21 : * definitions are here, and constant_time_internal.h has only the declarations.
22 : *
23 : * This results in duplicate declarations of the form:
24 : * static inline void f(); // from constant_time_internal.h
25 : * static inline void f() { ... } // from constant_time_impl.h
26 : * when constant_time_internal.h is included.
27 : *
28 : * This appears to behave as if the declaration-without-definition was not present
29 : * (except for warnings if gcc -Wredundant-decls or similar is used).
30 : *
31 : * Disable -Wredundant-decls so that gcc does not warn about this. This is re-enabled
32 : * at the bottom of this file.
33 : */
34 : #if defined(MBEDTLS_COMPILER_IS_GCC) && (__GNUC__ > 4)
35 : #pragma GCC diagnostic push
36 : #pragma GCC diagnostic ignored "-Wredundant-decls"
37 : #endif
38 :
39 : /* armcc5 --gnu defines __GNUC__ but doesn't support GNU's extended asm */
40 : #if defined(MBEDTLS_HAVE_ASM) && defined(__GNUC__) && (!defined(__ARMCC_VERSION) || \
41 : __ARMCC_VERSION >= 6000000)
42 : #define MBEDTLS_CT_ASM
43 : #if (defined(__arm__) || defined(__thumb__) || defined(__thumb2__))
44 : #define MBEDTLS_CT_ARM_ASM
45 : #elif defined(__aarch64__)
46 : #define MBEDTLS_CT_AARCH64_ASM
47 : #elif defined(__amd64__) || defined(__x86_64__)
48 : #define MBEDTLS_CT_X86_64_ASM
49 : #elif defined(__i386__)
50 : #define MBEDTLS_CT_X86_ASM
51 : #endif
52 : #endif
53 :
54 : #define MBEDTLS_CT_SIZE (sizeof(mbedtls_ct_uint_t) * 8)
55 :
56 :
57 : /* ============================================================================
58 : * Core const-time primitives
59 : */
60 :
61 : /* Ensure that the compiler cannot know the value of x (i.e., cannot optimise
62 : * based on its value) after this function is called.
63 : *
64 : * If we are not using assembly, this will be fairly inefficient, so its use
65 : * should be minimised.
66 : */
67 :
68 : #if !defined(MBEDTLS_CT_ASM)
69 : extern volatile mbedtls_ct_uint_t mbedtls_ct_zero;
70 : #endif
71 :
72 : /**
73 : * \brief Ensure that a value cannot be known at compile time.
74 : *
75 : * \param x The value to hide from the compiler.
76 : * \return The same value that was passed in, such that the compiler
77 : * cannot prove its value (even for calls of the form
78 : * x = mbedtls_ct_compiler_opaque(1), x will be unknown).
79 : *
80 : * \note This is mainly used in constructing mbedtls_ct_condition_t
81 : * values and performing operations over them, to ensure that
82 : * there is no way for the compiler to ever know anything about
83 : * the value of an mbedtls_ct_condition_t.
84 : */
85 3343327 : static inline mbedtls_ct_uint_t mbedtls_ct_compiler_opaque(mbedtls_ct_uint_t x)
86 : {
87 : #if defined(MBEDTLS_CT_ASM)
88 3343327 : asm volatile ("" : [x] "+r" (x) :);
89 3343327 : return x;
90 : #else
91 : return x ^ mbedtls_ct_zero;
92 : #endif
93 : }
94 :
95 : /*
96 : * Selecting unified syntax is needed for gcc, and harmless on clang.
97 : *
98 : * This is needed because on Thumb 1, condition flags are always set, so
99 : * e.g. "negs" is supported but "neg" is not (on Thumb 2, both exist).
100 : *
101 : * Under Thumb 1 unified syntax, only the "negs" form is accepted, and
102 : * under divided syntax, only the "neg" form is accepted. clang only
103 : * supports unified syntax.
104 : *
105 : * On Thumb 2 and Arm, both compilers are happy with the "s" suffix,
106 : * although we don't actually care about setting the flags.
107 : *
108 : * For old versions of gcc (see #8516 for details), restore divided
109 : * syntax afterwards - otherwise old versions of gcc seem to apply
110 : * unified syntax globally, which breaks other asm code.
111 : */
112 : #if defined(MBEDTLS_COMPILER_IS_GCC) && defined(__thumb__) && !defined(__thumb2__) && \
113 : (__GNUC__ < 11) && !defined(__ARM_ARCH_2__)
114 : #define RESTORE_ASM_SYNTAX ".syntax divided \n\t"
115 : #else
116 : #define RESTORE_ASM_SYNTAX
117 : #endif
118 :
119 : /* Convert a number into a condition in constant time. */
120 5399428 : static inline mbedtls_ct_condition_t mbedtls_ct_bool(mbedtls_ct_uint_t x)
121 : {
122 : /*
123 : * Define mask-generation code that, as far as possible, will not use branches or conditional instructions.
124 : *
125 : * For some platforms / type sizes, we define assembly to assure this.
126 : *
127 : * Otherwise, we define a plain C fallback which (in May 2023) does not get optimised into
128 : * conditional instructions or branches by trunk clang, gcc, or MSVC v19.
129 : */
130 : #if defined(MBEDTLS_CT_AARCH64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
131 : mbedtls_ct_uint_t s;
132 : asm volatile ("neg %x[s], %x[x] \n\t"
133 : "orr %x[x], %x[s], %x[x] \n\t"
134 : "asr %x[x], %x[x], 63 \n\t"
135 : :
136 : [s] "=&r" (s),
137 : [x] "+&r" (x)
138 : :
139 : :
140 : );
141 : return (mbedtls_ct_condition_t) x;
142 : #elif defined(MBEDTLS_CT_ARM_ASM) && defined(MBEDTLS_CT_SIZE_32)
143 : uint32_t s;
144 : asm volatile (".syntax unified \n\t"
145 : "negs %[s], %[x] \n\t"
146 : "orrs %[x], %[x], %[s] \n\t"
147 : "asrs %[x], %[x], #31 \n\t"
148 : RESTORE_ASM_SYNTAX
149 : :
150 : [s] "=&l" (s),
151 : [x] "+&l" (x)
152 : :
153 : :
154 : "cc" /* clobbers flag bits */
155 : );
156 : return (mbedtls_ct_condition_t) x;
157 : #elif defined(MBEDTLS_CT_X86_64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
158 : uint64_t s;
159 5399428 : asm volatile ("mov %[x], %[s] \n\t"
160 : "neg %[s] \n\t"
161 : "or %[x], %[s] \n\t"
162 : "sar $63, %[s] \n\t"
163 : :
164 : [s] "=&a" (s)
165 : :
166 : [x] "D" (x)
167 : :
168 : );
169 5399428 : return (mbedtls_ct_condition_t) s;
170 : #elif defined(MBEDTLS_CT_X86_ASM) && defined(MBEDTLS_CT_SIZE_32)
171 : uint32_t s;
172 : asm volatile ("mov %[x], %[s] \n\t"
173 : "neg %[s] \n\t"
174 : "or %[s], %[x] \n\t"
175 : "sar $31, %[x] \n\t"
176 : :
177 : [s] "=&c" (s),
178 : [x] "+&a" (x)
179 : :
180 : :
181 : );
182 : return (mbedtls_ct_condition_t) x;
183 : #else
184 : const mbedtls_ct_uint_t xo = mbedtls_ct_compiler_opaque(x);
185 : #if defined(_MSC_VER)
186 : /* MSVC has a warning about unary minus on unsigned, but this is
187 : * well-defined and precisely what we want to do here */
188 : #pragma warning( push )
189 : #pragma warning( disable : 4146 )
190 : #endif
191 : // y is negative (i.e., top bit set) iff x is non-zero
192 : mbedtls_ct_int_t y = (-xo) | -(xo >> 1);
193 :
194 : // extract only the sign bit of y so that y == 1 (if x is non-zero) or 0 (if x is zero)
195 : y = (((mbedtls_ct_uint_t) y) >> (MBEDTLS_CT_SIZE - 1));
196 :
197 : // -y has all bits set (if x is non-zero), or all bits clear (if x is zero)
198 : return (mbedtls_ct_condition_t) (-y);
199 : #if defined(_MSC_VER)
200 : #pragma warning( pop )
201 : #endif
202 : #endif
203 : }
204 :
205 30251009 : static inline mbedtls_ct_uint_t mbedtls_ct_if(mbedtls_ct_condition_t condition,
206 : mbedtls_ct_uint_t if1,
207 : mbedtls_ct_uint_t if0)
208 : {
209 : #if defined(MBEDTLS_CT_AARCH64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
210 : asm volatile ("and %x[if1], %x[if1], %x[condition] \n\t"
211 : "mvn %x[condition], %x[condition] \n\t"
212 : "and %x[condition], %x[condition], %x[if0] \n\t"
213 : "orr %x[condition], %x[if1], %x[condition]"
214 : :
215 : [condition] "+&r" (condition),
216 : [if1] "+&r" (if1)
217 : :
218 : [if0] "r" (if0)
219 : :
220 : );
221 : return (mbedtls_ct_uint_t) condition;
222 : #elif defined(MBEDTLS_CT_ARM_ASM) && defined(MBEDTLS_CT_SIZE_32)
223 : asm volatile (".syntax unified \n\t"
224 : "ands %[if1], %[if1], %[condition] \n\t"
225 : "mvns %[condition], %[condition] \n\t"
226 : "ands %[condition], %[condition], %[if0] \n\t"
227 : "orrs %[condition], %[if1], %[condition] \n\t"
228 : RESTORE_ASM_SYNTAX
229 : :
230 : [condition] "+&l" (condition),
231 : [if1] "+&l" (if1)
232 : :
233 : [if0] "l" (if0)
234 : :
235 : "cc"
236 : );
237 : return (mbedtls_ct_uint_t) condition;
238 : #elif defined(MBEDTLS_CT_X86_64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
239 30251009 : asm volatile ("and %[condition], %[if1] \n\t"
240 : "not %[condition] \n\t"
241 : "and %[condition], %[if0] \n\t"
242 : "or %[if1], %[if0] \n\t"
243 : :
244 : [condition] "+&D" (condition),
245 : [if1] "+&S" (if1),
246 : [if0] "+&a" (if0)
247 : :
248 : :
249 : );
250 30251009 : return if0;
251 : #elif defined(MBEDTLS_CT_X86_ASM) && defined(MBEDTLS_CT_SIZE_32)
252 : asm volatile ("and %[condition], %[if1] \n\t"
253 : "not %[condition] \n\t"
254 : "and %[if0], %[condition] \n\t"
255 : "or %[condition], %[if1] \n\t"
256 : :
257 : [condition] "+&c" (condition),
258 : [if1] "+&a" (if1)
259 : :
260 : [if0] "b" (if0)
261 : :
262 : );
263 : return if1;
264 : #else
265 : mbedtls_ct_condition_t not_cond =
266 : (mbedtls_ct_condition_t) (~mbedtls_ct_compiler_opaque(condition));
267 : return (mbedtls_ct_uint_t) ((condition & if1) | (not_cond & if0));
268 : #endif
269 : }
270 :
271 11344 : static inline mbedtls_ct_condition_t mbedtls_ct_uint_lt(mbedtls_ct_uint_t x, mbedtls_ct_uint_t y)
272 : {
273 : #if defined(MBEDTLS_CT_AARCH64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
274 : uint64_t s1;
275 : asm volatile ("eor %x[s1], %x[y], %x[x] \n\t"
276 : "sub %x[x], %x[x], %x[y] \n\t"
277 : "bic %x[x], %x[x], %x[s1] \n\t"
278 : "and %x[s1], %x[s1], %x[y] \n\t"
279 : "orr %x[s1], %x[x], %x[s1] \n\t"
280 : "asr %x[x], %x[s1], 63"
281 : :
282 : [s1] "=&r" (s1),
283 : [x] "+&r" (x)
284 : :
285 : [y] "r" (y)
286 : :
287 : );
288 : return (mbedtls_ct_condition_t) x;
289 : #elif defined(MBEDTLS_CT_ARM_ASM) && defined(MBEDTLS_CT_SIZE_32)
290 : uint32_t s1;
291 : asm volatile (
292 : ".syntax unified \n\t"
293 : #if defined(__thumb__) && !defined(__thumb2__)
294 : "movs %[s1], %[x] \n\t"
295 : "eors %[s1], %[s1], %[y] \n\t"
296 : #else
297 : "eors %[s1], %[x], %[y] \n\t"
298 : #endif
299 : "subs %[x], %[x], %[y] \n\t"
300 : "bics %[x], %[x], %[s1] \n\t"
301 : "ands %[y], %[s1], %[y] \n\t"
302 : "orrs %[x], %[x], %[y] \n\t"
303 : "asrs %[x], %[x], #31 \n\t"
304 : RESTORE_ASM_SYNTAX
305 : :
306 : [s1] "=&l" (s1),
307 : [x] "+&l" (x),
308 : [y] "+&l" (y)
309 : :
310 : :
311 : "cc"
312 : );
313 : return (mbedtls_ct_condition_t) x;
314 : #elif defined(MBEDTLS_CT_X86_64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
315 : uint64_t s;
316 11344 : asm volatile ("mov %[x], %[s] \n\t"
317 : "xor %[y], %[s] \n\t"
318 : "sub %[y], %[x] \n\t"
319 : "and %[s], %[y] \n\t"
320 : "not %[s] \n\t"
321 : "and %[s], %[x] \n\t"
322 : "or %[y], %[x] \n\t"
323 : "sar $63, %[x] \n\t"
324 : :
325 : [s] "=&a" (s),
326 : [x] "+&D" (x),
327 : [y] "+&S" (y)
328 : :
329 : :
330 : );
331 11344 : return (mbedtls_ct_condition_t) x;
332 : #elif defined(MBEDTLS_CT_X86_ASM) && defined(MBEDTLS_CT_SIZE_32)
333 : uint32_t s;
334 : asm volatile ("mov %[x], %[s] \n\t"
335 : "xor %[y], %[s] \n\t"
336 : "sub %[y], %[x] \n\t"
337 : "and %[s], %[y] \n\t"
338 : "not %[s] \n\t"
339 : "and %[s], %[x] \n\t"
340 : "or %[y], %[x] \n\t"
341 : "sar $31, %[x] \n\t"
342 : :
343 : [s] "=&b" (s),
344 : [x] "+&a" (x),
345 : [y] "+&c" (y)
346 : :
347 : :
348 : );
349 : return (mbedtls_ct_condition_t) x;
350 : #else
351 : /* Ensure that the compiler cannot optimise the following operations over x and y,
352 : * even if it knows the value of x and y.
353 : */
354 : const mbedtls_ct_uint_t xo = mbedtls_ct_compiler_opaque(x);
355 : const mbedtls_ct_uint_t yo = mbedtls_ct_compiler_opaque(y);
356 : /*
357 : * Check if the most significant bits (MSB) of the operands are different.
358 : * cond is true iff the MSBs differ.
359 : */
360 : mbedtls_ct_condition_t cond = mbedtls_ct_bool((xo ^ yo) >> (MBEDTLS_CT_SIZE - 1));
361 :
362 : /*
363 : * If the MSB are the same then the difference x-y will be negative (and
364 : * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
365 : *
366 : * If the MSB are different, then the operand with the MSB of 1 is the
367 : * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
368 : * the MSB of y is 0.)
369 : */
370 :
371 : // Select either y, or x - y
372 : mbedtls_ct_uint_t ret = mbedtls_ct_if(cond, yo, (mbedtls_ct_uint_t) (xo - yo));
373 :
374 : // Extract only the MSB of ret
375 : ret = ret >> (MBEDTLS_CT_SIZE - 1);
376 :
377 : // Convert to a condition (i.e., all bits set iff non-zero)
378 : return mbedtls_ct_bool(ret);
379 : #endif
380 : }
381 :
382 302464 : static inline mbedtls_ct_condition_t mbedtls_ct_uint_ne(mbedtls_ct_uint_t x, mbedtls_ct_uint_t y)
383 : {
384 : /* diff = 0 if x == y, non-zero otherwise */
385 302464 : const mbedtls_ct_uint_t diff = mbedtls_ct_compiler_opaque(x) ^ mbedtls_ct_compiler_opaque(y);
386 :
387 : /* all ones if x != y, 0 otherwise */
388 302464 : return mbedtls_ct_bool(diff);
389 : }
390 :
391 1279920 : static inline unsigned char mbedtls_ct_uchar_in_range_if(unsigned char low,
392 : unsigned char high,
393 : unsigned char c,
394 : unsigned char t)
395 : {
396 1279920 : const unsigned char co = (unsigned char) mbedtls_ct_compiler_opaque(c);
397 1279920 : const unsigned char to = (unsigned char) mbedtls_ct_compiler_opaque(t);
398 :
399 : /* low_mask is: 0 if low <= c, 0x...ff if low > c */
400 1279920 : unsigned low_mask = ((unsigned) co - low) >> 8;
401 : /* high_mask is: 0 if c <= high, 0x...ff if c > high */
402 1279920 : unsigned high_mask = ((unsigned) high - co) >> 8;
403 :
404 1279920 : return (unsigned char) (~(low_mask | high_mask)) & to;
405 : }
406 :
407 : /* ============================================================================
408 : * Everything below here is trivial wrapper functions
409 : */
410 :
411 : static inline size_t mbedtls_ct_size_if(mbedtls_ct_condition_t condition,
412 : size_t if1,
413 : size_t if0)
414 : {
415 : return (size_t) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) if1, (mbedtls_ct_uint_t) if0);
416 : }
417 :
418 4923341 : static inline unsigned mbedtls_ct_uint_if(mbedtls_ct_condition_t condition,
419 : unsigned if1,
420 : unsigned if0)
421 : {
422 4923341 : return (unsigned) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) if1, (mbedtls_ct_uint_t) if0);
423 : }
424 :
425 : static inline mbedtls_ct_condition_t mbedtls_ct_bool_if(mbedtls_ct_condition_t condition,
426 : mbedtls_ct_condition_t if1,
427 : mbedtls_ct_condition_t if0)
428 : {
429 : return (mbedtls_ct_condition_t) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) if1,
430 : (mbedtls_ct_uint_t) if0);
431 : }
432 :
433 : #if defined(MBEDTLS_BIGNUM_C)
434 :
435 25327668 : static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if(mbedtls_ct_condition_t condition,
436 : mbedtls_mpi_uint if1,
437 : mbedtls_mpi_uint if0)
438 : {
439 25327668 : return (mbedtls_mpi_uint) mbedtls_ct_if(condition,
440 : (mbedtls_ct_uint_t) if1,
441 : (mbedtls_ct_uint_t) if0);
442 : }
443 :
444 : #endif
445 :
446 0 : static inline size_t mbedtls_ct_size_if_else_0(mbedtls_ct_condition_t condition, size_t if1)
447 : {
448 0 : return (size_t) (condition & if1);
449 : }
450 :
451 0 : static inline unsigned mbedtls_ct_uint_if_else_0(mbedtls_ct_condition_t condition, unsigned if1)
452 : {
453 0 : return (unsigned) (condition & if1);
454 : }
455 :
456 : static inline mbedtls_ct_condition_t mbedtls_ct_bool_if_else_0(mbedtls_ct_condition_t condition,
457 : mbedtls_ct_condition_t if1)
458 : {
459 : return (mbedtls_ct_condition_t) (condition & if1);
460 : }
461 :
462 : #if defined(MBEDTLS_BIGNUM_C)
463 :
464 16955 : static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if_else_0(mbedtls_ct_condition_t condition,
465 : mbedtls_mpi_uint if1)
466 : {
467 16955 : return (mbedtls_mpi_uint) (condition & if1);
468 : }
469 :
470 : #endif /* MBEDTLS_BIGNUM_C */
471 :
472 0 : static inline int mbedtls_ct_error_if(mbedtls_ct_condition_t condition, int if1, int if0)
473 : {
474 : /* Coverting int -> uint -> int here is safe, because we require if1 and if0 to be
475 : * in the range -32767..0, and we require 32-bit int and uint types.
476 : *
477 : * This means that (0 <= -if0 < INT_MAX), so negating if0 is safe, and similarly for
478 : * converting back to int.
479 : */
480 0 : return -((int) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) (-if1),
481 0 : (mbedtls_ct_uint_t) (-if0)));
482 : }
483 :
484 0 : static inline int mbedtls_ct_error_if_else_0(mbedtls_ct_condition_t condition, int if1)
485 : {
486 0 : return -((int) (condition & (-if1)));
487 : }
488 :
489 302464 : static inline mbedtls_ct_condition_t mbedtls_ct_uint_eq(mbedtls_ct_uint_t x,
490 : mbedtls_ct_uint_t y)
491 : {
492 302464 : return ~mbedtls_ct_uint_ne(x, y);
493 : }
494 :
495 0 : static inline mbedtls_ct_condition_t mbedtls_ct_uint_gt(mbedtls_ct_uint_t x,
496 : mbedtls_ct_uint_t y)
497 : {
498 0 : return mbedtls_ct_uint_lt(y, x);
499 : }
500 :
501 1248 : static inline mbedtls_ct_condition_t mbedtls_ct_uint_ge(mbedtls_ct_uint_t x,
502 : mbedtls_ct_uint_t y)
503 : {
504 1248 : return ~mbedtls_ct_uint_lt(x, y);
505 : }
506 :
507 : static inline mbedtls_ct_condition_t mbedtls_ct_uint_le(mbedtls_ct_uint_t x,
508 : mbedtls_ct_uint_t y)
509 : {
510 : return ~mbedtls_ct_uint_gt(x, y);
511 : }
512 :
513 0 : static inline mbedtls_ct_condition_t mbedtls_ct_bool_ne(mbedtls_ct_condition_t x,
514 : mbedtls_ct_condition_t y)
515 : {
516 0 : return (mbedtls_ct_condition_t) (x ^ y);
517 : }
518 :
519 6296 : static inline mbedtls_ct_condition_t mbedtls_ct_bool_and(mbedtls_ct_condition_t x,
520 : mbedtls_ct_condition_t y)
521 : {
522 6296 : return (mbedtls_ct_condition_t) (x & y);
523 : }
524 :
525 20192 : static inline mbedtls_ct_condition_t mbedtls_ct_bool_or(mbedtls_ct_condition_t x,
526 : mbedtls_ct_condition_t y)
527 : {
528 20192 : return (mbedtls_ct_condition_t) (x | y);
529 : }
530 :
531 4928389 : static inline mbedtls_ct_condition_t mbedtls_ct_bool_not(mbedtls_ct_condition_t x)
532 : {
533 4928389 : return (mbedtls_ct_condition_t) (~x);
534 : }
535 :
536 : #if defined(MBEDTLS_COMPILER_IS_GCC) && (__GNUC__ > 4)
537 : /* Restore warnings for -Wredundant-decls on gcc */
538 : #pragma GCC diagnostic pop
539 : #endif
540 :
541 : #endif /* MBEDTLS_CONSTANT_TIME_IMPL_H */
|
