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