Merge pull request #4276 from gilles-peskine-arm/random-range-uniformity
Backport 2.x: Fix non-uniform random generation in a range
diff --git a/ChangeLog.d/mpi_random.txt b/ChangeLog.d/mpi_random.txt
new file mode 100644
index 0000000..9e6a416
--- /dev/null
+++ b/ChangeLog.d/mpi_random.txt
@@ -0,0 +1,3 @@
+Features
+ * The new function mbedtls_mpi_random() generates a random value in a
+ given range uniformly.
diff --git a/ChangeLog.d/random-range.txt b/ChangeLog.d/random-range.txt
new file mode 100644
index 0000000..dc35ec6
--- /dev/null
+++ b/ChangeLog.d/random-range.txt
@@ -0,0 +1,4 @@
+Security
+* Fix a bias in the generation of finite-field Diffie-Hellman-Merkle (DHM)
+ private keys and of blinding values for DHM and elliptic curves (ECP)
+ computations. Reported by FlorianF89 in #4245.
diff --git a/include/mbedtls/bignum.h b/include/mbedtls/bignum.h
index 637360e..f087035 100644
--- a/include/mbedtls/bignum.h
+++ b/include/mbedtls/bignum.h
@@ -871,6 +871,44 @@
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng );
+/** Generate a random number uniformly in a range.
+ *
+ * This function generates a random number between \p min inclusive and
+ * \p N exclusive.
+ *
+ * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA)
+ * when the RNG is a suitably parametrized instance of HMAC_DRBG
+ * and \p min is \c 1.
+ *
+ * \note There are `N - min` possible outputs. The lower bound
+ * \p min can be reached, but the upper bound \p N cannot.
+ *
+ * \param X The destination MPI. This must point to an initialized MPI.
+ * \param min The minimum value to return.
+ * It must be nonnegative.
+ * \param N The upper bound of the range, exclusive.
+ * In other words, this is one plus the maximum value to return.
+ * \p N must be strictly larger than \p min.
+ * \param f_rng The RNG function to use. This must not be \c NULL.
+ * \param p_rng The RNG parameter to be passed to \p f_rng.
+ *
+ * \return \c 0 if successful.
+ * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed.
+ * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p min or \p N is invalid
+ * or if they are incompatible.
+ * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was
+ * unable to find a suitable value within a limited number
+ * of attempts. This has a negligible probability if \p N
+ * is significantly larger than \p min, which is the case
+ * for all usual cryptographic applications.
+ * \return Another negative error code on failure.
+ */
+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 );
+
/**
* \brief Compute the greatest common divisor: G = gcd(A, B)
*
diff --git a/library/bignum.c b/library/bignum.c
index e00204b..3acc4b9 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -181,6 +181,27 @@
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
*/
@@ -838,14 +859,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);
@@ -874,17 +888,11 @@
MPI_VALIDATE_RET( buflen == 0 || buf != 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 ) );
- /* 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 );
@@ -2395,6 +2403,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.
*
@@ -2408,25 +2443,84 @@
{
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_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
+ if( size == 0 )
+ return( 0 );
+
+ 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 cmp = 0;
+ size_t n_bits = mbedtls_mpi_bitlen( N );
+ size_t n_bytes = ( n_bits + 7 ) / 8;
+
+ 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 );
+
+ /* 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 ) );
+
+ /*
+ * 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_free( X );
- mbedtls_mpi_init( X );
- MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
+ 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, N, &cmp ) );
}
- MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
-
- Xp = (unsigned char*) X->p;
- MBEDTLS_MPI_CHK( f_rng( p_rng, Xp + overhead, size ) );
-
- mpi_bigendian_to_host( X->p, limbs );
+ while( mbedtls_mpi_cmp_int( X, min ) < 0 || cmp != 1 );
cleanup:
return( ret );
diff --git a/library/dhm.c b/library/dhm.c
index 9758af7..accd5a8 100644
--- a/library/dhm.c
+++ b/library/dhm.c
@@ -100,22 +100,21 @@
*/
static int dhm_check_range( const mbedtls_mpi *param, const mbedtls_mpi *P )
{
- mbedtls_mpi L, U;
+ mbedtls_mpi U;
int ret = 0;
- mbedtls_mpi_init( &L ); mbedtls_mpi_init( &U );
+ mbedtls_mpi_init( &U );
- MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &L, 2 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &U, P, 2 ) );
- if( mbedtls_mpi_cmp_mpi( param, &L ) < 0 ||
+ if( mbedtls_mpi_cmp_int( param, 2 ) < 0 ||
mbedtls_mpi_cmp_mpi( param, &U ) > 0 )
{
ret = MBEDTLS_ERR_DHM_BAD_INPUT_DATA;
}
cleanup:
- mbedtls_mpi_free( &L ); mbedtls_mpi_free( &U );
+ mbedtls_mpi_free( &U );
return( ret );
}
@@ -151,38 +150,44 @@
}
/*
- * Setup and write the ServerKeyExchange parameters
+ * Pick a random R in the range [2, M-2] for blinding or key generation.
*/
-int mbedtls_dhm_make_params( mbedtls_dhm_context *ctx, int x_size,
- unsigned char *output, size_t *olen,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng )
+static int dhm_random_below( mbedtls_mpi *R, const mbedtls_mpi *M,
+ int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
{
- int ret, count = 0;
- size_t n1, n2, n3;
- unsigned char *p;
- DHM_VALIDATE_RET( ctx != NULL );
- DHM_VALIDATE_RET( output != NULL );
- DHM_VALIDATE_RET( olen != NULL );
- DHM_VALIDATE_RET( f_rng != NULL );
+ int ret;
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_random( R, 3, M, f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( R, R, 1 ) );
+
+cleanup:
+ return( ret );
+}
+
+static int dhm_make_common( mbedtls_dhm_context *ctx, int x_size,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret = 0;
if( mbedtls_mpi_cmp_int( &ctx->P, 0 ) == 0 )
return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
+ if( x_size < 0 )
+ return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
- /*
- * Generate X as large as possible ( < P )
- */
- do
+ if( (unsigned) x_size < mbedtls_mpi_size( &ctx->P ) )
{
MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->X, x_size, f_rng, p_rng ) );
-
- while( mbedtls_mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx->X, 1 ) );
-
- if( count++ > 10 )
- return( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED );
}
- while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
+ else
+ {
+ /* Generate X as large as possible ( <= P - 2 ) */
+ ret = dhm_random_below( &ctx->X, &ctx->P, f_rng, p_rng );
+ if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
+ return( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED );
+ if( ret != 0 )
+ return( ret );
+ }
/*
* Calculate GX = G^X mod P
@@ -193,8 +198,33 @@
if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
return( ret );
+cleanup:
+ return( ret );
+}
+
+/*
+ * Setup and write the ServerKeyExchange parameters
+ */
+int mbedtls_dhm_make_params( mbedtls_dhm_context *ctx, int x_size,
+ unsigned char *output, size_t *olen,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret;
+ size_t n1, n2, n3;
+ unsigned char *p;
+ DHM_VALIDATE_RET( ctx != NULL );
+ DHM_VALIDATE_RET( output != NULL );
+ DHM_VALIDATE_RET( olen != NULL );
+ DHM_VALIDATE_RET( f_rng != NULL );
+
+ ret = dhm_make_common( ctx, x_size, f_rng, p_rng );
+ if( ret != 0 )
+ goto cleanup;
+
/*
- * export P, G, GX
+ * Export P, G, GX. RFC 5246 §4.4 states that "leading zero octets are
+ * not required". We omit leading zeros for compactness.
*/
#define DHM_MPI_EXPORT( X, n ) \
do { \
@@ -220,11 +250,9 @@
ctx->len = n1;
cleanup:
-
- if( ret != 0 )
- return( MBEDTLS_ERROR_ADD( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED, ret ) );
-
- return( 0 );
+ if( ret != 0 && ret > -128 )
+ ret = MBEDTLS_ERROR_ADD( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED, ret );
+ return( ret );
}
/*
@@ -276,7 +304,7 @@
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
- int ret, count = 0;
+ int ret;
DHM_VALIDATE_RET( ctx != NULL );
DHM_VALIDATE_RET( output != NULL );
DHM_VALIDATE_RET( f_rng != NULL );
@@ -284,62 +312,17 @@
if( olen < 1 || olen > ctx->len )
return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
- if( mbedtls_mpi_cmp_int( &ctx->P, 0 ) == 0 )
- return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
-
- /*
- * generate X and calculate GX = G^X mod P
- */
- do
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->X, x_size, f_rng, p_rng ) );
-
- while( mbedtls_mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx->X, 1 ) );
-
- if( count++ > 10 )
- return( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED );
- }
- while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
- &ctx->P , &ctx->RP ) );
-
- if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
- return( ret );
+ ret = dhm_make_common( ctx, x_size, f_rng, p_rng );
+ if( ret == MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED )
+ return( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED );
+ if( ret != 0 )
+ goto cleanup;
MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &ctx->GX, output, olen ) );
cleanup:
-
- if( ret != 0 )
- return( MBEDTLS_ERROR_ADD( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED, ret ) );
-
- return( 0 );
-}
-
-/*
- * Pick a random R in the range [2, M) for blinding purposes
- */
-static int dhm_random_below( mbedtls_mpi *R, const mbedtls_mpi *M,
- int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
-{
- int ret, count;
-
- count = 0;
- do
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( R, mbedtls_mpi_size( M ), f_rng, p_rng ) );
-
- while( mbedtls_mpi_cmp_mpi( R, M ) >= 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( R, 1 ) );
-
- if( count++ > 10 )
- return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
- }
- while( mbedtls_mpi_cmp_int( R, 1 ) <= 0 );
-
-cleanup:
+ if( ret != 0 && ret > -128 )
+ ret = MBEDTLS_ERROR_ADD( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED, ret );
return( ret );
}
@@ -390,7 +373,7 @@
* We need to generate blinding values from scratch
*/
- /* Vi = random( 2, P-1 ) */
+ /* Vi = random( 2, P-2 ) */
MBEDTLS_MPI_CHK( dhm_random_below( &ctx->Vi, &ctx->P, f_rng, p_rng ) );
/* Vf = Vi^-X mod P
@@ -454,8 +437,9 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->K, &ctx->K, &ctx->P ) );
}
+ /* Output the secret without any leading zero byte. This is mandatory
+ * for TLS per RFC 5246 §8.1.2. */
*olen = mbedtls_mpi_size( &ctx->K );
-
MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &ctx->K, output, *olen ) );
cleanup:
diff --git a/library/ecp.c b/library/ecp.c
index 6b29415..f748704 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -1701,26 +1701,11 @@
#else
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
mbedtls_mpi l, ll;
- int count = 0;
- size_t p_size = ( grp->pbits + 7 ) / 8;
mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
/* Generate l such that 1 < l < p */
- do
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
-
- while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
-
- if( count++ > 10 )
- {
- ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
- goto cleanup;
- }
- }
- while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_random( &l, 2, &grp->P, f_rng, p_rng ) );
/* Z = l * Z */
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Z, &pt->Z, &l ) );
@@ -1736,6 +1721,8 @@
cleanup:
mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
+ if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
+ ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
return( ret );
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) */
}
@@ -2485,25 +2472,10 @@
#else
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
mbedtls_mpi l;
- int count = 0;
- size_t p_size = ( grp->pbits + 7 ) / 8;
mbedtls_mpi_init( &l );
/* Generate l such that 1 < l < p */
- do
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
-
- while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
-
- if( count++ > 10 )
- {
- ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
- goto cleanup;
- }
- }
- while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_random( &l, 2, &grp->P, f_rng, p_rng ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->X, &P->X, &l ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->Z, &P->Z, &l ) );
@@ -2511,6 +2483,8 @@
cleanup:
mbedtls_mpi_free( &l );
+ if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
+ ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
return( ret );
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) */
}
@@ -3040,6 +3014,56 @@
return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
}
+#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
+MBEDTLS_STATIC_TESTABLE
+int mbedtls_ecp_gen_privkey_mx( size_t high_bit,
+ mbedtls_mpi *d,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
+ size_t n_random_bytes = high_bit / 8 + 1;
+
+ /* [Curve25519] page 5 */
+ /* Generate a (high_bit+1)-bit random number by generating just enough
+ * random bytes, then shifting out extra bits from the top (necessary
+ * when (high_bit+1) is not a multiple of 8). */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_random_bytes,
+ f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_random_bytes - high_bit - 1 ) );
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, high_bit, 1 ) );
+
+ /* Make sure the last two bits are unset for Curve448, three bits for
+ Curve25519 */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
+ if( high_bit == 254 )
+ {
+ MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
+ }
+
+cleanup:
+ return( ret );
+}
+#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
+
+#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
+static int mbedtls_ecp_gen_privkey_sw(
+ const mbedtls_mpi *N, mbedtls_mpi *d,
+ int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+{
+ int ret = mbedtls_mpi_random( d, 1, N, f_rng, p_rng );
+ switch( ret )
+ {
+ case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE:
+ return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
+ default:
+ return( ret );
+ }
+}
+#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
+
/*
* Generate a private key
*/
@@ -3048,89 +3072,21 @@
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
- int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
- size_t n_size;
-
ECP_VALIDATE_RET( grp != NULL );
ECP_VALIDATE_RET( d != NULL );
ECP_VALIDATE_RET( f_rng != NULL );
- n_size = ( grp->nbits + 7 ) / 8;
-
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
- {
- /* [M225] page 5 */
- size_t b;
-
- do {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
- } while( mbedtls_mpi_bitlen( d ) == 0);
-
- /* Make sure the most significant bit is nbits */
- b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
- if( b > grp->nbits )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );
- else
- MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );
-
- /* Make sure the last two bits are unset for Curve448, three bits for
- Curve25519 */
- MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
- if( grp->nbits == 254 )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
- }
- }
+ return( mbedtls_ecp_gen_privkey_mx( grp->nbits, d, f_rng, p_rng ) );
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
- {
- /* SEC1 3.2.1: Generate d such that 1 <= n < N */
- int count = 0;
- unsigned cmp = 0;
-
- /*
- * Match the procedure given in RFC 6979 (deterministic ECDSA):
- * - use the same byte ordering;
- * - keep the leftmost nbits bits of the generated octet string;
- * - try until result is in the desired range.
- * This also avoids any biais, which is especially important for ECDSA.
- */
- do
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
-
- /*
- * 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).
- *
- * For most curves, 1 try is enough with overwhelming probability,
- * since N starts with a lot of 1s in binary, but some curves
- * such as secp224k1 are actually very close to the worst case.
- */
- if( ++count > 30 )
- {
- ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
- goto cleanup;
- }
-
- ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp );
- if( ret != 0 )
- {
- goto cleanup;
- }
- }
- while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 );
- }
+ return( mbedtls_ecp_gen_privkey_sw( &grp->N, d, f_rng, p_rng ) );
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
-cleanup:
- return( ret );
+ return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
}
/*
diff --git a/library/ecp_invasive.h b/library/ecp_invasive.h
index b523967..71c7702 100644
--- a/library/ecp_invasive.h
+++ b/library/ecp_invasive.h
@@ -27,6 +27,7 @@
#define MBEDTLS_ECP_INVASIVE_H
#include "common.h"
+#include "mbedtls/bignum.h"
#include "mbedtls/ecp.h"
#if defined(MBEDTLS_TEST_HOOKS) && defined(MBEDTLS_ECP_C)
@@ -46,6 +47,35 @@
void mbedtls_ecp_fix_negative( mbedtls_mpi *N, signed char c, size_t bits );
#endif
+#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
+/** Generate a private key on a Montgomery curve (Curve25519 or Curve448).
+ *
+ * This function implements key generation for the set of secret keys
+ * specified in [Curve25519] p. 5 and in [Curve448]. The resulting value
+ * has the lower bits masked but is not necessarily canonical.
+ *
+ * \note - [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
+ * - [RFC7748] https://tools.ietf.org/html/rfc7748
+ *
+ * \p high_bit The position of the high-order bit of the key to generate.
+ * This is the bit-size of the key minus 1:
+ * 254 for Curve25519 or 447 for Curve448.
+ * \param d The randomly generated key. This is a number of size
+ * exactly \p n_bits + 1 bits, with the least significant bits
+ * masked as specified in [Curve25519] and in [RFC7748] §5.
+ * \param f_rng The RNG function.
+ * \param p_rng The RNG context to be passed to \p f_rng.
+ *
+ * \return \c 0 on success.
+ * \return \c MBEDTLS_ERR_ECP_xxx or MBEDTLS_ERR_MPI_xxx on failure.
+ */
+int mbedtls_ecp_gen_privkey_mx( size_t n_bits,
+ mbedtls_mpi *d,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng );
+
+#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
+
#endif /* MBEDTLS_TEST_HOOKS && MBEDTLS_ECP_C */
#endif /* MBEDTLS_ECP_INVASIVE_H */
diff --git a/tests/include/test/random.h b/tests/include/test/random.h
index 5e7e4e6..6428280 100644
--- a/tests/include/test/random.h
+++ b/tests/include/test/random.h
@@ -36,8 +36,11 @@
typedef struct
{
- unsigned char *buf;
+ unsigned char *buf; /* Pointer to a buffer of length bytes. */
size_t length;
+ /* If fallback_f_rng is NULL, fail after delivering length bytes. */
+ int ( *fallback_f_rng )( void*, unsigned char *, size_t );
+ void *fallback_p_rng;
} mbedtls_test_rnd_buf_info;
/**
@@ -67,24 +70,25 @@
size_t len );
/**
- * This function only returns zeros
+ * This function only returns zeros.
*
- * rng_state shall be NULL.
+ * \p rng_state shall be \c NULL.
*/
int mbedtls_test_rnd_zero_rand( void *rng_state,
unsigned char *output,
size_t len );
/**
- * This function returns random based on a buffer it receives.
+ * This function returns random data based on a buffer it receives.
*
- * rng_state shall be a pointer to a rnd_buf_info structure.
+ * \p rng_state shall be a pointer to a #mbedtls_test_rnd_buf_info structure.
*
* The number of bytes released from the buffer on each call to
- * the random function is specified by per_call. (Can be between
- * 1 and 4)
+ * the random function is specified by \p len.
*
- * After the buffer is empty it will return rand();
+ * After the buffer is empty, this function will call the fallback RNG in the
+ * #mbedtls_test_rnd_buf_info structure if there is one, and
+ * will return #MBEDTLS_ERR_ENTROPY_SOURCE_FAILED otherwise.
*/
int mbedtls_test_rnd_buffer_rand( void *rng_state,
unsigned char *output,
@@ -96,7 +100,7 @@
* Pseudo random is based on the XTEA encryption algorithm to
* generate pseudorandom.
*
- * rng_state shall be a pointer to a rnd_pseudo_info structure.
+ * \p rng_state shall be a pointer to a #mbedtls_test_rnd_pseudo_info structure.
*/
int mbedtls_test_rnd_pseudo_rand( void *rng_state,
unsigned char *output,
diff --git a/tests/src/random.c b/tests/src/random.c
index e01bd4d..7f3f401 100644
--- a/tests/src/random.c
+++ b/tests/src/random.c
@@ -35,6 +35,8 @@
#include <test/random.h>
#include <string.h>
+#include <mbedtls/entropy.h>
+
int mbedtls_test_rnd_std_rand( void *rng_state,
unsigned char *output,
size_t len )
@@ -91,8 +93,16 @@
}
if( len - use_len > 0 )
- return( mbedtls_test_rnd_std_rand( NULL, output + use_len,
- len - use_len ) );
+ {
+ if( info->fallback_f_rng != NULL )
+ {
+ return( info->fallback_f_rng( info->fallback_p_rng,
+ output + use_len,
+ len - use_len ) );
+ }
+ else
+ return( MBEDTLS_ERR_ENTROPY_SOURCE_FAILED );
+ }
return( 0 );
}
diff --git a/tests/suites/test_suite_dhm.data b/tests/suites/test_suite_dhm.data
index c4795b6..33c7216 100644
--- a/tests/suites/test_suite_dhm.data
+++ b/tests/suites/test_suite_dhm.data
@@ -1,26 +1,92 @@
+Diffie-Hellman full exchange: tiny x_size
+dhm_do_dhm:10:"93450983094850938450983409623":1:10:"9345098304850938450983409622":0
+
Diffie-Hellman parameter validation
dhm_invalid_params:
-Diffie-Hellman full exchange #1
-dhm_do_dhm:10:"23":10:"5":0
+Diffie-Hellman full exchange: 5-bit, x_size=3
+dhm_do_dhm:10:"23":3:10:"5":0
-Diffie-Hellman full exchange #2
-dhm_do_dhm:10:"93450983094850938450983409623":10:"9345098304850938450983409622":0
+Diffie-Hellman full exchange: 5-bit, x_size=2
+dhm_do_dhm:10:"23":2:10:"5":0
-Diffie-Hellman full exchange #3
-dhm_do_dhm:10:"93450983094850938450983409623982317398171298719873918739182739712938719287391879381271":10:"9345098309485093845098340962223981329819812792137312973297123912791271":0
+## Repeat this test case and a few similar ones several times. The RNG state
+## changes, so we get to exercise the code with a few different values.
+Diffie-Hellman full exchange: 5-bit #1
+dhm_do_dhm:10:"23":1:10:"5":0
+
+Diffie-Hellman full exchange: 5-bit #2
+dhm_do_dhm:10:"23":1:10:"5":0
+
+Diffie-Hellman full exchange: 5-bit #3
+dhm_do_dhm:10:"23":1:10:"5":0
+
+Diffie-Hellman full exchange: 5-bit #4
+dhm_do_dhm:10:"23":1:10:"5":0
+
+Diffie-Hellman full exchange: 5-bit #5
+dhm_do_dhm:10:"23":1:10:"5":0
+
+## This is x_size = P_size + 1. Arguably x_size > P_size makes no sense,
+## but it's the current undocumented behavior to treat it the same as when
+## x_size = P_size. If this behavior changes in the future, change the expected
+## return status from 0 to MBEDTLS_ERR_DHM_BAD_INPUT_DATA.
+Diffie-Hellman full exchange: 97-bit, x_size=14
+dhm_do_dhm:10:"93450983094850938450983409623":14:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit #1
+dhm_do_dhm:10:"93450983094850938450983409623":13:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit #2
+dhm_do_dhm:10:"93450983094850938450983409623":13:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit #3
+dhm_do_dhm:10:"93450983094850938450983409623":13:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit #4
+dhm_do_dhm:10:"93450983094850938450983409623":13:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit #5
+dhm_do_dhm:10:"93450983094850938450983409623":13:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=12
+dhm_do_dhm:10:"93450983094850938450983409623":12:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=11
+dhm_do_dhm:10:"93450983094850938450983409623":11:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=1 #1
+dhm_do_dhm:10:"93450983094850938450983409623":1:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=1 #2
+dhm_do_dhm:10:"93450983094850938450983409623":1:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=1 #3
+dhm_do_dhm:10:"93450983094850938450983409623":1:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=1 #4
+dhm_do_dhm:10:"93450983094850938450983409623":1:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 97-bit, x_size=1 #5
+dhm_do_dhm:10:"93450983094850938450983409623":1:10:"9345098304850938450983409622":0
+
+Diffie-Hellman full exchange: 286-bit
+dhm_do_dhm:10:"93450983094850938450983409623982317398171298719873918739182739712938719287391879381271":36:10:"9345098309485093845098340962223981329819812792137312973297123912791271":0
Diffie-Hellman trivial subgroup #1
-dhm_do_dhm:10:"23":10:"1":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
+dhm_do_dhm:10:"23":1:10:"1":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
Diffie-Hellman trivial subgroup #2
-dhm_do_dhm:10:"23":10:"-1":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
+dhm_do_dhm:10:"23":1:10:"-1":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
Diffie-Hellman small modulus
-dhm_do_dhm:10:"3":10:"5":MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED
+dhm_do_dhm:10:"3":1:10:"5":MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED+MBEDTLS_ERR_MPI_BAD_INPUT_DATA
Diffie-Hellman zero modulus
-dhm_do_dhm:10:"0":10:"5":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
+dhm_do_dhm:10:"0":1:10:"5":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
+
+Diffie-Hellman: x_size < 0
+dhm_do_dhm:10:"93450983094850938450983409623":-1:10:"9345098304850938450983409622":MBEDTLS_ERR_DHM_BAD_INPUT_DATA
Diffie-Hellman MPI_MAX_SIZE modulus
dhm_make_public:MBEDTLS_MPI_MAX_SIZE:10:"5":0
diff --git a/tests/suites/test_suite_dhm.function b/tests/suites/test_suite_dhm.function
index 1726b9e..6d3743f 100644
--- a/tests/suites/test_suite_dhm.function
+++ b/tests/suites/test_suite_dhm.function
@@ -1,5 +1,68 @@
/* BEGIN_HEADER */
#include "mbedtls/dhm.h"
+
+/* Sanity checks on a Diffie-Hellman parameter: check the length-value
+ * syntax and check that the value is the expected one (taken from the
+ * DHM context by the caller). */
+static int check_dhm_param_output( const mbedtls_mpi *expected,
+ const unsigned char *buffer,
+ size_t size,
+ size_t *offset )
+{
+ size_t n;
+ mbedtls_mpi actual;
+ int ok = 0;
+ mbedtls_mpi_init( &actual );
+
+ ++mbedtls_test_info.step;
+
+ TEST_ASSERT( size >= *offset + 2 );
+ n = ( buffer[*offset] << 8 ) | buffer[*offset + 1];
+ *offset += 2;
+ /* The DHM param output from Mbed TLS has leading zeros stripped, as
+ * permitted but not required by RFC 5246 \S4.4. */
+ TEST_EQUAL( n, mbedtls_mpi_size( expected ) );
+ TEST_ASSERT( size >= *offset + n );
+ TEST_EQUAL( 0, mbedtls_mpi_read_binary( &actual, buffer + *offset, n ) );
+ TEST_EQUAL( 0, mbedtls_mpi_cmp_mpi( expected, &actual ) );
+ *offset += n;
+
+ ok = 1;
+exit:
+ mbedtls_mpi_free( &actual );
+ return( ok );
+}
+
+/* Sanity checks on Diffie-Hellman parameters: syntax, range, and comparison
+ * against the context. */
+static int check_dhm_params( const mbedtls_dhm_context *ctx,
+ size_t x_size,
+ const unsigned char *ske, size_t ske_len )
+{
+ size_t offset = 0;
+
+ /* Check that ctx->X and ctx->GX are within range. */
+ TEST_ASSERT( mbedtls_mpi_cmp_int( &ctx->X, 1 ) > 0 );
+ TEST_ASSERT( mbedtls_mpi_cmp_mpi( &ctx->X, &ctx->P ) < 0 );
+ TEST_ASSERT( mbedtls_mpi_size( &ctx->X ) <= x_size );
+ TEST_ASSERT( mbedtls_mpi_cmp_int( &ctx->GX, 1 ) > 0 );
+ TEST_ASSERT( mbedtls_mpi_cmp_mpi( &ctx->GX, &ctx->P ) < 0 );
+
+ /* Check ske: it must contain P, G and G^X, each prefixed with a
+ * 2-byte size. */
+ if( !check_dhm_param_output( &ctx->P, ske, ske_len, &offset ) )
+ goto exit;
+ if( !check_dhm_param_output( &ctx->G, ske, ske_len, &offset ) )
+ goto exit;
+ if( !check_dhm_param_output( &ctx->GX, ske, ske_len, &offset ) )
+ goto exit;
+ TEST_EQUAL( offset, ske_len );
+
+ return( 1 );
+exit:
+ return( 0 );
+}
+
/* END_HEADER */
/* BEGIN_DEPENDENCIES
@@ -115,7 +178,7 @@
/* END_CASE */
/* BEGIN_CASE */
-void dhm_do_dhm( int radix_P, char *input_P,
+void dhm_do_dhm( int radix_P, char *input_P, int x_size,
int radix_G, char *input_G, int result )
{
mbedtls_dhm_context ctx_srv;
@@ -129,7 +192,7 @@
size_t pub_cli_len = 0;
size_t sec_srv_len;
size_t sec_cli_len;
- int x_size, i;
+ int i;
mbedtls_test_rnd_pseudo_info rnd_info;
mbedtls_dhm_init( &ctx_srv );
@@ -145,17 +208,19 @@
*/
TEST_ASSERT( mbedtls_mpi_read_string( &ctx_srv.P, radix_P, input_P ) == 0 );
TEST_ASSERT( mbedtls_mpi_read_string( &ctx_srv.G, radix_G, input_G ) == 0 );
- x_size = mbedtls_mpi_size( &ctx_srv.P );
- pub_cli_len = x_size;
+ pub_cli_len = mbedtls_mpi_size( &ctx_srv.P );
/*
* First key exchange
*/
+ mbedtls_test_set_step( 10 );
TEST_ASSERT( mbedtls_dhm_make_params( &ctx_srv, x_size, ske, &ske_len,
&mbedtls_test_rnd_pseudo_rand,
&rnd_info ) == result );
if ( result != 0 )
goto exit;
+ if( !check_dhm_params( &ctx_srv, x_size, ske, ske_len ) )
+ goto exit;
ske[ske_len++] = 0;
ske[ske_len++] = 0;
@@ -179,6 +244,7 @@
/* Re-do calc_secret on server a few times to test update of blinding values */
for( i = 0; i < 3; i++ )
{
+ mbedtls_test_set_step( 20 + i );
sec_srv_len = 1000;
TEST_ASSERT( mbedtls_dhm_calc_secret( &ctx_srv, sec_srv,
sizeof( sec_srv ), &sec_srv_len,
@@ -195,9 +261,12 @@
*/
p = ske;
+ mbedtls_test_set_step( 30 );
TEST_ASSERT( mbedtls_dhm_make_params( &ctx_srv, x_size, ske, &ske_len,
&mbedtls_test_rnd_pseudo_rand,
&rnd_info ) == 0 );
+ if( !check_dhm_params( &ctx_srv, x_size, ske, ske_len ) )
+ goto exit;
ske[ske_len++] = 0;
ske[ske_len++] = 0;
TEST_ASSERT( mbedtls_dhm_read_params( &ctx_cli, &p, ske + ske_len ) == 0 );
diff --git a/tests/suites/test_suite_ecdh.function b/tests/suites/test_suite_ecdh.function
index 3ab96fa..da0531b 100644
--- a/tests/suites/test_suite_ecdh.function
+++ b/tests/suites/test_suite_ecdh.function
@@ -240,6 +240,8 @@
rnd_info_A.buf = rnd_buf_A->x;
rnd_info_A.length = rnd_buf_A->len;
+ rnd_info_A.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ rnd_info_A.fallback_p_rng = NULL;
/* Fix rnd_buf_A->x by shifting it left if necessary */
if( grp.nbits % 8 != 0 )
@@ -256,6 +258,8 @@
rnd_info_B.buf = rnd_buf_B->x;
rnd_info_B.length = rnd_buf_B->len;
+ rnd_info_B.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ rnd_info_B.fallback_p_rng = NULL;
/* Fix rnd_buf_B->x by shifting it left if necessary */
if( grp.nbits % 8 != 0 )
@@ -362,9 +366,13 @@
mbedtls_ecdh_init( &srv );
mbedtls_ecdh_init( &cli );
+ rnd_info_A.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ rnd_info_A.fallback_p_rng = NULL;
rnd_info_A.buf = dA->x;
rnd_info_A.length = dA->len;
+ rnd_info_B.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ rnd_info_B.fallback_p_rng = NULL;
rnd_info_B.buf = dB->x;
rnd_info_B.length = dB->len;
diff --git a/tests/suites/test_suite_ecdsa.function b/tests/suites/test_suite_ecdsa.function
index 8157234..fb6ed46 100644
--- a/tests/suites/test_suite_ecdsa.function
+++ b/tests/suites/test_suite_ecdsa.function
@@ -292,6 +292,8 @@
TEST_ASSERT( mbedtls_mpi_read_string( &d, 16, d_str ) == 0 );
TEST_ASSERT( mbedtls_mpi_read_string( &r_check, 16, r_str ) == 0 );
TEST_ASSERT( mbedtls_mpi_read_string( &s_check, 16, s_str ) == 0 );
+ rnd_info.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ rnd_info.fallback_p_rng = NULL;
rnd_info.buf = rnd_buf->x;
rnd_info.length = rnd_buf->len;
diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 106791c..5f92ca4 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -276,6 +276,42 @@
depends_on:MBEDTLS_ECP_DP_SECP192R1_ENABLED
mbedtls_ecp_gen_key:MBEDTLS_ECP_DP_SECP192R1
+ECP generate Montgomery key: Curve25519, random in range
+genkey_mx_known_answer:254:"9e020406080a0c0e10121416181a1c1e20222426282a2c2e30323436383a3df0":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
+
+ECP generate Montgomery key: Curve25519, clear higher bit
+genkey_mx_known_answer:254:"ff0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8":"7f808101820283038404850586068707880889098a0a8b0b8c0c8d0d8e0e8f78"
+
+ECP generate Montgomery key: Curve25519, clear low bits
+genkey_mx_known_answer:254:"9e020406080a0c0e10121416181a1c1e20222426282a2c2e30323436383a3dff":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
+
+ECP generate Montgomery key: Curve25519, random = all-bits-zero
+genkey_mx_known_answer:254:"0000000000000000000000000000000000000000000000000000000000000000":"4000000000000000000000000000000000000000000000000000000000000000"
+
+ECP generate Montgomery key: Curve25519, random = all-bits-one
+genkey_mx_known_answer:254:"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff":"7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8"
+
+ECP generate Montgomery key: Curve25519, not enough entropy
+genkey_mx_known_answer:254:"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e":""
+
+ECP generate Montgomery key: Curve448, random in range
+genkey_mx_known_answer:447:"cf0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536fc":"cf0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536fc"
+
+ECP generate Montgomery key: Curve448, set high bit
+genkey_mx_known_answer:447:"0f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536fc":"8f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536fc"
+
+ECP generate Montgomery key: Curve448, clear low bits
+genkey_mx_known_answer:447:"cf0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536ff":"cf0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536fc"
+
+ECP generate Montgomery key: Curve448, random = all-bits-zero
+genkey_mx_known_answer:447:"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000":"8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
+
+ECP generate Montgomery key: Curve448, random = all-bits-one
+genkey_mx_known_answer:447:"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff":"fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc"
+
+ECP generate Montgomery key: Curve448, not enough entropy
+genkey_mx_known_answer:447:"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536":""
+
ECP read key #1 (short weierstrass, too small)
depends_on:MBEDTLS_ECP_DP_SECP192R1_ENABLED
mbedtls_ecp_read_key:MBEDTLS_ECP_DP_SECP192R1:"00":MBEDTLS_ERR_ECP_INVALID_KEY:0
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index 6d23377..934598d 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -15,6 +15,7 @@
#define ECP_PT_RESET( x ) \
mbedtls_ecp_point_free( x ); \
mbedtls_ecp_point_init( x );
+
/* END_HEADER */
/* BEGIN_DEPENDENCIES
@@ -1237,6 +1238,55 @@
}
/* END_CASE */
+/* BEGIN_CASE depends_on:MBEDTLS_TEST_HOOKS:MBEDTLS_ECP_MONTGOMERY_ENABLED */
+void genkey_mx_known_answer( int bits, data_t *seed, data_t *expected )
+{
+ mbedtls_test_rnd_buf_info rnd_info;
+ mbedtls_mpi d;
+ int ret;
+ uint8_t *actual = NULL;
+
+ mbedtls_mpi_init( &d );
+ rnd_info.buf = seed->x;
+ rnd_info.length = seed->len;
+ rnd_info.fallback_f_rng = NULL;
+ rnd_info.fallback_p_rng = NULL;
+
+ ASSERT_ALLOC( actual, expected->len );
+
+ ret = mbedtls_ecp_gen_privkey_mx( bits, &d,
+ mbedtls_test_rnd_buffer_rand, &rnd_info );
+
+ if( expected->len == 0 )
+ {
+ /* Expecting an error (happens if there isn't enough randomness) */
+ TEST_ASSERT( ret != 0 );
+ }
+ else
+ {
+ TEST_EQUAL( ret, 0 );
+ TEST_EQUAL( (size_t) bits + 1, mbedtls_mpi_bitlen( &d ) );
+ TEST_EQUAL( 0, mbedtls_mpi_write_binary( &d, actual, expected->len ) );
+ /* Test the exact result. This assumes that the output of the
+ * RNG is used in a specific way, which is overly constraining.
+ * The advantage is that it's easier to test the expected properties
+ * of the generated key:
+ * - The most significant bit must be at a specific positions
+ * (can be enforced by checking the bit-length).
+ * - The least significant bits must have specific values
+ * (can be enforced by checking these bits).
+ * - Other bits must be random (by testing with different RNG outputs,
+ * we validate that those bits are indeed influenced by the RNG). */
+ ASSERT_COMPARE( expected->x, expected->len,
+ actual, expected->len );
+ }
+
+exit:
+ mbedtls_free( actual );
+ mbedtls_mpi_free( &d );
+}
+/* END_CASE */
+
/* BEGIN_CASE depends_on:MBEDTLS_SELF_TEST */
void ecp_selftest( )
{
diff --git a/tests/suites/test_suite_mpi.data b/tests/suites/test_suite_mpi.data
index 59fd782..1671d6e 100644
--- a/tests/suites/test_suite_mpi.data
+++ b/tests/suites/test_suite_mpi.data
@@ -992,46 +992,246 @@
mbedtls_mpi_set_bit:16:"00":5:2:16:"00":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
Fill random: 0 bytes
-mpi_fill_random:0:0:0
+mpi_fill_random:0:0:0:0
Fill random: 1 byte, good
-mpi_fill_random:1:1:0
+mpi_fill_random:1:1:0:0
Fill random: 2 bytes, good, no leading zero
-mpi_fill_random:2:2:0
+mpi_fill_random:2:2:0:0
Fill random: 2 bytes, good, 1 leading zero
-mpi_fill_random:2:256:0
+mpi_fill_random:2:256:0:0
Fill random: MAX_SIZE - 7, good
-mpi_fill_random:MBEDTLS_MPI_MAX_SIZE - 7:MBEDTLS_MPI_MAX_SIZE - 7:0
+mpi_fill_random:MBEDTLS_MPI_MAX_SIZE - 7:MBEDTLS_MPI_MAX_SIZE - 7:0:0
Fill random: MAX_SIZE, good
-mpi_fill_random:MBEDTLS_MPI_MAX_SIZE:MBEDTLS_MPI_MAX_SIZE:0
+mpi_fill_random:MBEDTLS_MPI_MAX_SIZE:MBEDTLS_MPI_MAX_SIZE:0:0
+
+Fill random: 0 bytes, previously small >0
+mpi_fill_random:0:0:1:0
+
+Fill random: 0 bytes, previously small <0
+mpi_fill_random:0:0:-1:0
+
+Fill random: 0 bytes, previously large >0
+mpi_fill_random:0:0:65:0
+
+Fill random: 0 bytes, previously large <0
+mpi_fill_random:0:0:-65:0
+
+Fill random: 1 byte, previously small >0
+mpi_fill_random:1:1:1:0
+
+Fill random: 1 byte, previously small <0
+mpi_fill_random:1:1:-1:0
+
+Fill random: 1 byte, previously large >0
+mpi_fill_random:1:1:65:0
+
+Fill random: 1 byte, previously large <0
+mpi_fill_random:1:1:-65:0
+
+Fill random: 9 bytes, previously small >0
+mpi_fill_random:1:1:1:0
+
+Fill random: 9 bytes, previously small <0
+mpi_fill_random:1:1:-1:0
Fill random: 1 byte, RNG failure
-mpi_fill_random:1:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:1:0:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: 2 bytes, RNG failure after 1 byte
-mpi_fill_random:2:1:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:2:1:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: 4 bytes, RNG failure after 3 bytes
-mpi_fill_random:4:3:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:4:3:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: 8 bytes, RNG failure after 7 bytes
-mpi_fill_random:8:7:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:8:7:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: 16 bytes, RNG failure after 1 bytes
-mpi_fill_random:16:1:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:16:1:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: 16 bytes, RNG failure after 8 bytes
-mpi_fill_random:16:8:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:16:8:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: 16 bytes, RNG failure after 15 bytes
-mpi_fill_random:16:15:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:16:15:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
Fill random: MAX_SIZE bytes, RNG failure after MAX_SIZE-1 bytes
-mpi_fill_random:MBEDTLS_MPI_MAX_SIZE:MBEDTLS_MPI_MAX_SIZE-1:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+mpi_fill_random:MBEDTLS_MPI_MAX_SIZE:MBEDTLS_MPI_MAX_SIZE-1:0:MBEDTLS_ERR_ENTROPY_SOURCE_FAILED
+
+MPI random in range: 1..2
+mpi_random_many:1:"02":1000
+
+MPI random in range: 1..3
+mpi_random_many:1:"03":1000
+
+MPI random in range: 1..4
+mpi_random_many:1:"04":1000
+
+MPI random in range: 1..5
+mpi_random_many:1:"05":1000
+
+MPI random in range: 1..6
+mpi_random_many:1:"06":1000
+
+MPI random in range: 1..7
+mpi_random_many:1:"07":1000
+
+MPI random in range: 1..8
+mpi_random_many:1:"08":1000
+
+MPI random in range: 1..9
+mpi_random_many:1:"09":1000
+
+MPI random in range: 1..10
+mpi_random_many:1:"0a":1000
+
+MPI random in range: 1..11
+mpi_random_many:1:"0b":1000
+
+MPI random in range: 1..12
+mpi_random_many:1:"0c":1000
+
+MPI random in range: 1..255
+mpi_random_many:1:"ff":100
+
+MPI random in range: 1..256
+mpi_random_many:1:"0100":100
+
+MPI random in range: 1..257
+mpi_random_many:1:"0101":100
+
+MPI random in range: 1..272
+mpi_random_many:1:"0110":100
+
+MPI random in range: 1..2^64-1
+mpi_random_many:1:"ffffffffffffffff":100
+
+MPI random in range: 1..2^64
+mpi_random_many:1:"010000000000000000":100
+
+MPI random in range: 1..2^64+1
+mpi_random_many:1:"010000000000000001":100
+
+MPI random in range: 1..2^64+2^63
+mpi_random_many:1:"018000000000000000":100
+
+MPI random in range: 1..2^65-1
+mpi_random_many:1:"01ffffffffffffffff":100
+
+MPI random in range: 1..2^65
+mpi_random_many:1:"020000000000000000":100
+
+MPI random in range: 1..2^65+1
+mpi_random_many:1:"020000000000000001":100
+
+MPI random in range: 1..2^65+2^64
+mpi_random_many:1:"030000000000000000":100
+
+MPI random in range: 1..2^66+2^65
+mpi_random_many:1:"060000000000000000":100
+
+MPI random in range: 1..2^71-1
+mpi_random_many:1:"7fffffffffffffffff":100
+
+MPI random in range: 1..2^71
+mpi_random_many:1:"800000000000000000":100
+
+MPI random in range: 1..2^71+1
+mpi_random_many:1:"800000000000000001":100
+
+MPI random in range: 1..2^71+2^70
+mpi_random_many:1:"c00000000000000000":100
+
+MPI random in range: 1..2^72-1
+mpi_random_many:1:"ffffffffffffffffff":100
+
+MPI random in range: 1..2^72
+mpi_random_many:1:"01000000000000000000":100
+
+MPI random in range: 1..2^72+1
+mpi_random_many:1:"01000000000000000001":100
+
+MPI random in range: 1..2^72+2^71
+mpi_random_many:1:"01800000000000000000":100
+
+MPI random in range: 0..1
+mpi_random_many:0:"04":10000
+
+MPI random in range: 0..4
+mpi_random_many:0:"04":10000
+
+MPI random in range: 2..4
+mpi_random_many:2:"04":10000
+
+MPI random in range: 3..4
+mpi_random_many:3:"04":10000
+
+MPI random in range: smaller result
+mpi_random_sizes:1:"aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbb":1:0
+
+MPI random in range: same size result (32-bit limbs)
+mpi_random_sizes:1:"aaaaaaaaaaaaaaaa":2:0
+
+MPI random in range: same size result (64-bit limbs)
+mpi_random_sizes:1:"aaaaaaaaaaaaaaaa":1:0
+
+MPI random in range: larger result
+mpi_random_sizes:1:"aaaaaaaaaaaaaaaa":3:0
+
+## The "0 limb in upper bound" tests rely on the fact that
+## mbedtls_mpi_read_binary() bases the size of the MPI on the size of
+## the input, without first checking for leading zeros. If this was
+## not the case, the tests would still pass, but would not exercise
+## the advertised behavior.
+MPI random in range: leading 0 limb in upper bound #0
+mpi_random_sizes:1:"00aaaaaaaaaaaaaaaa":0:0
+
+MPI random in range: leading 0 limb in upper bound #1
+mpi_random_sizes:1:"00aaaaaaaaaaaaaaaa":1:0
+
+MPI random in range: leading 0 limb in upper bound #2
+mpi_random_sizes:1:"00aaaaaaaaaaaaaaaa":2:0
+
+MPI random in range: leading 0 limb in upper bound #3
+mpi_random_sizes:1:"00aaaaaaaaaaaaaaaa":3:0
+
+MPI random in range: leading 0 limb in upper bound #4
+mpi_random_sizes:1:"00aaaaaaaaaaaaaaaa":4:0
+
+MPI random in range: previously small >0
+mpi_random_sizes:1:"1234567890":4:1
+
+MPI random in range: previously small <0
+mpi_random_sizes:1:"1234567890":4:-1
+
+MPI random in range: previously large >0
+mpi_random_sizes:1:"1234":4:65
+
+MPI random in range: previously large <0
+mpi_random_sizes:1:"1234":4:-65
+
+MPI random bad arguments: min < 0
+mpi_random_fail:-1:"04":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+MPI random bad arguments: min = N = 0
+mpi_random_fail:0:"00":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+MPI random bad arguments: min = N = 1
+mpi_random_fail:1:"01":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+MPI random bad arguments: min > N = 0
+mpi_random_fail:1:"00":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+MPI random bad arguments: min > N = 1
+mpi_random_fail:2:"01":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+MPI random bad arguments: min > N = 1, 0 limb in upper bound
+mpi_random_fail:2:"000000000000000001":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
MPI Selftest
depends_on:MBEDTLS_SELF_TEST
diff --git a/tests/suites/test_suite_mpi.function b/tests/suites/test_suite_mpi.function
index c5bb5a6..5807984 100644
--- a/tests/suites/test_suite_mpi.function
+++ b/tests/suites/test_suite_mpi.function
@@ -64,6 +64,50 @@
return( 0 );
}
+/* Test whether bytes represents (in big-endian base 256) a number b that
+ * is significantly above a power of 2. That is, b must not have a long run
+ * of unset bits after the most significant bit.
+ *
+ * Let n be the bit-size of b, i.e. the integer such that 2^n <= b < 2^{n+1}.
+ * This function returns 1 if, when drawing a number between 0 and b,
+ * the probability that this number is at least 2^n is not negligible.
+ * This probability is (b - 2^n) / b and this function checks that this
+ * number is above some threshold A. The threshold value is heuristic and
+ * based on the needs of mpi_random_many().
+ */
+static int is_significantly_above_a_power_of_2( data_t *bytes )
+{
+ const uint8_t *p = bytes->x;
+ size_t len = bytes->len;
+ unsigned x;
+
+ /* Skip leading null bytes */
+ while( len > 0 && p[0] == 0 )
+ {
+ ++p;
+ --len;
+ }
+ /* 0 is not significantly above a power of 2 */
+ if( len == 0 )
+ return( 0 );
+ /* Extract the (up to) 2 most significant bytes */
+ if( len == 1 )
+ x = p[0];
+ else
+ x = ( p[0] << 8 ) | p[1];
+
+ /* Shift the most significant bit of x to position 8 and mask it out */
+ while( ( x & 0xfe00 ) != 0 )
+ x >>= 1;
+ x &= 0x00ff;
+
+ /* At this point, x = floor((b - 2^n) / 2^(n-8)). b is significantly above
+ * a power of 2 iff x is significantly above 0 compared to 2^8.
+ * Testing x >= 2^4 amounts to picking A = 1/16 in the function
+ * description above. */
+ return( x >= 0x10 );
+}
+
/* END_HEADER */
/* BEGIN_DEPENDENCIES
@@ -1366,13 +1410,23 @@
/* END_CASE */
/* BEGIN_CASE */
-void mpi_fill_random( int wanted_bytes, int rng_bytes, int expected_ret )
+void mpi_fill_random( int wanted_bytes, int rng_bytes,
+ int before, int expected_ret )
{
mbedtls_mpi X;
int ret;
size_t bytes_left = rng_bytes;
mbedtls_mpi_init( &X );
+ if( before != 0 )
+ {
+ /* Set X to sign(before) * 2^(|before|-1) */
+ TEST_ASSERT( mbedtls_mpi_lset( &X, before > 0 ? 1 : -1 ) == 0 );
+ if( before < 0 )
+ before = - before;
+ TEST_ASSERT( mbedtls_mpi_shift_l( &X, before - 1 ) == 0 );
+ }
+
ret = mbedtls_mpi_fill_random( &X, wanted_bytes,
f_rng_bytes_left, &bytes_left );
TEST_ASSERT( ret == expected_ret );
@@ -1396,6 +1450,168 @@
}
/* END_CASE */
+/* BEGIN_CASE */
+void mpi_random_many( int min, data_t *bound_bytes, int iterations )
+{
+ /* Generate numbers in the range 1..bound-1. Do it iterations times.
+ * This function assumes that the value of bound is at least 2 and
+ * that iterations is large enough that a one-in-2^iterations chance
+ * effectively never occurs.
+ */
+
+ mbedtls_mpi upper_bound;
+ size_t n_bits;
+ mbedtls_mpi result;
+ size_t b;
+ /* If upper_bound is small, stats[b] is the number of times the value b
+ * has been generated. Otherwise stats[b] is the number of times a
+ * value with bit b set has been generated. */
+ size_t *stats = NULL;
+ size_t stats_len;
+ int full_stats;
+ size_t i;
+
+ mbedtls_mpi_init( &upper_bound );
+ mbedtls_mpi_init( &result );
+
+ TEST_EQUAL( 0, mbedtls_mpi_read_binary( &upper_bound,
+ bound_bytes->x, bound_bytes->len ) );
+ n_bits = mbedtls_mpi_bitlen( &upper_bound );
+ /* Consider a bound "small" if it's less than 2^5. This value is chosen
+ * to be small enough that the probability of missing one value is
+ * negligible given the number of iterations. It must be less than
+ * 256 because some of the code below assumes that "small" values
+ * fit in a byte. */
+ if( n_bits <= 5 )
+ {
+ full_stats = 1;
+ stats_len = bound_bytes->x[bound_bytes->len - 1];
+ }
+ else
+ {
+ full_stats = 0;
+ stats_len = n_bits;
+ }
+ ASSERT_ALLOC( stats, stats_len );
+
+ for( i = 0; i < (size_t) iterations; i++ )
+ {
+ mbedtls_test_set_step( i );
+ TEST_EQUAL( 0, mbedtls_mpi_random( &result, min, &upper_bound,
+ mbedtls_test_rnd_std_rand, NULL ) );
+
+ TEST_ASSERT( mbedtls_mpi_cmp_mpi( &result, &upper_bound ) < 0 );
+ TEST_ASSERT( mbedtls_mpi_cmp_int( &result, min ) >= 0 );
+ if( full_stats )
+ {
+ uint8_t value;
+ TEST_EQUAL( 0, mbedtls_mpi_write_binary( &result, &value, 1 ) );
+ TEST_ASSERT( value < stats_len );
+ ++stats[value];
+ }
+ else
+ {
+ for( b = 0; b < n_bits; b++ )
+ stats[b] += mbedtls_mpi_get_bit( &result, b );
+ }
+ }
+
+ if( full_stats )
+ {
+ for( b = min; b < stats_len; b++ )
+ {
+ mbedtls_test_set_step( 1000000 + b );
+ /* Assert that each value has been reached at least once.
+ * This is almost guaranteed if the iteration count is large
+ * enough. This is a very crude way of checking the distribution.
+ */
+ TEST_ASSERT( stats[b] > 0 );
+ }
+ }
+ else
+ {
+ int statistically_safe_all_the_way =
+ is_significantly_above_a_power_of_2( bound_bytes );
+ for( b = 0; b < n_bits; b++ )
+ {
+ mbedtls_test_set_step( 1000000 + b );
+ /* Assert that each bit has been set in at least one result and
+ * clear in at least one result. Provided that iterations is not
+ * too small, it would be extremely unlikely for this not to be
+ * the case if the results are uniformly distributed.
+ *
+ * As an exception, the top bit may legitimately never be set
+ * if bound is a power of 2 or only slightly above.
+ */
+ if( statistically_safe_all_the_way || b != n_bits - 1 )
+ {
+ TEST_ASSERT( stats[b] > 0 );
+ }
+ TEST_ASSERT( stats[b] < (size_t) iterations );
+ }
+ }
+
+exit:
+ mbedtls_mpi_free( &upper_bound );
+ mbedtls_mpi_free( &result );
+ mbedtls_free( stats );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
+void mpi_random_sizes( int min, data_t *bound_bytes, int nlimbs, int before )
+{
+ mbedtls_mpi upper_bound;
+ mbedtls_mpi result;
+
+ mbedtls_mpi_init( &upper_bound );
+ mbedtls_mpi_init( &result );
+
+ if( before != 0 )
+ {
+ /* Set result to sign(before) * 2^(|before|-1) */
+ TEST_ASSERT( mbedtls_mpi_lset( &result, before > 0 ? 1 : -1 ) == 0 );
+ if( before < 0 )
+ before = - before;
+ TEST_ASSERT( mbedtls_mpi_shift_l( &result, before - 1 ) == 0 );
+ }
+
+ TEST_EQUAL( 0, mbedtls_mpi_grow( &result, nlimbs ) );
+ TEST_EQUAL( 0, mbedtls_mpi_read_binary( &upper_bound,
+ bound_bytes->x, bound_bytes->len ) );
+ TEST_EQUAL( 0, mbedtls_mpi_random( &result, min, &upper_bound,
+ mbedtls_test_rnd_std_rand, NULL ) );
+ TEST_ASSERT( mbedtls_mpi_cmp_mpi( &result, &upper_bound ) < 0 );
+ TEST_ASSERT( mbedtls_mpi_cmp_int( &result, min ) >= 0 );
+
+exit:
+ mbedtls_mpi_free( &upper_bound );
+ mbedtls_mpi_free( &result );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
+void mpi_random_fail( int min, data_t *bound_bytes, int expected_ret )
+{
+ mbedtls_mpi upper_bound;
+ mbedtls_mpi result;
+ int actual_ret;
+
+ mbedtls_mpi_init( &upper_bound );
+ mbedtls_mpi_init( &result );
+
+ TEST_EQUAL( 0, mbedtls_mpi_read_binary( &upper_bound,
+ bound_bytes->x, bound_bytes->len ) );
+ actual_ret = mbedtls_mpi_random( &result, min, &upper_bound,
+ mbedtls_test_rnd_std_rand, NULL );
+ TEST_EQUAL( expected_ret, actual_ret );
+
+exit:
+ mbedtls_mpi_free( &upper_bound );
+ mbedtls_mpi_free( &result );
+}
+/* END_CASE */
+
/* BEGIN_CASE depends_on:MBEDTLS_SELF_TEST */
void mpi_selftest( )
{
diff --git a/tests/suites/test_suite_pkcs1_v15.function b/tests/suites/test_suite_pkcs1_v15.function
index 068027b..9af6aec 100644
--- a/tests/suites/test_suite_pkcs1_v15.function
+++ b/tests/suites/test_suite_pkcs1_v15.function
@@ -19,6 +19,8 @@
mbedtls_test_rnd_buf_info info;
mbedtls_mpi N, E;
+ info.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ info.fallback_p_rng = NULL;
info.buf = rnd_buf->x;
info.length = rnd_buf->len;
@@ -275,6 +277,8 @@
mbedtls_mpi N, P, Q, E;
mbedtls_test_rnd_buf_info info;
+ info.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ info.fallback_p_rng = NULL;
info.buf = rnd_buf->x;
info.length = rnd_buf->len;
diff --git a/tests/suites/test_suite_pkcs1_v21.function b/tests/suites/test_suite_pkcs1_v21.function
index 97f440d..c23a4ad 100644
--- a/tests/suites/test_suite_pkcs1_v21.function
+++ b/tests/suites/test_suite_pkcs1_v21.function
@@ -18,6 +18,8 @@
mbedtls_test_rnd_buf_info info;
mbedtls_mpi N, E;
+ info.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ info.fallback_p_rng = NULL;
info.buf = rnd_buf->x;
info.length = rnd_buf->len;
@@ -124,6 +126,8 @@
mbedtls_test_rnd_buf_info info;
mbedtls_mpi N, P, Q, E;
+ info.fallback_f_rng = mbedtls_test_rnd_std_rand;
+ info.fallback_p_rng = NULL;
info.buf = rnd_buf->x;
info.length = rnd_buf->len;