diff options
Diffstat (limited to 'thirdparty/mbedtls/library/bignum.c')
| -rw-r--r-- | thirdparty/mbedtls/library/bignum.c | 525 |
1 files changed, 420 insertions, 105 deletions
diff --git a/thirdparty/mbedtls/library/bignum.c b/thirdparty/mbedtls/library/bignum.c index 87ccf42fad..c553d0c5af 100644 --- a/thirdparty/mbedtls/library/bignum.c +++ b/thirdparty/mbedtls/library/bignum.c @@ -1,8 +1,14 @@ /* * Multi-precision integer library * - * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved - * SPDX-License-Identifier: Apache-2.0 + * Copyright The Mbed TLS Contributors + * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later + * + * This file is provided under the Apache License 2.0, or the + * GNU General Public License v2.0 or later. + * + * ********** + * Apache License 2.0: * * Licensed under the Apache License, Version 2.0 (the "License"); you may * not use this file except in compliance with the License. @@ -16,7 +22,26 @@ * See the License for the specific language governing permissions and * limitations under the License. * - * This file is part of mbed TLS (https://tls.mbed.org) + * ********** + * + * ********** + * GNU General Public License v2.0 or later: + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + * ********** */ /* @@ -47,6 +72,7 @@ #include "mbedtls/bn_mul.h" #include "mbedtls/platform_util.h" +#include <limits.h> #include <string.h> #if defined(MBEDTLS_PLATFORM_C) @@ -242,6 +268,67 @@ void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ) memcpy( Y, &T, sizeof( mbedtls_mpi ) ); } +/** + * Select between two sign values in constant-time. + * + * This is functionally equivalent to second ? a : b but uses only bit + * operations in order to avoid branches. + * + * \param[in] a The first sign; must be either +1 or -1. + * \param[in] b The second sign; must be either +1 or -1. + * \param[in] second Must be either 1 (return b) or 0 (return a). + * + * \return The selected sign value. + */ +static int mpi_safe_cond_select_sign( int a, int b, unsigned char second ) +{ + /* In order to avoid questions about what we can reasonnably assume about + * the representations of signed integers, move everything to unsigned + * by taking advantage of the fact that a and b are either +1 or -1. */ + unsigned ua = a + 1; + unsigned ub = b + 1; + + /* second was 0 or 1, mask is 0 or 2 as are ua and ub */ + const unsigned mask = second << 1; + + /* select ua or ub */ + unsigned ur = ( ua & ~mask ) | ( ub & mask ); + + /* ur is now 0 or 2, convert back to -1 or +1 */ + return( (int) ur - 1 ); +} + +/* + * Conditionally assign dest = src, without leaking information + * about whether the assignment was made or not. + * dest and src must be arrays of limbs of size n. + * assign must be 0 or 1. + */ +static void mpi_safe_cond_assign( size_t n, + mbedtls_mpi_uint *dest, + const mbedtls_mpi_uint *src, + unsigned char assign ) +{ + size_t i; + + /* MSVC has a warning about unary minus on unsigned integer types, + * but this is well-defined and precisely what we want to do here. */ +#if defined(_MSC_VER) +#pragma warning( push ) +#pragma warning( disable : 4146 ) +#endif + + /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */ + const mbedtls_mpi_uint mask = -assign; + +#if defined(_MSC_VER) +#pragma warning( pop ) +#endif + + for( i = 0; i < n; i++ ) + dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask ); +} + /* * Conditionally assign X = Y, without leaking information * about whether the assignment was made or not. @@ -251,21 +338,34 @@ int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned { int ret = 0; size_t i; + mbedtls_mpi_uint limb_mask; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( Y != NULL ); + /* MSVC has a warning about unary minus on unsigned integer types, + * but this is well-defined and precisely what we want to do here. */ +#if defined(_MSC_VER) +#pragma warning( push ) +#pragma warning( disable : 4146 ) +#endif + /* make sure assign is 0 or 1 in a time-constant manner */ - assign = (assign | (unsigned char)-assign) >> 7; + assign = (assign | (unsigned char)-assign) >> (sizeof( assign ) * 8 - 1); + /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */ + limb_mask = -assign; + +#if defined(_MSC_VER) +#pragma warning( pop ) +#endif MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) ); - X->s = X->s * ( 1 - assign ) + Y->s * assign; + X->s = mpi_safe_cond_select_sign( X->s, Y->s, assign ); - for( i = 0; i < Y->n; i++ ) - X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign; + mpi_safe_cond_assign( Y->n, X->p, Y->p, assign ); - for( ; i < X->n; i++ ) - X->p[i] *= ( 1 - assign ); + for( i = Y->n; i < X->n; i++ ) + X->p[i] &= ~limb_mask; cleanup: return( ret ); @@ -281,6 +381,7 @@ int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char sw { int ret, s; size_t i; + mbedtls_mpi_uint limb_mask; mbedtls_mpi_uint tmp; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( Y != NULL ); @@ -288,22 +389,35 @@ int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char sw if( X == Y ) return( 0 ); + /* MSVC has a warning about unary minus on unsigned integer types, + * but this is well-defined and precisely what we want to do here. */ +#if defined(_MSC_VER) +#pragma warning( push ) +#pragma warning( disable : 4146 ) +#endif + /* make sure swap is 0 or 1 in a time-constant manner */ - swap = (swap | (unsigned char)-swap) >> 7; + swap = (swap | (unsigned char)-swap) >> (sizeof( swap ) * 8 - 1); + /* all-bits 1 if swap is 1, all-bits 0 if swap is 0 */ + limb_mask = -swap; + +#if defined(_MSC_VER) +#pragma warning( pop ) +#endif MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) ); s = X->s; - X->s = X->s * ( 1 - swap ) + Y->s * swap; - Y->s = Y->s * ( 1 - swap ) + s * swap; + X->s = mpi_safe_cond_select_sign( X->s, Y->s, swap ); + Y->s = mpi_safe_cond_select_sign( Y->s, s, swap ); for( i = 0; i < X->n; i++ ) { tmp = X->p[i]; - X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap; - Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap; + X->p[i] = ( X->p[i] & ~limb_mask ) | ( Y->p[i] & limb_mask ); + Y->p[i] = ( Y->p[i] & ~limb_mask ) | ( tmp & limb_mask ); } cleanup: @@ -460,6 +574,7 @@ int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) { int ret; size_t i, j, slen, n; + int sign = 1; mbedtls_mpi_uint d; mbedtls_mpi T; MPI_VALIDATE_RET( X != NULL ); @@ -470,6 +585,12 @@ int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) mbedtls_mpi_init( &T ); + if( s[0] == '-' ) + { + ++s; + sign = -1; + } + slen = strlen( s ); if( radix == 16 ) @@ -484,12 +605,6 @@ int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) for( i = slen, j = 0; i > 0; i--, j++ ) { - if( i == 1 && s[i - 1] == '-' ) - { - X->s = -1; - break; - } - MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) ); X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 ); } @@ -500,26 +615,15 @@ int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) for( i = 0; i < slen; i++ ) { - if( i == 0 && s[i] == '-' ) - { - X->s = -1; - continue; - } - MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) ); - - if( X->s == 1 ) - { - MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) ); - } - else - { - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) ); - } + MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) ); } } + if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 ) + X->s = -1; + cleanup: mbedtls_mpi_free( &T ); @@ -1249,10 +1353,24 @@ cleanup: return( ret ); } -/* - * Helper for mbedtls_mpi subtraction +/** + * Helper for mbedtls_mpi subtraction. + * + * Calculate d - s where d and s have the same size. + * This function operates modulo (2^ciL)^n and returns the carry + * (1 if there was a wraparound, i.e. if `d < s`, and 0 otherwise). + * + * \param n Number of limbs of \p d and \p s. + * \param[in,out] d On input, the left operand. + * On output, the result of the subtraction: + * \param[in] s The right operand. + * + * \return 1 if `d < s`. + * 0 if `d >= s`. */ -static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d ) +static mbedtls_mpi_uint mpi_sub_hlp( size_t n, + mbedtls_mpi_uint *d, + const mbedtls_mpi_uint *s ) { size_t i; mbedtls_mpi_uint c, z; @@ -1263,28 +1381,22 @@ static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d ) c = ( *d < *s ) + z; *d -= *s; } - while( c != 0 ) - { - z = ( *d < c ); *d -= c; - c = z; d++; - } + return( c ); } /* - * Unsigned subtraction: X = |A| - |B| (HAC 14.9) + * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10) */ int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) { mbedtls_mpi TB; int ret; size_t n; + mbedtls_mpi_uint carry; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( A != NULL ); MPI_VALIDATE_RET( B != NULL ); - if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) - return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); - mbedtls_mpi_init( &TB ); if( X == B ) @@ -1306,8 +1418,28 @@ int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi for( n = B->n; n > 0; n-- ) if( B->p[n - 1] != 0 ) break; + if( n > A->n ) + { + /* B >= (2^ciL)^n > A */ + ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; + goto cleanup; + } - mpi_sub_hlp( n, B->p, X->p ); + carry = mpi_sub_hlp( n, X->p, B->p ); + if( carry != 0 ) + { + /* Propagate the carry to the first nonzero limb of X. */ + for( ; n < X->n && X->p[n] == 0; n++ ) + --X->p[n]; + /* If we ran out of space for the carry, it means that the result + * is negative. */ + if( n == X->n ) + { + ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; + goto cleanup; + } + --X->p[n]; + } cleanup: @@ -1391,17 +1523,17 @@ cleanup: */ int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) { - mbedtls_mpi _B; + mbedtls_mpi B; mbedtls_mpi_uint p[1]; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( A != NULL ); p[0] = ( b < 0 ) ? -b : b; - _B.s = ( b < 0 ) ? -1 : 1; - _B.n = 1; - _B.p = p; + B.s = ( b < 0 ) ? -1 : 1; + B.n = 1; + B.p = p; - return( mbedtls_mpi_add_mpi( X, A, &_B ) ); + return( mbedtls_mpi_add_mpi( X, A, &B ) ); } /* @@ -1409,17 +1541,17 @@ int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint */ int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) { - mbedtls_mpi _B; + mbedtls_mpi B; mbedtls_mpi_uint p[1]; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( A != NULL ); p[0] = ( b < 0 ) ? -b : b; - _B.s = ( b < 0 ) ? -1 : 1; - _B.n = 1; - _B.p = p; + B.s = ( b < 0 ) ? -1 : 1; + B.n = 1; + B.p = p; - return( mbedtls_mpi_sub_mpi( X, A, &_B ) ); + return( mbedtls_mpi_sub_mpi( X, A, &B ) ); } /* @@ -1502,6 +1634,7 @@ int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi int ret; size_t i, j; mbedtls_mpi TA, TB; + int result_is_zero = 0; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( A != NULL ); MPI_VALIDATE_RET( B != NULL ); @@ -1514,10 +1647,14 @@ int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi for( i = A->n; i > 0; i-- ) if( A->p[i - 1] != 0 ) break; + if( i == 0 ) + result_is_zero = 1; for( j = B->n; j > 0; j-- ) if( B->p[j - 1] != 0 ) break; + if( j == 0 ) + result_is_zero = 1; MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); @@ -1525,7 +1662,14 @@ int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi for( ; j > 0; j-- ) mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] ); - X->s = A->s * B->s; + /* If the result is 0, we don't shortcut the operation, which reduces + * but does not eliminate side channels leaking the zero-ness. We do + * need to take care to set the sign bit properly since the library does + * not fully support an MPI object with a value of 0 and s == -1. */ + if( result_is_zero ) + X->s = 1; + else + X->s = A->s * B->s; cleanup: @@ -1539,17 +1683,17 @@ cleanup: */ int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ) { - mbedtls_mpi _B; + mbedtls_mpi B; mbedtls_mpi_uint p[1]; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( A != NULL ); - _B.s = 1; - _B.n = 1; - _B.p = p; + B.s = 1; + B.n = 1; + B.p = p; p[0] = b; - return( mbedtls_mpi_mul_mpi( X, A, &_B ) ); + return( mbedtls_mpi_mul_mpi( X, A, &B ) ); } /* @@ -1773,16 +1917,16 @@ int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b ) { - mbedtls_mpi _B; + mbedtls_mpi B; mbedtls_mpi_uint p[1]; MPI_VALIDATE_RET( A != NULL ); p[0] = ( b < 0 ) ? -b : b; - _B.s = ( b < 0 ) ? -1 : 1; - _B.n = 1; - _B.p = p; + B.s = ( b < 0 ) ? -1 : 1; + B.n = 1; + B.p = p; - return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) ); + return( mbedtls_mpi_div_mpi( Q, R, A, &B ) ); } /* @@ -1887,18 +2031,34 @@ static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N ) *mm = ~x + 1; } -/* - * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) +/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) + * + * \param[in,out] A One of the numbers to multiply. + * It must have at least as many limbs as N + * (A->n >= N->n), and any limbs beyond n are ignored. + * On successful completion, A contains the result of + * the multiplication A * B * R^-1 mod N where + * R = (2^ciL)^n. + * \param[in] B One of the numbers to multiply. + * It must be nonzero and must not have more limbs than N + * (B->n <= N->n). + * \param[in] N The modulo. N must be odd. + * \param mm The value calculated by `mpi_montg_init(&mm, N)`. + * This is -N^-1 mod 2^ciL. + * \param[in,out] T A bignum for temporary storage. + * It must be at least twice the limb size of N plus 2 + * (T->n >= 2 * (N->n + 1)). + * Its initial content is unused and + * its final content is indeterminate. + * Note that unlike the usual convention in the library + * for `const mbedtls_mpi*`, the content of T can change. */ -static int mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm, +static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T ) { size_t i, n, m; mbedtls_mpi_uint u0, u1, *d; - if( T->n < N->n + 1 || T->p == NULL ) - return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); - memset( T->p, 0, T->n * ciL ); d = T->p; @@ -1919,22 +2079,34 @@ static int mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *d++ = u0; d[n + 1] = 0; } - memcpy( A->p, d, ( n + 1 ) * ciL ); - - if( mbedtls_mpi_cmp_abs( A, N ) >= 0 ) - mpi_sub_hlp( n, N->p, A->p ); - else - /* prevent timing attacks */ - mpi_sub_hlp( n, A->p, T->p ); - - return( 0 ); + /* At this point, d is either the desired result or the desired result + * plus N. We now potentially subtract N, avoiding leaking whether the + * subtraction is performed through side channels. */ + + /* Copy the n least significant limbs of d to A, so that + * A = d if d < N (recall that N has n limbs). */ + memcpy( A->p, d, n * ciL ); + /* If d >= N then we want to set A to d - N. To prevent timing attacks, + * do the calculation without using conditional tests. */ + /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */ + d[n] += 1; + d[n] -= mpi_sub_hlp( n, d, N->p ); + /* If d0 < N then d < (2^biL)^n + * so d[n] == 0 and we want to keep A as it is. + * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n + * so d[n] == 1 and we want to set A to the result of the subtraction + * which is d - (2^biL)^n, i.e. the n least significant limbs of d. + * This exactly corresponds to a conditional assignment. */ + mpi_safe_cond_assign( n, A->p, d, (unsigned char) d[n] ); } /* * Montgomery reduction: A = A * R^-1 mod N + * + * See mpi_montmul() regarding constraints and guarantees on the parameters. */ -static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, - mbedtls_mpi_uint mm, const mbedtls_mpi *T ) +static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, + mbedtls_mpi_uint mm, const mbedtls_mpi *T ) { mbedtls_mpi_uint z = 1; mbedtls_mpi U; @@ -1942,7 +2114,73 @@ static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, U.n = U.s = (int) z; U.p = &z; - return( mpi_montmul( A, &U, N, mm, T ) ); + mpi_montmul( A, &U, N, mm, T ); +} + +/* + * Constant-flow boolean "equal" comparison: + * return x == y + * + * This function can be used to write constant-time code by replacing branches + * with bit operations - it can be used in conjunction with + * mbedtls_ssl_cf_mask_from_bit(). + * + * This function is implemented without using comparison operators, as those + * might be translated to branches by some compilers on some platforms. + */ +static size_t mbedtls_mpi_cf_bool_eq( size_t x, size_t y ) +{ + /* diff = 0 if x == y, non-zero otherwise */ + const size_t diff = x ^ y; + + /* MSVC has a warning about unary minus on unsigned integer types, + * but this is well-defined and precisely what we want to do here. */ +#if defined(_MSC_VER) +#pragma warning( push ) +#pragma warning( disable : 4146 ) +#endif + + /* diff_msb's most significant bit is equal to x != y */ + const size_t diff_msb = ( diff | (size_t) -diff ); + +#if defined(_MSC_VER) +#pragma warning( pop ) +#endif + + /* diff1 = (x != y) ? 1 : 0 */ + const size_t diff1 = diff_msb >> ( sizeof( diff_msb ) * 8 - 1 ); + + return( 1 ^ diff1 ); +} + +/** + * Select an MPI from a table without leaking the index. + * + * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it + * reads the entire table in order to avoid leaking the value of idx to an + * attacker able to observe memory access patterns. + * + * \param[out] R Where to write the selected MPI. + * \param[in] T The table to read from. + * \param[in] T_size The number of elements in the table. + * \param[in] idx The index of the element to select; + * this must satisfy 0 <= idx < T_size. + * + * \return \c 0 on success, or a negative error code. + */ +static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx ) +{ + int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA; + size_t i; + + for( i = 0; i < T_size; i++ ) + { + MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i], + (unsigned char) mbedtls_mpi_cf_bool_eq( i, idx ) ) ); + } + +cleanup: + return( ret ); } /* @@ -1950,14 +2188,14 @@ static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, */ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, - mbedtls_mpi *_RR ) + mbedtls_mpi *prec_RR ) { int ret; size_t wbits, wsize, one = 1; size_t i, j, nblimbs; size_t bufsize, nbits; mbedtls_mpi_uint ei, mm, state; - mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos; + mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos; int neg; MPI_VALIDATE_RET( X != NULL ); @@ -1971,12 +2209,17 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, if( mbedtls_mpi_cmp_int( E, 0 ) < 0 ) return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); + if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS || + mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS ) + return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); + /* * Init temps and window size */ mpi_montg_init( &mm, N ); mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &Apos ); + mbedtls_mpi_init( &WW ); memset( W, 0, sizeof( W ) ); i = mbedtls_mpi_bitlen( E ); @@ -1990,6 +2233,11 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, #endif j = N->n + 1; + /* All W[i] and X must have at least N->n limbs for the mpi_montmul() + * and mpi_montred() calls later. Here we ensure that W[1] and X are + * large enough, and later we'll grow other W[i] to the same length. + * They must not be shrunk midway through this function! + */ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) ); @@ -2008,17 +2256,17 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, /* * If 1st call, pre-compute R^2 mod N */ - if( _RR == NULL || _RR->p == NULL ) + if( prec_RR == NULL || prec_RR->p == NULL ) { MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) ); - if( _RR != NULL ) - memcpy( _RR, &RR, sizeof( mbedtls_mpi ) ); + if( prec_RR != NULL ) + memcpy( prec_RR, &RR, sizeof( mbedtls_mpi ) ); } else - memcpy( &RR, _RR, sizeof( mbedtls_mpi ) ); + memcpy( &RR, prec_RR, sizeof( mbedtls_mpi ) ); /* * W[1] = A * R^2 * R^-1 mod N = A * R mod N @@ -2027,14 +2275,18 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) ); else MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) ); + /* Re-grow W[1] if necessary. This should be only necessary in one corner + * case: when A == 0 represented with A.n == 0, mbedtls_mpi_copy shrinks + * W[1] to 0 limbs. */ + MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n +1 ) ); - MBEDTLS_MPI_CHK( mpi_montmul( &W[1], &RR, N, mm, &T ) ); + mpi_montmul( &W[1], &RR, N, mm, &T ); /* * X = R^2 * R^-1 mod N = R mod N */ MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) ); - MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) ); + mpi_montred( X, N, mm, &T ); if( wsize > 1 ) { @@ -2047,7 +2299,7 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) ); for( i = 0; i < wsize - 1; i++ ) - MBEDTLS_MPI_CHK( mpi_montmul( &W[j], &W[j], N, mm, &T ) ); + mpi_montmul( &W[j], &W[j], N, mm, &T ); /* * W[i] = W[i - 1] * W[1] @@ -2057,7 +2309,7 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) ); - MBEDTLS_MPI_CHK( mpi_montmul( &W[i], &W[1], N, mm, &T ) ); + mpi_montmul( &W[i], &W[1], N, mm, &T ); } } @@ -2094,7 +2346,7 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, /* * out of window, square X */ - MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) ); + mpi_montmul( X, X, N, mm, &T ); continue; } @@ -2112,12 +2364,13 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, * X = X^wsize R^-1 mod N */ for( i = 0; i < wsize; i++ ) - MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) ); + mpi_montmul( X, X, N, mm, &T ); /* * X = X * W[wbits] R^-1 mod N */ - MBEDTLS_MPI_CHK( mpi_montmul( X, &W[wbits], N, mm, &T ) ); + MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) ); + mpi_montmul( X, &WW, N, mm, &T ); state--; nbits = 0; @@ -2130,18 +2383,18 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, */ for( i = 0; i < nbits; i++ ) { - MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) ); + mpi_montmul( X, X, N, mm, &T ); wbits <<= 1; if( ( wbits & ( one << wsize ) ) != 0 ) - MBEDTLS_MPI_CHK( mpi_montmul( X, &W[1], N, mm, &T ) ); + mpi_montmul( X, &W[1], N, mm, &T ); } /* * X = A^E * R * R^-1 mod N = A^E mod N */ - MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) ); + mpi_montred( X, N, mm, &T ); if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 ) { @@ -2155,8 +2408,9 @@ cleanup: mbedtls_mpi_free( &W[i] ); mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos ); + mbedtls_mpi_free( &WW ); - if( _RR == NULL || _RR->p == NULL ) + if( prec_RR == NULL || prec_RR->p == NULL ) mbedtls_mpi_free( &RR ); return( ret ); @@ -2183,6 +2437,16 @@ int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B lz = mbedtls_mpi_lsb( &TA ); lzt = mbedtls_mpi_lsb( &TB ); + /* The loop below gives the correct result when A==0 but not when B==0. + * So have a special case for B==0. Leverage the fact that we just + * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test + * slightly more efficient than cmp_int(). */ + if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 ) + { + ret = mbedtls_mpi_copy( G, A ); + goto cleanup; + } + if( lzt < lz ) lz = lzt; @@ -2191,11 +2455,52 @@ int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B TA.s = TB.s = 1; + /* We mostly follow the procedure described in HAC 14.54, but with some + * minor differences: + * - Sequences of multiplications or divisions by 2 are grouped into a + * single shift operation. + * - The procedure in HAC assumes that 0 < TB <= TA. + * - The condition TB <= TA is not actually necessary for correctness. + * TA and TB have symmetric roles except for the loop termination + * condition, and the shifts at the beginning of the loop body + * remove any significance from the ordering of TA vs TB before + * the shifts. + * - If TA = 0, the loop goes through 0 iterations and the result is + * correctly TB. + * - The case TB = 0 was short-circuited above. + * + * For the correctness proof below, decompose the original values of + * A and B as + * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1 + * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1 + * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'), + * and gcd(A',B') is odd or 0. + * + * At the beginning, we have TA = |A|/2^a and TB = |B|/2^b. + * The code maintains the following invariant: + * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I) + */ + + /* Proof that the loop terminates: + * At each iteration, either the right-shift by 1 is made on a nonzero + * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases + * by at least 1, or the right-shift by 1 is made on zero and then + * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted + * since in that case TB is calculated from TB-TA with the condition TB>TA). + */ while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 ) { + /* Divisions by 2 preserve the invariant (I). */ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) ); + /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd, + * TA-TB is even so the division by 2 has an integer result. + * Invariant (I) is preserved since any odd divisor of both TA and TB + * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2 + * also divides TB, and any odd divisior of both TB and |TA-TB|/2 also + * divides TA. + */ if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 ) { MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) ); @@ -2206,8 +2511,18 @@ int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) ); } + /* Note that one of TA or TB is still odd. */ } + /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k. + * At the loop exit, TA = 0, so gcd(TA,TB) = TB. + * - If there was at least one loop iteration, then one of TA or TB is odd, + * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case, + * lz = min(a,b) so gcd(A,B) = 2^lz * TB. + * - If there was no loop iteration, then A was 0, and gcd(A,B) = B. + * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well. + */ + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) ); @@ -2247,7 +2562,7 @@ int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); Xp = (unsigned char*) X->p; - f_rng( p_rng, Xp + overhead, size ); + MBEDTLS_MPI_CHK( f_rng( p_rng, Xp + overhead, size ) ); mpi_bigendian_to_host( X->p, limbs ); |