Import mbedtls-2.27.0
Imports Mbed TLS 2.27.0 from https://github.com/ARMmbed/mbedtls.git
commit f71e28780841 ("Merge pull request #843 from
paul-elliott-arm/mbedtls-2.27.0rc0-pr") (tag mbedtls-2.27.0, v2.27.0).
Files that are not needed are removed.
cd lib/libmbedtls
rm -rf mbedtls
cp -R path/to/mbedtls-2.27.0/mbedtls .
cd mbedtls
rm CMakeLists.txt DartConfiguration.tcl Makefile
rm .gitignore .travis.yml .pylintrc .globalrc .mypy.ini BRANCHES.md
rm include/.gitignore include/CMakeLists.txt library/.gitignore
rm library/CMakeLists.txt library/Makefile
rm -rf .git .github doxygen configs programs scripts tests visualc yotta
rm -rf 3rdparty ChangeLog.d docs
rm -rf include/mbedtls/config_psa.h include/psa
rm library/psa_* library/mps_*
cd ..
git add mbedtls
This is a complete overwrite of previous code so earlier changes in the
previous branch import/mbedtls-2.22.0 will be added on top of this commit.
Signed-off-by: Jerome Forissier <jerome@forissier.org>
diff --git a/lib/libmbedtls/mbedtls/library/bignum.c b/lib/libmbedtls/mbedtls/library/bignum.c
index 9478670..20afa22 100644
--- a/lib/libmbedtls/mbedtls/library/bignum.c
+++ b/lib/libmbedtls/mbedtls/library/bignum.c
@@ -1,8 +1,8 @@
-// SPDX-License-Identifier: Apache-2.0
/*
* Multi-precision integer library
*
- * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
+ * Copyright The Mbed TLS Contributors
+ * SPDX-License-Identifier: Apache-2.0
*
* Licensed under the Apache License, Version 2.0 (the "License"); you may
* not use this file except in compliance with the License.
@@ -15,8 +15,6 @@
* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* 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)
*/
/*
@@ -35,11 +33,7 @@
*
*/
-#if !defined(MBEDTLS_CONFIG_FILE)
-#include "mbedtls/config.h"
-#else
-#include MBEDTLS_CONFIG_FILE
-#endif
+#include "common.h"
#if defined(MBEDTLS_BIGNUM_C)
@@ -60,9 +54,6 @@
#define mbedtls_free free
#endif
-#include <mempool.h>
-#include <util.h>
-
#define MPI_VALIDATE_RET( cond ) \
MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
#define MPI_VALIDATE( cond ) \
@@ -81,8 +72,6 @@
#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
-void *mbedtls_mpi_mempool;
-
/* Implementation that should never be optimized out by the compiler */
static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
{
@@ -92,26 +81,15 @@
/*
* Initialize one MPI
*/
-static void mpi_init( mbedtls_mpi *X, short use_mempool )
+void mbedtls_mpi_init( mbedtls_mpi *X )
{
MPI_VALIDATE( X != NULL );
X->s = 1;
- X->use_mempool = use_mempool;
X->n = 0;
X->p = NULL;
}
-void mbedtls_mpi_init( mbedtls_mpi *X )
-{
- mpi_init( X, 0 /*use_mempool*/ );
-}
-
-void mbedtls_mpi_init_mempool( mbedtls_mpi *X )
-{
- mpi_init( X, !!mbedtls_mpi_mempool /*use_mempool*/ );
-}
-
/*
* Unallocate one MPI
*/
@@ -123,10 +101,7 @@
if( X->p != NULL )
{
mbedtls_mpi_zeroize( X->p, X->n );
- if( X->use_mempool )
- mempool_free( mbedtls_mpi_mempool, X->p );
- else
- mbedtls_free( X->p );
+ mbedtls_free( X->p );
}
X->s = 1;
@@ -147,28 +122,14 @@
if( X->n < nblimbs )
{
- if( X->use_mempool )
- {
- p = mempool_alloc( mbedtls_mpi_mempool, nblimbs * ciL );
- if( p == NULL )
- return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
- memset( p, 0, nblimbs * ciL );
- }
- else
- {
- p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL );
- if( p == NULL )
- return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
- }
+ if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
+ return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
if( X->p != NULL )
{
memcpy( p, X->p, X->n * ciL );
mbedtls_mpi_zeroize( X->p, X->n );
- if( X->use_mempool )
- mempool_free( mbedtls_mpi_mempool, X->p);
- else
- mbedtls_free( X->p );
+ mbedtls_free( X->p );
}
X->n = nblimbs;
@@ -204,28 +165,14 @@
if( i < nblimbs )
i = nblimbs;
- if( X->use_mempool )
- {
- p = mempool_alloc( mbedtls_mpi_mempool, i * ciL );
- if( p == NULL )
- return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
- memset( p, 0, i * ciL );
- }
- else
- {
- p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL );
- if( p == NULL )
- return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
- }
+ if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
+ return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
if( X->p != NULL )
{
memcpy( p, X->p, i * ciL );
mbedtls_mpi_zeroize( X->p, X->n );
- if( X->use_mempool )
- mempool_free( mbedtls_mpi_mempool, X->p );
- else
- mbedtls_free( X->p );
+ mbedtls_free( X->p );
}
X->n = i;
@@ -234,8 +181,35 @@
return( 0 );
}
+/* Resize X to have exactly n limbs and set it to 0. */
+static int mbedtls_mpi_resize_clear( mbedtls_mpi *X, size_t limbs )
+{
+ if( limbs == 0 )
+ {
+ mbedtls_mpi_free( X );
+ return( 0 );
+ }
+ else if( X->n == limbs )
+ {
+ memset( X->p, 0, limbs * ciL );
+ X->s = 1;
+ return( 0 );
+ }
+ else
+ {
+ mbedtls_mpi_free( X );
+ return( mbedtls_mpi_grow( X, limbs ) );
+ }
+}
+
/*
- * Copy the contents of Y into X
+ * Copy the contents of Y into X.
+ *
+ * This function is not constant-time. Leading zeros in Y may be removed.
+ *
+ * Ensure that X does not shrink. This is not guaranteed by the public API,
+ * but some code in the bignum module relies on this property, for example
+ * in mbedtls_mpi_exp_mod().
*/
int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
{
@@ -249,7 +223,11 @@
if( Y->n == 0 )
{
- mbedtls_mpi_free( X );
+ if( X->n != 0 )
+ {
+ X->s = 1;
+ memset( X->p, 0, X->n * ciL );
+ }
return( 0 );
}
@@ -290,6 +268,67 @@
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.
@@ -299,21 +338,34 @@
{
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 );
@@ -329,6 +381,7 @@
{
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 );
@@ -336,22 +389,35 @@
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:
@@ -508,6 +574,7 @@
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
size_t i, j, slen, n;
+ int sign = 1;
mbedtls_mpi_uint d;
mbedtls_mpi T;
MPI_VALIDATE_RET( X != NULL );
@@ -516,7 +583,19 @@
if( radix < 2 || radix > 16 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- mbedtls_mpi_init_mempool( &T );
+ mbedtls_mpi_init( &T );
+
+ if( s[0] == 0 )
+ {
+ mbedtls_mpi_free( X );
+ return( 0 );
+ }
+
+ if( s[0] == '-' )
+ {
+ ++s;
+ sign = -1;
+ }
slen = strlen( s );
@@ -532,12 +611,6 @@
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 );
}
@@ -548,26 +621,15 @@
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 );
@@ -653,7 +715,7 @@
}
p = buf;
- mbedtls_mpi_init_mempool( &T );
+ mbedtls_mpi_init( &T );
if( X->s == -1 )
{
@@ -886,14 +948,7 @@
size_t const limbs = CHARS_TO_LIMBS( buflen );
/* 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( mbedtls_mpi_resize_clear( X, limbs ) );
for( i = 0; i < buflen; i++ )
X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3);
@@ -922,19 +977,11 @@
MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
/* Ensure that target MPI has exactly the necessary number of limbs */
- if( X->n != limbs )
- {
- short use_mempool = X->use_mempool;
+ MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
- mbedtls_mpi_free( X );
- mpi_init( X, use_mempool );
- MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
- }
- MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
-
- /* Avoid calling `memcpy` with NULL source argument,
+ /* Avoid calling `memcpy` with NULL source or destination argument,
* even if buflen is 0. */
- if( buf != NULL )
+ if( buflen != 0 )
{
Xp = (unsigned char*) X->p;
memcpy( Xp + overhead, buf, buflen );
@@ -1376,70 +1423,92 @@
return( ret );
}
-/*
- * Helper for mbedtls_mpi subtraction
+/**
+ * Helper for mbedtls_mpi subtraction.
+ *
+ * Calculate l - r where l and r have the same size.
+ * This function operates modulo (2^ciL)^n and returns the carry
+ * (1 if there was a wraparound, i.e. if `l < r`, and 0 otherwise).
+ *
+ * d may be aliased to l or r.
+ *
+ * \param n Number of limbs of \p d, \p l and \p r.
+ * \param[out] d The result of the subtraction.
+ * \param[in] l The left operand.
+ * \param[in] r The right operand.
+ *
+ * \return 1 if `l < r`.
+ * 0 if `l >= r`.
*/
-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 *l,
+ const mbedtls_mpi_uint *r )
{
size_t i;
- mbedtls_mpi_uint c, z;
+ mbedtls_mpi_uint c = 0, t, z;
- for( i = c = 0; i < n; i++, s++, d++ )
+ for( i = 0; i < n; i++ )
{
- z = ( *d < c ); *d -= c;
- c = ( *d < *s ) + z; *d -= *s;
+ z = ( l[i] < c ); t = l[i] - c;
+ c = ( t < r[i] ) + z; d[i] = t - r[i];
}
- 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 = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
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_mempool( &TB );
-
- if( X == B )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
- B = &TB;
- }
-
- if( X != A )
- MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
-
- /*
- * X should always be positive as a result of unsigned subtractions.
- */
- X->s = 1;
-
- ret = 0;
-
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 );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) );
+
+ /* Set the high limbs of X to match A. Don't touch the lower limbs
+ * because X might be aliased to B, and we must not overwrite the
+ * significant digits of B. */
+ if( A->n > n )
+ memcpy( X->p + n, A->p + n, ( A->n - n ) * ciL );
+ if( X->n > A->n )
+ memset( X->p + A->n, 0, ( X->n - A->n ) * ciL );
+
+ carry = mpi_sub_hlp( n, X->p, A->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];
+ }
+
+ /* X should always be positive as a result of unsigned subtractions. */
+ X->s = 1;
cleanup:
-
- mbedtls_mpi_free( &TB );
-
return( ret );
}
@@ -1549,8 +1618,21 @@
return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
}
-/*
- * Helper for mbedtls_mpi multiplication
+/** Helper for mbedtls_mpi multiplication.
+ *
+ * Add \p b * \p s to \p d.
+ *
+ * \param i The number of limbs of \p s.
+ * \param[in] s A bignum to multiply, of size \p i.
+ * It may overlap with \p d, but only if
+ * \p d <= \p s.
+ * Its leading limb must not be \c 0.
+ * \param[in,out] d The bignum to add to.
+ * It must be sufficiently large to store the
+ * result of the multiplication. This means
+ * \p i + 1 limbs if \p d[\p i - 1] started as 0 and \p b
+ * is not known a priori.
+ * \param b A scalar to multiply.
*/
static
#if defined(__APPLE__) && defined(__arm__)
@@ -1560,7 +1642,10 @@
*/
__attribute__ ((noinline))
#endif
-void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
+void mpi_mul_hlp( size_t i,
+ const mbedtls_mpi_uint *s,
+ mbedtls_mpi_uint *d,
+ mbedtls_mpi_uint b )
{
mbedtls_mpi_uint c = 0, t = 0;
@@ -1615,10 +1700,10 @@
t++;
- do {
+ while( c != 0 )
+ {
*d += c; c = ( *d < c ); d++;
}
- while( c != 0 );
}
/*
@@ -1629,11 +1714,12 @@
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
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 );
- mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB );
+ mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
@@ -1641,10 +1727,14 @@
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 ) );
@@ -1652,7 +1742,14 @@
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:
@@ -1666,17 +1763,37 @@
*/
int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint 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;
- p[0] = b;
+ /* mpi_mul_hlp can't deal with a leading 0. */
+ size_t n = A->n;
+ while( n > 0 && A->p[n - 1] == 0 )
+ --n;
- return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
+ /* The general method below doesn't work if n==0 or b==0. By chance
+ * calculating the result is trivial in those cases. */
+ if( b == 0 || n == 0 )
+ {
+ return( mbedtls_mpi_lset( X, 0 ) );
+ }
+
+ /* Calculate A*b as A + A*(b-1) to take advantage of mpi_mul_hlp */
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+ /* In general, A * b requires 1 limb more than b. If
+ * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
+ * number of limbs as A and the call to grow() is not required since
+ * copy() will take care of the growth if needed. However, experimentally,
+ * making the call to grow() unconditional causes slightly fewer
+ * calls to calloc() in ECP code, presumably because it reuses the
+ * same mpi for a while and this way the mpi is more likely to directly
+ * grow to its final size. */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
+ mpi_mul_hlp( n, A->p, X->p, b - 1 );
+
+cleanup:
+ return( ret );
}
/*
@@ -1791,8 +1908,8 @@
if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
- mbedtls_mpi_init_mempool( &X ); mbedtls_mpi_init_mempool( &Y );
- mbedtls_mpi_init_mempool( &Z ); mbedtls_mpi_init_mempool( &T1 );
+ mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
+ mbedtls_mpi_init( &T1 );
/*
* Avoid dynamic memory allocations for constant-size T2.
*
@@ -1817,7 +1934,7 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) );
k = mbedtls_mpi_bitlen( &Y ) % biL;
if( k < biL - 1 )
@@ -2010,7 +2127,7 @@
/*
* Fast Montgomery initialization (thanks to Tom St Denis)
*/
-void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
+static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
{
mbedtls_mpi_uint x, m0 = N->p[0];
unsigned int i;
@@ -2024,19 +2141,34 @@
*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.
*/
-int mbedtls_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;
@@ -2057,22 +2189,34 @@
*d++ = u0; d[n + 1] = 0;
}
- memcpy( A->p, d, ( n + 1 ) * ciL );
+ /* 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. */
- 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 );
+ /* 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, 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.
*/
-int mbedtls_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;
@@ -2080,7 +2224,72 @@
U.n = U.s = (int) z;
U.p = &z;
- return( mbedtls_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_ERROR_CORRUPTION_DETECTED;
+
+ for( size_t 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 );
}
/*
@@ -2095,9 +2304,7 @@
size_t i, j, nblimbs;
size_t bufsize, nbits;
mbedtls_mpi_uint ei, mm, state;
- mbedtls_mpi RR, T, Apos;
- mbedtls_mpi *W = NULL;
- const size_t array_size_W = 2 << MBEDTLS_MPI_WINDOW_SIZE;
+ mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
int neg;
MPI_VALIDATE_RET( X != NULL );
@@ -2111,12 +2318,18 @@
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
*/
- mbedtls_mpi_montg_init( &mm, N );
- mbedtls_mpi_init_mempool( &RR ); mbedtls_mpi_init_mempool( &T );
- mbedtls_mpi_init_mempool( &Apos );
+ 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 );
@@ -2129,8 +2342,13 @@
#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 ) );
/*
@@ -2159,31 +2377,29 @@
else
memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
- W = mempool_alloc( mbedtls_mpi_mempool,
- sizeof( mbedtls_mpi ) * array_size_W );
- if( W == NULL ) {
- ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
- goto cleanup;
- }
- for( i = 0; i < array_size_W; i++ )
- mbedtls_mpi_init_mempool( W + i );
- MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
-
/*
* W[1] = A * R^2 * R^-1 mod N = A * R mod N
*/
if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
+ {
MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
+ /* This should be a no-op because W[1] is already that large before
+ * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
+ * in mpi_montmul() below, so let's make sure. */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) );
+ }
else
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[1], &RR, N, mm, &T ) );
+ /* Note that this is safe because W[1] always has at least N->n limbs
+ * (it grew above and was preserved by mbedtls_mpi_copy()). */
+ 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( mbedtls_mpi_montred( X, N, mm, &T ) );
+ mpi_montred( X, N, mm, &T );
if( wsize > 1 )
{
@@ -2196,7 +2412,7 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
for( i = 0; i < wsize - 1; i++ )
- MBEDTLS_MPI_CHK( mbedtls_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]
@@ -2206,7 +2422,7 @@
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( mbedtls_mpi_montmul( &W[i], &W[1], N, mm, &T ) );
+ mpi_montmul( &W[i], &W[1], N, mm, &T );
}
}
@@ -2243,7 +2459,7 @@
/*
* out of window, square X
*/
- MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) );
+ mpi_montmul( X, X, N, mm, &T );
continue;
}
@@ -2261,12 +2477,13 @@
* X = X^wsize R^-1 mod N
*/
for( i = 0; i < wsize; i++ )
- MBEDTLS_MPI_CHK( mbedtls_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( mbedtls_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;
@@ -2279,18 +2496,18 @@
*/
for( i = 0; i < nbits; i++ )
{
- MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) );
+ mpi_montmul( X, X, N, mm, &T );
wbits <<= 1;
if( ( wbits & ( one << wsize ) ) != 0 )
- MBEDTLS_MPI_CHK( mbedtls_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( mbedtls_mpi_montred( X, N, mm, &T ) );
+ mpi_montred( X, N, mm, &T );
if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
{
@@ -2300,12 +2517,11 @@
cleanup:
- if( W )
- for( i = 0; i < array_size_W; i++ )
- mbedtls_mpi_free( W + i );
- mempool_free( mbedtls_mpi_mempool , W );
+ for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
+ mbedtls_mpi_free( &W[i] );
- mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
+ mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
+ mbedtls_mpi_free( &WW );
if( _RR == NULL || _RR->p == NULL )
mbedtls_mpi_free( &RR );
@@ -2326,7 +2542,7 @@
MPI_VALIDATE_RET( A != NULL );
MPI_VALIDATE_RET( B != NULL );
- mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB );
+ mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
@@ -2334,19 +2550,67 @@
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;
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
-
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| and TB = |B| so gcd(A,B) = gcd(TA,TB).
+ * 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 ) );
@@ -2357,8 +2621,18 @@
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 ) );
@@ -2369,6 +2643,33 @@
return( ret );
}
+/* Fill X with n_bytes random bytes.
+ * X must already have room for those bytes.
+ * The ordering of the bytes returned from the RNG is suitable for
+ * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()).
+ * The size and sign of X are unchanged.
+ * n_bytes must not be 0.
+ */
+static int mpi_fill_random_internal(
+ mbedtls_mpi *X, size_t n_bytes,
+ int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+{
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+ const size_t limbs = CHARS_TO_LIMBS( n_bytes );
+ const size_t overhead = ( limbs * ciL ) - n_bytes;
+
+ if( X->n < limbs )
+ return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+
+ memset( X->p, 0, overhead );
+ memset( (unsigned char *) X->p + limbs * ciL, 0, ( X->n - limbs ) * ciL );
+ MBEDTLS_MPI_CHK( f_rng( p_rng, (unsigned char *) X->p + overhead, n_bytes ) );
+ mpi_bigendian_to_host( X->p, limbs );
+
+cleanup:
+ return( ret );
+}
+
/*
* Fill X with size bytes of random.
*
@@ -2382,30 +2683,96 @@
{
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
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 );
/* 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( mbedtls_mpi_resize_clear( X, limbs ) );
+ if( size == 0 )
+ return( 0 );
- Xp = (unsigned char*) X->p;
- f_rng( p_rng, Xp + overhead, size );
-
- mpi_bigendian_to_host( X->p, limbs );
+ ret = mpi_fill_random_internal( X, size, f_rng, p_rng );
cleanup:
return( ret );
}
+int mbedtls_mpi_random( mbedtls_mpi *X,
+ mbedtls_mpi_sint min,
+ const mbedtls_mpi *N,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+ int count;
+ unsigned lt_lower = 1, lt_upper = 0;
+ size_t n_bits = mbedtls_mpi_bitlen( N );
+ size_t n_bytes = ( n_bits + 7 ) / 8;
+ mbedtls_mpi lower_bound;
+
+ if( min < 0 )
+ return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+ if( mbedtls_mpi_cmp_int( N, min ) <= 0 )
+ return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+
+ /*
+ * When min == 0, each try has at worst a probability 1/2 of failing
+ * (the msb has a probability 1/2 of being 0, and then the result will
+ * be < N), so after 30 tries failure probability is a most 2**(-30).
+ *
+ * When N is just below a power of 2, as is the case when generating
+ * a random scalar on most elliptic curves, 1 try is enough with
+ * overwhelming probability. When N is just above a power of 2,
+ * as when generating a random scalar on secp224k1, each try has
+ * a probability of failing that is almost 1/2.
+ *
+ * The probabilities are almost the same if min is nonzero but negligible
+ * compared to N. This is always the case when N is crypto-sized, but
+ * it's convenient to support small N for testing purposes. When N
+ * is small, use a higher repeat count, otherwise the probability of
+ * failure is macroscopic.
+ */
+ count = ( n_bytes > 4 ? 30 : 250 );
+
+ mbedtls_mpi_init( &lower_bound );
+
+ /* Ensure that target MPI has exactly the same number of limbs
+ * as the upper bound, even if the upper bound has leading zeros.
+ * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
+
+ /*
+ * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
+ * when f_rng is a suitably parametrized instance of HMAC_DRBG:
+ * - use the same byte ordering;
+ * - keep the leftmost n_bits bits of the generated octet string;
+ * - try until result is in the desired range.
+ * This also avoids any bias, which is especially important for ECDSA.
+ */
+ do
+ {
+ MBEDTLS_MPI_CHK( mpi_fill_random_internal( X, n_bytes, f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) );
+
+ if( --count == 0 )
+ {
+ ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
+ goto cleanup;
+ }
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, <_lower ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, <_upper ) );
+ }
+ while( lt_lower != 0 || lt_upper == 0 );
+
+cleanup:
+ mbedtls_mpi_free( &lower_bound );
+ return( ret );
+}
+
/*
* Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
*/
@@ -2420,11 +2787,9 @@
if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TU );
- mbedtls_mpi_init_mempool( &U1 ); mbedtls_mpi_init_mempool( &U2 );
- mbedtls_mpi_init_mempool( &G ); mbedtls_mpi_init_mempool( &TB );
- mbedtls_mpi_init_mempool( &TV ); mbedtls_mpi_init_mempool( &V1 );
- mbedtls_mpi_init_mempool( &V2 );
+ mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
+ mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
+ mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
@@ -2580,9 +2945,9 @@
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( f_rng != NULL );
- mbedtls_mpi_init_mempool( &W ); mbedtls_mpi_init_mempool( &R );
- mbedtls_mpi_init_mempool( &T ); mbedtls_mpi_init_mempool( &A );
- mbedtls_mpi_init_mempool( &RR );
+ mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
+ mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
+ mbedtls_mpi_init( &RR );
/*
* W = |X| - 1
@@ -2608,7 +2973,7 @@
A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
}
- if (count++ > 300) {
+ if (count++ > 30) {
ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
goto cleanup;
}
@@ -2743,7 +3108,7 @@
if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- mbedtls_mpi_init_mempool( &Y );
+ mbedtls_mpi_init( &Y );
n = BITS_TO_LIMBS( nbits );
@@ -2861,10 +3226,8 @@
int ret, i;
mbedtls_mpi A, E, N, X, Y, U, V;
- mbedtls_mpi_init_mempool( &A ); mbedtls_mpi_init_mempool( &E );
- mbedtls_mpi_init_mempool( &N ); mbedtls_mpi_init_mempool( &X );
- mbedtls_mpi_init_mempool( &Y ); mbedtls_mpi_init_mempool( &U );
- mbedtls_mpi_init_mempool( &V );
+ mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
+ mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
"EFE021C2645FD1DC586E69184AF4A31E" \
@@ -3005,7 +3368,7 @@
cleanup:
if( ret != 0 && verbose != 0 )
- mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
+ mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );