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) 84extern 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 */ 100static 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. */ 135static 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 220static 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 286static 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 397static 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 406static 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 426static 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 433static 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 440static 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 450static 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 461static 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 466static inline unsigned mbedtls_ct_uint_if_else_0(mbedtls_ct_condition_t condition, unsigned if1) 467{ 468 return (unsigned) (condition & if1); 469} 470 471static 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 479static 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 487static 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 499static inline int mbedtls_ct_error_if_else_0(mbedtls_ct_condition_t condition, int if1) 500{ 501 return -((int) (condition & (-if1))); 502} 503 504static 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 510static 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 516static 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 522static 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 528static 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 534static 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 540static 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 546static 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