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 */ 192