1/**
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 /*
21 * The following functions are implemented without using comparison operators, as those
22 * might be translated to branches by some compilers on some platforms.
23 */
24
25#include "common.h"
26#include "constant_time_internal.h"
27#include "mbedtls/constant_time.h"
28#include "mbedtls/error.h"
29#include "mbedtls/platform_util.h"
30
31#if defined(MBEDTLS_BIGNUM_C)
32#include "mbedtls/bignum.h"
33#endif
34
35#if defined(MBEDTLS_SSL_TLS_C)
36#include "ssl_misc.h"
37#endif
38
39#if defined(MBEDTLS_RSA_C)
40#include "mbedtls/rsa.h"
41#endif
42
43#if defined(MBEDTLS_BASE64_C)
44#include "constant_time_invasive.h"
45#endif
46
47#include <string.h>
48
49int mbedtls_ct_memcmp( const void *a,
50 const void *b,
51 size_t n )
52{
53 size_t i;
54 volatile const unsigned char *A = (volatile const unsigned char *) a;
55 volatile const unsigned char *B = (volatile const unsigned char *) b;
56 volatile unsigned char diff = 0;
57
58 for( i = 0; i < n; i++ )
59 {
60 /* Read volatile data in order before computing diff.
61 * This avoids IAR compiler warning:
62 * 'the order of volatile accesses is undefined ..' */
63 unsigned char x = A[i], y = B[i];
64 diff |= x ^ y;
65 }
66
67 return( (int)diff );
68}
69
70unsigned mbedtls_ct_uint_mask( unsigned value )
71{
72 /* MSVC has a warning about unary minus on unsigned, but this is
73 * well-defined and precisely what we want to do here */
74#if defined(_MSC_VER)
75#pragma warning( push )
76#pragma warning( disable : 4146 )
77#endif
78 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
79#if defined(_MSC_VER)
80#pragma warning( pop )
81#endif
82}
83
84#if defined(MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC)
85
86size_t mbedtls_ct_size_mask( size_t value )
87{
88 /* MSVC has a warning about unary minus on unsigned integer types,
89 * but this is well-defined and precisely what we want to do here. */
90#if defined(_MSC_VER)
91#pragma warning( push )
92#pragma warning( disable : 4146 )
93#endif
94 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
95#if defined(_MSC_VER)
96#pragma warning( pop )
97#endif
98}
99
100#endif /* MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC */
101
102#if defined(MBEDTLS_BIGNUM_C)
103
104mbedtls_mpi_uint mbedtls_ct_mpi_uint_mask( mbedtls_mpi_uint value )
105{
106 /* MSVC has a warning about unary minus on unsigned, but this is
107 * well-defined and precisely what we want to do here */
108#if defined(_MSC_VER)
109#pragma warning( push )
110#pragma warning( disable : 4146 )
111#endif
112 return( - ( ( value | - value ) >> ( sizeof( value ) * 8 - 1 ) ) );
113#if defined(_MSC_VER)
114#pragma warning( pop )
115#endif
116}
117
118#endif /* MBEDTLS_BIGNUM_C */
119
120#if defined(MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC)
121
122/** Constant-flow mask generation for "less than" comparison:
123 * - if \p x < \p y, return all-bits 1, that is (size_t) -1
124 * - otherwise, return all bits 0, that is 0
125 *
126 * This function can be used to write constant-time code by replacing branches
127 * with bit operations using masks.
128 *
129 * \param x The first value to analyze.
130 * \param y The second value to analyze.
131 *
132 * \return All-bits-one if \p x is less than \p y, otherwise zero.
133 */
134static size_t mbedtls_ct_size_mask_lt( size_t x,
135 size_t y )
136{
137 /* This has the most significant bit set if and only if x < y */
138 const size_t sub = x - y;
139
140 /* sub1 = (x < y) ? 1 : 0 */
141 const size_t sub1 = sub >> ( sizeof( sub ) * 8 - 1 );
142
143 /* mask = (x < y) ? 0xff... : 0x00... */
144 const size_t mask = mbedtls_ct_size_mask( sub1 );
145
146 return( mask );
147}
148
149size_t mbedtls_ct_size_mask_ge( size_t x,
150 size_t y )
151{
152 return( ~mbedtls_ct_size_mask_lt( x, y ) );
153}
154
155#endif /* MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC */
156
157#if defined(MBEDTLS_BASE64_C)
158
159/* Return 0xff if low <= c <= high, 0 otherwise.
160 *
161 * Constant flow with respect to c.
162 */
163MBEDTLS_STATIC_TESTABLE
164unsigned char mbedtls_ct_uchar_mask_of_range( unsigned char low,
165 unsigned char high,
166 unsigned char c )
167{
168 /* low_mask is: 0 if low <= c, 0x...ff if low > c */
169 unsigned low_mask = ( (unsigned) c - low ) >> 8;
170 /* high_mask is: 0 if c <= high, 0x...ff if c > high */
171 unsigned high_mask = ( (unsigned) high - c ) >> 8;
172 return( ~( low_mask | high_mask ) & 0xff );
173}
174
175#endif /* MBEDTLS_BASE64_C */
176
177unsigned mbedtls_ct_size_bool_eq( size_t x,
178 size_t y )
179{
180 /* diff = 0 if x == y, non-zero otherwise */
181 const size_t diff = x ^ y;
182
183 /* MSVC has a warning about unary minus on unsigned integer types,
184 * but this is well-defined and precisely what we want to do here. */
185#if defined(_MSC_VER)
186#pragma warning( push )
187#pragma warning( disable : 4146 )
188#endif
189
190 /* diff_msb's most significant bit is equal to x != y */
191 const size_t diff_msb = ( diff | (size_t) -diff );
192
193#if defined(_MSC_VER)
194#pragma warning( pop )
195#endif
196
197 /* diff1 = (x != y) ? 1 : 0 */
198 const unsigned diff1 = diff_msb >> ( sizeof( diff_msb ) * 8 - 1 );
199
200 return( 1 ^ diff1 );
201}
202
203#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)
204
205/** Constant-flow "greater than" comparison:
206 * return x > y
207 *
208 * This is equivalent to \p x > \p y, but is likely to be compiled
209 * to code using bitwise operation rather than a branch.
210 *
211 * \param x The first value to analyze.
212 * \param y The second value to analyze.
213 *
214 * \return 1 if \p x greater than \p y, otherwise 0.
215 */
216static unsigned mbedtls_ct_size_gt( size_t x,
217 size_t y )
218{
219 /* Return the sign bit (1 for negative) of (y - x). */
220 return( ( y - x ) >> ( sizeof( size_t ) * 8 - 1 ) );
221}
222
223#endif /* MBEDTLS_PKCS1_V15 && MBEDTLS_RSA_C && ! MBEDTLS_RSA_ALT */
224
225#if defined(MBEDTLS_BIGNUM_C)
226
227unsigned mbedtls_ct_mpi_uint_lt( const mbedtls_mpi_uint x,
228 const mbedtls_mpi_uint y )
229{
230 mbedtls_mpi_uint ret;
231 mbedtls_mpi_uint cond;
232
233 /*
234 * Check if the most significant bits (MSB) of the operands are different.
235 */
236 cond = ( x ^ y );
237 /*
238 * If the MSB are the same then the difference x-y will be negative (and
239 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
240 */
241 ret = ( x - y ) & ~cond;
242 /*
243 * If the MSB are different, then the operand with the MSB of 1 is the
244 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
245 * the MSB of y is 0.)
246 */
247 ret |= y & cond;
248
249
250 ret = ret >> ( sizeof( mbedtls_mpi_uint ) * 8 - 1 );
251
252 return (unsigned) ret;
253}
254
255#endif /* MBEDTLS_BIGNUM_C */
256
257unsigned mbedtls_ct_uint_if( unsigned condition,
258 unsigned if1,
259 unsigned if0 )
260{
261 unsigned mask = mbedtls_ct_uint_mask( value: condition );
262 return( ( mask & if1 ) | (~mask & if0 ) );
263}
264
265#if defined(MBEDTLS_BIGNUM_C)
266
267/** Select between two sign values without branches.
268 *
269 * This is functionally equivalent to `condition ? if1 : if0` but uses only bit
270 * operations in order to avoid branches.
271 *
272 * \note if1 and if0 must be either 1 or -1, otherwise the result
273 * is undefined.
274 *
275 * \param condition Condition to test.
276 * \param if1 The first sign; must be either +1 or -1.
277 * \param if0 The second sign; must be either +1 or -1.
278 *
279 * \return \c if1 if \p condition is nonzero, otherwise \c if0.
280 * */
281static int mbedtls_ct_cond_select_sign( unsigned char condition,
282 int if1,
283 int if0 )
284{
285 /* In order to avoid questions about what we can reasonably assume about
286 * the representations of signed integers, move everything to unsigned
287 * by taking advantage of the fact that if1 and if0 are either +1 or -1. */
288 unsigned uif1 = if1 + 1;
289 unsigned uif0 = if0 + 1;
290
291 /* condition was 0 or 1, mask is 0 or 2 as are uif1 and uif0 */
292 const unsigned mask = condition << 1;
293
294 /* select uif1 or uif0 */
295 unsigned ur = ( uif0 & ~mask ) | ( uif1 & mask );
296
297 /* ur is now 0 or 2, convert back to -1 or +1 */
298 return( (int) ur - 1 );
299}
300
301void mbedtls_ct_mpi_uint_cond_assign( size_t n,
302 mbedtls_mpi_uint *dest,
303 const mbedtls_mpi_uint *src,
304 unsigned char condition )
305{
306 size_t i;
307
308 /* MSVC has a warning about unary minus on unsigned integer types,
309 * but this is well-defined and precisely what we want to do here. */
310#if defined(_MSC_VER)
311#pragma warning( push )
312#pragma warning( disable : 4146 )
313#endif
314
315 /* all-bits 1 if condition is 1, all-bits 0 if condition is 0 */
316 const mbedtls_mpi_uint mask = -condition;
317
318#if defined(_MSC_VER)
319#pragma warning( pop )
320#endif
321
322 for( i = 0; i < n; i++ )
323 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
324}
325
326#endif /* MBEDTLS_BIGNUM_C */
327
328#if defined(MBEDTLS_BASE64_C)
329
330unsigned char mbedtls_ct_base64_enc_char( unsigned char value )
331{
332 unsigned char digit = 0;
333 /* For each range of values, if value is in that range, mask digit with
334 * the corresponding value. Since value can only be in a single range,
335 * only at most one masking will change digit. */
336 digit |= mbedtls_ct_uchar_mask_of_range( low: 0, high: 25, c: value ) & ( 'A' + value );
337 digit |= mbedtls_ct_uchar_mask_of_range( low: 26, high: 51, c: value ) & ( 'a' + value - 26 );
338 digit |= mbedtls_ct_uchar_mask_of_range( low: 52, high: 61, c: value ) & ( '0' + value - 52 );
339 digit |= mbedtls_ct_uchar_mask_of_range( low: 62, high: 62, c: value ) & '+';
340 digit |= mbedtls_ct_uchar_mask_of_range( low: 63, high: 63, c: value ) & '/';
341 return( digit );
342}
343
344signed char mbedtls_ct_base64_dec_value( unsigned char c )
345{
346 unsigned char val = 0;
347 /* For each range of digits, if c is in that range, mask val with
348 * the corresponding value. Since c can only be in a single range,
349 * only at most one masking will change val. Set val to one plus
350 * the desired value so that it stays 0 if c is in none of the ranges. */
351 val |= mbedtls_ct_uchar_mask_of_range( low: 'A', high: 'Z', c ) & ( c - 'A' + 0 + 1 );
352 val |= mbedtls_ct_uchar_mask_of_range( low: 'a', high: 'z', c ) & ( c - 'a' + 26 + 1 );
353 val |= mbedtls_ct_uchar_mask_of_range( low: '0', high: '9', c ) & ( c - '0' + 52 + 1 );
354 val |= mbedtls_ct_uchar_mask_of_range( low: '+', high: '+', c ) & ( c - '+' + 62 + 1 );
355 val |= mbedtls_ct_uchar_mask_of_range( low: '/', high: '/', c ) & ( c - '/' + 63 + 1 );
356 /* At this point, val is 0 if c is an invalid digit and v+1 if c is
357 * a digit with the value v. */
358 return( val - 1 );
359}
360
361#endif /* MBEDTLS_BASE64_C */
362
363#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)
364
365/** Shift some data towards the left inside a buffer.
366 *
367 * `mbedtls_ct_mem_move_to_left(start, total, offset)` is functionally
368 * equivalent to
369 * ```
370 * memmove(start, start + offset, total - offset);
371 * memset(start + offset, 0, total - offset);
372 * ```
373 * but it strives to use a memory access pattern (and thus total timing)
374 * that does not depend on \p offset. This timing independence comes at
375 * the expense of performance.
376 *
377 * \param start Pointer to the start of the buffer.
378 * \param total Total size of the buffer.
379 * \param offset Offset from which to copy \p total - \p offset bytes.
380 */
381static void mbedtls_ct_mem_move_to_left( void *start,
382 size_t total,
383 size_t offset )
384{
385 volatile unsigned char *buf = (volatile unsigned char *) start;
386 size_t i, n;
387 if( total == 0 )
388 return;
389 for( i = 0; i < total; i++ )
390 {
391 unsigned no_op = mbedtls_ct_size_gt( x: total - offset, y: i );
392 /* The first `total - offset` passes are a no-op. The last
393 * `offset` passes shift the data one byte to the left and
394 * zero out the last byte. */
395 for( n = 0; n < total - 1; n++ )
396 {
397 unsigned char current = buf[n];
398 unsigned char next = buf[n+1];
399 buf[n] = mbedtls_ct_uint_if( condition: no_op, if1: current, if0: next );
400 }
401 buf[total-1] = mbedtls_ct_uint_if( condition: no_op, if1: buf[total-1], if0: 0 );
402 }
403}
404
405#endif /* MBEDTLS_PKCS1_V15 && MBEDTLS_RSA_C && ! MBEDTLS_RSA_ALT */
406
407#if defined(MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC)
408
409void mbedtls_ct_memcpy_if_eq( unsigned char *dest,
410 const unsigned char *src,
411 size_t len,
412 size_t c1,
413 size_t c2 )
414{
415 /* mask = c1 == c2 ? 0xff : 0x00 */
416 const size_t equal = mbedtls_ct_size_bool_eq( c1, c2 );
417 const unsigned char mask = (unsigned char) mbedtls_ct_size_mask( equal );
418
419 /* dest[i] = c1 == c2 ? src[i] : dest[i] */
420 for( size_t i = 0; i < len; i++ )
421 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
422}
423
424void mbedtls_ct_memcpy_offset( unsigned char *dest,
425 const unsigned char *src,
426 size_t offset,
427 size_t offset_min,
428 size_t offset_max,
429 size_t len )
430{
431 size_t offsetval;
432
433 for( offsetval = offset_min; offsetval <= offset_max; offsetval++ )
434 {
435 mbedtls_ct_memcpy_if_eq( dest, src + offsetval, len,
436 offsetval, offset );
437 }
438}
439
440int mbedtls_ct_hmac( mbedtls_md_context_t *ctx,
441 const unsigned char *add_data,
442 size_t add_data_len,
443 const unsigned char *data,
444 size_t data_len_secret,
445 size_t min_data_len,
446 size_t max_data_len,
447 unsigned char *output )
448{
449 /*
450 * This function breaks the HMAC abstraction and uses the md_clone()
451 * extension to the MD API in order to get constant-flow behaviour.
452 *
453 * HMAC(msg) is defined as HASH(okey + HASH(ikey + msg)) where + means
454 * concatenation, and okey/ikey are the XOR of the key with some fixed bit
455 * patterns (see RFC 2104, sec. 2), which are stored in ctx->hmac_ctx.
456 *
457 * We'll first compute inner_hash = HASH(ikey + msg) by hashing up to
458 * minlen, then cloning the context, and for each byte up to maxlen
459 * finishing up the hash computation, keeping only the correct result.
460 *
461 * Then we only need to compute HASH(okey + inner_hash) and we're done.
462 */
463 const mbedtls_md_type_t md_alg = mbedtls_md_get_type( ctx->md_info );
464 /* TLS 1.2 only supports SHA-384, SHA-256, SHA-1, MD-5,
465 * all of which have the same block size except SHA-384. */
466 const size_t block_size = md_alg == MBEDTLS_MD_SHA384 ? 128 : 64;
467 const unsigned char * const ikey = ctx->hmac_ctx;
468 const unsigned char * const okey = ikey + block_size;
469 const size_t hash_size = mbedtls_md_get_size( ctx->md_info );
470
471 unsigned char aux_out[MBEDTLS_MD_MAX_SIZE];
472 mbedtls_md_context_t aux;
473 size_t offset;
474 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
475
476 mbedtls_md_init( &aux );
477
478#define MD_CHK( func_call ) \
479 do { \
480 ret = (func_call); \
481 if( ret != 0 ) \
482 goto cleanup; \
483 } while( 0 )
484
485 MD_CHK( mbedtls_md_setup( &aux, ctx->md_info, 0 ) );
486
487 /* After hmac_start() of hmac_reset(), ikey has already been hashed,
488 * so we can start directly with the message */
489 MD_CHK( mbedtls_md_update( ctx, add_data, add_data_len ) );
490 MD_CHK( mbedtls_md_update( ctx, data, min_data_len ) );
491
492 /* For each possible length, compute the hash up to that point */
493 for( offset = min_data_len; offset <= max_data_len; offset++ )
494 {
495 MD_CHK( mbedtls_md_clone( &aux, ctx ) );
496 MD_CHK( mbedtls_md_finish( &aux, aux_out ) );
497 /* Keep only the correct inner_hash in the output buffer */
498 mbedtls_ct_memcpy_if_eq( output, aux_out, hash_size,
499 offset, data_len_secret );
500
501 if( offset < max_data_len )
502 MD_CHK( mbedtls_md_update( ctx, data + offset, 1 ) );
503 }
504
505 /* The context needs to finish() before it starts() again */
506 MD_CHK( mbedtls_md_finish( ctx, aux_out ) );
507
508 /* Now compute HASH(okey + inner_hash) */
509 MD_CHK( mbedtls_md_starts( ctx ) );
510 MD_CHK( mbedtls_md_update( ctx, okey, block_size ) );
511 MD_CHK( mbedtls_md_update( ctx, output, hash_size ) );
512 MD_CHK( mbedtls_md_finish( ctx, output ) );
513
514 /* Done, get ready for next time */
515 MD_CHK( mbedtls_md_hmac_reset( ctx ) );
516
517#undef MD_CHK
518
519cleanup:
520 mbedtls_md_free( &aux );
521 return( ret );
522}
523
524#endif /* MBEDTLS_SSL_SOME_SUITES_USE_TLS_CBC */
525
526#if defined(MBEDTLS_BIGNUM_C)
527
528#define MPI_VALIDATE_RET( cond ) \
529 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
530
531/*
532 * Conditionally assign X = Y, without leaking information
533 * about whether the assignment was made or not.
534 * (Leaking information about the respective sizes of X and Y is ok however.)
535 */
536int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X,
537 const mbedtls_mpi *Y,
538 unsigned char assign )
539{
540 int ret = 0;
541 size_t i;
542 mbedtls_mpi_uint limb_mask;
543 MPI_VALIDATE_RET( X != NULL );
544 MPI_VALIDATE_RET( Y != NULL );
545
546 /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */
547 limb_mask = mbedtls_ct_mpi_uint_mask( value: assign );;
548
549 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
550
551 X->s = mbedtls_ct_cond_select_sign( condition: assign, if1: Y->s, if0: X->s );
552
553 mbedtls_ct_mpi_uint_cond_assign( n: Y->n, dest: X->p, src: Y->p, condition: assign );
554
555 for( i = Y->n; i < X->n; i++ )
556 X->p[i] &= ~limb_mask;
557
558cleanup:
559 return( ret );
560}
561
562/*
563 * Conditionally swap X and Y, without leaking information
564 * about whether the swap was made or not.
565 * Here it is not ok to simply swap the pointers, which whould lead to
566 * different memory access patterns when X and Y are used afterwards.
567 */
568int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X,
569 mbedtls_mpi *Y,
570 unsigned char swap )
571{
572 int ret, s;
573 size_t i;
574 mbedtls_mpi_uint limb_mask;
575 mbedtls_mpi_uint tmp;
576 MPI_VALIDATE_RET( X != NULL );
577 MPI_VALIDATE_RET( Y != NULL );
578
579 if( X == Y )
580 return( 0 );
581
582 /* all-bits 1 if swap is 1, all-bits 0 if swap is 0 */
583 limb_mask = mbedtls_ct_mpi_uint_mask( value: swap );
584
585 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
586 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
587
588 s = X->s;
589 X->s = mbedtls_ct_cond_select_sign( condition: swap, if1: Y->s, if0: X->s );
590 Y->s = mbedtls_ct_cond_select_sign( condition: swap, if1: s, if0: Y->s );
591
592
593 for( i = 0; i < X->n; i++ )
594 {
595 tmp = X->p[i];
596 X->p[i] = ( X->p[i] & ~limb_mask ) | ( Y->p[i] & limb_mask );
597 Y->p[i] = ( Y->p[i] & ~limb_mask ) | ( tmp & limb_mask );
598 }
599
600cleanup:
601 return( ret );
602}
603
604/*
605 * Compare signed values in constant time
606 */
607int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X,
608 const mbedtls_mpi *Y,
609 unsigned *ret )
610{
611 size_t i;
612 /* The value of any of these variables is either 0 or 1 at all times. */
613 unsigned cond, done, X_is_negative, Y_is_negative;
614
615 MPI_VALIDATE_RET( X != NULL );
616 MPI_VALIDATE_RET( Y != NULL );
617 MPI_VALIDATE_RET( ret != NULL );
618
619 if( X->n != Y->n )
620 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
621
622 /*
623 * Set sign_N to 1 if N >= 0, 0 if N < 0.
624 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
625 */
626 X_is_negative = ( X->s & 2 ) >> 1;
627 Y_is_negative = ( Y->s & 2 ) >> 1;
628
629 /*
630 * If the signs are different, then the positive operand is the bigger.
631 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
632 * is false if X is positive (X_is_negative == 0).
633 */
634 cond = ( X_is_negative ^ Y_is_negative );
635 *ret = cond & X_is_negative;
636
637 /*
638 * This is a constant-time function. We might have the result, but we still
639 * need to go through the loop. Record if we have the result already.
640 */
641 done = cond;
642
643 for( i = X->n; i > 0; i-- )
644 {
645 /*
646 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
647 * X and Y are negative.
648 *
649 * Again even if we can make a decision, we just mark the result and
650 * the fact that we are done and continue looping.
651 */
652 cond = mbedtls_ct_mpi_uint_lt( x: Y->p[i - 1], y: X->p[i - 1] );
653 *ret |= cond & ( 1 - done ) & X_is_negative;
654 done |= cond;
655
656 /*
657 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
658 * X and Y are positive.
659 *
660 * Again even if we can make a decision, we just mark the result and
661 * the fact that we are done and continue looping.
662 */
663 cond = mbedtls_ct_mpi_uint_lt( x: X->p[i - 1], y: Y->p[i - 1] );
664 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
665 done |= cond;
666 }
667
668 return( 0 );
669}
670
671#endif /* MBEDTLS_BIGNUM_C */
672
673#if defined(MBEDTLS_PKCS1_V15) && defined(MBEDTLS_RSA_C) && !defined(MBEDTLS_RSA_ALT)
674
675int mbedtls_ct_rsaes_pkcs1_v15_unpadding( unsigned char *input,
676 size_t ilen,
677 unsigned char *output,
678 size_t output_max_len,
679 size_t *olen )
680{
681 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
682 size_t i, plaintext_max_size;
683
684 /* The following variables take sensitive values: their value must
685 * not leak into the observable behavior of the function other than
686 * the designated outputs (output, olen, return value). Otherwise
687 * this would open the execution of the function to
688 * side-channel-based variants of the Bleichenbacher padding oracle
689 * attack. Potential side channels include overall timing, memory
690 * access patterns (especially visible to an adversary who has access
691 * to a shared memory cache), and branches (especially visible to
692 * an adversary who has access to a shared code cache or to a shared
693 * branch predictor). */
694 size_t pad_count = 0;
695 unsigned bad = 0;
696 unsigned char pad_done = 0;
697 size_t plaintext_size = 0;
698 unsigned output_too_large;
699
700 plaintext_max_size = ( output_max_len > ilen - 11 ) ? ilen - 11
701 : output_max_len;
702
703 /* Check and get padding length in constant time and constant
704 * memory trace. The first byte must be 0. */
705 bad |= input[0];
706
707
708 /* Decode EME-PKCS1-v1_5 padding: 0x00 || 0x02 || PS || 0x00
709 * where PS must be at least 8 nonzero bytes. */
710 bad |= input[1] ^ MBEDTLS_RSA_CRYPT;
711
712 /* Read the whole buffer. Set pad_done to nonzero if we find
713 * the 0x00 byte and remember the padding length in pad_count. */
714 for( i = 2; i < ilen; i++ )
715 {
716 pad_done |= ((input[i] | (unsigned char)-input[i]) >> 7) ^ 1;
717 pad_count += ((pad_done | (unsigned char)-pad_done) >> 7) ^ 1;
718 }
719
720
721 /* If pad_done is still zero, there's no data, only unfinished padding. */
722 bad |= mbedtls_ct_uint_if( condition: pad_done, if1: 0, if0: 1 );
723
724 /* There must be at least 8 bytes of padding. */
725 bad |= mbedtls_ct_size_gt( x: 8, y: pad_count );
726
727 /* If the padding is valid, set plaintext_size to the number of
728 * remaining bytes after stripping the padding. If the padding
729 * is invalid, avoid leaking this fact through the size of the
730 * output: use the maximum message size that fits in the output
731 * buffer. Do it without branches to avoid leaking the padding
732 * validity through timing. RSA keys are small enough that all the
733 * size_t values involved fit in unsigned int. */
734 plaintext_size = mbedtls_ct_uint_if(
735 condition: bad, if1: (unsigned) plaintext_max_size,
736 if0: (unsigned) ( ilen - pad_count - 3 ) );
737
738 /* Set output_too_large to 0 if the plaintext fits in the output
739 * buffer and to 1 otherwise. */
740 output_too_large = mbedtls_ct_size_gt( x: plaintext_size,
741 y: plaintext_max_size );
742
743 /* Set ret without branches to avoid timing attacks. Return:
744 * - INVALID_PADDING if the padding is bad (bad != 0).
745 * - OUTPUT_TOO_LARGE if the padding is good but the decrypted
746 * plaintext does not fit in the output buffer.
747 * - 0 if the padding is correct. */
748 ret = - (int) mbedtls_ct_uint_if(
749 condition: bad, if1: - MBEDTLS_ERR_RSA_INVALID_PADDING,
750 if0: mbedtls_ct_uint_if( condition: output_too_large,
751 if1: - MBEDTLS_ERR_RSA_OUTPUT_TOO_LARGE,
752 if0: 0 ) );
753
754 /* If the padding is bad or the plaintext is too large, zero the
755 * data that we're about to copy to the output buffer.
756 * We need to copy the same amount of data
757 * from the same buffer whether the padding is good or not to
758 * avoid leaking the padding validity through overall timing or
759 * through memory or cache access patterns. */
760 bad = mbedtls_ct_uint_mask( value: bad | output_too_large );
761 for( i = 11; i < ilen; i++ )
762 input[i] &= ~bad;
763
764 /* If the plaintext is too large, truncate it to the buffer size.
765 * Copy anyway to avoid revealing the length through timing, because
766 * revealing the length is as bad as revealing the padding validity
767 * for a Bleichenbacher attack. */
768 plaintext_size = mbedtls_ct_uint_if( condition: output_too_large,
769 if1: (unsigned) plaintext_max_size,
770 if0: (unsigned) plaintext_size );
771
772 /* Move the plaintext to the leftmost position where it can start in
773 * the working buffer, i.e. make it start plaintext_max_size from
774 * the end of the buffer. Do this with a memory access trace that
775 * does not depend on the plaintext size. After this move, the
776 * starting location of the plaintext is no longer sensitive
777 * information. */
778 mbedtls_ct_mem_move_to_left( start: input + ilen - plaintext_max_size,
779 total: plaintext_max_size,
780 offset: plaintext_max_size - plaintext_size );
781
782 /* Finally copy the decrypted plaintext plus trailing zeros into the output
783 * buffer. If output_max_len is 0, then output may be an invalid pointer
784 * and the result of memcpy() would be undefined; prevent undefined
785 * behavior making sure to depend only on output_max_len (the size of the
786 * user-provided output buffer), which is independent from plaintext
787 * length, validity of padding, success of the decryption, and other
788 * secrets. */
789 if( output_max_len != 0 )
790 memcpy( dest: output, src: input + ilen - plaintext_max_size, n: plaintext_max_size );
791
792 /* Report the amount of data we copied to the output buffer. In case
793 * of errors (bad padding or output too large), the value of *olen
794 * when this function returns is not specified. Making it equivalent
795 * to the good case limits the risks of leaking the padding validity. */
796 *olen = plaintext_size;
797
798 return( ret );
799}
800
801#endif /* MBEDTLS_PKCS1_V15 && MBEDTLS_RSA_C && ! MBEDTLS_RSA_ALT */
802