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