#include "mbedtls/ecp.h"
#include "mbedtls/threading.h"
#include "mbedtls/platform_util.h"
+#include "mbedtls/bn_mul.h"
#include <string.h>
/* 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 )
+ if( count++ > 30 )
{
ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
goto cleanup;
}
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, ( p_size * 8 ) - grp->pbits ) );
}
- while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
+ while( ( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ) ||
+ ( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) );
/* Z = l * Z */
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
#if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
if( mbedtls_internal_ecp_grp_capable( grp ) )
- return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );
+ return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ) );
#endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
p_size = ( grp->pbits + 7 ) / 8;
/* 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 )
+ if( count++ > 30 )
{
ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
goto cleanup;
}
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, ( p_size * 8 ) - grp->pbits ) );
}
- while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
+ while( ( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ) ||
+ ( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
}
#if defined(ECP_MONTGOMERY)
+#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
+#define ECP_MPI_INIT(s, n, p) {s, (n), (mbedtls_mpi_uint *)(p)}
+#define ECP_MPI_INIT_ARRAY(x) \
+ ECP_MPI_INIT(1, sizeof(x) / sizeof(mbedtls_mpi_uint), x)
+/*
+ * Constants for the two points other than 0, 1, -1 (mod p) in
+ * https://cr.yp.to/ecdh.html#validate
+ * See ecp_check_pubkey_x25519().
+ */
+static const mbedtls_mpi_uint x25519_bad_point_1[] = {
+ MBEDTLS_BYTES_TO_T_UINT_8( 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae ),
+ MBEDTLS_BYTES_TO_T_UINT_8( 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a ),
+ MBEDTLS_BYTES_TO_T_UINT_8( 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd ),
+ MBEDTLS_BYTES_TO_T_UINT_8( 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00 ),
+};
+static const mbedtls_mpi_uint x25519_bad_point_2[] = {
+ MBEDTLS_BYTES_TO_T_UINT_8( 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24 ),
+ MBEDTLS_BYTES_TO_T_UINT_8( 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b ),
+ MBEDTLS_BYTES_TO_T_UINT_8( 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86 ),
+ MBEDTLS_BYTES_TO_T_UINT_8( 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57 ),
+};
+static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY(
+ x25519_bad_point_1 );
+static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY(
+ x25519_bad_point_2 );
+#endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
+
+/*
+ * Check that the input point is not one of the low-order points.
+ * This is recommended by the "May the Fourth" paper:
+ * https://eprint.iacr.org/2017/806.pdf
+ * Those points are never sent by an honest peer.
+ */
+static int ecp_check_bad_points_mx( const mbedtls_mpi *X, const mbedtls_mpi *P,
+ const mbedtls_ecp_group_id grp_id )
+{
+ int ret;
+ mbedtls_mpi XmP;
+
+ mbedtls_mpi_init( &XmP );
+
+ /* Reduce X mod P so that we only need to check values less than P.
+ * We know X < 2^256 so we can proceed by subtraction. */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &XmP, X ) );
+ while( mbedtls_mpi_cmp_mpi( &XmP, P ) >= 0 )
+ MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &XmP, &XmP, P ) );
+
+ /* Check against the known bad values that are less than P. For Curve448
+ * these are 0, 1 and -1. For Curve25519 we check the values less than P
+ * from the following list: https://cr.yp.to/ecdh.html#validate */
+ if( mbedtls_mpi_cmp_int( &XmP, 1 ) <= 0 ) /* takes care of 0 and 1 */
+ {
+ ret = MBEDTLS_ERR_ECP_INVALID_KEY;
+ goto cleanup;
+ }
+
+#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
+ if( grp_id == MBEDTLS_ECP_DP_CURVE25519 )
+ {
+ if( mbedtls_mpi_cmp_mpi( &XmP, &ecp_x25519_bad_point_1 ) == 0 )
+ {
+ ret = MBEDTLS_ERR_ECP_INVALID_KEY;
+ goto cleanup;
+ }
+
+ if( mbedtls_mpi_cmp_mpi( &XmP, &ecp_x25519_bad_point_2 ) == 0 )
+ {
+ ret = MBEDTLS_ERR_ECP_INVALID_KEY;
+ goto cleanup;
+ }
+ }
+#else
+ (void) grp_id;
+#endif
+
+ /* Final check: check if XmP + 1 is P (final because it changes XmP!) */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &XmP, &XmP, 1 ) );
+ if( mbedtls_mpi_cmp_mpi( &XmP, P ) == 0 )
+ {
+ ret = MBEDTLS_ERR_ECP_INVALID_KEY;
+ goto cleanup;
+ }
+
+ ret = 0;
+
+cleanup:
+ mbedtls_mpi_free( &XmP );
+
+ return( ret );
+}
+
/*
* Check validity of a public key for Montgomery curves with x-only schemes
*/
if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
return( MBEDTLS_ERR_ECP_INVALID_KEY );
- return( 0 );
+ /* Implicit in all standards (as they don't consider negative numbers):
+ * X must be non-negative. This is normally ensured by the way it's
+ * encoded for transmission, but let's be extra sure. */
+ if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 )
+ return( MBEDTLS_ERR_ECP_INVALID_KEY );
+
+ return( ecp_check_bad_points_mx( &pt->X, &grp->P, grp->id ) );
}
#endif /* ECP_MONTGOMERY */
{
int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
size_t n_size;
+#if defined(ECP_SHORTWEIERSTRASS)
+ mbedtls_mpi one;
+
+ mbedtls_mpi_init( &one );
+#endif
ECP_VALIDATE_RET( grp != NULL );
ECP_VALIDATE_RET( d != NULL );
{
/* SEC1 3.2.1: Generate d such that 1 <= n < N */
int count = 0;
- unsigned cmp = 0;
+ unsigned lt_lower = 1, lt_upper = 0;
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &one, grp->N.n ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &one, 1 ) );
/*
* Match the procedure given in RFC 6979 (deterministic ECDSA):
* such as secp224k1 are actually very close to the worst case.
*/
if( ++count > 30 )
- return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
-
- ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp );
- if( ret != 0 )
{
+ ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
goto cleanup;
}
+
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d, &grp->N, <_upper ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d, &one, <_lower ) );
}
- while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 );
+ while( lt_lower != 0 || lt_upper == 0 );
}
#endif /* ECP_SHORTWEIERSTRASS */
cleanup:
+#if defined(ECP_SHORTWEIERSTRASS)
+ mbedtls_mpi_free( &one );
+#endif
return( ret );
}
projects / reactos.git / blobdiff