1/* 2 * Copyright 2014-2019 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10#ifndef OSSL_INTERNAL_CONSTANT_TIME_H 11# define OSSL_INTERNAL_CONSTANT_TIME_H 12 13# include <stdlib.h> 14# include <string.h> 15# include <openssl/e_os2.h> /* For 'ossl_inline' */ 16 17/*- 18 * The boolean methods return a bitmask of all ones (0xff...f) for true 19 * and 0 for false. This is useful for choosing a value based on the result 20 * of a conditional in constant time. For example, 21 * if (a < b) { 22 * c = a; 23 * } else { 24 * c = b; 25 * } 26 * can be written as 27 * unsigned int lt = constant_time_lt(a, b); 28 * c = constant_time_select(lt, a, b); 29 */ 30 31/* Returns the given value with the MSB copied to all the other bits. */ 32static ossl_inline unsigned int constant_time_msb(unsigned int a); 33/* Convenience method for uint32_t. */ 34static ossl_inline uint32_t constant_time_msb_32(uint32_t a); 35/* Convenience method for uint64_t. */ 36static ossl_inline uint64_t constant_time_msb_64(uint64_t a); 37 38/* Returns 0xff..f if a < b and 0 otherwise. */ 39static ossl_inline unsigned int constant_time_lt(unsigned int a, 40 unsigned int b); 41/* Convenience method for getting an 8-bit mask. */ 42static ossl_inline unsigned char constant_time_lt_8(unsigned int a, 43 unsigned int b); 44/* Convenience method for uint64_t. */ 45static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b); 46 47/* Returns 0xff..f if a >= b and 0 otherwise. */ 48static ossl_inline unsigned int constant_time_ge(unsigned int a, 49 unsigned int b); 50/* Convenience method for getting an 8-bit mask. */ 51static ossl_inline unsigned char constant_time_ge_8(unsigned int a, 52 unsigned int b); 53 54/* Returns 0xff..f if a == 0 and 0 otherwise. */ 55static ossl_inline unsigned int constant_time_is_zero(unsigned int a); 56/* Convenience method for getting an 8-bit mask. */ 57static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a); 58/* Convenience method for getting a 32-bit mask. */ 59static ossl_inline uint32_t constant_time_is_zero_32(uint32_t a); 60 61/* Returns 0xff..f if a == b and 0 otherwise. */ 62static ossl_inline unsigned int constant_time_eq(unsigned int a, 63 unsigned int b); 64/* Convenience method for getting an 8-bit mask. */ 65static ossl_inline unsigned char constant_time_eq_8(unsigned int a, 66 unsigned int b); 67/* Signed integers. */ 68static ossl_inline unsigned int constant_time_eq_int(int a, int b); 69/* Convenience method for getting an 8-bit mask. */ 70static ossl_inline unsigned char constant_time_eq_int_8(int a, int b); 71 72/*- 73 * Returns (mask & a) | (~mask & b). 74 * 75 * When |mask| is all 1s or all 0s (as returned by the methods above), 76 * the select methods return either |a| (if |mask| is nonzero) or |b| 77 * (if |mask| is zero). 78 */ 79static ossl_inline unsigned int constant_time_select(unsigned int mask, 80 unsigned int a, 81 unsigned int b); 82/* Convenience method for unsigned chars. */ 83static ossl_inline unsigned char constant_time_select_8(unsigned char mask, 84 unsigned char a, 85 unsigned char b); 86 87/* Convenience method for uint32_t. */ 88static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a, 89 uint32_t b); 90 91/* Convenience method for uint64_t. */ 92static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a, 93 uint64_t b); 94/* Convenience method for signed integers. */ 95static ossl_inline int constant_time_select_int(unsigned int mask, int a, 96 int b); 97 98 99static ossl_inline unsigned int constant_time_msb(unsigned int a) 100{ 101 return 0 - (a >> (sizeof(a) * 8 - 1)); 102} 103 104 105static ossl_inline uint32_t constant_time_msb_32(uint32_t a) 106{ 107 return 0 - (a >> 31); 108} 109 110static ossl_inline uint64_t constant_time_msb_64(uint64_t a) 111{ 112 return 0 - (a >> 63); 113} 114 115static ossl_inline size_t constant_time_msb_s(size_t a) 116{ 117 return 0 - (a >> (sizeof(a) * 8 - 1)); 118} 119 120static ossl_inline unsigned int constant_time_lt(unsigned int a, 121 unsigned int b) 122{ 123 return constant_time_msb(a ^ ((a ^ b) | ((a - b) ^ b))); 124} 125 126static ossl_inline size_t constant_time_lt_s(size_t a, size_t b) 127{ 128 return constant_time_msb_s(a ^ ((a ^ b) | ((a - b) ^ b))); 129} 130 131static ossl_inline unsigned char constant_time_lt_8(unsigned int a, 132 unsigned int b) 133{ 134 return (unsigned char)constant_time_lt(a, b); 135} 136 137static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b) 138{ 139 return constant_time_msb_64(a ^ ((a ^ b) | ((a - b) ^ b))); 140} 141 142static ossl_inline unsigned int constant_time_ge(unsigned int a, 143 unsigned int b) 144{ 145 return ~constant_time_lt(a, b); 146} 147 148static ossl_inline size_t constant_time_ge_s(size_t a, size_t b) 149{ 150 return ~constant_time_lt_s(a, b); 151} 152 153static ossl_inline unsigned char constant_time_ge_8(unsigned int a, 154 unsigned int b) 155{ 156 return (unsigned char)constant_time_ge(a, b); 157} 158 159static ossl_inline unsigned char constant_time_ge_8_s(size_t a, size_t b) 160{ 161 return (unsigned char)constant_time_ge_s(a, b); 162} 163 164static ossl_inline unsigned int constant_time_is_zero(unsigned int a) 165{ 166 return constant_time_msb(~a & (a - 1)); 167} 168 169static ossl_inline size_t constant_time_is_zero_s(size_t a) 170{ 171 return constant_time_msb_s(~a & (a - 1)); 172} 173 174static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a) 175{ 176 return (unsigned char)constant_time_is_zero(a); 177} 178 179static ossl_inline uint32_t constant_time_is_zero_32(uint32_t a) 180{ 181 return constant_time_msb_32(~a & (a - 1)); 182} 183 184static ossl_inline unsigned int constant_time_eq(unsigned int a, 185 unsigned int b) 186{ 187 return constant_time_is_zero(a ^ b); 188} 189 190static ossl_inline size_t constant_time_eq_s(size_t a, size_t b) 191{ 192 return constant_time_is_zero_s(a ^ b); 193} 194 195static ossl_inline unsigned char constant_time_eq_8(unsigned int a, 196 unsigned int b) 197{ 198 return (unsigned char)constant_time_eq(a, b); 199} 200 201static ossl_inline unsigned char constant_time_eq_8_s(size_t a, size_t b) 202{ 203 return (unsigned char)constant_time_eq_s(a, b); 204} 205 206static ossl_inline unsigned int constant_time_eq_int(int a, int b) 207{ 208 return constant_time_eq((unsigned)(a), (unsigned)(b)); 209} 210 211static ossl_inline unsigned char constant_time_eq_int_8(int a, int b) 212{ 213 return constant_time_eq_8((unsigned)(a), (unsigned)(b)); 214} 215 216/* 217 * Returns the value unmodified, but avoids optimizations. 218 * The barriers prevent the compiler from narrowing down the 219 * possible value range of the mask and ~mask in the select 220 * statements, which avoids the recognition of the select 221 * and turning it into a conditional load or branch. 222 */ 223static ossl_inline unsigned int value_barrier(unsigned int a) 224{ 225#if !defined(OPENSSL_NO_ASM) && defined(__GNUC__) 226 unsigned int r; 227 __asm__("" : "=r"(r) : "0"(a)); 228#else 229 volatile unsigned int r = a; 230#endif 231 return r; 232} 233 234/* Convenience method for uint32_t. */ 235static ossl_inline uint32_t value_barrier_32(uint32_t a) 236{ 237#if !defined(OPENSSL_NO_ASM) && defined(__GNUC__) 238 uint32_t r; 239 __asm__("" : "=r"(r) : "0"(a)); 240#else 241 volatile uint32_t r = a; 242#endif 243 return r; 244} 245 246/* Convenience method for uint64_t. */ 247static ossl_inline uint64_t value_barrier_64(uint64_t a) 248{ 249#if !defined(OPENSSL_NO_ASM) && defined(__GNUC__) 250 uint64_t r; 251 __asm__("" : "=r"(r) : "0"(a)); 252#else 253 volatile uint64_t r = a; 254#endif 255 return r; 256} 257 258/* Convenience method for size_t. */ 259static ossl_inline size_t value_barrier_s(size_t a) 260{ 261#if !defined(OPENSSL_NO_ASM) && defined(__GNUC__) 262 size_t r; 263 __asm__("" : "=r"(r) : "0"(a)); 264#else 265 volatile size_t r = a; 266#endif 267 return r; 268} 269 270static ossl_inline unsigned int constant_time_select(unsigned int mask, 271 unsigned int a, 272 unsigned int b) 273{ 274 return (value_barrier(mask) & a) | (value_barrier(~mask) & b); 275} 276 277static ossl_inline size_t constant_time_select_s(size_t mask, 278 size_t a, 279 size_t b) 280{ 281 return (value_barrier_s(mask) & a) | (value_barrier_s(~mask) & b); 282} 283 284static ossl_inline unsigned char constant_time_select_8(unsigned char mask, 285 unsigned char a, 286 unsigned char b) 287{ 288 return (unsigned char)constant_time_select(mask, a, b); 289} 290 291static ossl_inline int constant_time_select_int(unsigned int mask, int a, 292 int b) 293{ 294 return (int)constant_time_select(mask, (unsigned)(a), (unsigned)(b)); 295} 296 297static ossl_inline int constant_time_select_int_s(size_t mask, int a, int b) 298{ 299 return (int)constant_time_select((unsigned)mask, (unsigned)(a), 300 (unsigned)(b)); 301} 302 303static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a, 304 uint32_t b) 305{ 306 return (value_barrier_32(mask) & a) | (value_barrier_32(~mask) & b); 307} 308 309static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a, 310 uint64_t b) 311{ 312 return (value_barrier_64(mask) & a) | (value_barrier_64(~mask) & b); 313} 314 315/* 316 * mask must be 0xFFFFFFFF or 0x00000000. 317 * 318 * if (mask) { 319 * uint32_t tmp = *a; 320 * 321 * *a = *b; 322 * *b = tmp; 323 * } 324 */ 325static ossl_inline void constant_time_cond_swap_32(uint32_t mask, uint32_t *a, 326 uint32_t *b) 327{ 328 uint32_t xor = *a ^ *b; 329 330 xor &= mask; 331 *a ^= xor; 332 *b ^= xor; 333} 334 335/* 336 * mask must be 0xFFFFFFFF or 0x00000000. 337 * 338 * if (mask) { 339 * uint64_t tmp = *a; 340 * 341 * *a = *b; 342 * *b = tmp; 343 * } 344 */ 345static ossl_inline void constant_time_cond_swap_64(uint64_t mask, uint64_t *a, 346 uint64_t *b) 347{ 348 uint64_t xor = *a ^ *b; 349 350 xor &= mask; 351 *a ^= xor; 352 *b ^= xor; 353} 354 355/* 356 * table is a two dimensional array of bytes. Each row has rowsize elements. 357 * Copies row number idx into out. rowsize and numrows are not considered 358 * private. 359 */ 360static ossl_inline void constant_time_lookup(void *out, 361 const void *table, 362 size_t rowsize, 363 size_t numrows, 364 size_t idx) 365{ 366 size_t i, j; 367 const unsigned char *tablec = (const unsigned char *)table; 368 unsigned char *outc = (unsigned char *)out; 369 unsigned char mask; 370 371 memset(out, 0, rowsize); 372 373 /* Note idx may underflow - but that is well defined */ 374 for (i = 0; i < numrows; i++, idx--) { 375 mask = (unsigned char)constant_time_is_zero_s(idx); 376 for (j = 0; j < rowsize; j++) 377 *(outc + j) |= constant_time_select_8(mask, *(tablec++), 0); 378 } 379} 380 381/* 382 * Expected usage pattern is to unconditionally set error and then 383 * wipe it if there was no actual error. |clear| is 1 or 0. 384 */ 385void err_clear_last_constant_time(int clear); 386 387#endif /* OSSL_INTERNAL_CONSTANT_TIME_H */ 388