Branch data Line data Source code
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 : :
49 : 0 : int mbedtls_ct_memcmp( const void *a,
50 : : const void *b,
51 : : size_t n )
52 : : {
53 : 0 : size_t i;
54 : 0 : volatile const unsigned char *A = (volatile const unsigned char *) a;
55 : 0 : volatile const unsigned char *B = (volatile const unsigned char *) b;
56 : 0 : volatile unsigned char diff = 0;
57 : :
58 [ # # ]: 0 : 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 : 0 : unsigned char x = A[i], y = B[i];
64 : 0 : diff |= x ^ y;
65 : : }
66 : :
67 : 0 : return( (int)diff );
68 : : }
69 : :
70 : 0 : unsigned 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 : 0 : 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 : :
86 : : size_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 : :
104 : 29732 : mbedtls_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 : 29732 : 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 : : */
134 : : static 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 : :
149 : : size_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 : : */
163 : : MBEDTLS_STATIC_TESTABLE
164 : : unsigned 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 : :
177 : 1152 : unsigned mbedtls_ct_size_bool_eq( size_t x,
178 : : size_t y )
179 : : {
180 : : /* diff = 0 if x == y, non-zero otherwise */
181 : 1152 : 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 : 1152 : 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 : 1152 : const unsigned diff1 = diff_msb >> ( sizeof( diff_msb ) * 8 - 1 );
199 : :
200 : 1152 : 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 : : */
216 : : static 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 : :
227 : 768 : unsigned mbedtls_ct_mpi_uint_lt( const mbedtls_mpi_uint x,
228 : : const mbedtls_mpi_uint y )
229 : : {
230 : 768 : mbedtls_mpi_uint ret;
231 : 768 : mbedtls_mpi_uint cond;
232 : :
233 : : /*
234 : : * Check if the most significant bits (MSB) of the operands are different.
235 : : */
236 : 768 : 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 : 768 : 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 : 768 : ret |= y & cond;
248 : :
249 : :
250 : 768 : ret = ret >> ( sizeof( mbedtls_mpi_uint ) * 8 - 1 );
251 : :
252 : 768 : return (unsigned) ret;
253 : : }
254 : :
255 : : #endif /* MBEDTLS_BIGNUM_C */
256 : :
257 : 0 : unsigned mbedtls_ct_uint_if( unsigned condition,
258 : : unsigned if1,
259 : : unsigned if0 )
260 : : {
261 : 0 : unsigned mask = mbedtls_ct_uint_mask( condition );
262 : 0 : 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 : : * */
281 : 29732 : static 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 : 29732 : unsigned uif1 = if1 + 1;
289 : 29732 : unsigned uif0 = if0 + 1;
290 : :
291 : : /* condition was 0 or 1, mask is 0 or 2 as are uif1 and uif0 */
292 : 29732 : const unsigned mask = condition << 1;
293 : :
294 : : /* select uif1 or uif0 */
295 : 29732 : unsigned ur = ( uif0 & ~mask ) | ( uif1 & mask );
296 : :
297 : : /* ur is now 0 or 2, convert back to -1 or +1 */
298 : 29732 : return( (int) ur - 1 );
299 : : }
300 : :
301 : 30872 : void 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 : 30872 : 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 : 30872 : const mbedtls_mpi_uint mask = -condition;
317 : :
318 : : #if defined(_MSC_VER)
319 : : #pragma warning( pop )
320 : : #endif
321 : :
322 [ + + ]: 274140 : for( i = 0; i < n; i++ )
323 : 243268 : dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
324 : 30872 : }
325 : :
326 : : #endif /* MBEDTLS_BIGNUM_C */
327 : :
328 : : #if defined(MBEDTLS_BASE64_C)
329 : :
330 : : unsigned 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( 0, 25, value ) & ( 'A' + value );
337 : : digit |= mbedtls_ct_uchar_mask_of_range( 26, 51, value ) & ( 'a' + value - 26 );
338 : : digit |= mbedtls_ct_uchar_mask_of_range( 52, 61, value ) & ( '0' + value - 52 );
339 : : digit |= mbedtls_ct_uchar_mask_of_range( 62, 62, value ) & '+';
340 : : digit |= mbedtls_ct_uchar_mask_of_range( 63, 63, value ) & '/';
341 : : return( digit );
342 : : }
343 : :
344 : : signed 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( 'A', 'Z', c ) & ( c - 'A' + 0 + 1 );
352 : : val |= mbedtls_ct_uchar_mask_of_range( 'a', 'z', c ) & ( c - 'a' + 26 + 1 );
353 : : val |= mbedtls_ct_uchar_mask_of_range( '0', '9', c ) & ( c - '0' + 52 + 1 );
354 : : val |= mbedtls_ct_uchar_mask_of_range( '+', '+', c ) & ( c - '+' + 62 + 1 );
355 : : val |= mbedtls_ct_uchar_mask_of_range( '/', '/', 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 : : */
381 : : static void mbedtls_ct_mem_move_to_left( void *start,
382 : : size_t total,
383 : : size_t offset )
384 : : {
385 : : volatile unsigned char *buf = 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( total - offset, 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( no_op, current, next );
400 : : }
401 : : buf[total-1] = mbedtls_ct_uint_if( no_op, buf[total-1], 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 : :
409 : : void 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 : :
424 : : void 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 : :
440 : : int 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 : :
519 : : cleanup:
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 : : */
536 : 29732 : int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X,
537 : : const mbedtls_mpi *Y,
538 : : unsigned char assign )
539 : : {
540 : 29732 : int ret = 0;
541 : 29732 : size_t i;
542 : 29732 : mbedtls_mpi_uint limb_mask;
543 : 29732 : MPI_VALIDATE_RET( X != NULL );
544 : 29732 : MPI_VALIDATE_RET( Y != NULL );
545 : :
546 : : /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */
547 : 29732 : limb_mask = mbedtls_ct_mpi_uint_mask( assign );;
548 : :
549 [ - + ]: 29732 : MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
550 : :
551 : 29732 : X->s = mbedtls_ct_cond_select_sign( assign, Y->s, X->s );
552 : :
553 : 29732 : mbedtls_ct_mpi_uint_cond_assign( Y->n, X->p, Y->p, assign );
554 : :
555 [ + + ]: 34620 : for( i = Y->n; i < X->n; i++ )
556 : 4888 : X->p[i] &= ~limb_mask;
557 : :
558 : 29732 : cleanup:
559 : 29732 : 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 : : */
568 : 0 : int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X,
569 : : mbedtls_mpi *Y,
570 : : unsigned char swap )
571 : : {
572 : 0 : int ret, s;
573 : 0 : size_t i;
574 : 0 : mbedtls_mpi_uint limb_mask;
575 : 0 : mbedtls_mpi_uint tmp;
576 : 0 : MPI_VALIDATE_RET( X != NULL );
577 : 0 : MPI_VALIDATE_RET( Y != NULL );
578 : :
579 [ # # ]: 0 : if( X == Y )
580 : : return( 0 );
581 : :
582 : : /* all-bits 1 if swap is 1, all-bits 0 if swap is 0 */
583 : 0 : limb_mask = mbedtls_ct_mpi_uint_mask( swap );
584 : :
585 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
586 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
587 : :
588 : 0 : s = X->s;
589 : 0 : X->s = mbedtls_ct_cond_select_sign( swap, Y->s, X->s );
590 : 0 : Y->s = mbedtls_ct_cond_select_sign( swap, s, Y->s );
591 : :
592 : :
593 [ # # ]: 0 : for( i = 0; i < X->n; i++ )
594 : : {
595 : 0 : tmp = X->p[i];
596 : 0 : X->p[i] = ( X->p[i] & ~limb_mask ) | ( Y->p[i] & limb_mask );
597 : 0 : Y->p[i] = ( Y->p[i] & ~limb_mask ) | ( tmp & limb_mask );
598 : : }
599 : :
600 : 0 : cleanup:
601 : : return( ret );
602 : : }
603 : :
604 : : /*
605 : : * Compare signed values in constant time
606 : : */
607 : 48 : int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X,
608 : : const mbedtls_mpi *Y,
609 : : unsigned *ret )
610 : : {
611 : 48 : size_t i;
612 : : /* The value of any of these variables is either 0 or 1 at all times. */
613 : 48 : unsigned cond, done, X_is_negative, Y_is_negative;
614 : :
615 : 48 : MPI_VALIDATE_RET( X != NULL );
616 : 48 : MPI_VALIDATE_RET( Y != NULL );
617 : 48 : MPI_VALIDATE_RET( ret != NULL );
618 : :
619 [ + - ]: 48 : 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 : 48 : X_is_negative = ( X->s & 2 ) >> 1;
627 : 48 : 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 : 48 : cond = ( X_is_negative ^ Y_is_negative );
635 : 48 : *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 : 48 : done = cond;
642 : :
643 [ + + ]: 432 : 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 : 384 : cond = mbedtls_ct_mpi_uint_lt( Y->p[i - 1], X->p[i - 1] );
653 : 384 : *ret |= cond & ( 1 - done ) & X_is_negative;
654 : 384 : 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 : 384 : cond = mbedtls_ct_mpi_uint_lt( X->p[i - 1], Y->p[i - 1] );
664 : 384 : *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
665 : 384 : 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 : :
675 : : int 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( pad_done, 0, 1 );
723 : :
724 : : /* There must be at least 8 bytes of padding. */
725 : : bad |= mbedtls_ct_size_gt( 8, 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 : : bad, (unsigned) plaintext_max_size,
736 : : (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( plaintext_size,
741 : : 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 : : bad, - MBEDTLS_ERR_RSA_INVALID_PADDING,
750 : : mbedtls_ct_uint_if( output_too_large,
751 : : - MBEDTLS_ERR_RSA_OUTPUT_TOO_LARGE,
752 : : 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( 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( output_too_large,
769 : : (unsigned) plaintext_max_size,
770 : : (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( input + ilen - plaintext_max_size,
779 : : plaintext_max_size,
780 : : 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( output, input + ilen - plaintext_max_size, 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 */
|
