diff options
Diffstat (limited to 'thirdparty/mbedtls/library/ecp.c')
-rw-r--r-- | thirdparty/mbedtls/library/ecp.c | 151 |
1 files changed, 129 insertions, 22 deletions
diff --git a/thirdparty/mbedtls/library/ecp.c b/thirdparty/mbedtls/library/ecp.c index fe41b4128a..a7486c198a 100644 --- a/thirdparty/mbedtls/library/ecp.c +++ b/thirdparty/mbedtls/library/ecp.c @@ -106,6 +106,7 @@ #include "mbedtls/ecp.h" #include "mbedtls/threading.h" #include "mbedtls/platform_util.h" +#include "mbedtls/bn_mul.h" #include <string.h> @@ -1738,18 +1739,17 @@ static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *p /* 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 ); @@ -2505,7 +2505,7 @@ static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P #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; @@ -2514,18 +2514,17 @@ static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P /* 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 ); @@ -2970,6 +2969,97 @@ int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, } #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 */ @@ -2981,7 +3071,13 @@ static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_ 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 */ @@ -3059,6 +3155,11 @@ int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, { 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 ); @@ -3099,7 +3200,10 @@ int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, { /* 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): @@ -3123,19 +3227,22 @@ int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, * 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 ); } |