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 */
const_time_fill_msb(unsigned int val)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 */
const_time_is_zero(unsigned int val)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 */
const_time_eq(unsigned int a,unsigned int 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 */
const_time_eq_u8(unsigned int a,unsigned int 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 */
const_time_eq_bin(const void * a,const void * b,size_t len)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 */
const_time_select(unsigned int mask,unsigned int true_val,unsigned int false_val)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 */
const_time_select_int(unsigned int mask,int true_val,int false_val)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 */
const_time_select_u8(u8 mask,u8 true_val,u8 false_val)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 */
const_time_select_s8(u8 mask,s8 true_val,s8 false_val)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 */
const_time_select_bin(u8 mask,const u8 * true_val,const u8 * false_val,size_t len,u8 * dst)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
const_time_memcmp(const void * a,const void * b,size_t len)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