blob: 2d9e91de92cac142b1ee479844bc147551d5040d [file] [log] [blame]
gabor-mezei-armd1125342021-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
Gabor Mezeieab90bc2021-10-18 16:09:41 +020020 /*
21 * The following functiona are implemented without using comparison operators, as those
22 * might be translated to branches by some compilers on some platforms.
23 */
24
gabor-mezei-armd1125342021-07-12 16:31:22 +020025#include "common.h"
gabor-mezei-armdb9a38c2021-09-27 11:28:54 +020026#include "constant_time.h"
gabor-mezei-arm1349ffd2021-09-27 14:28:31 +020027#include "mbedtls/error.h"
gabor-mezei-arm5b3a32d2021-09-29 10:50:31 +020028#include "mbedtls/platform_util.h"
gabor-mezei-armdb9a38c2021-09-27 11:28:54 +020029
gabor-mezei-arm3f90fd52021-09-27 12:55:33 +020030#if defined(MBEDTLS_BIGNUM_C)
31#include "mbedtls/bignum.h"
32#endif
33
gabor-mezei-arm1349ffd2021-09-27 14:28:31 +020034#if defined(MBEDTLS_SSL_TLS_C)
35#include "ssl_misc.h"
36#endif
37
gabor-mezei-arm5b3a32d2021-09-29 10:50:31 +020038#if defined(MBEDTLS_RSA_C)
39#include "mbedtls/rsa.h"
40#endif
41
gabor-mezei-armfdb71182021-09-27 16:11:12 +020042#include <string.h>
gabor-mezei-arm3f90fd52021-09-27 12:55:33 +020043
gabor-mezei-arm46025642021-07-19 15:19:19 +020044int mbedtls_cf_memcmp( const void *a,
45 const void *b,
46 size_t n )
gabor-mezei-armdb9a38c2021-09-27 11:28:54 +020047{
48 size_t i;
49 volatile const unsigned char *A = (volatile const unsigned char *) a;
50 volatile const unsigned char *B = (volatile const unsigned char *) b;
51 volatile unsigned char diff = 0;
52
53 for( i = 0; i < n; i++ )
54 {
55 /* Read volatile data in order before computing diff.
56 * This avoids IAR compiler warning:
57 * 'the order of volatile accesses is undefined ..' */
58 unsigned char x = A[i], y = B[i];
59 diff |= x ^ y;
60 }
61
gabor-mezei-armdb9a38c2021-09-27 11:28:54 +020062 return( (int)diff );
63}
64
gabor-mezei-arm340948e2021-09-27 11:40:03 +020065unsigned mbedtls_cf_uint_mask( unsigned value )
66{
67 /* MSVC has a warning about unary minus on unsigned, but this is
68 * well-defined and precisely what we want to do here */
69#if defined(_MSC_VER)
70#pragma warning( push )
71#pragma warning( disable : 4146 )
72#endif
73 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
74#if defined(_MSC_VER)
75#pragma warning( pop )
76#endif
77}
gabor-mezei-arm3733bf82021-09-27 11:49:42 +020078
gabor-mezei-arm396438c2021-08-10 20:56:21 +020079size_t mbedtls_cf_size_mask( size_t value )
gabor-mezei-arm3733bf82021-09-27 11:49:42 +020080{
81 /* MSVC has a warning about unary minus on unsigned integer types,
82 * but this is well-defined and precisely what we want to do here. */
83#if defined(_MSC_VER)
84#pragma warning( push )
85#pragma warning( disable : 4146 )
86#endif
gabor-mezei-arm396438c2021-08-10 20:56:21 +020087 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
gabor-mezei-arm3733bf82021-09-27 11:49:42 +020088#if defined(_MSC_VER)
89#pragma warning( pop )
90#endif
91}
gabor-mezei-armc76227d2021-09-27 11:53:54 +020092
gabor-mezei-arm9cb55692021-08-11 15:07:02 +020093#if defined(MBEDTLS_BIGNUM_C)
94
95mbedtls_mpi_uint mbedtls_cf_mpi_uint_mask( mbedtls_mpi_uint value )
96{
97 /* MSVC has a warning about unary minus on unsigned, but this is
98 * well-defined and precisely what we want to do here */
99#if defined(_MSC_VER)
100#pragma warning( push )
101#pragma warning( disable : 4146 )
102#endif
103 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
104#if defined(_MSC_VER)
105#pragma warning( pop )
106#endif
107}
108
109#endif /* MBEDTLS_BIGNUM_C */
110
Gabor Mezei1e642612021-10-18 16:05:50 +0200111/** Constant-flow mask generation for "less than" comparison:
112 * - if \p x < \p y, return all-bits 1, that is (size_t) -1
113 * - otherwise, return all bits 0, that is 0
114 *
115 * This function can be used to write constant-time code by replacing branches
116 * with bit operations using masks.
117 *
118 * \param x The first value to analyze.
119 * \param y The second value to analyze.
120 *
121 * \return All-bits-one if \p x is less than \p y, otherwise zero.
122 */
123static size_t mbedtls_cf_size_mask_lt( size_t x,
124 size_t y )
gabor-mezei-armc76227d2021-09-27 11:53:54 +0200125{
126 /* This has the most significant bit set if and only if x < y */
127 const size_t sub = x - y;
128
129 /* sub1 = (x < y) ? 1 : 0 */
130 const size_t sub1 = sub >> ( sizeof( sub ) * 8 - 1 );
131
132 /* mask = (x < y) ? 0xff... : 0x00... */
133 const size_t mask = mbedtls_cf_size_mask( sub1 );
134
135 return( mask );
136}
gabor-mezei-arm16fc57b2021-09-27 11:58:31 +0200137
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200138size_t mbedtls_cf_size_mask_ge( size_t x,
139 size_t y )
gabor-mezei-arm16fc57b2021-09-27 11:58:31 +0200140{
141 return( ~mbedtls_cf_size_mask_lt( x, y ) );
142}
gabor-mezei-arm8d1d5fd2021-09-27 12:15:19 +0200143
gabor-mezei-armb11a56e2021-08-11 17:28:49 +0200144unsigned mbedtls_cf_size_bool_eq( size_t x,
145 size_t y )
gabor-mezei-arm8d1d5fd2021-09-27 12:15:19 +0200146{
147 /* diff = 0 if x == y, non-zero otherwise */
148 const size_t diff = x ^ y;
149
150 /* MSVC has a warning about unary minus on unsigned integer types,
151 * but this is well-defined and precisely what we want to do here. */
152#if defined(_MSC_VER)
153#pragma warning( push )
154#pragma warning( disable : 4146 )
155#endif
156
157 /* diff_msb's most significant bit is equal to x != y */
158 const size_t diff_msb = ( diff | (size_t) -diff );
159
160#if defined(_MSC_VER)
161#pragma warning( pop )
162#endif
163
164 /* diff1 = (x != y) ? 1 : 0 */
gabor-mezei-armb11a56e2021-08-11 17:28:49 +0200165 const unsigned diff1 = diff_msb >> ( sizeof( diff_msb ) * 8 - 1 );
gabor-mezei-arm8d1d5fd2021-09-27 12:15:19 +0200166
167 return( 1 ^ diff1 );
168}
gabor-mezei-arm5a854422021-09-27 12:25:07 +0200169
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200170unsigned mbedtls_cf_size_gt( size_t x,
171 size_t y )
gabor-mezei-arm5a854422021-09-27 12:25:07 +0200172{
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200173 /* Return the sign bit (1 for negative) of (y - x). */
174 return( ( y - x ) >> ( sizeof( size_t ) * 8 - 1 ) );
gabor-mezei-arm5a854422021-09-27 12:25:07 +0200175}
gabor-mezei-arm3f90fd52021-09-27 12:55:33 +0200176
177#if defined(MBEDTLS_BIGNUM_C)
178
gabor-mezei-arm3f90fd52021-09-27 12:55:33 +0200179unsigned mbedtls_cf_mpi_uint_lt( const mbedtls_mpi_uint x,
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200180 const mbedtls_mpi_uint y )
gabor-mezei-arm3f90fd52021-09-27 12:55:33 +0200181{
182 mbedtls_mpi_uint ret;
183 mbedtls_mpi_uint cond;
184
185 /*
186 * Check if the most significant bits (MSB) of the operands are different.
187 */
188 cond = ( x ^ y );
189 /*
190 * If the MSB are the same then the difference x-y will be negative (and
191 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
192 */
193 ret = ( x - y ) & ~cond;
194 /*
195 * If the MSB are different, then the operand with the MSB of 1 is the
196 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
197 * the MSB of y is 0.)
198 */
199 ret |= y & cond;
200
201
202 ret = ret >> ( sizeof( mbedtls_mpi_uint ) * 8 - 1 );
203
204 return (unsigned) ret;
205}
206
207#endif /* MBEDTLS_BIGNUM_C */
gabor-mezei-armb2dbf2c2021-09-27 12:59:30 +0200208
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200209unsigned mbedtls_cf_uint_if( unsigned condition,
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200210 unsigned if1,
211 unsigned if0 )
gabor-mezei-armb2dbf2c2021-09-27 12:59:30 +0200212{
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200213 unsigned mask = mbedtls_cf_uint_mask( condition );
gabor-mezei-armb2dbf2c2021-09-27 12:59:30 +0200214 return( ( mask & if1 ) | (~mask & if0 ) );
215}
gabor-mezei-armd3230d52021-09-27 13:03:57 +0200216
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200217size_t mbedtls_cf_size_if( unsigned condition,
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200218 size_t if1,
219 size_t if0 )
gabor-mezei-arm65cefdb2021-09-27 15:47:00 +0200220{
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200221 size_t mask = mbedtls_cf_size_mask( condition );
gabor-mezei-arm65cefdb2021-09-27 15:47:00 +0200222 return( ( mask & if1 ) | (~mask & if0 ) );
223}
224
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200225int mbedtls_cf_cond_select_sign( unsigned char condition,
226 int if1,
227 int if0 )
gabor-mezei-armd3230d52021-09-27 13:03:57 +0200228{
229 /* In order to avoid questions about what we can reasonnably assume about
230 * the representations of signed integers, move everything to unsigned
231 * by taking advantage of the fact that a and b are either +1 or -1. */
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200232 unsigned uif1 = if1 + 1;
233 unsigned uif0 = if0 + 1;
gabor-mezei-armd3230d52021-09-27 13:03:57 +0200234
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200235 /* condition was 0 or 1, mask is 0 or 2 as are ua and ub */
236 const unsigned mask = condition << 1;
gabor-mezei-armd3230d52021-09-27 13:03:57 +0200237
238 /* select ua or ub */
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200239 unsigned ur = ( uif0 & ~mask ) | ( uif1 & mask );
gabor-mezei-armd3230d52021-09-27 13:03:57 +0200240
241 /* ur is now 0 or 2, convert back to -1 or +1 */
242 return( (int) ur - 1 );
243}
gabor-mezei-armbe8d98b2021-09-27 13:17:15 +0200244
245#if defined(MBEDTLS_BIGNUM_C)
246
gabor-mezei-armbe8d98b2021-09-27 13:17:15 +0200247void mbedtls_cf_mpi_uint_cond_assign( size_t n,
248 mbedtls_mpi_uint *dest,
249 const mbedtls_mpi_uint *src,
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200250 unsigned char condition )
gabor-mezei-armbe8d98b2021-09-27 13:17:15 +0200251{
252 size_t i;
253
254 /* MSVC has a warning about unary minus on unsigned integer types,
255 * but this is well-defined and precisely what we want to do here. */
256#if defined(_MSC_VER)
257#pragma warning( push )
258#pragma warning( disable : 4146 )
259#endif
260
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200261 /* all-bits 1 if condition is 1, all-bits 0 if condition is 0 */
262 const mbedtls_mpi_uint mask = -condition;
gabor-mezei-armbe8d98b2021-09-27 13:17:15 +0200263
264#if defined(_MSC_VER)
265#pragma warning( pop )
266#endif
267
268 for( i = 0; i < n; i++ )
269 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
270}
271
272#endif /* MBEDTLS_BIGNUM_C */
gabor-mezei-arm394aeaa2021-09-27 13:31:06 +0200273
gabor-mezei-arm394aeaa2021-09-27 13:31:06 +0200274void mbedtls_cf_mem_move_to_left( void *start,
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200275 size_t total,
276 size_t offset )
gabor-mezei-arm394aeaa2021-09-27 13:31:06 +0200277{
278 volatile unsigned char *buf = start;
279 size_t i, n;
280 if( total == 0 )
281 return;
282 for( i = 0; i < total; i++ )
283 {
284 unsigned no_op = mbedtls_cf_size_gt( total - offset, i );
285 /* The first `total - offset` passes are a no-op. The last
286 * `offset` passes shift the data one byte to the left and
287 * zero out the last byte. */
288 for( n = 0; n < total - 1; n++ )
289 {
290 unsigned char current = buf[n];
291 unsigned char next = buf[n+1];
292 buf[n] = mbedtls_cf_uint_if( no_op, current, next );
293 }
294 buf[total-1] = mbedtls_cf_uint_if( no_op, buf[total-1], 0 );
295 }
296}
gabor-mezei-armdee0fd32021-09-27 13:34:25 +0200297
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200298void mbedtls_cf_memcpy_if_eq( unsigned char *dest,
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200299 const unsigned char *src,
300 size_t len,
301 size_t c1,
302 size_t c2 )
gabor-mezei-armdee0fd32021-09-27 13:34:25 +0200303{
304 /* mask = c1 == c2 ? 0xff : 0x00 */
305 const size_t equal = mbedtls_cf_size_bool_eq( c1, c2 );
306 const unsigned char mask = (unsigned char) mbedtls_cf_size_mask( equal );
307
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200308 /* dest[i] = c1 == c2 ? src[i] : dest[i] */
gabor-mezei-armdee0fd32021-09-27 13:34:25 +0200309 for( size_t i = 0; i < len; i++ )
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200310 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
gabor-mezei-armdee0fd32021-09-27 13:34:25 +0200311}
gabor-mezei-arm0e7f71e2021-09-27 13:57:45 +0200312
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200313void mbedtls_cf_memcpy_offset( unsigned char *dst,
314 const unsigned char *src_base,
315 size_t offset_secret,
316 size_t offset_min,
317 size_t offset_max,
318 size_t len )
gabor-mezei-arm0e7f71e2021-09-27 13:57:45 +0200319{
320 size_t offset;
321
322 for( offset = offset_min; offset <= offset_max; offset++ )
323 {
324 mbedtls_cf_memcpy_if_eq( dst, src_base + offset, len,
325 offset, offset_secret );
326 }
327}
gabor-mezei-arm1349ffd2021-09-27 14:28:31 +0200328
329#if defined(MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC)
330
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200331int mbedtls_cf_hmac( mbedtls_md_context_t *ctx,
332 const unsigned char *add_data,
333 size_t add_data_len,
334 const unsigned char *data,
335 size_t data_len_secret,
336 size_t min_data_len,
337 size_t max_data_len,
338 unsigned char *output )
gabor-mezei-arm1349ffd2021-09-27 14:28:31 +0200339{
340 /*
341 * This function breaks the HMAC abstraction and uses the md_clone()
342 * extension to the MD API in order to get constant-flow behaviour.
343 *
344 * HMAC(msg) is defined as HASH(okey + HASH(ikey + msg)) where + means
345 * concatenation, and okey/ikey are the XOR of the key with some fixed bit
346 * patterns (see RFC 2104, sec. 2), which are stored in ctx->hmac_ctx.
347 *
348 * We'll first compute inner_hash = HASH(ikey + msg) by hashing up to
349 * minlen, then cloning the context, and for each byte up to maxlen
350 * finishing up the hash computation, keeping only the correct result.
351 *
352 * Then we only need to compute HASH(okey + inner_hash) and we're done.
353 */
354 const mbedtls_md_type_t md_alg = mbedtls_md_get_type( ctx->md_info );
355 /* TLS 1.2 only supports SHA-384, SHA-256, SHA-1, MD-5,
356 * all of which have the same block size except SHA-384. */
357 const size_t block_size = md_alg == MBEDTLS_MD_SHA384 ? 128 : 64;
358 const unsigned char * const ikey = ctx->hmac_ctx;
359 const unsigned char * const okey = ikey + block_size;
360 const size_t hash_size = mbedtls_md_get_size( ctx->md_info );
361
362 unsigned char aux_out[MBEDTLS_MD_MAX_SIZE];
363 mbedtls_md_context_t aux;
364 size_t offset;
365 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
366
367 mbedtls_md_init( &aux );
368
369#define MD_CHK( func_call ) \
370 do { \
371 ret = (func_call); \
372 if( ret != 0 ) \
373 goto cleanup; \
374 } while( 0 )
375
376 MD_CHK( mbedtls_md_setup( &aux, ctx->md_info, 0 ) );
377
378 /* After hmac_start() of hmac_reset(), ikey has already been hashed,
379 * so we can start directly with the message */
380 MD_CHK( mbedtls_md_update( ctx, add_data, add_data_len ) );
381 MD_CHK( mbedtls_md_update( ctx, data, min_data_len ) );
382
383 /* For each possible length, compute the hash up to that point */
384 for( offset = min_data_len; offset <= max_data_len; offset++ )
385 {
386 MD_CHK( mbedtls_md_clone( &aux, ctx ) );
387 MD_CHK( mbedtls_md_finish( &aux, aux_out ) );
388 /* Keep only the correct inner_hash in the output buffer */
389 mbedtls_cf_memcpy_if_eq( output, aux_out, hash_size,
390 offset, data_len_secret );
391
392 if( offset < max_data_len )
393 MD_CHK( mbedtls_md_update( ctx, data + offset, 1 ) );
394 }
395
396 /* The context needs to finish() before it starts() again */
397 MD_CHK( mbedtls_md_finish( ctx, aux_out ) );
398
399 /* Now compute HASH(okey + inner_hash) */
400 MD_CHK( mbedtls_md_starts( ctx ) );
401 MD_CHK( mbedtls_md_update( ctx, okey, block_size ) );
402 MD_CHK( mbedtls_md_update( ctx, output, hash_size ) );
403 MD_CHK( mbedtls_md_finish( ctx, output ) );
404
405 /* Done, get ready for next time */
406 MD_CHK( mbedtls_md_hmac_reset( ctx ) );
407
408#undef MD_CHK
409
410cleanup:
411 mbedtls_md_free( &aux );
412 return( ret );
413}
414
415#endif /* MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC */
gabor-mezei-arm40a49252021-09-27 15:33:35 +0200416
417#if defined(MBEDTLS_BIGNUM_C)
418
419#define MPI_VALIDATE_RET( cond ) \
420 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
421
422/*
423 * Conditionally assign X = Y, without leaking information
424 * about whether the assignment was made or not.
425 * (Leaking information about the respective sizes of X and Y is ok however.)
426 */
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200427int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X,
428 const mbedtls_mpi *Y,
429 unsigned char assign )
gabor-mezei-arm40a49252021-09-27 15:33:35 +0200430{
431 int ret = 0;
432 size_t i;
433 mbedtls_mpi_uint limb_mask;
434 MPI_VALIDATE_RET( X != NULL );
435 MPI_VALIDATE_RET( Y != NULL );
436
gabor-mezei-arm40a49252021-09-27 15:33:35 +0200437 /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */
gabor-mezei-arm9cb55692021-08-11 15:07:02 +0200438 limb_mask = mbedtls_cf_mpi_uint_mask( assign );;
gabor-mezei-arm40a49252021-09-27 15:33:35 +0200439
440 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
441
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200442 X->s = mbedtls_cf_cond_select_sign( assign, Y->s, X->s );
gabor-mezei-arm40a49252021-09-27 15:33:35 +0200443
444 mbedtls_cf_mpi_uint_cond_assign( Y->n, X->p, Y->p, assign );
445
446 for( i = Y->n; i < X->n; i++ )
447 X->p[i] &= ~limb_mask;
448
449cleanup:
450 return( ret );
451}
452
gabor-mezei-arm5c976212021-09-27 15:37:50 +0200453/*
454 * Conditionally swap X and Y, without leaking information
455 * about whether the swap was made or not.
456 * Here it is not ok to simply swap the pointers, which whould lead to
457 * different memory access patterns when X and Y are used afterwards.
458 */
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200459int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X,
460 mbedtls_mpi *Y,
461 unsigned char swap )
gabor-mezei-arm5c976212021-09-27 15:37:50 +0200462{
463 int ret, s;
464 size_t i;
465 mbedtls_mpi_uint limb_mask;
466 mbedtls_mpi_uint tmp;
467 MPI_VALIDATE_RET( X != NULL );
468 MPI_VALIDATE_RET( Y != NULL );
469
470 if( X == Y )
471 return( 0 );
472
gabor-mezei-arm5c976212021-09-27 15:37:50 +0200473 /* all-bits 1 if swap is 1, all-bits 0 if swap is 0 */
gabor-mezei-arm9cb55692021-08-11 15:07:02 +0200474 limb_mask = mbedtls_cf_mpi_uint_mask( swap );
gabor-mezei-arm5c976212021-09-27 15:37:50 +0200475
476 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
477 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
478
479 s = X->s;
gabor-mezei-arm87ac5be2021-08-10 20:36:09 +0200480 X->s = mbedtls_cf_cond_select_sign( swap, Y->s, X->s );
481 Y->s = mbedtls_cf_cond_select_sign( swap, s, Y->s );
gabor-mezei-arm5c976212021-09-27 15:37:50 +0200482
483
484 for( i = 0; i < X->n; i++ )
485 {
486 tmp = X->p[i];
487 X->p[i] = ( X->p[i] & ~limb_mask ) | ( Y->p[i] & limb_mask );
488 Y->p[i] = ( Y->p[i] & ~limb_mask ) | ( tmp & limb_mask );
489 }
490
491cleanup:
492 return( ret );
493}
494
gabor-mezei-armc29a3da2021-09-27 15:41:30 +0200495/*
496 * Compare signed values in constant time
497 */
gabor-mezei-arm2dcd7682021-09-27 16:29:52 +0200498int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X,
499 const mbedtls_mpi *Y,
500 unsigned *ret )
gabor-mezei-armc29a3da2021-09-27 15:41:30 +0200501{
502 size_t i;
503 /* The value of any of these variables is either 0 or 1 at all times. */
504 unsigned cond, done, X_is_negative, Y_is_negative;
505
506 MPI_VALIDATE_RET( X != NULL );
507 MPI_VALIDATE_RET( Y != NULL );
508 MPI_VALIDATE_RET( ret != NULL );
509
510 if( X->n != Y->n )
511 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
512
513 /*
514 * Set sign_N to 1 if N >= 0, 0 if N < 0.
515 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
516 */
517 X_is_negative = ( X->s & 2 ) >> 1;
518 Y_is_negative = ( Y->s & 2 ) >> 1;
519
520 /*
521 * If the signs are different, then the positive operand is the bigger.
522 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
523 * is false if X is positive (X_is_negative == 0).
524 */
525 cond = ( X_is_negative ^ Y_is_negative );
526 *ret = cond & X_is_negative;
527
528 /*
529 * This is a constant-time function. We might have the result, but we still
530 * need to go through the loop. Record if we have the result already.
531 */
532 done = cond;
533
534 for( i = X->n; i > 0; i-- )
535 {
536 /*
537 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
538 * X and Y are negative.
539 *
540 * Again even if we can make a decision, we just mark the result and
541 * the fact that we are done and continue looping.
542 */
543 cond = mbedtls_cf_mpi_uint_lt( Y->p[i - 1], X->p[i - 1] );
544 *ret |= cond & ( 1 - done ) & X_is_negative;
545 done |= cond;
546
547 /*
548 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
549 * X and Y are positive.
550 *
551 * Again even if we can make a decision, we just mark the result and
552 * the fact that we are done and continue looping.
553 */
554 cond = mbedtls_cf_mpi_uint_lt( X->p[i - 1], Y->p[i - 1] );
555 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
556 done |= cond;
557 }
558
559 return( 0 );
560}
561
gabor-mezei-arm40a49252021-09-27 15:33:35 +0200562#endif /* MBEDTLS_BIGNUM_C */
gabor-mezei-armfdb71182021-09-27 16:11:12 +0200563
564#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)
565
566int mbedtls_cf_rsaes_pkcs1_v15_unpadding( size_t ilen,
567 size_t *olen,
568 unsigned char *output,
569 size_t output_max_len,
570 unsigned char *buf )
571{
572 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
573 size_t i, plaintext_max_size;
574
575 /* The following variables take sensitive values: their value must
576 * not leak into the observable behavior of the function other than
577 * the designated outputs (output, olen, return value). Otherwise
578 * this would open the execution of the function to
579 * side-channel-based variants of the Bleichenbacher padding oracle
580 * attack. Potential side channels include overall timing, memory
581 * access patterns (especially visible to an adversary who has access
582 * to a shared memory cache), and branches (especially visible to
583 * an adversary who has access to a shared code cache or to a shared
584 * branch predictor). */
585 size_t pad_count = 0;
586 unsigned bad = 0;
587 unsigned char pad_done = 0;
588 size_t plaintext_size = 0;
589 unsigned output_too_large;
590
Gabor Mezei7013f622021-10-18 16:12:45 +0200591 plaintext_max_size = ( output_max_len > ilen - 11 ) ? ilen - 11
592 : output_max_len;
gabor-mezei-armfdb71182021-09-27 16:11:12 +0200593
594 /* Check and get padding length in constant time and constant
595 * memory trace. The first byte must be 0. */
596 bad |= buf[0];
597
598
599 /* Decode EME-PKCS1-v1_5 padding: 0x00 || 0x02 || PS || 0x00
600 * where PS must be at least 8 nonzero bytes. */
601 bad |= buf[1] ^ MBEDTLS_RSA_CRYPT;
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 for( i = 2; i < ilen; i++ )
606 {
607 pad_done |= ((buf[i] | (unsigned char)-buf[i]) >> 7) ^ 1;
608 pad_count += ((pad_done | (unsigned char)-pad_done) >> 7) ^ 1;
609 }
610
611
612 /* If pad_done is still zero, there's no data, only unfinished padding. */
613 bad |= mbedtls_cf_uint_if( pad_done, 0, 1 );
614
615 /* There must be at least 8 bytes of padding. */
616 bad |= mbedtls_cf_size_gt( 8, pad_count );
617
618 /* If the padding is valid, set plaintext_size to the number of
619 * remaining bytes after stripping the padding. If the padding
620 * is invalid, avoid leaking this fact through the size of the
621 * output: use the maximum message size that fits in the output
622 * buffer. Do it without branches to avoid leaking the padding
623 * validity through timing. RSA keys are small enough that all the
624 * size_t values involved fit in unsigned int. */
625 plaintext_size = mbedtls_cf_uint_if(
626 bad, (unsigned) plaintext_max_size,
627 (unsigned) ( ilen - pad_count - 3 ) );
628
629 /* Set output_too_large to 0 if the plaintext fits in the output
630 * buffer and to 1 otherwise. */
631 output_too_large = mbedtls_cf_size_gt( plaintext_size,
632 plaintext_max_size );
633
634 /* Set ret without branches to avoid timing attacks. Return:
635 * - INVALID_PADDING if the padding is bad (bad != 0).
636 * - OUTPUT_TOO_LARGE if the padding is good but the decrypted
637 * plaintext does not fit in the output buffer.
638 * - 0 if the padding is correct. */
639 ret = - (int) mbedtls_cf_uint_if(
640 bad, - MBEDTLS_ERR_RSA_INVALID_PADDING,
641 mbedtls_cf_uint_if( output_too_large,
642 - MBEDTLS_ERR_RSA_OUTPUT_TOO_LARGE,
643 0 ) );
644
645 /* If the padding is bad or the plaintext is too large, zero the
646 * data that we're about to copy to the output buffer.
647 * We need to copy the same amount of data
648 * from the same buffer whether the padding is good or not to
649 * avoid leaking the padding validity through overall timing or
650 * through memory or cache access patterns. */
651 bad = mbedtls_cf_uint_mask( bad | output_too_large );
652 for( i = 11; i < ilen; i++ )
653 buf[i] &= ~bad;
654
655 /* If the plaintext is too large, truncate it to the buffer size.
656 * Copy anyway to avoid revealing the length through timing, because
657 * revealing the length is as bad as revealing the padding validity
658 * for a Bleichenbacher attack. */
659 plaintext_size = mbedtls_cf_uint_if( output_too_large,
660 (unsigned) plaintext_max_size,
661 (unsigned) plaintext_size );
662
663 /* Move the plaintext to the leftmost position where it can start in
664 * the working buffer, i.e. make it start plaintext_max_size from
665 * the end of the buffer. Do this with a memory access trace that
666 * does not depend on the plaintext size. After this move, the
667 * starting location of the plaintext is no longer sensitive
668 * information. */
669 mbedtls_cf_mem_move_to_left( buf + ilen - plaintext_max_size,
670 plaintext_max_size,
671 plaintext_max_size - plaintext_size );
672
673 /* Finally copy the decrypted plaintext plus trailing zeros into the output
674 * buffer. If output_max_len is 0, then output may be an invalid pointer
675 * and the result of memcpy() would be undefined; prevent undefined
676 * behavior making sure to depend only on output_max_len (the size of the
677 * user-provided output buffer), which is independent from plaintext
678 * length, validity of padding, success of the decryption, and other
679 * secrets. */
680 if( output_max_len != 0 )
681 memcpy( output, buf + ilen - plaintext_max_size, plaintext_max_size );
682
683 /* Report the amount of data we copied to the output buffer. In case
684 * of errors (bad padding or output too large), the value of *olen
685 * when this function returns is not specified. Making it equivalent
686 * to the good case limits the risks of leaking the padding validity. */
687 *olen = plaintext_size;
688
689 return( ret );
690}
691
692#endif /* MBEDTLS_PKCS1_V15 && MBEDTLS_RSA_C && ! MBEDTLS_RSA_ALT */