summaryrefslogtreecommitdiff
path: root/thirdparty/mbedtls/library/bignum.c
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/mbedtls/library/bignum.c')
-rw-r--r--thirdparty/mbedtls/library/bignum.c230
1 files changed, 146 insertions, 84 deletions
diff --git a/thirdparty/mbedtls/library/bignum.c b/thirdparty/mbedtls/library/bignum.c
index 32578e2c68..37193f55a8 100644
--- a/thirdparty/mbedtls/library/bignum.c
+++ b/thirdparty/mbedtls/library/bignum.c
@@ -46,15 +46,7 @@
#include <limits.h>
#include <string.h>
-#if defined(MBEDTLS_PLATFORM_C)
#include "mbedtls/platform.h"
-#else
-#include <stdio.h>
-#include <stdlib.h>
-#define mbedtls_printf printf
-#define mbedtls_calloc calloc
-#define mbedtls_free free
-#endif
#define MPI_VALIDATE_RET( cond ) \
MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
@@ -270,6 +262,17 @@ void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
memcpy( Y, &T, sizeof( mbedtls_mpi ) );
}
+static inline mbedtls_mpi_uint mpi_sint_abs( mbedtls_mpi_sint z )
+{
+ if( z >= 0 )
+ return( z );
+ /* Take care to handle the most negative value (-2^(biL-1)) correctly.
+ * A naive -z would have undefined behavior.
+ * Write this in a way that makes popular compilers happy (GCC, Clang,
+ * MSVC). */
+ return( (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z );
+}
+
/*
* Set value from integer
*/
@@ -281,7 +284,7 @@ int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
memset( X->p, 0, X->n * ciL );
- X->p[0] = ( z < 0 ) ? -z : z;
+ X->p[0] = mpi_sint_abs( z );
X->s = ( z < 0 ) ? -1 : 1;
cleanup:
@@ -1101,7 +1104,7 @@ int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
mbedtls_mpi_uint p[1];
MPI_VALIDATE_RET( X != NULL );
- *p = ( z < 0 ) ? -z : z;
+ *p = mpi_sint_abs( z );
Y.s = ( z < 0 ) ? -1 : 1;
Y.n = 1;
Y.p = p;
@@ -1138,6 +1141,11 @@ int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
if( B->p[j - 1] != 0 )
break;
+ /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
+ * and B is 0 (of any size). */
+ if( j == 0 )
+ return( 0 );
+
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
o = B->p; p = X->p; c = 0;
@@ -1257,10 +1265,12 @@ cleanup:
return( ret );
}
-/*
- * Signed addition: X = A + B
+/* Common function for signed addition and subtraction.
+ * Calculate A + B * flip_B where flip_B is 1 or -1.
*/
-int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
+static int add_sub_mpi( mbedtls_mpi *X,
+ const mbedtls_mpi *A, const mbedtls_mpi *B,
+ int flip_B )
{
int ret, s;
MPI_VALIDATE_RET( X != NULL );
@@ -1268,16 +1278,21 @@ int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
MPI_VALIDATE_RET( B != NULL );
s = A->s;
- if( A->s * B->s < 0 )
+ if( A->s * B->s * flip_B < 0 )
{
- if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
+ int cmp = mbedtls_mpi_cmp_abs( A, B );
+ if( cmp >= 0 )
{
MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
- X->s = s;
+ /* If |A| = |B|, the result is 0 and we must set the sign bit
+ * to +1 regardless of which of A or B was negative. Otherwise,
+ * since |A| > |B|, the sign is the sign of A. */
+ X->s = cmp == 0 ? 1 : s;
}
else
{
MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
+ /* Since |A| < |B|, the sign is the opposite of A. */
X->s = -s;
}
}
@@ -1293,38 +1308,19 @@ cleanup:
}
/*
+ * Signed addition: X = A + B
+ */
+int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
+{
+ return( add_sub_mpi( X, A, B, 1 ) );
+}
+
+/*
* Signed subtraction: X = A - B
*/
int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
{
- int ret, s;
- MPI_VALIDATE_RET( X != NULL );
- MPI_VALIDATE_RET( A != NULL );
- MPI_VALIDATE_RET( B != NULL );
-
- s = A->s;
- if( A->s * B->s > 0 )
- {
- if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
- X->s = s;
- }
- else
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
- X->s = -s;
- }
- }
- else
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
- X->s = s;
- }
-
-cleanup:
-
- return( ret );
+ return( add_sub_mpi( X, A, B, -1 ) );
}
/*
@@ -1337,7 +1333,7 @@ int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( A != NULL );
- p[0] = ( b < 0 ) ? -b : b;
+ p[0] = mpi_sint_abs( b );
B.s = ( b < 0 ) ? -1 : 1;
B.n = 1;
B.p = p;
@@ -1355,7 +1351,7 @@ int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( A != NULL );
- p[0] = ( b < 0 ) ? -b : b;
+ p[0] = mpi_sint_abs( b );
B.s = ( b < 0 ) ? -1 : 1;
B.n = 1;
B.p = p;
@@ -1776,7 +1772,7 @@ int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
mbedtls_mpi_uint p[1];
MPI_VALIDATE_RET( A != NULL );
- p[0] = ( b < 0 ) ? -b : b;
+ p[0] = mpi_sint_abs( b );
B.s = ( b < 0 ) ? -1 : 1;
B.n = 1;
B.p = p;
@@ -2009,11 +2005,11 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
mbedtls_mpi *prec_RR )
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- size_t wbits, wsize, one = 1;
+ size_t window_bitsize;
size_t i, j, nblimbs;
size_t bufsize, nbits;
mbedtls_mpi_uint ei, mm, state;
- mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
+ mbedtls_mpi RR, T, W[ (size_t) 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
int neg;
MPI_VALIDATE_RET( X != NULL );
@@ -2042,21 +2038,59 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
i = mbedtls_mpi_bitlen( E );
- wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
+ window_bitsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
- if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
- wsize = MBEDTLS_MPI_WINDOW_SIZE;
+ if( window_bitsize > MBEDTLS_MPI_WINDOW_SIZE )
+ window_bitsize = MBEDTLS_MPI_WINDOW_SIZE;
#endif
+ const size_t w_table_used_size = (size_t) 1 << window_bitsize;
+
+ /*
+ * This function is not constant-trace: its memory accesses depend on the
+ * exponent value. To defend against timing attacks, callers (such as RSA
+ * and DHM) should use exponent blinding. However this is not enough if the
+ * adversary can find the exponent in a single trace, so this function
+ * takes extra precautions against adversaries who can observe memory
+ * access patterns.
+ *
+ * This function performs a series of multiplications by table elements and
+ * squarings, and we want the prevent the adversary from finding out which
+ * table element was used, and from distinguishing between multiplications
+ * and squarings. Firstly, when multiplying by an element of the window
+ * W[i], we do a constant-trace table lookup to obfuscate i. This leaves
+ * squarings as having a different memory access patterns from other
+ * multiplications. So secondly, we put the accumulator X in the table as
+ * well, and also do a constant-trace table lookup to multiply by X.
+ *
+ * This way, all multiplications take the form of a lookup-and-multiply.
+ * The number of lookup-and-multiply operations inside each iteration of
+ * the main loop still depends on the bits of the exponent, but since the
+ * other operations in the loop don't have an easily recognizable memory
+ * trace, an adversary is unlikely to be able to observe the exact
+ * patterns.
+ *
+ * An adversary may still be able to recover the exponent if they can
+ * observe both memory accesses and branches. However, branch prediction
+ * exploitation typically requires many traces of execution over the same
+ * data, which is defeated by randomized blinding.
+ *
+ * To achieve this, we make a copy of X and we use the table entry in each
+ * calculation from this point on.
+ */
+ const size_t x_index = 0;
+ mbedtls_mpi_init( &W[x_index] );
+ mbedtls_mpi_copy( &W[x_index], X );
+
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[x_index], j ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
@@ -2105,28 +2139,36 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
mpi_montmul( &W[1], &RR, N, mm, &T );
/*
- * X = R^2 * R^-1 mod N = R mod N
+ * W[x_index] = R^2 * R^-1 mod N = R mod N
*/
- MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
- mpi_montred( X, N, mm, &T );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[x_index], &RR ) );
+ mpi_montred( &W[x_index], N, mm, &T );
+
- if( wsize > 1 )
+ if( window_bitsize > 1 )
{
/*
- * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
+ * W[i] = W[1] ^ i
+ *
+ * The first bit of the sliding window is always 1 and therefore we
+ * only need to store the second half of the table.
+ *
+ * (There are two special elements in the table: W[0] for the
+ * accumulator/result and W[1] for A in Montgomery form. Both of these
+ * are already set at this point.)
*/
- j = one << ( wsize - 1 );
+ j = w_table_used_size / 2;
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
- for( i = 0; i < wsize - 1; i++ )
+ for( i = 0; i < window_bitsize - 1; i++ )
mpi_montmul( &W[j], &W[j], N, mm, &T );
/*
* W[i] = W[i - 1] * W[1]
*/
- for( i = j + 1; i < ( one << wsize ); i++ )
+ for( i = j + 1; i < w_table_used_size; i++ )
{
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
@@ -2138,7 +2180,7 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
nblimbs = E->n;
bufsize = 0;
nbits = 0;
- wbits = 0;
+ size_t exponent_bits_in_window = 0;
state = 0;
while( 1 )
@@ -2166,9 +2208,10 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
if( ei == 0 && state == 1 )
{
/*
- * out of window, square X
+ * out of window, square W[x_index]
*/
- mpi_montmul( X, X, N, mm, &T );
+ MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_table_used_size, x_index ) );
+ mpi_montmul( &W[x_index], &WW, N, mm, &T );
continue;
}
@@ -2178,25 +2221,30 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
state = 2;
nbits++;
- wbits |= ( ei << ( wsize - nbits ) );
+ exponent_bits_in_window |= ( ei << ( window_bitsize - nbits ) );
- if( nbits == wsize )
+ if( nbits == window_bitsize )
{
/*
- * X = X^wsize R^-1 mod N
+ * W[x_index] = W[x_index]^window_bitsize R^-1 mod N
*/
- for( i = 0; i < wsize; i++ )
- mpi_montmul( X, X, N, mm, &T );
+ for( i = 0; i < window_bitsize; i++ )
+ {
+ MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_table_used_size,
+ x_index ) );
+ mpi_montmul( &W[x_index], &WW, N, mm, &T );
+ }
/*
- * X = X * W[wbits] R^-1 mod N
+ * W[x_index] = W[x_index] * W[exponent_bits_in_window] R^-1 mod N
*/
- MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
- mpi_montmul( X, &WW, N, mm, &T );
+ MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_table_used_size,
+ exponent_bits_in_window ) );
+ mpi_montmul( &W[x_index], &WW, N, mm, &T );
state--;
nbits = 0;
- wbits = 0;
+ exponent_bits_in_window = 0;
}
}
@@ -2205,31 +2253,45 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
*/
for( i = 0; i < nbits; i++ )
{
- mpi_montmul( X, X, N, mm, &T );
+ MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_table_used_size, x_index ) );
+ mpi_montmul( &W[x_index], &WW, N, mm, &T );
- wbits <<= 1;
+ exponent_bits_in_window <<= 1;
- if( ( wbits & ( one << wsize ) ) != 0 )
- mpi_montmul( X, &W[1], N, mm, &T );
+ if( ( exponent_bits_in_window & ( (size_t) 1 << window_bitsize ) ) != 0 )
+ {
+ MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_table_used_size, 1 ) );
+ mpi_montmul( &W[x_index], &WW, N, mm, &T );
+ }
}
/*
- * X = A^E * R * R^-1 mod N = A^E mod N
+ * W[x_index] = A^E * R * R^-1 mod N = A^E mod N
*/
- mpi_montred( X, N, mm, &T );
+ mpi_montred( &W[x_index], N, mm, &T );
if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
{
- X->s = -1;
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
+ W[x_index].s = -1;
+ MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &W[x_index], N, &W[x_index] ) );
}
+ /*
+ * Load the result in the output variable.
+ */
+ mbedtls_mpi_copy( X, &W[x_index] );
+
cleanup:
- for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
+ /* The first bit of the sliding window is always 1 and therefore the first
+ * half of the table was unused. */
+ for( i = w_table_used_size/2; i < w_table_used_size; i++ )
mbedtls_mpi_free( &W[i] );
- mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
+ mbedtls_mpi_free( &W[x_index] );
+ mbedtls_mpi_free( &W[1] );
+ mbedtls_mpi_free( &T );
+ mbedtls_mpi_free( &Apos );
mbedtls_mpi_free( &WW );
if( prec_RR == NULL || prec_RR->p == NULL )
@@ -2862,7 +2924,7 @@ int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
else
{
/*
- * An necessary condition for Y and X = 2Y + 1 to be prime
+ * A necessary condition for Y and X = 2Y + 1 to be prime
* is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
* Make sure it is satisfied, while keeping X = 3 mod 4
*/
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 18:30:23 +0000