constant_time_impl.h (21202B)
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 static inline mbedtls_ct_uint_t mbedtls_ct_compiler_opaque(mbedtls_ct_uint_t x) 86 { 87 #if defined(MBEDTLS_CT_ASM) 88 asm volatile ("" : [x] "+r" (x) :); 89 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 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 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 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 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 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 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 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 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 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 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 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 return mbedtls_ct_bool(diff); 389 } 390 391 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 const unsigned char co = (unsigned char) mbedtls_ct_compiler_opaque(c); 397 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 unsigned low_mask = ((unsigned) co - low) >> 8; 401 /* high_mask is: 0 if c <= high, 0x...ff if c > high */ 402 unsigned high_mask = ((unsigned) high - co) >> 8; 403 404 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 static inline unsigned mbedtls_ct_uint_if(mbedtls_ct_condition_t condition, 419 unsigned if1, 420 unsigned if0) 421 { 422 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 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 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 static inline size_t mbedtls_ct_size_if_else_0(mbedtls_ct_condition_t condition, size_t if1) 447 { 448 return (size_t) (condition & if1); 449 } 450 451 static inline unsigned mbedtls_ct_uint_if_else_0(mbedtls_ct_condition_t condition, unsigned if1) 452 { 453 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 static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if_else_0(mbedtls_ct_condition_t condition, 465 mbedtls_mpi_uint if1) 466 { 467 return (mbedtls_mpi_uint) (condition & if1); 468 } 469 470 #endif /* MBEDTLS_BIGNUM_C */ 471 472 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 return -((int) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) (-if1), 481 (mbedtls_ct_uint_t) (-if0))); 482 } 483 484 static inline int mbedtls_ct_error_if_else_0(mbedtls_ct_condition_t condition, int if1) 485 { 486 return -((int) (condition & (-if1))); 487 } 488 489 static inline mbedtls_ct_condition_t mbedtls_ct_uint_eq(mbedtls_ct_uint_t x, 490 mbedtls_ct_uint_t y) 491 { 492 return ~mbedtls_ct_uint_ne(x, y); 493 } 494 495 static inline mbedtls_ct_condition_t mbedtls_ct_uint_gt(mbedtls_ct_uint_t x, 496 mbedtls_ct_uint_t y) 497 { 498 return mbedtls_ct_uint_lt(y, x); 499 } 500 501 static inline mbedtls_ct_condition_t mbedtls_ct_uint_ge(mbedtls_ct_uint_t x, 502 mbedtls_ct_uint_t y) 503 { 504 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 static inline mbedtls_ct_condition_t mbedtls_ct_bool_ne(mbedtls_ct_condition_t x, 514 mbedtls_ct_condition_t y) 515 { 516 return (mbedtls_ct_condition_t) (x ^ y); 517 } 518 519 static inline mbedtls_ct_condition_t mbedtls_ct_bool_and(mbedtls_ct_condition_t x, 520 mbedtls_ct_condition_t y) 521 { 522 return (mbedtls_ct_condition_t) (x & y); 523 } 524 525 static inline mbedtls_ct_condition_t mbedtls_ct_bool_or(mbedtls_ct_condition_t x, 526 mbedtls_ct_condition_t y) 527 { 528 return (mbedtls_ct_condition_t) (x | y); 529 } 530 531 static inline mbedtls_ct_condition_t mbedtls_ct_bool_not(mbedtls_ct_condition_t x) 532 { 533 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 */