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