blob: 98f69db7110f2ccd9fad0ea329e6d63eb2e15a50 [file] [log] [blame]
gabor-mezei-arm90559722021-07-12 16:31:22 +02001/**
2 * Constant-time functions
3 *
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20#include "common.h"
gabor-mezei-arm944c1072021-09-27 11:28:54 +020021#include "constant_time.h"
gabor-mezei-armcb4317b2021-09-27 14:28:31 +020022#include "mbedtls/error.h"
gabor-mezei-armd5a392a2021-09-29 10:50:31 +020023#include "mbedtls/platform_util.h"
gabor-mezei-arm944c1072021-09-27 11:28:54 +020024
gabor-mezei-arm097d4f52021-09-27 12:55:33 +020025#if defined(MBEDTLS_BIGNUM_C)
26#include "mbedtls/bignum.h"
27#endif
28
gabor-mezei-armcb4317b2021-09-27 14:28:31 +020029#if defined(MBEDTLS_SSL_TLS_C)
30#include "mbedtls/ssl_internal.h"
31#endif
32
gabor-mezei-armd5a392a2021-09-29 10:50:31 +020033#if defined(MBEDTLS_RSA_C)
34#include "mbedtls/rsa.h"
35#endif
36
gabor-mezei-armf52941e2021-09-27 16:11:12 +020037#include <string.h>
gabor-mezei-arm097d4f52021-09-27 12:55:33 +020038
gabor-mezei-arm378e7eb2021-07-19 15:19:19 +020039int mbedtls_cf_memcmp( const void *a,
40 const void *b,
41 size_t n )
gabor-mezei-arm944c1072021-09-27 11:28:54 +020042{
43 size_t i;
44 volatile const unsigned char *A = (volatile const unsigned char *) a;
45 volatile const unsigned char *B = (volatile const unsigned char *) b;
46 volatile unsigned char diff = 0;
47
48 for( i = 0; i < n; i++ )
49 {
50 /* Read volatile data in order before computing diff.
51 * This avoids IAR compiler warning:
52 * 'the order of volatile accesses is undefined ..' */
53 unsigned char x = A[i], y = B[i];
54 diff |= x ^ y;
55 }
56
gabor-mezei-arm944c1072021-09-27 11:28:54 +020057 return( (int)diff );
58}
59
gabor-mezei-armc11cac92021-09-27 11:40:03 +020060unsigned mbedtls_cf_uint_mask( unsigned value )
61{
62 /* MSVC has a warning about unary minus on unsigned, but this is
63 * well-defined and precisely what we want to do here */
64#if defined(_MSC_VER)
65#pragma warning( push )
66#pragma warning( disable : 4146 )
67#endif
68 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
69#if defined(_MSC_VER)
70#pragma warning( pop )
71#endif
72}
gabor-mezei-armd361ccd2021-09-27 11:49:42 +020073
gabor-mezei-arm2f2c0be2021-08-10 20:56:21 +020074size_t mbedtls_cf_size_mask( size_t value )
gabor-mezei-armd361ccd2021-09-27 11:49:42 +020075{
76 /* MSVC has a warning about unary minus on unsigned integer types,
77 * but this is well-defined and precisely what we want to do here. */
78#if defined(_MSC_VER)
79#pragma warning( push )
80#pragma warning( disable : 4146 )
81#endif
gabor-mezei-arm2f2c0be2021-08-10 20:56:21 +020082 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
gabor-mezei-armd361ccd2021-09-27 11:49:42 +020083#if defined(_MSC_VER)
84#pragma warning( pop )
85#endif
86}
gabor-mezei-arm4d6b1462021-09-27 11:53:54 +020087
gabor-mezei-arm60febd52021-08-11 15:07:02 +020088#if defined(MBEDTLS_BIGNUM_C)
89
90mbedtls_mpi_uint mbedtls_cf_mpi_uint_mask( mbedtls_mpi_uint value )
91{
92 /* MSVC has a warning about unary minus on unsigned, but this is
93 * well-defined and precisely what we want to do here */
94#if defined(_MSC_VER)
95#pragma warning( push )
96#pragma warning( disable : 4146 )
97#endif
98 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
99#if defined(_MSC_VER)
100#pragma warning( pop )
101#endif
102}
103
104#endif /* MBEDTLS_BIGNUM_C */
105
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200106size_t mbedtls_cf_size_mask_lt( size_t x,
107 size_t y )
gabor-mezei-arm4d6b1462021-09-27 11:53:54 +0200108{
109 /* This has the most significant bit set if and only if x < y */
110 const size_t sub = x - y;
111
112 /* sub1 = (x < y) ? 1 : 0 */
113 const size_t sub1 = sub >> ( sizeof( sub ) * 8 - 1 );
114
115 /* mask = (x < y) ? 0xff... : 0x00... */
116 const size_t mask = mbedtls_cf_size_mask( sub1 );
117
118 return( mask );
119}
gabor-mezei-arma2bcabc2021-09-27 11:58:31 +0200120
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200121size_t mbedtls_cf_size_mask_ge( size_t x,
122 size_t y )
gabor-mezei-arma2bcabc2021-09-27 11:58:31 +0200123{
124 return( ~mbedtls_cf_size_mask_lt( x, y ) );
125}
gabor-mezei-arm96584dd2021-09-27 12:15:19 +0200126
gabor-mezei-arm1ffd0cc2021-08-11 17:28:49 +0200127unsigned mbedtls_cf_size_bool_eq( size_t x,
128 size_t y )
gabor-mezei-arm96584dd2021-09-27 12:15:19 +0200129{
130 /* diff = 0 if x == y, non-zero otherwise */
131 const size_t diff = x ^ y;
132
133 /* MSVC has a warning about unary minus on unsigned integer types,
134 * but this is well-defined and precisely what we want to do here. */
135#if defined(_MSC_VER)
136#pragma warning( push )
137#pragma warning( disable : 4146 )
138#endif
139
140 /* diff_msb's most significant bit is equal to x != y */
141 const size_t diff_msb = ( diff | (size_t) -diff );
142
143#if defined(_MSC_VER)
144#pragma warning( pop )
145#endif
146
147 /* diff1 = (x != y) ? 1 : 0 */
gabor-mezei-arm1ffd0cc2021-08-11 17:28:49 +0200148 const unsigned diff1 = diff_msb >> ( sizeof( diff_msb ) * 8 - 1 );
gabor-mezei-arm96584dd2021-09-27 12:15:19 +0200149
150 return( 1 ^ diff1 );
151}
gabor-mezei-arm9d7bf092021-09-27 12:25:07 +0200152
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200153unsigned mbedtls_cf_size_gt( size_t x,
154 size_t y )
gabor-mezei-arm9d7bf092021-09-27 12:25:07 +0200155{
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200156 /* Return the sign bit (1 for negative) of (y - x). */
157 return( ( y - x ) >> ( sizeof( size_t ) * 8 - 1 ) );
gabor-mezei-arm9d7bf092021-09-27 12:25:07 +0200158}
gabor-mezei-arm097d4f52021-09-27 12:55:33 +0200159
160#if defined(MBEDTLS_BIGNUM_C)
161
gabor-mezei-arm097d4f52021-09-27 12:55:33 +0200162unsigned mbedtls_cf_mpi_uint_lt( const mbedtls_mpi_uint x,
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200163 const mbedtls_mpi_uint y )
gabor-mezei-arm097d4f52021-09-27 12:55:33 +0200164{
165 mbedtls_mpi_uint ret;
166 mbedtls_mpi_uint cond;
167
168 /*
169 * Check if the most significant bits (MSB) of the operands are different.
170 */
171 cond = ( x ^ y );
172 /*
173 * If the MSB are the same then the difference x-y will be negative (and
174 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
175 */
176 ret = ( x - y ) & ~cond;
177 /*
178 * If the MSB are different, then the operand with the MSB of 1 is the
179 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
180 * the MSB of y is 0.)
181 */
182 ret |= y & cond;
183
184
185 ret = ret >> ( sizeof( mbedtls_mpi_uint ) * 8 - 1 );
186
187 return (unsigned) ret;
188}
189
190#endif /* MBEDTLS_BIGNUM_C */
gabor-mezei-arm75332532021-09-27 12:59:30 +0200191
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200192unsigned mbedtls_cf_uint_if( unsigned condition,
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200193 unsigned if1,
194 unsigned if0 )
gabor-mezei-arm75332532021-09-27 12:59:30 +0200195{
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200196 unsigned mask = mbedtls_cf_uint_mask( condition );
gabor-mezei-arm75332532021-09-27 12:59:30 +0200197 return( ( mask & if1 ) | (~mask & if0 ) );
198}
gabor-mezei-arm5cec8b42021-09-27 13:03:57 +0200199
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200200size_t mbedtls_cf_size_if( unsigned condition,
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200201 size_t if1,
202 size_t if0 )
gabor-mezei-armbc3a2882021-09-27 15:47:00 +0200203{
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200204 size_t mask = mbedtls_cf_size_mask( condition );
gabor-mezei-armbc3a2882021-09-27 15:47:00 +0200205 return( ( mask & if1 ) | (~mask & if0 ) );
206}
207
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200208int mbedtls_cf_cond_select_sign( unsigned char condition,
209 int if1,
210 int if0 )
gabor-mezei-arm5cec8b42021-09-27 13:03:57 +0200211{
212 /* In order to avoid questions about what we can reasonnably assume about
213 * the representations of signed integers, move everything to unsigned
214 * by taking advantage of the fact that a and b are either +1 or -1. */
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200215 unsigned uif1 = if1 + 1;
216 unsigned uif0 = if0 + 1;
gabor-mezei-arm5cec8b42021-09-27 13:03:57 +0200217
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200218 /* condition was 0 or 1, mask is 0 or 2 as are ua and ub */
219 const unsigned mask = condition << 1;
gabor-mezei-arm5cec8b42021-09-27 13:03:57 +0200220
221 /* select ua or ub */
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200222 unsigned ur = ( uif0 & ~mask ) | ( uif1 & mask );
gabor-mezei-arm5cec8b42021-09-27 13:03:57 +0200223
224 /* ur is now 0 or 2, convert back to -1 or +1 */
225 return( (int) ur - 1 );
226}
gabor-mezei-arm043192d2021-09-27 13:17:15 +0200227
228#if defined(MBEDTLS_BIGNUM_C)
229
gabor-mezei-arm043192d2021-09-27 13:17:15 +0200230void mbedtls_cf_mpi_uint_cond_assign( size_t n,
231 mbedtls_mpi_uint *dest,
232 const mbedtls_mpi_uint *src,
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200233 unsigned char condition )
gabor-mezei-arm043192d2021-09-27 13:17:15 +0200234{
235 size_t i;
236
237 /* MSVC has a warning about unary minus on unsigned integer types,
238 * but this is well-defined and precisely what we want to do here. */
239#if defined(_MSC_VER)
240#pragma warning( push )
241#pragma warning( disable : 4146 )
242#endif
243
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200244 /* all-bits 1 if condition is 1, all-bits 0 if condition is 0 */
245 const mbedtls_mpi_uint mask = -condition;
gabor-mezei-arm043192d2021-09-27 13:17:15 +0200246
247#if defined(_MSC_VER)
248#pragma warning( pop )
249#endif
250
251 for( i = 0; i < n; i++ )
252 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
253}
254
255#endif /* MBEDTLS_BIGNUM_C */
gabor-mezei-arm7b23c0b2021-09-27 13:31:06 +0200256
gabor-mezei-arm7b23c0b2021-09-27 13:31:06 +0200257void mbedtls_cf_mem_move_to_left( void *start,
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200258 size_t total,
259 size_t offset )
gabor-mezei-arm7b23c0b2021-09-27 13:31:06 +0200260{
261 volatile unsigned char *buf = start;
262 size_t i, n;
263 if( total == 0 )
264 return;
265 for( i = 0; i < total; i++ )
266 {
267 unsigned no_op = mbedtls_cf_size_gt( total - offset, i );
268 /* The first `total - offset` passes are a no-op. The last
269 * `offset` passes shift the data one byte to the left and
270 * zero out the last byte. */
271 for( n = 0; n < total - 1; n++ )
272 {
273 unsigned char current = buf[n];
274 unsigned char next = buf[n+1];
275 buf[n] = mbedtls_cf_uint_if( no_op, current, next );
276 }
277 buf[total-1] = mbedtls_cf_uint_if( no_op, buf[total-1], 0 );
278 }
279}
gabor-mezei-armee06feb2021-09-27 13:34:25 +0200280
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200281void mbedtls_cf_memcpy_if_eq( unsigned char *dest,
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200282 const unsigned char *src,
283 size_t len,
284 size_t c1,
285 size_t c2 )
gabor-mezei-armee06feb2021-09-27 13:34:25 +0200286{
287 /* mask = c1 == c2 ? 0xff : 0x00 */
288 const size_t equal = mbedtls_cf_size_bool_eq( c1, c2 );
289 const unsigned char mask = (unsigned char) mbedtls_cf_size_mask( equal );
290
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200291 /* dest[i] = c1 == c2 ? src[i] : dest[i] */
gabor-mezei-armee06feb2021-09-27 13:34:25 +0200292 for( size_t i = 0; i < len; i++ )
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200293 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
gabor-mezei-armee06feb2021-09-27 13:34:25 +0200294}
gabor-mezei-arm0f7b9e42021-09-27 13:57:45 +0200295
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200296void mbedtls_cf_memcpy_offset( unsigned char *dst,
297 const unsigned char *src_base,
298 size_t offset_secret,
299 size_t offset_min,
300 size_t offset_max,
301 size_t len )
gabor-mezei-arm0f7b9e42021-09-27 13:57:45 +0200302{
303 size_t offset;
304
305 for( offset = offset_min; offset <= offset_max; offset++ )
306 {
307 mbedtls_cf_memcpy_if_eq( dst, src_base + offset, len,
308 offset, offset_secret );
309 }
310}
gabor-mezei-armcb4317b2021-09-27 14:28:31 +0200311
312#if defined(MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC)
313
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200314int mbedtls_cf_hmac( mbedtls_md_context_t *ctx,
315 const unsigned char *add_data,
316 size_t add_data_len,
317 const unsigned char *data,
318 size_t data_len_secret,
319 size_t min_data_len,
320 size_t max_data_len,
321 unsigned char *output )
gabor-mezei-armcb4317b2021-09-27 14:28:31 +0200322{
323 /*
324 * This function breaks the HMAC abstraction and uses the md_clone()
325 * extension to the MD API in order to get constant-flow behaviour.
326 *
327 * HMAC(msg) is defined as HASH(okey + HASH(ikey + msg)) where + means
328 * concatenation, and okey/ikey are the XOR of the key with some fixed bit
329 * patterns (see RFC 2104, sec. 2), which are stored in ctx->hmac_ctx.
330 *
331 * We'll first compute inner_hash = HASH(ikey + msg) by hashing up to
332 * minlen, then cloning the context, and for each byte up to maxlen
333 * finishing up the hash computation, keeping only the correct result.
334 *
335 * Then we only need to compute HASH(okey + inner_hash) and we're done.
336 */
337 const mbedtls_md_type_t md_alg = mbedtls_md_get_type( ctx->md_info );
338 /* TLS 1.0-1.2 only support SHA-384, SHA-256, SHA-1, MD-5,
339 * all of which have the same block size except SHA-384. */
340 const size_t block_size = md_alg == MBEDTLS_MD_SHA384 ? 128 : 64;
341 const unsigned char * const ikey = ctx->hmac_ctx;
342 const unsigned char * const okey = ikey + block_size;
343 const size_t hash_size = mbedtls_md_get_size( ctx->md_info );
344
345 unsigned char aux_out[MBEDTLS_MD_MAX_SIZE];
346 mbedtls_md_context_t aux;
347 size_t offset;
348 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
349
350 mbedtls_md_init( &aux );
351
352#define MD_CHK( func_call ) \
353 do { \
354 ret = (func_call); \
355 if( ret != 0 ) \
356 goto cleanup; \
357 } while( 0 )
358
359 MD_CHK( mbedtls_md_setup( &aux, ctx->md_info, 0 ) );
360
361 /* After hmac_start() of hmac_reset(), ikey has already been hashed,
362 * so we can start directly with the message */
363 MD_CHK( mbedtls_md_update( ctx, add_data, add_data_len ) );
364 MD_CHK( mbedtls_md_update( ctx, data, min_data_len ) );
365
366 /* For each possible length, compute the hash up to that point */
367 for( offset = min_data_len; offset <= max_data_len; offset++ )
368 {
369 MD_CHK( mbedtls_md_clone( &aux, ctx ) );
370 MD_CHK( mbedtls_md_finish( &aux, aux_out ) );
371 /* Keep only the correct inner_hash in the output buffer */
372 mbedtls_cf_memcpy_if_eq( output, aux_out, hash_size,
373 offset, data_len_secret );
374
375 if( offset < max_data_len )
376 MD_CHK( mbedtls_md_update( ctx, data + offset, 1 ) );
377 }
378
379 /* The context needs to finish() before it starts() again */
380 MD_CHK( mbedtls_md_finish( ctx, aux_out ) );
381
382 /* Now compute HASH(okey + inner_hash) */
383 MD_CHK( mbedtls_md_starts( ctx ) );
384 MD_CHK( mbedtls_md_update( ctx, okey, block_size ) );
385 MD_CHK( mbedtls_md_update( ctx, output, hash_size ) );
386 MD_CHK( mbedtls_md_finish( ctx, output ) );
387
388 /* Done, get ready for next time */
389 MD_CHK( mbedtls_md_hmac_reset( ctx ) );
390
391#undef MD_CHK
392
393cleanup:
394 mbedtls_md_free( &aux );
395 return( ret );
396}
397
398#endif /* MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC */
gabor-mezei-armb8caeee2021-09-27 15:33:35 +0200399
400#if defined(MBEDTLS_BIGNUM_C)
401
402#define MPI_VALIDATE_RET( cond ) \
403 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
404
405/*
406 * Conditionally assign X = Y, without leaking information
407 * about whether the assignment was made or not.
408 * (Leaking information about the respective sizes of X and Y is ok however.)
409 */
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200410int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X,
411 const mbedtls_mpi *Y,
412 unsigned char assign )
gabor-mezei-armb8caeee2021-09-27 15:33:35 +0200413{
414 int ret = 0;
415 size_t i;
416 mbedtls_mpi_uint limb_mask;
417 MPI_VALIDATE_RET( X != NULL );
418 MPI_VALIDATE_RET( Y != NULL );
419
gabor-mezei-armb8caeee2021-09-27 15:33:35 +0200420 /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */
gabor-mezei-arm60febd52021-08-11 15:07:02 +0200421 limb_mask = mbedtls_cf_mpi_uint_mask( assign );;
gabor-mezei-armb8caeee2021-09-27 15:33:35 +0200422
423 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
424
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200425 X->s = mbedtls_cf_cond_select_sign( assign, Y->s, X->s );
gabor-mezei-armb8caeee2021-09-27 15:33:35 +0200426
427 mbedtls_cf_mpi_uint_cond_assign( Y->n, X->p, Y->p, assign );
428
429 for( i = Y->n; i < X->n; i++ )
430 X->p[i] &= ~limb_mask;
431
432cleanup:
433 return( ret );
434}
435
gabor-mezei-arm58fc8a62021-09-27 15:37:50 +0200436/*
437 * Conditionally swap X and Y, without leaking information
438 * about whether the swap was made or not.
439 * Here it is not ok to simply swap the pointers, which whould lead to
440 * different memory access patterns when X and Y are used afterwards.
441 */
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200442int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X,
443 mbedtls_mpi *Y,
444 unsigned char swap )
gabor-mezei-arm58fc8a62021-09-27 15:37:50 +0200445{
446 int ret, s;
447 size_t i;
448 mbedtls_mpi_uint limb_mask;
449 mbedtls_mpi_uint tmp;
450 MPI_VALIDATE_RET( X != NULL );
451 MPI_VALIDATE_RET( Y != NULL );
452
453 if( X == Y )
454 return( 0 );
455
gabor-mezei-arm58fc8a62021-09-27 15:37:50 +0200456 /* all-bits 1 if swap is 1, all-bits 0 if swap is 0 */
gabor-mezei-arm60febd52021-08-11 15:07:02 +0200457 limb_mask = mbedtls_cf_mpi_uint_mask( swap );
gabor-mezei-arm58fc8a62021-09-27 15:37:50 +0200458
459 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
460 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
461
462 s = X->s;
gabor-mezei-arm5e488242021-08-10 20:36:09 +0200463 X->s = mbedtls_cf_cond_select_sign( swap, Y->s, X->s );
464 Y->s = mbedtls_cf_cond_select_sign( swap, s, Y->s );
gabor-mezei-arm58fc8a62021-09-27 15:37:50 +0200465
466
467 for( i = 0; i < X->n; i++ )
468 {
469 tmp = X->p[i];
470 X->p[i] = ( X->p[i] & ~limb_mask ) | ( Y->p[i] & limb_mask );
471 Y->p[i] = ( Y->p[i] & ~limb_mask ) | ( tmp & limb_mask );
472 }
473
474cleanup:
475 return( ret );
476}
477
gabor-mezei-armb10301d2021-09-27 15:41:30 +0200478/*
479 * Compare signed values in constant time
480 */
gabor-mezei-arm04087df2021-09-27 16:29:52 +0200481int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X,
482 const mbedtls_mpi *Y,
483 unsigned *ret )
gabor-mezei-armb10301d2021-09-27 15:41:30 +0200484{
485 size_t i;
486 /* The value of any of these variables is either 0 or 1 at all times. */
487 unsigned cond, done, X_is_negative, Y_is_negative;
488
489 MPI_VALIDATE_RET( X != NULL );
490 MPI_VALIDATE_RET( Y != NULL );
491 MPI_VALIDATE_RET( ret != NULL );
492
493 if( X->n != Y->n )
494 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
495
496 /*
497 * Set sign_N to 1 if N >= 0, 0 if N < 0.
498 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
499 */
500 X_is_negative = ( X->s & 2 ) >> 1;
501 Y_is_negative = ( Y->s & 2 ) >> 1;
502
503 /*
504 * If the signs are different, then the positive operand is the bigger.
505 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
506 * is false if X is positive (X_is_negative == 0).
507 */
508 cond = ( X_is_negative ^ Y_is_negative );
509 *ret = cond & X_is_negative;
510
511 /*
512 * This is a constant-time function. We might have the result, but we still
513 * need to go through the loop. Record if we have the result already.
514 */
515 done = cond;
516
517 for( i = X->n; i > 0; i-- )
518 {
519 /*
520 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
521 * X and Y are negative.
522 *
523 * Again even if we can make a decision, we just mark the result and
524 * the fact that we are done and continue looping.
525 */
526 cond = mbedtls_cf_mpi_uint_lt( Y->p[i - 1], X->p[i - 1] );
527 *ret |= cond & ( 1 - done ) & X_is_negative;
528 done |= cond;
529
530 /*
531 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
532 * X and Y are positive.
533 *
534 * Again even if we can make a decision, we just mark the result and
535 * the fact that we are done and continue looping.
536 */
537 cond = mbedtls_cf_mpi_uint_lt( X->p[i - 1], Y->p[i - 1] );
538 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
539 done |= cond;
540 }
541
542 return( 0 );
543}
544
gabor-mezei-armb8caeee2021-09-27 15:33:35 +0200545#endif /* MBEDTLS_BIGNUM_C */
gabor-mezei-armf52941e2021-09-27 16:11:12 +0200546
547#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)
548
549int mbedtls_cf_rsaes_pkcs1_v15_unpadding( int mode,
550 size_t ilen,
551 size_t *olen,
552 unsigned char *output,
553 size_t output_max_len,
554 unsigned char *buf )
555{
556 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
557 size_t i, plaintext_max_size;
558
559 /* The following variables take sensitive values: their value must
560 * not leak into the observable behavior of the function other than
561 * the designated outputs (output, olen, return value). Otherwise
562 * this would open the execution of the function to
563 * side-channel-based variants of the Bleichenbacher padding oracle
564 * attack. Potential side channels include overall timing, memory
565 * access patterns (especially visible to an adversary who has access
566 * to a shared memory cache), and branches (especially visible to
567 * an adversary who has access to a shared code cache or to a shared
568 * branch predictor). */
569 size_t pad_count = 0;
570 unsigned bad = 0;
571 unsigned char pad_done = 0;
572 size_t plaintext_size = 0;
573 unsigned output_too_large;
574
575 plaintext_max_size = mbedtls_cf_size_if( output_max_len > ilen - 11,
576 ilen - 11,
577 output_max_len );
578
579 /* Check and get padding length in constant time and constant
580 * memory trace. The first byte must be 0. */
581 bad |= buf[0];
582
583 if( mode == MBEDTLS_RSA_PRIVATE )
584 {
585 /* Decode EME-PKCS1-v1_5 padding: 0x00 || 0x02 || PS || 0x00
586 * where PS must be at least 8 nonzero bytes. */
587 bad |= buf[1] ^ MBEDTLS_RSA_CRYPT;
588
589 /* Read the whole buffer. Set pad_done to nonzero if we find
590 * the 0x00 byte and remember the padding length in pad_count. */
591 for( i = 2; i < ilen; i++ )
592 {
593 pad_done |= ((buf[i] | (unsigned char)-buf[i]) >> 7) ^ 1;
594 pad_count += ((pad_done | (unsigned char)-pad_done) >> 7) ^ 1;
595 }
596 }
597 else
598 {
599 /* Decode EMSA-PKCS1-v1_5 padding: 0x00 || 0x01 || PS || 0x00
600 * where PS must be at least 8 bytes with the value 0xFF. */
601 bad |= buf[1] ^ MBEDTLS_RSA_SIGN;
602
603 /* Read the whole buffer. Set pad_done to nonzero if we find
604 * the 0x00 byte and remember the padding length in pad_count.
605 * If there's a non-0xff byte in the padding, the padding is bad. */
606 for( i = 2; i < ilen; i++ )
607 {
608 pad_done |= mbedtls_cf_uint_if( buf[i], 0, 1 );
609 pad_count += mbedtls_cf_uint_if( pad_done, 0, 1 );
610 bad |= mbedtls_cf_uint_if( pad_done, 0, buf[i] ^ 0xFF );
611 }
612 }
613
614 /* If pad_done is still zero, there's no data, only unfinished padding. */
615 bad |= mbedtls_cf_uint_if( pad_done, 0, 1 );
616
617 /* There must be at least 8 bytes of padding. */
618 bad |= mbedtls_cf_size_gt( 8, pad_count );
619
620 /* If the padding is valid, set plaintext_size to the number of
621 * remaining bytes after stripping the padding. If the padding
622 * is invalid, avoid leaking this fact through the size of the
623 * output: use the maximum message size that fits in the output
624 * buffer. Do it without branches to avoid leaking the padding
625 * validity through timing. RSA keys are small enough that all the
626 * size_t values involved fit in unsigned int. */
627 plaintext_size = mbedtls_cf_uint_if(
628 bad, (unsigned) plaintext_max_size,
629 (unsigned) ( ilen - pad_count - 3 ) );
630
631 /* Set output_too_large to 0 if the plaintext fits in the output
632 * buffer and to 1 otherwise. */
633 output_too_large = mbedtls_cf_size_gt( plaintext_size,
634 plaintext_max_size );
635
636 /* Set ret without branches to avoid timing attacks. Return:
637 * - INVALID_PADDING if the padding is bad (bad != 0).
638 * - OUTPUT_TOO_LARGE if the padding is good but the decrypted
639 * plaintext does not fit in the output buffer.
640 * - 0 if the padding is correct. */
641 ret = - (int) mbedtls_cf_uint_if(
642 bad, - MBEDTLS_ERR_RSA_INVALID_PADDING,
643 mbedtls_cf_uint_if( output_too_large,
644 - MBEDTLS_ERR_RSA_OUTPUT_TOO_LARGE,
645 0 ) );
646
647 /* If the padding is bad or the plaintext is too large, zero the
648 * data that we're about to copy to the output buffer.
649 * We need to copy the same amount of data
650 * from the same buffer whether the padding is good or not to
651 * avoid leaking the padding validity through overall timing or
652 * through memory or cache access patterns. */
653 bad = mbedtls_cf_uint_mask( bad | output_too_large );
654 for( i = 11; i < ilen; i++ )
655 buf[i] &= ~bad;
656
657 /* If the plaintext is too large, truncate it to the buffer size.
658 * Copy anyway to avoid revealing the length through timing, because
659 * revealing the length is as bad as revealing the padding validity
660 * for a Bleichenbacher attack. */
661 plaintext_size = mbedtls_cf_uint_if( output_too_large,
662 (unsigned) plaintext_max_size,
663 (unsigned) plaintext_size );
664
665 /* Move the plaintext to the leftmost position where it can start in
666 * the working buffer, i.e. make it start plaintext_max_size from
667 * the end of the buffer. Do this with a memory access trace that
668 * does not depend on the plaintext size. After this move, the
669 * starting location of the plaintext is no longer sensitive
670 * information. */
671 mbedtls_cf_mem_move_to_left( buf + ilen - plaintext_max_size,
672 plaintext_max_size,
673 plaintext_max_size - plaintext_size );
674
675 /* Finally copy the decrypted plaintext plus trailing zeros into the output
676 * buffer. If output_max_len is 0, then output may be an invalid pointer
677 * and the result of memcpy() would be undefined; prevent undefined
678 * behavior making sure to depend only on output_max_len (the size of the
679 * user-provided output buffer), which is independent from plaintext
680 * length, validity of padding, success of the decryption, and other
681 * secrets. */
682 if( output_max_len != 0 )
683 memcpy( output, buf + ilen - plaintext_max_size, plaintext_max_size );
684
685 /* Report the amount of data we copied to the output buffer. In case
686 * of errors (bad padding or output too large), the value of *olen
687 * when this function returns is not specified. Making it equivalent
688 * to the good case limits the risks of leaking the padding validity. */
689 *olen = plaintext_size;
690
691 return( ret );
692}
693
694#endif /* MBEDTLS_PKCS1_V15 && MBEDTLS_RSA_C && ! MBEDTLS_RSA_ALT */