blob: a5284cb7a61aa390273ec6a57f8be7ab3390da92 [file] [log] [blame]
Dave Rodgman40a41d02023-05-17 11:59:56 +01001/**
2 * Constant-time functions
3 *
4 * For readability, the static inline definitions are here, and
5 * constant_time_internal.h has only the declarations.
6 *
7 * This results in duplicate declarations of the form:
8 * static inline void f() { ... }
9 * static inline void f();
10 * when constant_time_internal.h is included. This appears to behave
11 * exactly as if the declaration-without-definition was not present.
12 *
13 * Copyright The Mbed TLS Contributors
14 * SPDX-License-Identifier: Apache-2.0
15 *
16 * Licensed under the Apache License, Version 2.0 (the "License"); you may
17 * not use this file except in compliance with the License.
18 * You may obtain a copy of the License at
19 *
20 * http://www.apache.org/licenses/LICENSE-2.0
21 *
22 * Unless required by applicable law or agreed to in writing, software
23 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
24 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
25 * See the License for the specific language governing permissions and
26 * limitations under the License.
27 */
28
29#ifndef MBEDTLS_CONSTANT_TIME_IMPL_H
30#define MBEDTLS_CONSTANT_TIME_IMPL_H
31
32#include <stddef.h>
33
34#include "common.h"
35
36#if defined(MBEDTLS_BIGNUM_C)
37#include "mbedtls/bignum.h"
38#endif
39
Dave Rodgman205295c2023-08-01 14:10:56 +010040/* constant_time_impl.h contains all the static inline implementations,
41 * so that constant_time_internal.h is more readable.
42 *
43 * gcc generates warnings about duplicate declarations, so disable this
44 * warning.
45 */
46#ifdef __GNUC__
47 #pragma GCC diagnostic push
48 #pragma GCC diagnostic ignored "-Wredundant-decls"
49#endif
50
Dave Rodgman3d574da2023-07-31 16:54:00 +010051/* Disable asm under Memsan because it confuses Memsan and generates false errors */
52#if defined(MBEDTLS_TEST_CONSTANT_FLOW_MEMSAN)
53#define MBEDTLS_CT_NO_ASM
54#elif defined(__has_feature)
55#if __has_feature(memory_sanitizer)
56#define MBEDTLS_CT_NO_ASM
57#endif
58#endif
Dave Rodgman40a41d02023-05-17 11:59:56 +010059
60/* armcc5 --gnu defines __GNUC__ but doesn't support GNU's extended asm */
61#if defined(MBEDTLS_HAVE_ASM) && defined(__GNUC__) && (!defined(__ARMCC_VERSION) || \
Dave Rodgman3d574da2023-07-31 16:54:00 +010062 __ARMCC_VERSION >= 6000000) && !defined(MBEDTLS_CT_NO_ASM)
Dave Rodgman40a41d02023-05-17 11:59:56 +010063#define MBEDTLS_CT_ASM
64#if (defined(__arm__) || defined(__thumb__) || defined(__thumb2__))
65#define MBEDTLS_CT_ARM_ASM
66#elif defined(__aarch64__)
67#define MBEDTLS_CT_AARCH64_ASM
68#endif
69#endif
70
71#define MBEDTLS_CT_SIZE (sizeof(mbedtls_ct_uint_t) * 8)
72
73
74/* ============================================================================
75 * Core const-time primitives
76 */
77
Dave Rodgman2894d002023-06-08 17:52:21 +010078/* Ensure that the compiler cannot know the value of x (i.e., cannot optimise
Dave Rodgman40a41d02023-05-17 11:59:56 +010079 * based on its value) after this function is called.
80 *
81 * If we are not using assembly, this will be fairly inefficient, so its use
82 * should be minimised.
83 */
Dave Rodgman2894d002023-06-08 17:52:21 +010084
85#if !defined(MBEDTLS_CT_ASM)
Dave Rodgman58c80f42023-06-12 18:19:46 +010086extern volatile mbedtls_ct_uint_t mbedtls_ct_zero;
Dave Rodgman2894d002023-06-08 17:52:21 +010087#endif
88
Dave Rodgman93cec452023-07-31 12:30:26 +010089/**
90 * \brief Ensure that a value cannot be known at compile time.
91 *
92 * \param x The value to hide from the compiler.
93 * \return The same value that was passed in, such that the compiler
94 * cannot prove its value (even for calls of the form
95 * x = mbedtls_ct_compiler_opaque(1), x will be unknown).
96 *
97 * \note This is mainly used in constructing mbedtls_ct_condition_t
98 * values and performing operations over them, to ensure that
99 * there is no way for the compiler to ever know anything about
100 * the value of an mbedtls_ct_condition_t.
101 */
Dave Rodgman40a41d02023-05-17 11:59:56 +0100102static inline mbedtls_ct_uint_t mbedtls_ct_compiler_opaque(mbedtls_ct_uint_t x)
103{
104#if defined(MBEDTLS_CT_ASM)
105 asm volatile ("" : [x] "+r" (x) :);
106 return x;
107#else
Dave Rodgman2894d002023-06-08 17:52:21 +0100108 return x ^ mbedtls_ct_zero;
Dave Rodgman40a41d02023-05-17 11:59:56 +0100109#endif
110}
111
112/* Convert a number into a condition in constant time. */
113static inline mbedtls_ct_condition_t mbedtls_ct_bool(mbedtls_ct_uint_t x)
114{
115 /*
116 * Define mask-generation code that, as far as possible, will not use branches or conditional instructions.
117 *
118 * For some platforms / type sizes, we define assembly to assure this.
119 *
120 * Otherwise, we define a plain C fallback which (in May 2023) does not get optimised into
121 * conditional instructions or branches by trunk clang, gcc, or MSVC v19.
122 */
Dave Rodgmanc9ed5de2023-05-13 12:47:02 +0100123#if defined(MBEDTLS_CT_AARCH64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
124 mbedtls_ct_uint_t s;
125 asm volatile ("neg %x[s], %x[x] \n\t"
126 "orr %x[x], %x[s], %x[x] \n\t"
127 "asr %x[x], %x[x], 63"
128 :
129 [s] "=&r" (s),
130 [x] "+&r" (x)
131 :
132 :
133 );
134 return (mbedtls_ct_condition_t) x;
135#else
Dave Rodgman40a41d02023-05-17 11:59:56 +0100136 const mbedtls_ct_uint_t xo = mbedtls_ct_compiler_opaque(x);
137#if defined(_MSC_VER)
138 /* MSVC has a warning about unary minus on unsigned, but this is
139 * well-defined and precisely what we want to do here */
140#pragma warning( push )
141#pragma warning( disable : 4146 )
142#endif
143 return (mbedtls_ct_condition_t) (((mbedtls_ct_int_t) ((-xo) | -(xo >> 1))) >>
144 (MBEDTLS_CT_SIZE - 1));
145#if defined(_MSC_VER)
146#pragma warning( pop )
147#endif
Dave Rodgmanc9ed5de2023-05-13 12:47:02 +0100148#endif
Dave Rodgman40a41d02023-05-17 11:59:56 +0100149}
150
151static inline mbedtls_ct_uint_t mbedtls_ct_if(mbedtls_ct_condition_t condition,
152 mbedtls_ct_uint_t if1,
153 mbedtls_ct_uint_t if0)
154{
Dave Rodgmanc9ed5de2023-05-13 12:47:02 +0100155#if defined(MBEDTLS_CT_AARCH64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
156 asm volatile ("and %x[if1], %x[if1], %x[condition] \n\t"
157 "mvn %x[condition], %x[condition] \n\t"
158 "and %x[condition], %x[condition], %x[if0] \n\t"
159 "orr %x[condition], %x[if1], %x[condition]"
160 :
161 [condition] "+&r" (condition),
162 [if1] "+&r" (if1)
163 :
164 [if0] "r" (if0)
165 :
166 );
167 return (mbedtls_ct_uint_t) condition;
168#else
Dave Rodgman1c4eaa12023-05-17 12:22:59 +0100169 mbedtls_ct_condition_t not_cond =
Dave Rodgman40a41d02023-05-17 11:59:56 +0100170 (mbedtls_ct_condition_t) (~mbedtls_ct_compiler_opaque(condition));
Dave Rodgman1c4eaa12023-05-17 12:22:59 +0100171 return (mbedtls_ct_uint_t) ((condition & if1) | (not_cond & if0));
Dave Rodgmanc9ed5de2023-05-13 12:47:02 +0100172#endif
Dave Rodgman40a41d02023-05-17 11:59:56 +0100173}
174
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100175static inline mbedtls_ct_condition_t mbedtls_ct_uint_lt(mbedtls_ct_uint_t x, mbedtls_ct_uint_t y)
Dave Rodgman40a41d02023-05-17 11:59:56 +0100176{
Dave Rodgmanc9ed5de2023-05-13 12:47:02 +0100177#if defined(MBEDTLS_CT_AARCH64_ASM) && (defined(MBEDTLS_CT_SIZE_32) || defined(MBEDTLS_CT_SIZE_64))
178 uint64_t s1, s2;
179 asm volatile ("eor %x[s1], %x[y], %x[x] \n\t"
180 "sub %x[s2], %x[x], %x[y] \n\t"
181 "bic %x[s2], %x[s2], %[s1] \n\t"
182 "and %x[s1], %x[s1], %x[y] \n\t"
183 "orr %x[s1], %x[s2], %x[s1] \n\t"
184 "asr %x[x], %x[s1], 63"
185 : [s1] "=&r" (s1), [s2] "=&r" (s2), [x] "+r" (x)
186 : [y] "r" (y)
187 :
188 );
189 return (mbedtls_ct_condition_t) x;
190#else
Dave Rodgman40a41d02023-05-17 11:59:56 +0100191 /* Ensure that the compiler cannot optimise the following operations over x and y,
192 * even if it knows the value of x and y.
193 */
Dave Rodgman74e18eb2023-05-17 12:21:32 +0100194 const mbedtls_ct_uint_t xo = mbedtls_ct_compiler_opaque(x);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100195 const mbedtls_ct_uint_t yo = mbedtls_ct_compiler_opaque(y);
196 /*
197 * Check if the most significant bits (MSB) of the operands are different.
198 * cond is true iff the MSBs differ.
199 */
Dave Rodgman74e18eb2023-05-17 12:21:32 +0100200 mbedtls_ct_condition_t cond = mbedtls_ct_bool((xo ^ yo) >> (MBEDTLS_CT_SIZE - 1));
Dave Rodgman40a41d02023-05-17 11:59:56 +0100201
202 /*
203 * If the MSB are the same then the difference x-y will be negative (and
204 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
205 *
206 * If the MSB are different, then the operand with the MSB of 1 is the
207 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
208 * the MSB of y is 0.)
209 */
210
211 // Select either y, or x - y
Dave Rodgman74e18eb2023-05-17 12:21:32 +0100212 mbedtls_ct_uint_t ret = mbedtls_ct_if(cond, yo, (mbedtls_ct_uint_t) (xo - yo));
Dave Rodgman40a41d02023-05-17 11:59:56 +0100213
214 // Extract only the MSB of ret
215 ret = ret >> (MBEDTLS_CT_SIZE - 1);
216
217 // Convert to a condition (i.e., all bits set iff non-zero)
218 return mbedtls_ct_bool(ret);
Dave Rodgmanc9ed5de2023-05-13 12:47:02 +0100219#endif
Dave Rodgman40a41d02023-05-17 11:59:56 +0100220}
221
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100222static inline mbedtls_ct_condition_t mbedtls_ct_uint_ne(mbedtls_ct_uint_t x, mbedtls_ct_uint_t y)
Dave Rodgman40a41d02023-05-17 11:59:56 +0100223{
224 /* diff = 0 if x == y, non-zero otherwise */
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100225 const mbedtls_ct_uint_t diff = mbedtls_ct_compiler_opaque(x) ^ mbedtls_ct_compiler_opaque(y);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100226
227 /* all ones if x != y, 0 otherwise */
228 return mbedtls_ct_bool(diff);
229}
230
231static inline unsigned char mbedtls_ct_uchar_in_range_if(unsigned char low,
232 unsigned char high,
233 unsigned char c,
234 unsigned char t)
235{
236 const unsigned char co = (const unsigned char) mbedtls_ct_compiler_opaque(c);
237 const unsigned char to = (const unsigned char) mbedtls_ct_compiler_opaque(t);
238
239 /* low_mask is: 0 if low <= c, 0x...ff if low > c */
240 unsigned low_mask = ((unsigned) co - low) >> 8;
241 /* high_mask is: 0 if c <= high, 0x...ff if c > high */
242 unsigned high_mask = ((unsigned) high - co) >> 8;
243
244 return (unsigned char) (~(low_mask | high_mask)) & to;
245}
246
247
248/* ============================================================================
249 * Everything below here is trivial wrapper functions
250 */
251
Dave Rodgman40a41d02023-05-17 11:59:56 +0100252static inline size_t mbedtls_ct_size_if(mbedtls_ct_condition_t condition,
253 size_t if1,
254 size_t if0)
255{
256 return (size_t) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) if1, (mbedtls_ct_uint_t) if0);
257}
258
Dave Rodgman2b4486a2023-05-17 15:51:59 +0100259static inline unsigned mbedtls_ct_uint_if(mbedtls_ct_condition_t condition,
Dave Rodgman40a41d02023-05-17 11:59:56 +0100260 unsigned if1,
261 unsigned if0)
262{
263 return (unsigned) mbedtls_ct_if(condition, (mbedtls_ct_uint_t) if1, (mbedtls_ct_uint_t) if0);
264}
265
266#if defined(MBEDTLS_BIGNUM_C)
267
Dave Rodgman585f7f72023-05-17 17:45:33 +0100268static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if(mbedtls_ct_condition_t condition,
269 mbedtls_mpi_uint if1,
Dave Rodgman40a41d02023-05-17 11:59:56 +0100270 mbedtls_mpi_uint if0)
271{
272 return (mbedtls_mpi_uint) mbedtls_ct_if(condition,
273 (mbedtls_ct_uint_t) if1,
274 (mbedtls_ct_uint_t) if0);
275}
276
277#endif
278
Dave Rodgman98ddc012023-08-10 12:11:31 +0100279static inline size_t mbedtls_ct_size_if_else_0(mbedtls_ct_condition_t condition, size_t if1)
Dave Rodgman40a41d02023-05-17 11:59:56 +0100280{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100281 return (size_t) (condition & if1);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100282}
283
Dave Rodgman98ddc012023-08-10 12:11:31 +0100284static inline unsigned mbedtls_ct_uint_if_else_0(mbedtls_ct_condition_t condition, unsigned if1)
Dave Rodgman40a41d02023-05-17 11:59:56 +0100285{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100286 return (unsigned) (condition & if1);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100287}
288
289#if defined(MBEDTLS_BIGNUM_C)
290
Dave Rodgman98ddc012023-08-10 12:11:31 +0100291static inline mbedtls_mpi_uint mbedtls_ct_mpi_uint_if_else_0(mbedtls_ct_condition_t condition,
292 mbedtls_mpi_uint if1)
Dave Rodgman40a41d02023-05-17 11:59:56 +0100293{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100294 return (mbedtls_mpi_uint) (condition & if1);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100295}
296
297#endif /* MBEDTLS_BIGNUM_C */
298
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100299static inline mbedtls_ct_condition_t mbedtls_ct_uint_eq(mbedtls_ct_uint_t x,
Dave Rodgman585f7f72023-05-17 17:45:33 +0100300 mbedtls_ct_uint_t y)
301{
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100302 return ~mbedtls_ct_uint_ne(x, y);
Dave Rodgman585f7f72023-05-17 17:45:33 +0100303}
304
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100305static inline mbedtls_ct_condition_t mbedtls_ct_uint_gt(mbedtls_ct_uint_t x,
Dave Rodgman40a41d02023-05-17 11:59:56 +0100306 mbedtls_ct_uint_t y)
307{
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100308 return mbedtls_ct_uint_lt(y, x);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100309}
310
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100311static inline mbedtls_ct_condition_t mbedtls_ct_uint_ge(mbedtls_ct_uint_t x,
Dave Rodgman40a41d02023-05-17 11:59:56 +0100312 mbedtls_ct_uint_t y)
313{
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100314 return ~mbedtls_ct_uint_lt(x, y);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100315}
316
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100317static inline mbedtls_ct_condition_t mbedtls_ct_uint_le(mbedtls_ct_uint_t x,
Dave Rodgman40a41d02023-05-17 11:59:56 +0100318 mbedtls_ct_uint_t y)
319{
Dave Rodgmanb7825ce2023-08-10 11:58:18 +0100320 return ~mbedtls_ct_uint_gt(x, y);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100321}
322
323static inline mbedtls_ct_condition_t mbedtls_ct_bool_xor(mbedtls_ct_condition_t x,
324 mbedtls_ct_condition_t y)
325{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100326 return (mbedtls_ct_condition_t) (x ^ y);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100327}
328
329static inline mbedtls_ct_condition_t mbedtls_ct_bool_and(mbedtls_ct_condition_t x,
330 mbedtls_ct_condition_t y)
331{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100332 return (mbedtls_ct_condition_t) (x & y);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100333}
334
335static inline mbedtls_ct_condition_t mbedtls_ct_bool_or(mbedtls_ct_condition_t x,
336 mbedtls_ct_condition_t y)
337{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100338 return (mbedtls_ct_condition_t) (x | y);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100339}
340
341static inline mbedtls_ct_condition_t mbedtls_ct_bool_not(mbedtls_ct_condition_t x)
342{
Dave Rodgmanfe76af22023-05-17 17:45:17 +0100343 return (mbedtls_ct_condition_t) (~x);
Dave Rodgman40a41d02023-05-17 11:59:56 +0100344}
345
Dave Rodgman205295c2023-08-01 14:10:56 +0100346#ifdef __GNUC__
347 #pragma GCC diagnostic pop
348#endif
349
Dave Rodgman40a41d02023-05-17 11:59:56 +0100350#endif /* MBEDTLS_CONSTANT_TIME_IMPL_H */