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