Introduce muladd_restartable() and its sub-context
Only the administrative parts for now, not actually restartable so far.
diff --git a/include/mbedtls/ecp.h b/include/mbedtls/ecp.h
index 7d0abc0..e2c605b 100644
--- a/include/mbedtls/ecp.h
+++ b/include/mbedtls/ecp.h
@@ -180,6 +180,13 @@
typedef struct mbedtls_ecp_restart_mul mbedtls_ecp_restart_mul_ctx;
/**
+ * \brief Internal restart context for ecp_muladd()
+ *
+ * \note Opaque struct
+ */
+typedef struct mbedtls_ecp_restart_muladd mbedtls_ecp_restart_muladd_ctx;
+
+/**
* \brief General context for resuming ECC operations
*/
typedef struct
@@ -187,6 +194,7 @@
unsigned ops_done; /*!< current ops count */
unsigned depth; /*!< call depth (0 = top-level) */
mbedtls_ecp_restart_mul_ctx *rsm; /*!< ecp_mul_comb() sub-context */
+ mbedtls_ecp_restart_muladd_ctx *ma; /*!< ecp_muladd() sub-context */
} mbedtls_ecp_restart_ctx;
#endif /* MBEDTLS_ECP_EARLY_RETURN */
@@ -654,6 +662,33 @@
const mbedtls_mpi *m, const mbedtls_ecp_point *P,
const mbedtls_mpi *n, const mbedtls_ecp_point *Q );
+#if defined(MBEDTLS_ECP_EARLY_RETURN)
+/**
+ * \brief Restartable version of \c mbedtls_ecp_muladd()
+ *
+ * \note Performs the same job as \c mbedtls_ecp_muladd(), but can
+ * return early and restart according to the limit set with
+ * \c mbedtls_ecp_set_max_ops() to reduce blocking.
+ *
+ * \param grp ECP group
+ * \param R Destination point
+ * \param m Integer by which to multiply P
+ * \param P Point to multiply by m
+ * \param n Integer by which to multiply Q
+ * \param Q Point to be multiplied by n
+ * \param rs_ctx Restart context
+ *
+ * \return See \c mbedtls_ecp_muladd(), or
+ * MBEDTLS_ERR_ECP_IN_PROGRESS if maximum number of
+ * operations was reached: see \c mbedtls_ecp_set_max_ops().
+ */
+int mbedtls_ecp_muladd_restartable(
+ mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
+ const mbedtls_mpi *m, const mbedtls_ecp_point *P,
+ const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
+ mbedtls_ecp_restart_ctx *rs_ctx );
+#endif
+
/**
* \brief Check that a point is a valid public key on this curve
*
diff --git a/library/ecp.c b/library/ecp.c
index 4e637d7..4933460 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -101,9 +101,10 @@
}
/*
- * Restart context type for interrupted operations
+ * Restart sub-context for ecp_mul_comb()
*/
-struct mbedtls_ecp_restart_mul {
+struct mbedtls_ecp_restart_mul
+{
mbedtls_ecp_point R; /* current intermediate result */
size_t i; /* current index in various loops, 0 outside */
mbedtls_ecp_point *T; /* table for precomputed points */
@@ -119,7 +120,7 @@
};
/*
- * Init restart_mul context
+ * Init restart_mul sub-context
*/
static void ecp_restart_mul_init( mbedtls_ecp_restart_mul_ctx *ctx )
{
@@ -127,7 +128,7 @@
}
/*
- * Free the components of a restart_mul context
+ * Free the components of a restart_mul sub-context
*/
static void ecp_restart_mul_free( mbedtls_ecp_restart_mul_ctx *ctx )
{
@@ -148,6 +149,33 @@
}
/*
+ * Restart context for ecp_muladd()
+ */
+struct mbedtls_ecp_restart_muladd
+{
+ int state; /* dummy for now */
+};
+
+/*
+ * Init restart_muladd sub-context
+ */
+static void ecp_restart_muladd_init( mbedtls_ecp_restart_muladd_ctx *ctx )
+{
+ memset( ctx, 0, sizeof( *ctx ) );
+}
+
+/*
+ * Free the components of a restart_muladd sub-context
+ */
+static void ecp_restart_muladd_free( mbedtls_ecp_restart_muladd_ctx *ctx )
+{
+ if( ctx == NULL )
+ return;
+
+ memset( ctx, 0, sizeof( *ctx ) );
+}
+
+/*
* Initialize a restart context
*/
void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx *ctx )
@@ -1868,9 +1896,9 @@
if( ret != 0 )
mbedtls_ecp_point_free( R );
- /* clear restart context when not in progress (done or error) */
+ /* clear our sub-context when not in progress (done or error) */
#if defined(MBEDTLS_ECP_EARLY_RETURN)
- if( rs_ctx != NULL && rs_ctx->rsm != NULL && ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) {
+ if( rs_ctx != NULL && ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) {
ecp_restart_mul_free( rs_ctx->rsm );
mbedtls_free( rs_ctx->rsm );
rs_ctx->rsm = NULL;
@@ -2248,12 +2276,17 @@
}
/*
- * Linear combination
+ * Restartable linear combination
* NOT constant-time
*/
-int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
+#if !defined(MBEDTLS_ECP_EARLY_RETURN)
+static
+#endif
+int mbedtls_ecp_muladd_restartable(
+ mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
const mbedtls_mpi *m, const mbedtls_ecp_point *P,
- const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
+ const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
+ mbedtls_ecp_restart_ctx *rs_ctx )
{
int ret;
mbedtls_ecp_point mP;
@@ -2261,9 +2294,29 @@
char is_grp_capable = 0;
#endif
+#if !defined(MBEDTLS_ECP_EARLY_RETURN)
+ (void) rs_ctx;
+#endif
+
if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
+#if defined(MBEDTLS_ECP_EARLY_RETURN)
+ /* reset ops count for this call if top-level */
+ if( rs_ctx != NULL && rs_ctx->depth++ == 0 )
+ rs_ctx->ops_done = 0;
+
+ /* set up our own sub-context if needed */
+ if( ecp_max_ops != 0 && rs_ctx != NULL && rs_ctx->ma == NULL )
+ {
+ rs_ctx->ma = mbedtls_calloc( 1, sizeof( mbedtls_ecp_restart_muladd_ctx ) );
+ if( rs_ctx->ma == NULL )
+ return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
+
+ ecp_restart_muladd_init( rs_ctx->ma );
+ }
+#endif /* MBEDTLS_ECP_EARLY_RETURN */
+
mbedtls_ecp_point_init( &mP );
MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) );
@@ -2290,9 +2343,32 @@
#endif /* MBEDTLS_ECP_INTERNAL_ALT */
mbedtls_ecp_point_free( &mP );
+#if defined(MBEDTLS_ECP_EARLY_RETURN)
+ /* clear our sub-context when not in progress (done or error) */
+ if( rs_ctx != NULL && ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) {
+ ecp_restart_muladd_free( rs_ctx->ma );
+ mbedtls_free( rs_ctx->ma );
+ rs_ctx->ma = NULL;
+ }
+
+
+ if( rs_ctx != NULL )
+ rs_ctx->depth--;
+#endif /* MBEDTLS_ECP_EARLY_RETURN */
+
return( ret );
}
+/*
+ * Linear combination
+ * NOT constant-time
+ */
+int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
+ const mbedtls_mpi *m, const mbedtls_ecp_point *P,
+ const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
+{
+ return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) );
+}
#if defined(ECP_MONTGOMERY)
/*
diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 82ffec5..9d25d22 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -345,18 +345,22 @@
ECP selftest
ecp_selftest:
-ECP early return secp256r1 restart disabled
+ECP early return mul secp256r1 restart disabled
depends_on:MBEDTLS_ECP_DP_SECP256R1_ENABLED
ecp_test_vect_restart:MBEDTLS_ECP_DP_SECP256R1:"814264145F2F56F2E96A8E337A1284993FAF432A5ABCE59E867B7291D507A3AF":"2AF502F3BE8952F2C9B5A8D4160D09E97165BE50BC42AE4A5E8D3B4BA83AEB15":"EB0FAF4CA986C4D38681A0F9872D79D56795BD4BFF6E6DE3C0F5015ECE5EFD85":"2CE1788EC197E096DB95A200CC0AB26A19CE6BCCAD562B8EEE1B593761CF7F41":"DD0F5396219D1EA393310412D19A08F1F5811E9DC8EC8EEA7F80D21C820C2788":"0357DCCD4C804D0D8D33AA42B848834AA5605F9AB0D37239A115BBB647936F50":0:0:0
-ECP early return secp256r1 restart max_ops=1
+ECP early return mul secp256r1 restart max_ops=1
depends_on:MBEDTLS_ECP_DP_SECP256R1_ENABLED
ecp_test_vect_restart:MBEDTLS_ECP_DP_SECP256R1:"814264145F2F56F2E96A8E337A1284993FAF432A5ABCE59E867B7291D507A3AF":"2AF502F3BE8952F2C9B5A8D4160D09E97165BE50BC42AE4A5E8D3B4BA83AEB15":"EB0FAF4CA986C4D38681A0F9872D79D56795BD4BFF6E6DE3C0F5015ECE5EFD85":"2CE1788EC197E096DB95A200CC0AB26A19CE6BCCAD562B8EEE1B593761CF7F41":"DD0F5396219D1EA393310412D19A08F1F5811E9DC8EC8EEA7F80D21C820C2788":"0357DCCD4C804D0D8D33AA42B848834AA5605F9AB0D37239A115BBB647936F50":1:1:5000
-ECP early return secp256r1 restart max_ops=10000
+ECP early return mul secp256r1 restart max_ops=10000
depends_on:MBEDTLS_ECP_DP_SECP256R1_ENABLED
ecp_test_vect_restart:MBEDTLS_ECP_DP_SECP256R1:"814264145F2F56F2E96A8E337A1284993FAF432A5ABCE59E867B7291D507A3AF":"2AF502F3BE8952F2C9B5A8D4160D09E97165BE50BC42AE4A5E8D3B4BA83AEB15":"EB0FAF4CA986C4D38681A0F9872D79D56795BD4BFF6E6DE3C0F5015ECE5EFD85":"2CE1788EC197E096DB95A200CC0AB26A19CE6BCCAD562B8EEE1B593761CF7F41":"DD0F5396219D1EA393310412D19A08F1F5811E9DC8EC8EEA7F80D21C820C2788":"0357DCCD4C804D0D8D33AA42B848834AA5605F9AB0D37239A115BBB647936F50":10000:0:0
-ECP early return secp256r1 restart max_ops=250
+ECP early return mul secp256r1 restart max_ops=250
depends_on:MBEDTLS_ECP_DP_SECP256R1_ENABLED
ecp_test_vect_restart:MBEDTLS_ECP_DP_SECP256R1:"814264145F2F56F2E96A8E337A1284993FAF432A5ABCE59E867B7291D507A3AF":"2AF502F3BE8952F2C9B5A8D4160D09E97165BE50BC42AE4A5E8D3B4BA83AEB15":"EB0FAF4CA986C4D38681A0F9872D79D56795BD4BFF6E6DE3C0F5015ECE5EFD85":"2CE1788EC197E096DB95A200CC0AB26A19CE6BCCAD562B8EEE1B593761CF7F41":"DD0F5396219D1EA393310412D19A08F1F5811E9DC8EC8EEA7F80D21C820C2788":"0357DCCD4C804D0D8D33AA42B848834AA5605F9AB0D37239A115BBB647936F50":250:2:32
+
+ECP early return muladd secp256r1 restart disabled
+depends_on:MBEDTLS_ECP_DP_SECP256R1_ENABLED
+ecp_muladd_restart:MBEDTLS_ECP_DP_SECP256R1:"CB28E0999B9C7715FD0A80D8E47A77079716CBBF917DD72E97566EA1C066957C":"2B57C0235FB7489768D058FF4911C20FDBE71E3699D91339AFBB903EE17255DC":"C3875E57C85038A0D60370A87505200DC8317C8C534948BEA6559C7C18E6D4CE":"3B4E49C4FDBFC006FF993C81A50EAE221149076D6EC09DDD9FB3B787F85B6483":"2442A5CC0ECD015FA3CA31DC8E2BBC70BF42D60CBCA20085E0822CB04235E970":"6FC98BD7E50211A4A27102FA3549DF79EBCB4BF246B80945CDDFE7D509BBFD7D":0:0:0
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index 23905ce..659830e 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -145,6 +145,77 @@
}
/* END_CASE */
+/* BEGIN_CASE depends_on:MBEDTLS_ECP_EARLY_RETURN */
+void ecp_muladd_restart( int id, char *xR_str, char *yR_str,
+ char *u1_str, char *u2_str,
+ char *xQ_str, char *yQ_str,
+ int max_ops, int min_restarts, int max_restarts )
+{
+ /*
+ * Compute R = u1 * G + u2 * Q
+ * (test vectors mostly taken from ECDSA intermediate results)
+ *
+ * See comments at the top of ecp_test_vect_restart()
+ */
+ mbedtls_ecp_restart_ctx ctx;
+ mbedtls_ecp_group grp;
+ mbedtls_ecp_point R, Q;
+ mbedtls_mpi u1, u2, xR, yR;
+ int cnt_restarts;
+ int ret;
+
+ mbedtls_ecp_restart_init( &ctx );
+ mbedtls_ecp_group_init( &grp );
+ mbedtls_ecp_point_init( &R );
+ mbedtls_ecp_point_init( &Q );
+ mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );
+ mbedtls_mpi_init( &xR ); mbedtls_mpi_init( &yR );
+
+ TEST_ASSERT( mbedtls_ecp_group_load( &grp, id ) == 0 );
+
+ TEST_ASSERT( mbedtls_mpi_read_string( &u1, 16, u1_str ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_read_string( &u2, 16, u2_str ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_read_string( &xR, 16, xR_str ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_read_string( &yR, 16, yR_str ) == 0 );
+
+ TEST_ASSERT( mbedtls_mpi_read_string( &Q.X, 16, xQ_str ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_read_string( &Q.Y, 16, yQ_str ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_lset( &Q.Z, 1 ) == 0 );
+
+ mbedtls_ecp_set_max_ops( (unsigned) max_ops );
+
+ cnt_restarts = 0;
+ do {
+ ret = mbedtls_ecp_muladd_restartable( &grp, &R,
+ &u1, &grp.G, &u2, &Q, &ctx );
+ TEST_ASSERT( ret == 0 || ret == MBEDTLS_ERR_ECP_IN_PROGRESS );
+
+ if( ret == MBEDTLS_ERR_ECP_IN_PROGRESS )
+ cnt_restarts++;
+ }
+ while( ret != 0 );
+
+ TEST_ASSERT( mbedtls_mpi_cmp_mpi( &R.X, &xR ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_cmp_mpi( &R.Y, &yR ) == 0 );
+
+ TEST_ASSERT( cnt_restarts >= min_restarts );
+ TEST_ASSERT( cnt_restarts <= max_restarts );
+
+ /* Do we leak memory when aborting? */
+ ret = mbedtls_ecp_muladd_restartable( &grp, &R,
+ &u1, &grp.G, &u2, &Q, &ctx );
+ TEST_ASSERT( ret == 0 || ret == MBEDTLS_ERR_ECP_IN_PROGRESS );
+
+exit:
+ mbedtls_ecp_restart_free( &ctx );
+ mbedtls_ecp_group_free( &grp );
+ mbedtls_ecp_point_free( &R );
+ mbedtls_ecp_point_free( &Q );
+ mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );
+ mbedtls_mpi_free( &xR ); mbedtls_mpi_free( &yR );
+}
+/* END_CASE */
+
/* BEGIN_CASE */
void ecp_test_vect( int id, char *dA_str, char *xA_str, char *yA_str,
char *dB_str, char *xB_str, char *yB_str, char *xZ_str,