| 1 |
/* |
| 2 |
* Helper functions for constant time operations |
| 3 |
* Copyright (c) 2019, The Linux Foundation |
| 4 |
* |
| 5 |
* This software may be distributed under the terms of the BSD license. |
| 6 |
* See README for more details. |
| 7 |
* |
| 8 |
* These helper functions can be used to implement logic that needs to minimize |
| 9 |
* externally visible differences in execution path by avoiding use of branches, |
| 10 |
* avoiding early termination or other time differences, and forcing same memory |
| 11 |
* access pattern regardless of values. |
| 12 |
*/ |
| 13 |
|
| 14 |
#ifndef CONST_TIME_H |
| 15 |
#define CONST_TIME_H |
| 16 |
|
| 17 |
|
| 18 |
#if defined(__clang__) |
| 19 |
#define NO_UBSAN_UINT_OVERFLOW \ |
| 20 |
__attribute__((no_sanitize("unsigned-integer-overflow"))) |
| 21 |
#else |
| 22 |
#define NO_UBSAN_UINT_OVERFLOW |
| 23 |
#endif |
| 24 |
|
| 25 |
|
| 26 |
/** |
| 27 |
* const_time_fill_msb - Fill all bits with MSB value |
| 28 |
* @val: Input value |
| 29 |
* Returns: Value with all the bits set to the MSB of the input val |
| 30 |
*/ |
| 31 |
static inline unsigned int const_time_fill_msb(unsigned int val) |
| 32 |
{ |
| 33 |
/* Move the MSB to LSB and multiple by -1 to fill in all bits. */ |
| 34 |
return (val >> (sizeof(val) * 8 - 1)) * ~0U; |
| 35 |
} |
| 36 |
|
| 37 |
|
| 38 |
/* Returns: -1 if val is zero; 0 if val is not zero */ |
| 39 |
static inline unsigned int const_time_is_zero(unsigned int val) |
| 40 |
NO_UBSAN_UINT_OVERFLOW |
| 41 |
{ |
| 42 |
/* Set MSB to 1 for 0 and fill rest of bits with the MSB value */ |
| 43 |
return const_time_fill_msb(~val & (val - 1)); |
| 44 |
} |
| 45 |
|
| 46 |
|
| 47 |
/* Returns: -1 if a == b; 0 if a != b */ |
| 48 |
static inline unsigned int const_time_eq(unsigned int a, unsigned int b) |
| 49 |
{ |
| 50 |
return const_time_is_zero(a ^ b); |
| 51 |
} |
| 52 |
|
| 53 |
|
| 54 |
/* Returns: -1 if a == b; 0 if a != b */ |
| 55 |
static inline u8 const_time_eq_u8(unsigned int a, unsigned int b) |
| 56 |
{ |
| 57 |
return (u8) const_time_eq(a, b); |
| 58 |
} |
| 59 |
|
| 60 |
|
| 61 |
/** |
| 62 |
* const_time_eq_bin - Constant time memory comparison |
| 63 |
* @a: First buffer to compare |
| 64 |
* @b: Second buffer to compare |
| 65 |
* @len: Number of octets to compare |
| 66 |
* Returns: -1 if buffers are equal, 0 if not |
| 67 |
* |
| 68 |
* This function is meant for comparing passwords or hash values where |
| 69 |
* difference in execution time or memory access pattern could provide external |
| 70 |
* observer information about the location of the difference in the memory |
| 71 |
* buffers. The return value does not behave like memcmp(), i.e., |
| 72 |
* const_time_eq_bin() cannot be used to sort items into a defined order. Unlike |
| 73 |
* memcmp(), the execution time of const_time_eq_bin() does not depend on the |
| 74 |
* contents of the compared memory buffers, but only on the total compared |
| 75 |
* length. |
| 76 |
*/ |
| 77 |
static inline unsigned int const_time_eq_bin(const void *a, const void *b, |
| 78 |
size_t len) |
| 79 |
{ |
| 80 |
const u8 *aa = a; |
| 81 |
const u8 *bb = b; |
| 82 |
size_t i; |
| 83 |
u8 res = 0; |
| 84 |
|
| 85 |
for (i = 0; i < len; i++) |
| 86 |
res |= aa[i] ^ bb[i]; |
| 87 |
|
| 88 |
return const_time_is_zero(res); |
| 89 |
} |
| 90 |
|
| 91 |
|
| 92 |
/** |
| 93 |
* const_time_select - Constant time unsigned int selection |
| 94 |
* @mask: 0 (false) or -1 (true) to identify which value to select |
| 95 |
* @true_val: Value to select for the true case |
| 96 |
* @false_val: Value to select for the false case |
| 97 |
* Returns: true_val if mask == -1, false_val if mask == 0 |
| 98 |
*/ |
| 99 |
static inline unsigned int const_time_select(unsigned int mask, |
| 100 |
unsigned int true_val, |
| 101 |
unsigned int false_val) |
| 102 |
{ |
| 103 |
return (mask & true_val) | (~mask & false_val); |
| 104 |
} |
| 105 |
|
| 106 |
|
| 107 |
/** |
| 108 |
* const_time_select_int - Constant time int selection |
| 109 |
* @mask: 0 (false) or -1 (true) to identify which value to select |
| 110 |
* @true_val: Value to select for the true case |
| 111 |
* @false_val: Value to select for the false case |
| 112 |
* Returns: true_val if mask == -1, false_val if mask == 0 |
| 113 |
*/ |
| 114 |
static inline int const_time_select_int(unsigned int mask, int true_val, |
| 115 |
int false_val) |
| 116 |
{ |
| 117 |
return (int) const_time_select(mask, (unsigned int) true_val, |
| 118 |
(unsigned int) false_val); |
| 119 |
} |
| 120 |
|
| 121 |
|
| 122 |
/** |
| 123 |
* const_time_select_u8 - Constant time u8 selection |
| 124 |
* @mask: 0 (false) or -1 (true) to identify which value to select |
| 125 |
* @true_val: Value to select for the true case |
| 126 |
* @false_val: Value to select for the false case |
| 127 |
* Returns: true_val if mask == -1, false_val if mask == 0 |
| 128 |
*/ |
| 129 |
static inline u8 const_time_select_u8(u8 mask, u8 true_val, u8 false_val) |
| 130 |
{ |
| 131 |
return (u8) const_time_select(mask, true_val, false_val); |
| 132 |
} |
| 133 |
|
| 134 |
|
| 135 |
/** |
| 136 |
* const_time_select_s8 - Constant time s8 selection |
| 137 |
* @mask: 0 (false) or -1 (true) to identify which value to select |
| 138 |
* @true_val: Value to select for the true case |
| 139 |
* @false_val: Value to select for the false case |
| 140 |
* Returns: true_val if mask == -1, false_val if mask == 0 |
| 141 |
*/ |
| 142 |
static inline s8 const_time_select_s8(u8 mask, s8 true_val, s8 false_val) |
| 143 |
{ |
| 144 |
return (s8) const_time_select(mask, (unsigned int) true_val, |
| 145 |
(unsigned int) false_val); |
| 146 |
} |
| 147 |
|
| 148 |
|
| 149 |
/** |
| 150 |
* const_time_select_bin - Constant time binary buffer selection copy |
| 151 |
* @mask: 0 (false) or -1 (true) to identify which value to copy |
| 152 |
* @true_val: Buffer to copy for the true case |
| 153 |
* @false_val: Buffer to copy for the false case |
| 154 |
* @len: Number of octets to copy |
| 155 |
* @dst: Destination buffer for the copy |
| 156 |
* |
| 157 |
* This function copies the specified buffer into the destination buffer using |
| 158 |
* operations with identical memory access pattern regardless of which buffer |
| 159 |
* is being copied. |
| 160 |
*/ |
| 161 |
static inline void const_time_select_bin(u8 mask, const u8 *true_val, |
| 162 |
const u8 *false_val, size_t len, |
| 163 |
u8 *dst) |
| 164 |
{ |
| 165 |
size_t i; |
| 166 |
|
| 167 |
for (i = 0; i < len; i++) |
| 168 |
dst[i] = const_time_select_u8(mask, true_val[i], false_val[i]); |
| 169 |
} |
| 170 |
|
| 171 |
|
| 172 |
static inline int const_time_memcmp(const void *a, const void *b, size_t len) |
| 173 |
{ |
| 174 |
const u8 *aa = a; |
| 175 |
const u8 *bb = b; |
| 176 |
int diff, res = 0; |
| 177 |
unsigned int mask; |
| 178 |
|
| 179 |
if (len == 0) |
| 180 |
return 0; |
| 181 |
do { |
| 182 |
len--; |
| 183 |
diff = (int) aa[len] - (int) bb[len]; |
| 184 |
mask = const_time_is_zero((unsigned int) diff); |
| 185 |
res = const_time_select_int(mask, res, diff); |
| 186 |
} while (len); |
| 187 |
|
| 188 |
return res; |
| 189 |
} |
| 190 |
|
| 191 |
#endif /* CONST_TIME_H */ |