diff options
Diffstat (limited to 'thirdparty/mbedtls/library/ecp.c')
| -rw-r--r-- | thirdparty/mbedtls/library/ecp.c | 1408 |
1 files changed, 775 insertions, 633 deletions
diff --git a/thirdparty/mbedtls/library/ecp.c b/thirdparty/mbedtls/library/ecp.c index fe41b4128a..890f364a08 100644 --- a/thirdparty/mbedtls/library/ecp.c +++ b/thirdparty/mbedtls/library/ecp.c @@ -2,13 +2,7 @@ * Elliptic curves over GF(p): generic functions * * Copyright The Mbed TLS Contributors - * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later - * - * This file is provided under the Apache License 2.0, or the - * GNU General Public License v2.0 or later. - * - * ********** - * Apache License 2.0: + * 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. @@ -21,27 +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. - * - * ********** - * - * ********** - * GNU General Public License v2.0 or later: - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * ********** */ /* @@ -66,11 +39,7 @@ * <http://eprint.iacr.org/2004/342.pdf> */ -#if !defined(MBEDTLS_CONFIG_FILE) -#include "mbedtls/config.h" -#else -#include MBEDTLS_CONFIG_FILE -#endif +#include "common.h" /** * \brief Function level alternative implementation. @@ -106,6 +75,10 @@ #include "mbedtls/ecp.h" #include "mbedtls/threading.h" #include "mbedtls/platform_util.h" +#include "mbedtls/error.h" +#include "mbedtls/bn_mul.h" + +#include "ecp_invasive.h" #include <string.h> @@ -134,10 +107,6 @@ #include "mbedtls/hmac_drbg.h" #elif defined(MBEDTLS_CTR_DRBG_C) #include "mbedtls/ctr_drbg.h" -#elif defined(MBEDTLS_SHA512_C) -#include "mbedtls/sha512.h" -#elif defined(MBEDTLS_SHA256_C) -#include "mbedtls/sha256.h" #else #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid." #endif @@ -209,6 +178,12 @@ static int ecp_drbg_seed( ecp_drbg_context *ctx, const mbedtls_md_type_t md_type = mbedtls_md_list()[0]; const mbedtls_md_info_t *md_info = mbedtls_md_info_from_type( md_type ); + if( secret_len > MBEDTLS_ECP_MAX_BYTES ) + { + ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; + goto cleanup; + } + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret, secret_bytes, secret_len ) ); @@ -265,6 +240,12 @@ static int ecp_drbg_seed( ecp_drbg_context *ctx, int ret; unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES]; + if( secret_len > MBEDTLS_ECP_MAX_BYTES ) + { + ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; + goto cleanup; + } + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret, secret_bytes, secret_len ) ); @@ -277,110 +258,9 @@ cleanup: return( ret ); } -#elif defined(MBEDTLS_SHA512_C) || defined(MBEDTLS_SHA256_C) - -/* This will be used in the self-test function */ -#define ECP_ONE_STEP_KDF - -/* - * We need to expand secret data (the scalar) into a longer stream of bytes. - * - * We'll use the One-Step KDF from NIST SP 800-56C, with option 1 (H is a hash - * function) and empty FixedInfo. (Though we'll make it fit the DRBG API for - * convenience, this is not a full-fledged DRBG, but we don't need one here.) - * - * We need a basic hash abstraction layer to use whatever SHA-2 is available. - */ -#if defined(MBEDTLS_SHA512_C) - -#define HASH_FUNC( in, ilen, out ) mbedtls_sha512_ret( in, ilen, out, 0 ); -#define HASH_BLOCK_BYTES ( 512 / 8 ) - -#elif defined(MBEDTLS_SHA256_C) - -#define HASH_FUNC( in, ilen, out ) mbedtls_sha256_ret( in, ilen, out, 0 ); -#define HASH_BLOCK_BYTES ( 256 / 8 ) - -#endif /* SHA512/SHA256 abstraction */ - -/* - * State consists of a 32-bit counter plus the secret value. - * - * We stored them concatenated in a single buffer as that's what will get - * passed to the hash function. - */ -typedef struct { - size_t total_len; - uint8_t buf[4 + MBEDTLS_ECP_MAX_BYTES]; -} ecp_drbg_context; - -static void ecp_drbg_init( ecp_drbg_context *ctx ) -{ - memset( ctx, 0, sizeof( ecp_drbg_context ) ); -} - -static void ecp_drbg_free( ecp_drbg_context *ctx ) -{ - mbedtls_platform_zeroize( ctx, sizeof( ecp_drbg_context ) ); -} - -static int ecp_drbg_seed( ecp_drbg_context *ctx, - const mbedtls_mpi *secret, size_t secret_len ) -{ - ctx->total_len = 4 + secret_len; - memset( ctx->buf, 0, 4); - return( mbedtls_mpi_write_binary( secret, ctx->buf + 4, secret_len ) ); -} - -static int ecp_drbg_random( void *p_rng, unsigned char *output, size_t output_len ) -{ - ecp_drbg_context *ctx = p_rng; - int ret; - size_t len_done = 0; - uint8_t tmp[HASH_BLOCK_BYTES]; - - while( len_done < output_len ) - { - uint8_t use_len; - - /* This function is only called for coordinate randomisation, which - * happens only twice in a scalar multiplication. Each time needs a - * random value in the range [2, p-1], and gets it by drawing len(p) - * bytes from this function, and retrying up to 10 times if unlucky. - * - * So for the largest curve, each scalar multiplication draws at most - * 20 * 66 bytes. The minimum block size is 32 (SHA-256), so with - * rounding that means a most 20 * 3 blocks. - * - * Since we don't need to draw more that 255 blocks, don't bother - * with carry propagation and just return an error instead. We can - * change that it we even need to draw more blinding values. - */ - ctx->buf[3] += 1; - if( ctx->buf[3] == 0 ) - return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); - - ret = HASH_FUNC( ctx->buf, ctx->total_len, tmp ); - if( ret != 0 ) - return( ret ); - - if( output_len - len_done > HASH_BLOCK_BYTES ) - use_len = HASH_BLOCK_BYTES; - else - use_len = output_len - len_done; - - memcpy( output + len_done, tmp, use_len ); - len_done += use_len; - } - - mbedtls_platform_zeroize( tmp, sizeof( tmp ) ); - - return( 0 ); -} - -#else /* DRBG/SHA modules */ +#else #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid." -#endif /* DRBG/SHA modules */ +#endif /* DRBG modules */ #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */ #if defined(MBEDTLS_ECP_RESTARTABLE) @@ -622,39 +502,10 @@ int mbedtls_ecp_check_budget( const mbedtls_ecp_group *grp, #endif /* MBEDTLS_ECP_RESTARTABLE */ -#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \ - defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) -#define ECP_SHORTWEIERSTRASS -#endif - -#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \ - defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) -#define ECP_MONTGOMERY -#endif - -/* - * Curve types: internal for now, might be exposed later - */ -typedef enum -{ - ECP_TYPE_NONE = 0, - ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */ - ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */ -} ecp_curve_type; - /* * List of supported curves: * - internal ID - * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2) + * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2, RFC 8446 sec. 4.2.7) * - size in bits * - readable name * @@ -698,6 +549,12 @@ static const mbedtls_ecp_curve_info ecp_supported_curves[] = #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" }, #endif +#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) + { MBEDTLS_ECP_DP_CURVE25519, 29, 256, "x25519" }, +#endif +#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) + { MBEDTLS_ECP_DP_CURVE448, 30, 448, "x448" }, +#endif { MBEDTLS_ECP_DP_NONE, 0, 0, NULL }, }; @@ -800,15 +657,15 @@ const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name /* * Get the type of a curve */ -static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp ) +mbedtls_ecp_curve_type mbedtls_ecp_get_type( const mbedtls_ecp_group *grp ) { if( grp->G.X.p == NULL ) - return( ECP_TYPE_NONE ); + return( MBEDTLS_ECP_TYPE_NONE ); if( grp->G.Y.p == NULL ) - return( ECP_TYPE_MONTGOMERY ); + return( MBEDTLS_ECP_TYPE_MONTGOMERY ); else - return( ECP_TYPE_SHORT_WEIERSTRASS ); + return( MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ); } /* @@ -919,7 +776,7 @@ void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key ) */ int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; ECP_VALIDATE_RET( P != NULL ); ECP_VALIDATE_RET( Q != NULL ); @@ -947,7 +804,7 @@ int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src */ int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; ECP_VALIDATE_RET( pt != NULL ); MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) ); @@ -993,7 +850,7 @@ int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P, int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix, const char *x, const char *y ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; ECP_VALIDATE_RET( P != NULL ); ECP_VALIDATE_RET( x != NULL ); ECP_VALIDATE_RET( y != NULL ); @@ -1007,14 +864,14 @@ cleanup: } /* - * Export a point into unsigned binary data (SEC1 2.3.3) + * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748) */ int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P, int format, size_t *olen, unsigned char *buf, size_t buflen ) { - int ret = 0; + int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; size_t plen; ECP_VALIDATE_RET( grp != NULL ); ECP_VALIDATE_RET( P != NULL ); @@ -1023,56 +880,72 @@ int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED || format == MBEDTLS_ECP_PF_COMPRESSED ); - /* - * Common case: P == 0 - */ - if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) - { - if( buflen < 1 ) - return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); - - buf[0] = 0x00; - *olen = 1; - - return( 0 ); - } - plen = mbedtls_mpi_size( &grp->P ); - if( format == MBEDTLS_ECP_PF_UNCOMPRESSED ) +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + (void) format; /* Montgomery curves always use the same point format */ + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) { - *olen = 2 * plen + 1; - + *olen = plen; if( buflen < *olen ) return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); - buf[0] = 0x04; - MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); - MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary_le( &P->X, buf, plen ) ); } - else if( format == MBEDTLS_ECP_PF_COMPRESSED ) +#endif +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) { - *olen = plen + 1; + /* + * Common case: P == 0 + */ + if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) + { + if( buflen < 1 ) + return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); - if( buflen < *olen ) - return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); + buf[0] = 0x00; + *olen = 1; + + return( 0 ); + } + + if( format == MBEDTLS_ECP_PF_UNCOMPRESSED ) + { + *olen = 2 * plen + 1; - buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); + if( buflen < *olen ) + return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); + + buf[0] = 0x04; + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) ); + } + else if( format == MBEDTLS_ECP_PF_COMPRESSED ) + { + *olen = plen + 1; + + if( buflen < *olen ) + return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); + + buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 ); + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); + } } +#endif cleanup: return( ret ); } /* - * Import a point from unsigned binary data (SEC1 2.3.4) + * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748) */ int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, const unsigned char *buf, size_t ilen ) { - int ret; + int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; size_t plen; ECP_VALIDATE_RET( grp != NULL ); ECP_VALIDATE_RET( pt != NULL ); @@ -1081,25 +954,47 @@ int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, if( ilen < 1 ) return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); - if( buf[0] == 0x00 ) + plen = mbedtls_mpi_size( &grp->P ); + +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) { - if( ilen == 1 ) - return( mbedtls_ecp_set_zero( pt ) ); - else + if( plen != ilen ) return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); - } - plen = mbedtls_mpi_size( &grp->P ); + MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &pt->X, buf, plen ) ); + mbedtls_mpi_free( &pt->Y ); - if( buf[0] != 0x04 ) - return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); + if( grp->id == MBEDTLS_ECP_DP_CURVE25519 ) + /* Set most significant bit to 0 as prescribed in RFC7748 ยง5 */ + MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &pt->X, plen * 8 - 1, 0 ) ); - if( ilen != 2 * plen + 1 ) - return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); + MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); + } +#endif +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) + { + if( buf[0] == 0x00 ) + { + if( ilen == 1 ) + return( mbedtls_ecp_set_zero( pt ) ); + else + return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); + } - MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) ); - MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) ); - MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); + if( buf[0] != 0x04 ) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); + + if( ilen != 2 * plen + 1 ) + return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); + + MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, + buf + 1 + plen, plen ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); + } +#endif cleanup: return( ret ); @@ -1151,7 +1046,7 @@ int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp int format, size_t *olen, unsigned char *buf, size_t blen ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; ECP_VALIDATE_RET( grp != NULL ); ECP_VALIDATE_RET( pt != NULL ); ECP_VALIDATE_RET( olen != NULL ); @@ -1184,7 +1079,7 @@ int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_ecp_group_id grp_id; ECP_VALIDATE_RET( grp != NULL ); ECP_VALIDATE_RET( buf != NULL ); @@ -1265,8 +1160,7 @@ int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen, /* * Next two bytes are the namedcurve value */ - buf[0] = curve_info->tls_id >> 8; - buf[1] = curve_info->tls_id & 0xFF; + MBEDTLS_PUT_UINT16_BE( curve_info->tls_id, buf, 0 ); return( 0 ); } @@ -1279,7 +1173,7 @@ int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen, */ static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; if( grp->modp == NULL ) return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) ); @@ -1331,6 +1225,18 @@ cleanup: INC_MUL_COUNT \ } while( 0 ) +static inline int mbedtls_mpi_mul_mod( const mbedtls_ecp_group *grp, + mbedtls_mpi *X, + const mbedtls_mpi *A, + const mbedtls_mpi *B ) +{ + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( X, A, B ) ); + MOD_MUL( *X ); +cleanup: + return( ret ); +} + /* * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi * N->s < 0 is a very fast test, which fails only if N is 0 @@ -1339,6 +1245,26 @@ cleanup: while( (N).s < 0 && mbedtls_mpi_cmp_int( &(N), 0 ) != 0 ) \ MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &(N), &(N), &grp->P ) ) +#if ( defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \ + !( defined(MBEDTLS_ECP_NO_FALLBACK) && \ + defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \ + defined(MBEDTLS_ECP_ADD_MIXED_ALT) ) ) || \ + ( defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) && \ + !( defined(MBEDTLS_ECP_NO_FALLBACK) && \ + defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) ) ) +static inline int mbedtls_mpi_sub_mod( const mbedtls_ecp_group *grp, + mbedtls_mpi *X, + const mbedtls_mpi *A, + const mbedtls_mpi *B ) +{ + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( X, A, B ) ); + MOD_SUB( *X ); +cleanup: + return( ret ); +} +#endif /* All functions referencing mbedtls_mpi_sub_mod() are alt-implemented without fallback */ + /* * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. * We known P, N and the result are positive, so sub_abs is correct, and @@ -1348,12 +1274,40 @@ cleanup: while( mbedtls_mpi_cmp_mpi( &(N), &grp->P ) >= 0 ) \ MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &(N), &(N), &grp->P ) ) -#if defined(ECP_SHORTWEIERSTRASS) +static inline int mbedtls_mpi_add_mod( const mbedtls_ecp_group *grp, + mbedtls_mpi *X, + const mbedtls_mpi *A, + const mbedtls_mpi *B ) +{ + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, A, B ) ); + MOD_ADD( *X ); +cleanup: + return( ret ); +} + +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \ + !( defined(MBEDTLS_ECP_NO_FALLBACK) && \ + defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \ + defined(MBEDTLS_ECP_ADD_MIXED_ALT) ) +static inline int mbedtls_mpi_shift_l_mod( const mbedtls_ecp_group *grp, + mbedtls_mpi *X, + size_t count ) +{ + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( X, count ) ); + MOD_ADD( *X ); +cleanup: + return( ret ); +} +#endif /* All functions referencing mbedtls_mpi_shift_l_mod() are alt-implemented without fallback */ + +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) /* * For curves in short Weierstrass form, we do all the internal operations in * Jacobian coordinates. * - * For multiplication, we'll use a comb method with coutermeasueres against + * For multiplication, we'll use a comb method with countermeasures against * SPA, hence timing attacks. */ @@ -1363,9 +1317,6 @@ cleanup: */ static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt ) { - int ret; - mbedtls_mpi Zi, ZZi; - if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ) return( 0 ); @@ -1374,20 +1325,25 @@ static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *p return( mbedtls_internal_ecp_normalize_jac( grp, pt ) ); #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + mbedtls_mpi Zi, ZZi; mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); /* * X = X / Z^2 mod p */ MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi, &Zi, &Zi ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X, &pt->X, &ZZi ) ); /* * Y = Y / Z^3 mod p */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &ZZi ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &Zi ) ); /* * Z = 1 @@ -1399,6 +1355,7 @@ cleanup: mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); return( ret ); +#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) */ } /* @@ -1415,10 +1372,6 @@ cleanup: static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, mbedtls_ecp_point *T[], size_t T_size ) { - int ret; - size_t i; - mbedtls_mpi *c, u, Zi, ZZi; - if( T_size < 2 ) return( ecp_normalize_jac( grp, *T ) ); @@ -1427,6 +1380,13 @@ static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) ); #endif +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + size_t i; + mbedtls_mpi *c, u, Zi, ZZi; + if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL ) return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); @@ -1441,8 +1401,7 @@ static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) ); for( i = 1; i < T_size; i++ ) { - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) ); - MOD_MUL( c[i] ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &c[i], &c[i-1], &T[i]->Z ) ); } /* @@ -1461,17 +1420,17 @@ static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, } else { - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Zi, &u, &c[i-1] ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &u, &u, &T[i]->Z ) ); } /* * proceed as in normalize() */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi, &Zi, &Zi ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->X, &T[i]->X, &ZZi ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &ZZi ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &Zi ) ); /* * Post-precessing: reclaim some memory by shrinking coordinates @@ -1495,6 +1454,7 @@ cleanup: mbedtls_free( c ); return( ret ); +#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) */ } /* @@ -1505,7 +1465,7 @@ static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *Q, unsigned char inv ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; unsigned char nonzero; mbedtls_mpi mQY; @@ -1539,9 +1499,6 @@ cleanup: static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_ecp_point *P ) { - int ret; - mbedtls_mpi M, S, T, U; - #if defined(MBEDTLS_SELF_TEST) dbl_count++; #endif @@ -1551,58 +1508,64 @@ static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, return( mbedtls_internal_ecp_double_jac( grp, R, P ) ); #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + mbedtls_mpi M, S, T, U; + mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U ); /* Special case for A = -3 */ if( grp->A.p == NULL ) { /* M = 3(X + Z^2)(X - Z^2) */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->Z, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &T, &P->X, &S ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &U, &P->X, &S ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &T, &U ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); } else { /* M = 3.X^2 */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->X, &P->X ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); /* Optimize away for "koblitz" curves with A = 0 */ if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 ) { /* M += A.Z^4 */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->Z, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &S, &S ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &T, &grp->A ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &M, &M, &S ) ); } } /* S = 4.X.Y^2 */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T ); - MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S ); - MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &P->Y, &P->Y ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T, 1 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->X, &T ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &S, 1 ) ); /* U = 8.Y^4 */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U ); - MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U, &T, &T ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U, 1 ) ); /* T = M^2 - 2.S */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &M, &M ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T, &T, &S ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T, &T, &S ) ); /* S = M(S - T) - U */ - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S, &S, &T ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &S, &M ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S, &S, &U ) ); /* U = 2.Y.Z */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U ); - MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U, &P->Y, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U, 1 ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) ); @@ -1612,6 +1575,7 @@ cleanup: mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U ); return( ret ); +#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) */ } /* @@ -1635,9 +1599,6 @@ cleanup: static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) { - int ret; - mbedtls_mpi T1, T2, T3, T4, X, Y, Z; - #if defined(MBEDTLS_SELF_TEST) add_count++; #endif @@ -1647,6 +1608,12 @@ static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) ); #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_ADD_MIXED_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + mbedtls_mpi T1, T2, T3, T4, X, Y, Z; + /* * Trivial cases: P == 0 or Q == 0 (case 1) */ @@ -1665,12 +1632,12 @@ static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 ); mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1, &P->Z, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2, &T1, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1, &T1, &Q->X ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2, &T2, &Q->Y ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T1, &T1, &P->X ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T2, &T2, &P->Y ) ); /* Special cases (2) and (3) */ if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 ) @@ -1687,18 +1654,19 @@ static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, } } - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Z, &P->Z, &T1 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T1, &T1 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4, &T3, &T1 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T3, &P->X ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &T3 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T1, 1 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &X, &T2, &T2 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X, &X, &T1 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X, &X, &T4 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T3, &T3, &X ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T3, &T2 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4, &T4, &P->Y ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &Y, &T3, &T4 ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) ); @@ -1710,6 +1678,7 @@ cleanup: mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); return( ret ); +#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_ADD_MIXED_ALT) */ } /* @@ -1722,50 +1691,40 @@ cleanup: static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) { - int ret; - mbedtls_mpi l, ll; - size_t p_size; - int count = 0; - #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) if( mbedtls_internal_ecp_grp_capable( grp ) ) return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) ); #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ - p_size = ( grp->pbits + 7 ) / 8; +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + mbedtls_mpi l, ll; + 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_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Z, &pt->Z, &l ) ); /* X = l^2 * X */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll, &l, &l ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X, &pt->X, &ll ) ); /* Y = l^3 * Y */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll, &ll, &l ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &ll ) ); 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) */ } /* @@ -1897,7 +1856,7 @@ static int ecp_precompute_comb( const mbedtls_ecp_group *grp, unsigned char w, size_t d, mbedtls_ecp_restart_ctx *rs_ctx ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; unsigned char i; size_t j = 0; const unsigned char T_size = 1U << ( w - 1 ); @@ -2033,7 +1992,7 @@ static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_ecp_point T[], unsigned char T_size, unsigned char i ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; unsigned char ii, j; /* Ignore the "sign" bit and scale down */ @@ -2066,7 +2025,7 @@ static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R void *p_rng, mbedtls_ecp_restart_ctx *rs_ctx ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_ecp_point Txi; size_t i; @@ -2148,7 +2107,7 @@ static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp, unsigned char w, unsigned char *parity_trick ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_mpi M, mm; mbedtls_mpi_init( &M ); @@ -2194,7 +2153,7 @@ static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp, void *p_rng, mbedtls_ecp_restart_ctx *rs_ctx ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; unsigned char parity_trick; unsigned char k[COMB_MAX_D + 1]; mbedtls_ecp_point *RR = R; @@ -2276,8 +2235,10 @@ static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp, * Make sure w is within bounds. * (The last test is useful only for very small curves in the test suite.) */ +#if( MBEDTLS_ECP_WINDOW_SIZE < 6 ) if( w > MBEDTLS_ECP_WINDOW_SIZE ) w = MBEDTLS_ECP_WINDOW_SIZE; +#endif if( w >= grp->nbits ) w = 2; @@ -2290,7 +2251,7 @@ static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp, * This function is mainly responsible for administrative work: * - managing the restart context if enabled * - managing the table of precomputed points (passed between the below two - * functions): allocation, computation, ownership tranfer, freeing. + * functions): allocation, computation, ownership transfer, freeing. * * It delegates the actual arithmetic work to: * ecp_precompute_comb() and ecp_mul_comb_with_precomp() @@ -2303,7 +2264,7 @@ static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, void *p_rng, mbedtls_ecp_restart_ctx *rs_ctx ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; unsigned char w, p_eq_g, i; size_t d; unsigned char T_size = 0, T_ok = 0; @@ -2455,13 +2416,13 @@ cleanup: return( ret ); } -#endif /* ECP_SHORTWEIERSTRASS */ +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ -#if defined(ECP_MONTGOMERY) +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) /* * For Montgomery curves, we do all the internal arithmetic in projective * coordinates. Import/export of points uses only the x coordinates, which is - * internaly represented as X / Z. + * internally represented as X / Z. * * For scalar multiplication, we'll use a Montgomery ladder. */ @@ -2472,19 +2433,22 @@ cleanup: */ static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) { - int ret; - #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) if( mbedtls_internal_ecp_grp_capable( grp ) ) return( mbedtls_internal_ecp_normalize_mxz( grp, P ) ); #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->X, &P->X, &P->Z ) ); MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); cleanup: return( ret ); +#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) */ } /* @@ -2498,42 +2462,31 @@ cleanup: static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) { - int ret; - mbedtls_mpi l; - size_t p_size; - int count = 0; - #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; +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + mbedtls_mpi l; 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 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_random( &l, 2, &grp->P, 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_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 ); + 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 ) ); 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) */ } /* @@ -2556,36 +2509,39 @@ static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, const mbedtls_mpi *d ) { - int ret; - mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; - #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) if( mbedtls_internal_ecp_grp_capable( grp ) ) return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) ); #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ +#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) + return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); +#else + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; + mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; + mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &A, &P->X, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &AA, &A, &A ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &B, &P->X, &P->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &BB, &B, &B ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &E, &AA, &BB ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &C, &Q->X, &Q->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &D, &Q->X, &Q->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &DA, &D, &A ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &CB, &C, &B ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &S->X, &DA, &CB ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->X, &S->X, &S->X ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S->Z, &DA, &CB ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->Z, &S->Z, &S->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->Z, d, &S->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->X, &AA, &BB ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->Z, &grp->A, &E ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &R->Z, &BB, &R->Z ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->Z, &E, &R->Z ) ); cleanup: mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); @@ -2593,6 +2549,7 @@ cleanup: mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); return( ret ); +#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) */ } /* @@ -2604,7 +2561,7 @@ static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; size_t i; unsigned char b; mbedtls_ecp_point RP; @@ -2635,7 +2592,7 @@ static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) ); mbedtls_mpi_free( &R->Y ); - /* RP.X might be sligtly larger than P, so reduce it */ + /* RP.X might be slightly larger than P, so reduce it */ MOD_ADD( RP.X ); /* Randomize coordinates of the starting point */ @@ -2691,7 +2648,7 @@ cleanup: return( ret ); } -#endif /* ECP_MONTGOMERY */ +#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ /* * Restartable multiplication R = m * P @@ -2714,6 +2671,8 @@ int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, /* reset ops count for this call if top-level */ if( rs_ctx != NULL && rs_ctx->depth++ == 0 ) rs_ctx->ops_done = 0; +#else + (void) rs_ctx; #endif #if defined(MBEDTLS_ECP_INTERNAL_ALT) @@ -2735,12 +2694,12 @@ int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, } ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; -#if defined(ECP_MONTGOMERY) - if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) ); #endif -#if defined(ECP_SHORTWEIERSTRASS) - if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) ); #endif @@ -2773,14 +2732,14 @@ int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) ); } -#if defined(ECP_SHORTWEIERSTRASS) +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) /* * Check that an affine point is valid as a public key, * short weierstrass curves (SEC1 3.2.3.1) */ static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_mpi YY, RHS; /* pt coordinates must be normalized for our checks */ @@ -2796,8 +2755,8 @@ static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_ * YY = Y^2 * RHS = X (X^2 + A) + B = X^3 + A X + B */ - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY ); - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &YY, &pt->Y, &pt->Y ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &pt->X, &pt->X ) ); /* Special case for A = -3 */ if( grp->A.p == NULL ) @@ -2806,11 +2765,11 @@ static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_ } else { - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->A ) ); } - MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); - MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); + MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &RHS, &pt->X ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->B ) ); if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) ret = MBEDTLS_ERR_ECP_INVALID_KEY; @@ -2821,10 +2780,11 @@ cleanup: return( ret ); } -#endif /* ECP_SHORTWEIERSTRASS */ +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) /* - * R = m * P with shortcuts for m == 1 and m == -1 + * R = m * P with shortcuts for m == 0, m == 1 and m == -1 * NOT constant-time - ONLY for short Weierstrass! */ static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, @@ -2833,9 +2793,13 @@ static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, const mbedtls_ecp_point *P, mbedtls_ecp_restart_ctx *rs_ctx ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; - if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) + if( mbedtls_mpi_cmp_int( m, 0 ) == 0 ) + { + MBEDTLS_MPI_CHK( mbedtls_ecp_set_zero( R ) ); + } + else if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) { MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); } @@ -2865,7 +2829,7 @@ int mbedtls_ecp_muladd_restartable( const mbedtls_mpi *n, const mbedtls_ecp_point *Q, mbedtls_ecp_restart_ctx *rs_ctx ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_ecp_point mP; mbedtls_ecp_point *pmP = &mP; mbedtls_ecp_point *pR = R; @@ -2879,7 +2843,7 @@ int mbedtls_ecp_muladd_restartable( ECP_VALIDATE_RET( n != NULL ); ECP_VALIDATE_RET( Q != NULL ); - if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ) + if( mbedtls_ecp_get_type( grp ) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); mbedtls_ecp_point_init( &mP ); @@ -2968,8 +2932,100 @@ int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, ECP_VALIDATE_RET( Q != NULL ); return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) ); } +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ + +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) +#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 ); +} -#if defined(ECP_MONTGOMERY) /* * Check validity of a public key for Montgomery curves with x-only schemes */ @@ -2981,9 +3037,15 @@ 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 */ +#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ /* * Check that a point is valid as a public key @@ -2998,12 +3060,12 @@ int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 ) return( MBEDTLS_ERR_ECP_INVALID_KEY ); -#if defined(ECP_MONTGOMERY) - if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) return( ecp_check_pubkey_mx( grp, pt ) ); #endif -#if defined(ECP_SHORTWEIERSTRASS) - if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) return( ecp_check_pubkey_sw( grp, pt ) ); #endif return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); @@ -3018,8 +3080,8 @@ int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, ECP_VALIDATE_RET( grp != NULL ); ECP_VALIDATE_RET( d != NULL ); -#if defined(ECP_MONTGOMERY) - if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) { /* see RFC 7748 sec. 5 para. 5 */ if( mbedtls_mpi_get_bit( d, 0 ) != 0 || @@ -3033,9 +3095,9 @@ int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, return( 0 ); } -#endif /* ECP_MONTGOMERY */ -#if defined(ECP_SHORTWEIERSTRASS) - if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) +#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) { /* see SEC1 3.2 */ if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || @@ -3044,11 +3106,61 @@ int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, else return( 0 ); } -#endif /* ECP_SHORTWEIERSTRASS */ +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 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 */ @@ -3057,86 +3169,21 @@ int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, 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(ECP_MONTGOMERY) - if( ecp_get_type( grp ) == 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 ) ); - } - } -#endif /* ECP_MONTGOMERY */ +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) + return( mbedtls_ecp_gen_privkey_mx( grp->nbits, d, f_rng, p_rng ) ); +#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ -#if defined(ECP_SHORTWEIERSTRASS) - if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) - { - /* SEC1 3.2.1: Generate d such that 1 <= n < N */ - int count = 0; - unsigned cmp = 0; +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) + return( mbedtls_ecp_gen_privkey_sw( &grp->N, d, f_rng, p_rng ) ); +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ - /* - * 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 ) - return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); - - 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 ); - } -#endif /* ECP_SHORTWEIERSTRASS */ - -cleanup: - return( ret ); + return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); } /* @@ -3148,7 +3195,7 @@ int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; ECP_VALIDATE_RET( grp != NULL ); ECP_VALIDATE_RET( d != NULL ); ECP_VALIDATE_RET( G != NULL ); @@ -3184,7 +3231,7 @@ int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; ECP_VALIDATE_RET( key != NULL ); ECP_VALIDATE_RET( f_rng != NULL ); @@ -3194,12 +3241,120 @@ int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); } +#define ECP_CURVE25519_KEY_SIZE 32 +/* + * Read a private key. + */ +int mbedtls_ecp_read_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, + const unsigned char *buf, size_t buflen ) +{ + int ret = 0; + + ECP_VALIDATE_RET( key != NULL ); + ECP_VALIDATE_RET( buf != NULL ); + + if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) + return( ret ); + + ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; + +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) + { + /* + * If it is Curve25519 curve then mask the key as mandated by RFC7748 + */ + if( grp_id == MBEDTLS_ECP_DP_CURVE25519 ) + { + if( buflen != ECP_CURVE25519_KEY_SIZE ) + return MBEDTLS_ERR_ECP_INVALID_KEY; + + MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &key->d, buf, buflen ) ); + + /* Set the three least significant bits to 0 */ + MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 0, 0 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 1, 0 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 2, 0 ) ); + + /* Set the most significant bit to 0 */ + MBEDTLS_MPI_CHK( + mbedtls_mpi_set_bit( &key->d, + ECP_CURVE25519_KEY_SIZE * 8 - 1, 0 ) + ); + + /* Set the second most significant bit to 1 */ + MBEDTLS_MPI_CHK( + mbedtls_mpi_set_bit( &key->d, + ECP_CURVE25519_KEY_SIZE * 8 - 2, 1 ) + ); + } + else + ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; + } + +#endif +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) + { + MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &key->d, buf, buflen ) ); + + MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( &key->grp, &key->d ) ); + } + +#endif +cleanup: + + if( ret != 0 ) + mbedtls_mpi_free( &key->d ); + + return( ret ); +} + +/* + * Write a private key. + */ +int mbedtls_ecp_write_key( mbedtls_ecp_keypair *key, + unsigned char *buf, size_t buflen ) +{ + int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; + + ECP_VALIDATE_RET( key != NULL ); + ECP_VALIDATE_RET( buf != NULL ); + +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) + { + if( key->grp.id == MBEDTLS_ECP_DP_CURVE25519 ) + { + if( buflen < ECP_CURVE25519_KEY_SIZE ) + return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; + + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary_le( &key->d, buf, buflen ) ); + } + else + ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; + } + +#endif +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) + { + MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &key->d, buf, buflen ) ); + } + +#endif +cleanup: + + return( ret ); +} + + /* * Check a public-private key pair */ int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) { - int ret; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_ecp_point Q; mbedtls_ecp_group grp; ECP_VALIDATE_RET( pub != NULL ); @@ -3240,103 +3395,141 @@ cleanup: #if defined(MBEDTLS_SELF_TEST) -#if defined(ECP_ONE_STEP_KDF) -/* - * There are no test vectors from NIST for the One-Step KDF in SP 800-56C, - * but unofficial ones can be found at: - * https://github.com/patrickfav/singlestep-kdf/wiki/NIST-SP-800-56C-Rev1:-Non-Official-Test-Vectors - * - * We only use the ones with empty fixedInfo, and for brevity's sake, only - * 40-bytes output (with SHA-256 that's more than one block, and with SHA-512 - * less than one block). - */ -#if defined(MBEDTLS_SHA512_C) - -static const uint8_t test_kdf_z[16] = { - 0x3b, 0xa9, 0x79, 0xe9, 0xbc, 0x5e, 0x3e, 0xc7, - 0x61, 0x30, 0x36, 0xb6, 0xf5, 0x1c, 0xd5, 0xaa, -}; -static const uint8_t test_kdf_out[40] = { - 0x3e, 0xf6, 0xda, 0xf9, 0x51, 0x60, 0x70, 0x5f, - 0xdf, 0x21, 0xcd, 0xab, 0xac, 0x25, 0x7b, 0x05, - 0xfe, 0xc1, 0xab, 0x7c, 0xc9, 0x68, 0x43, 0x25, - 0x8a, 0xfc, 0x40, 0x6e, 0x5b, 0xf7, 0x98, 0x27, - 0x10, 0xfa, 0x7b, 0x93, 0x52, 0xd4, 0x16, 0xaa, -}; - -#elif defined(MBEDTLS_SHA256_C) - -static const uint8_t test_kdf_z[16] = { - 0xc8, 0x3e, 0x35, 0x8e, 0x99, 0xa6, 0x89, 0xc6, - 0x7d, 0xb4, 0xfe, 0x39, 0xcf, 0x8f, 0x26, 0xe1, -}; -static const uint8_t test_kdf_out[40] = { - 0x7d, 0xf6, 0x41, 0xf8, 0x3c, 0x47, 0xdc, 0x28, - 0x5f, 0x7f, 0xaa, 0xde, 0x05, 0x64, 0xd6, 0x25, - 0x00, 0x6a, 0x47, 0xd9, 0x1e, 0xa4, 0xa0, 0x8c, - 0xd7, 0xf7, 0x0c, 0x99, 0xaa, 0xa0, 0x72, 0x66, - 0x69, 0x0e, 0x25, 0xaa, 0xa1, 0x63, 0x14, 0x79, -}; - +/* Adjust the exponent to be a valid private point for the specified curve. + * This is sometimes necessary because we use a single set of exponents + * for all curves but the validity of values depends on the curve. */ +static int self_test_adjust_exponent( const mbedtls_ecp_group *grp, + mbedtls_mpi *m ) +{ + int ret = 0; + switch( grp->id ) + { + /* If Curve25519 is available, then that's what we use for the + * Montgomery test, so we don't need the adjustment code. */ +#if ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) +#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) + case MBEDTLS_ECP_DP_CURVE448: + /* Move highest bit from 254 to N-1. Setting bit N-1 is + * necessary to enforce the highest-bit-set constraint. */ + MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( m, 254, 0 ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( m, grp->nbits, 1 ) ); + /* Copy second-highest bit from 253 to N-2. This is not + * necessary but improves the test variety a bit. */ + MBEDTLS_MPI_CHK( + mbedtls_mpi_set_bit( m, grp->nbits - 1, + mbedtls_mpi_get_bit( m, 253 ) ) ); + break; #endif +#endif /* ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) */ + default: + /* Non-Montgomery curves and Curve25519 need no adjustment. */ + (void) grp; + (void) m; + goto cleanup; + } +cleanup: + return( ret ); +} -static int ecp_kdf_self_test( void ) +/* Calculate R = m.P for each m in exponents. Check that the number of + * basic operations doesn't depend on the value of m. */ +static int self_test_point( int verbose, + mbedtls_ecp_group *grp, + mbedtls_ecp_point *R, + mbedtls_mpi *m, + const mbedtls_ecp_point *P, + const char *const *exponents, + size_t n_exponents ) { - int ret; - ecp_drbg_context kdf_ctx; - mbedtls_mpi scalar; - uint8_t out[sizeof( test_kdf_out )]; - - ecp_drbg_init( &kdf_ctx ); - mbedtls_mpi_init( &scalar ); - memset( out, 0, sizeof( out ) ); + int ret = 0; + size_t i = 0; + unsigned long add_c_prev, dbl_c_prev, mul_c_prev; + add_count = 0; + dbl_count = 0; + mul_count = 0; - MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &scalar, - test_kdf_z, sizeof( test_kdf_z ) ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( m, 16, exponents[0] ) ); + MBEDTLS_MPI_CHK( self_test_adjust_exponent( grp, m ) ); + MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); - MBEDTLS_MPI_CHK( ecp_drbg_seed( &kdf_ctx, - &scalar, sizeof( test_kdf_z ) ) ); + for( i = 1; i < n_exponents; i++ ) + { + add_c_prev = add_count; + dbl_c_prev = dbl_count; + mul_c_prev = mul_count; + add_count = 0; + dbl_count = 0; + mul_count = 0; - MBEDTLS_MPI_CHK( ecp_drbg_random( &kdf_ctx, out, sizeof( out ) ) ); + MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( m, 16, exponents[i] ) ); + MBEDTLS_MPI_CHK( self_test_adjust_exponent( grp, m ) ); + MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); - if( memcmp( out, test_kdf_out, sizeof( out ) ) != 0 ) - ret = -1; + if( add_count != add_c_prev || + dbl_count != dbl_c_prev || + mul_count != mul_c_prev ) + { + ret = 1; + break; + } + } cleanup: - ecp_drbg_free( &kdf_ctx ); - mbedtls_mpi_free( &scalar ); - + if( verbose != 0 ) + { + if( ret != 0 ) + mbedtls_printf( "failed (%u)\n", (unsigned int) i ); + else + mbedtls_printf( "passed\n" ); + } return( ret ); } -#endif /* ECP_ONE_STEP_KDF */ /* * Checkup routine */ int mbedtls_ecp_self_test( int verbose ) { - int ret; - size_t i; + int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; mbedtls_ecp_group grp; mbedtls_ecp_point R, P; mbedtls_mpi m; - unsigned long add_c_prev, dbl_c_prev, mul_c_prev; - /* exponents especially adapted for secp192r1 */ - const char *exponents[] = + +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) + /* Exponents especially adapted for secp192k1, which has the lowest + * order n of all supported curves (secp192r1 is in a slightly larger + * field but the order of its base point is slightly smaller). */ + const char *sw_exponents[] = { "000000000000000000000000000000000000000000000001", /* one */ - "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ + "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8C", /* n - 1 */ "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ "400000000000000000000000000000000000000000000000", /* one and zeros */ "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ "555555555555555555555555555555555555555555555555", /* 101010... */ }; +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) + const char *m_exponents[] = + { + /* Valid private values for Curve25519. In a build with Curve448 + * but not Curve25519, they will be adjusted in + * self_test_adjust_exponent(). */ + "4000000000000000000000000000000000000000000000000000000000000000", + "5C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C30", + "5715ECCE24583F7A7023C24164390586842E816D7280A49EF6DF4EAE6B280BF8", + "41A2B017516F6D254E1F002BCCBADD54BE30F8CEC737A0E912B4963B6BA74460", + "5555555555555555555555555555555555555555555555555555555555555550", + "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8", + }; +#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ mbedtls_ecp_group_init( &grp ); mbedtls_ecp_point_init( &R ); mbedtls_ecp_point_init( &P ); mbedtls_mpi_init( &m ); +#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) /* Use secp192r1 if available, or any available curve */ #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); @@ -3345,104 +3538,53 @@ int mbedtls_ecp_self_test( int verbose ) #endif if( verbose != 0 ) - mbedtls_printf( " ECP test #1 (constant op_count, base point G): " ); - + mbedtls_printf( " ECP SW test #1 (constant op_count, base point G): " ); /* Do a dummy multiplication first to trigger precomputation */ MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); - - add_count = 0; - dbl_count = 0; - mul_count = 0; - MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); - MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); - - for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) - { - add_c_prev = add_count; - dbl_c_prev = dbl_count; - mul_c_prev = mul_count; - add_count = 0; - dbl_count = 0; - mul_count = 0; - - MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); - MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); - - if( add_count != add_c_prev || - dbl_count != dbl_c_prev || - mul_count != mul_c_prev ) - { - if( verbose != 0 ) - mbedtls_printf( "failed (%u)\n", (unsigned int) i ); - - ret = 1; - goto cleanup; - } - } - - if( verbose != 0 ) - mbedtls_printf( "passed\n" ); + ret = self_test_point( verbose, + &grp, &R, &m, &grp.G, + sw_exponents, + sizeof( sw_exponents ) / sizeof( sw_exponents[0] )); + if( ret != 0 ) + goto cleanup; if( verbose != 0 ) - mbedtls_printf( " ECP test #2 (constant op_count, other point): " ); + mbedtls_printf( " ECP SW test #2 (constant op_count, other point): " ); /* We computed P = 2G last time, use it */ + ret = self_test_point( verbose, + &grp, &R, &m, &P, + sw_exponents, + sizeof( sw_exponents ) / sizeof( sw_exponents[0] )); + if( ret != 0 ) + goto cleanup; - add_count = 0; - dbl_count = 0; - mul_count = 0; - MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); - MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); - - for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) - { - add_c_prev = add_count; - dbl_c_prev = dbl_count; - mul_c_prev = mul_count; - add_count = 0; - dbl_count = 0; - mul_count = 0; - - MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); - MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); - - if( add_count != add_c_prev || - dbl_count != dbl_c_prev || - mul_count != mul_c_prev ) - { - if( verbose != 0 ) - mbedtls_printf( "failed (%u)\n", (unsigned int) i ); - - ret = 1; - goto cleanup; - } - } - - if( verbose != 0 ) - mbedtls_printf( "passed\n" ); + mbedtls_ecp_group_free( &grp ); + mbedtls_ecp_point_free( &R ); +#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ -#if defined(ECP_ONE_STEP_KDF) +#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) if( verbose != 0 ) - mbedtls_printf( " ECP test #3 (internal KDF): " ); - - ret = ecp_kdf_self_test(); + mbedtls_printf( " ECP Montgomery test (constant op_count): " ); +#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) + MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_CURVE25519 ) ); +#elif defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) + MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_CURVE448 ) ); +#else +#error "MBEDTLS_ECP_MONTGOMERY_ENABLED is defined, but no curve is supported for self-test" +#endif + ret = self_test_point( verbose, + &grp, &R, &m, &grp.G, + m_exponents, + sizeof( m_exponents ) / sizeof( m_exponents[0] )); if( ret != 0 ) - { - if( verbose != 0 ) - mbedtls_printf( "failed\n" ); - - ret = 1; goto cleanup; - } - - if( verbose != 0 ) - mbedtls_printf( "passed\n" ); -#endif /* ECP_ONE_STEP_KDF */ +#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 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_ecp_group_free( &grp ); mbedtls_ecp_point_free( &R ); |