Remove temporary stack-buffer from mbedtls_mpi_fill_random()
Context: The function `mbedtls_mpi_fill_random()` uses a temporary stack
buffer to hold the random data before reading it into the target MPI.
Problem: This is inefficient both computationally and memory-wise.
Memory-wise, it may lead to a stack overflow on constrained devices with
limited stack.
Fix: This commit introduces the following changes to get rid of the
temporary stack buffer entirely:
1. It modifies the call to the PRNG to output the random data directly
into the target MPI's data buffer.
This alone, however, constitutes a change of observable behaviour:
The previous implementation guaranteed to interpret the bytes emitted by
the PRNG in a big-endian fashion, while rerouting the PRNG output into the
target MPI's limb array leads to an interpretation that depends on the
endianness of the host machine.
As a remedy, the following change is applied, too:
2. Reorder the bytes emitted from the PRNG within the target MPI's
data buffer to ensure big-endian semantics.
Luckily, the byte reordering was already implemented as part of
`mbedtls_mpi_read_binary()`, so:
3. Extract bigendian-to-host byte reordering from
`mbedtls_mpi_read_binary()` to a separate internal function
`mpi_bigendian_to_host()` to be used by `mbedtls_mpi_read_binary()`
and `mbedtls_mpi_fill_random()`.
diff --git a/library/bignum.c b/library/bignum.c
index f968a0a..d141a17 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -715,14 +715,70 @@
}
#endif /* MBEDTLS_FS_IO */
+
+/* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
+ * into the storage form used by mbedtls_mpi. */
+static int mpi_bigendian_to_host( unsigned char * const buf, size_t size )
+{
+ mbedtls_mpi_uint * const p = (mbedtls_mpi_uint *) buf;
+ size_t const limbs = size / ciL;
+ size_t i;
+
+ unsigned char *cur_byte_left;
+ unsigned char *cur_byte_right;
+
+ mbedtls_mpi_uint *cur_limb_left;
+ mbedtls_mpi_uint *cur_limb_right;
+
+ mbedtls_mpi_uint tmp_left, tmp_right;
+
+ if( size % ciL != 0 || limbs == 0 )
+ return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+
+ /*
+ * Traverse limbs and
+ * - adapt byte-order in each limb
+ * - swap the limbs themselves.
+ * For that, simultaneously traverse the limbs from left to right
+ * and from right to left, as long as the left index is not bigger
+ * than the right index (it's not a problem if limbs is odd and the
+ * indices coincide in the last iteration).
+ */
+
+ for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
+ cur_limb_left <= cur_limb_right;
+ cur_limb_left++, cur_limb_right-- )
+ {
+ cur_byte_left = (unsigned char*) cur_limb_left;
+ cur_byte_right = (unsigned char*) cur_limb_right;
+
+ tmp_left = 0;
+ tmp_right = 0;
+
+ for( i = 0; i < ciL; i++ )
+ {
+ tmp_left |= ( (mbedtls_mpi_uint) *cur_byte_left++ )
+ << ( ( ciL - 1 - i ) << 3 );
+ tmp_right |= ( (mbedtls_mpi_uint) *cur_byte_right++ )
+ << ( ( ciL - 1 - i ) << 3 );
+ }
+
+ *cur_limb_right = tmp_left;
+ *cur_limb_left = tmp_right;
+ }
+
+ return( 0 );
+}
+
/*
* Import X from unsigned binary data, big endian
*/
int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
{
int ret;
- size_t i, j;
- size_t const limbs = CHARS_TO_LIMBS( buflen );
+ size_t const limbs = CHARS_TO_LIMBS( buflen );
+ size_t const overhead = ( limbs * ciL ) - buflen;
+ unsigned char *Xp;
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
@@ -734,11 +790,12 @@
mbedtls_mpi_init( X );
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
}
-
MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
- for( i = buflen, j = 0; i > 0; i--, j++ )
- X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
+ Xp = (unsigned char*) X->p;
+ memcpy( Xp + overhead, buf, buflen );
+
+ MBEDTLS_MPI_CHK( mpi_bigendian_to_host( Xp, limbs * ciL ) );
cleanup:
@@ -2008,18 +2065,28 @@
void *p_rng )
{
int ret;
- unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
+ size_t const limbs CHARS_TO_LIMBS( size );
+ size_t const overhead = ( limbs * ciL ) - size;
+ unsigned char *Xp;
+
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( f_rng != NULL );
- if( size > MBEDTLS_MPI_MAX_SIZE )
- return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+ /* Ensure that target MPI has exactly the necessary number of limbs */
+ if( X->n != limbs )
+ {
+ mbedtls_mpi_free( X );
+ mbedtls_mpi_init( X );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
+ }
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
- MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
+ Xp = (unsigned char*) X->p;
+ f_rng( p_rng, Xp + overhead, size );
+
+ MBEDTLS_MPI_CHK( mpi_bigendian_to_host( Xp, limbs * ciL ) );
cleanup:
- mbedtls_platform_zeroize( buf, sizeof( buf ) );
return( ret );
}