Bignum: Deprecate mbedtls_mpi_is_prime()
When using a primality testing function the tolerable error rate depends
on the scheme in question, the required security strength and wether it
is used for key generation or parameter validation. To support all use
cases we need more flexibility than what the old API provides.
diff --git a/include/mbedtls/bignum.h b/include/mbedtls/bignum.h
index 0ee32dd..40cfab4 100644
--- a/include/mbedtls/bignum.h
+++ b/include/mbedtls/bignum.h
@@ -725,10 +725,19 @@
*/
int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N );
+#if !defined(MBEDTLS_DEPRECATED_REMOVED)
+#if defined(MBEDTLS_DEPRECATED_WARNING)
+#define MBEDTLS_DEPRECATED __attribute__((deprecated))
+#else
+#define MBEDTLS_DEPRECATED
+#endif
/**
* \brief Miller-Rabin primality test with error probability of
* 2<sup>-80</sup>
*
+ * \deprecated Superseded by mbedtls_mpi_is_prime_ext() which allows
+ * specifying the number of Miller-Rabin rounds.
+ *
* \param X MPI to check
* \param f_rng RNG function
* \param p_rng RNG parameter
@@ -737,11 +746,39 @@
* MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
* MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime
*/
-int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng );
+MBEDTLS_DEPRECATED int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng );
+#undef MBEDTLS_DEPRECATED
+#endif /* !MBEDTLS_DEPRECATED_REMOVED */
/**
+ * \brief Miller-Rabin primality test.
+ *
+ * \warning If \p X is potentially generated by an adversary, for example
+ * when validating cryptographic parameters that you didn't
+ * generate yourself and that are supposed to be prime, then
+ * \p rounds should be at least the half of the security
+ * strength of the cryptographic algorithm. On the other hand,
+ * if \p X is chosen uniformly or non-adversially (as is the
+ * case when mbedtls_mpi_gen_prime calls this function), then
+ * \p rounds can be much lower.
+ *
+ * \param X MPI to check
+ * \param rounds Number of bases to perform Miller-Rabin primality test for.
+ * The probability of returning 0 on a composite is at most
+ * 2<sup>-2*\p rounds</sup>.
+ * \param f_rng RNG function
+ * \param p_rng RNG parameter
+ *
+ * \return 0 if successful (probably prime),
+ * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
+ * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime
+ */
+int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng );
+/**
* \brief Flags for mbedtls_mpi_gen_prime()
*
* Each of these flags is a constraint on the result X returned by
diff --git a/library/bignum.c b/library/bignum.c
index 6d166c6..9dc4e4d 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -2145,9 +2145,9 @@
/*
* Pseudo-primality test: small factors, then Miller-Rabin
*/
-int mpi_is_prime_internal( const mbedtls_mpi *X, int rounds,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng )
+int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
{
int ret;
mbedtls_mpi XX;
@@ -2174,6 +2174,7 @@
return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
}
+#if !defined(MBEDTLS_DEPRECATED_REMOVED)
/*
* Pseudo-primality test, error probability 2^-80
*/
@@ -2181,8 +2182,14 @@
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
- return mpi_is_prime_internal( X, 40, f_rng, p_rng );
+ /*
+ * In the past our key generation aimed for an error rate of at most
+ * 2^-80. Since this function is deprecated, aim for the same certainty
+ * here as well.
+ */
+ return mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng );
}
+#endif
/*
* Prime number generation
@@ -2248,7 +2255,7 @@
if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
{
- ret = mpi_is_prime_internal( X, rounds, f_rng, p_rng );
+ ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
goto cleanup;
diff --git a/library/rsa_internal.c b/library/rsa_internal.c
index 507009f..9a42d47 100644
--- a/library/rsa_internal.c
+++ b/library/rsa_internal.c
@@ -351,15 +351,20 @@
*/
#if defined(MBEDTLS_GENPRIME)
+ /*
+ * When generating keys, the strongest security we support aims for an error
+ * rate of at most 2^-100 and we are aiming for the same certainty here as
+ * well.
+ */
if( f_rng != NULL && P != NULL &&
- ( ret = mbedtls_mpi_is_prime( P, f_rng, p_rng ) ) != 0 )
+ ( ret = mbedtls_mpi_is_prime_ext( P, 50, f_rng, p_rng ) ) != 0 )
{
ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
goto cleanup;
}
if( f_rng != NULL && Q != NULL &&
- ( ret = mbedtls_mpi_is_prime( Q, f_rng, p_rng ) ) != 0 )
+ ( ret = mbedtls_mpi_is_prime_ext( Q, 50, f_rng, p_rng ) ) != 0 )
{
ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
goto cleanup;
diff --git a/programs/pkey/dh_genprime.c b/programs/pkey/dh_genprime.c
index dbe9153..360e355 100644
--- a/programs/pkey/dh_genprime.c
+++ b/programs/pkey/dh_genprime.c
@@ -156,7 +156,7 @@
goto exit;
}
- if( ( ret = mbedtls_mpi_is_prime( &Q, mbedtls_ctr_drbg_random, &ctr_drbg ) ) != 0 )
+ if( ( ret = mbedtls_mpi_is_prime_ext( &Q, 50, mbedtls_ctr_drbg_random, &ctr_drbg ) ) != 0 )
{
mbedtls_printf( " failed\n ! mbedtls_mpi_is_prime returned %d\n\n", ret );
goto exit;
diff --git a/tests/suites/test_suite_mpi.data b/tests/suites/test_suite_mpi.data
index b046be7..b8b7b9e 100644
--- a/tests/suites/test_suite_mpi.data
+++ b/tests/suites/test_suite_mpi.data
@@ -682,11 +682,11 @@
Test mbedtls_mpi_is_prime_det (4 non-witnesses)
depends_on:MBEDTLS_GENPRIME
-mbedtls_mpi_is_prime_det:"043BD64BA10B11DA83FBD296B04BCA9E0552FAF6E09CAC74E2D7E735ED0DB09FC47ED76145644203EE0C826013BC602F560BCDAAED557D04683859A65D659FF828A245A2C5B1AC41E01E4669A525A45E23AF":"040EA852F7935ACCECC0E87B845281F047D10DC9AAFEF990AF9D3D66770DA30B0C5B5E03EEA8C0CB79B936FE0BB8EE5389EC1D34EB16C58AA3F2E11AF084160CDF6400BE1CC179867AB074866952D9F34EE7042D27F960E715A97FCB93F3182247D0A6AE51BD21CC2F6B0651F9E572C5FB86F3137053FA85FD7A51816D69B3A53A5A438C17754836D04E98CA240B901F828332F2D72D88C497DA45F533F99A6E53EDEA6B0424EC8951B048FA9A80134B37D0A67014597934E3CFC52C5A4DD4751ADF8D66FC79E84E2A3148C4B15C17E12CB659390FD275F39A331FFC80EC699BC3F6FAB868E30E9B14575FCDAB6FAED01E00112DD28704177E09C335AD43A696FEA761E8DF3B0663277A5C3637F9060CB5E5654F72E9A6B0F369E660AD4CF7ABF4195493545B367BD55271CD4BB7D9C15D3F508FE8F7409C2126FC8E73B43A67CD4EFB21E9F15DBF040A2A8D5F5ED75CEAC12B595C0051F3EC9D5A58ACE82A9506E64F780E9836728260FFE1BFD73E8A9869E3D46A35A856D3028F7FEAB9F4F1A04449AEDC80017EE1014080D87F0B50C8EF255324CD89F7D039":82:MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
+mbedtls_mpi_is_prime_det:"043BD64BA10B11DA83FBD296B04BCA9E0552FAF6E09CAC74E2D7E735ED0DB09FC47ED76145644203EE0C826013BC602F560BCDAAED557D04683859A65D659FF828A245A2C5B1AC41E01E4669A525A45E23AF":"040EA852F7935ACCECC0E87B845281F047D10DC9AAFEF990AF9D3D66770DA30B0C5B5E03EEA8C0CB79B936FE0BB8EE5389EC1D34EB16C58AA3F2E11AF084160CDF6400BE1CC179867AB074866952D9F34EE7042D27F960E715A97FCB93F3182247D0A6AE51BD21CC2F6B0651F9E572C5FB86F3137053FA85FD7A51816D69B3A53A5A438C17754836D04E98CA240B901F828332F2D72D88C497DA45F533F99A6E53EDEA6B0424EC8951B048FA9A80134B37D0A67014597934E3CFC52C5A4DD4751ADF8D66FC79E84E2A3148C4B15C17E12CB659390FD275F39A331FFC80EC699BC3F6FAB868E30E9B14575FCDAB6FAED01E00112DD28704177E09C335AD43A696FEA761E8DF3B0663277A5C3637F9060CB5E5654F72E9A6B0F369E660AD4CF7ABF4195493545B367BD55271CD4BB7D9C15D3F508FE8F7409C2126FC8E73B43A67CD4EFB21E9F15DBF040A2A8D5F5ED75CEAC12B595C0051F3EC9D5A58ACE82A9506E64F780E9836728260FFE1BFD73E8A9869E3D46A35A856D3028F7FEAB9F4F1A04449AEDC80017EE1014080D87F0B50C8EF255324CD89F7D039":82:5:MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
Test mbedtls_mpi_is_prime_det (39 non-witnesses)
depends_on:MBEDTLS_GENPRIME
-mbedtls_mpi_is_prime_det:"155102B67930FBE8858DF6C0642D77D419A7B7968E622CC7500F3E3F2C5168368C50E0083187":"119B3E2C721834D83416239B04447AA18AE0163E61DCAE97054563D79E094A6FA4485BD6A0501445BF57FE9C058926CDB862E04CC1A95D79D61D9AB3466857A53E04F8D7470C9C86649B226A13DDC534E18DFD5C22FAEA317CA4D4960F18457FD6D2FFB5F3273F74C89980DC774590D8D30D1159CA81999ED94A042D67DA68C82616AD46C2C88288A8EBD0B37AC7C152D9522CA4544642AD1210F6B642FEBF43563FA872B0DEFAFC69D0B6570E8FEA9570D0AADCFA9B06CC8BFD62CEDC221541210EEEF9762448C6D49F26AA767A4D66CB168589E0201923015314E6CD4A480E5936E7CF145F73A564C5B782635B3AFC3028E2632C5D3458224A7C9E8BA1876E8F690463C878292D3DC011E9640331E7F7621F2B5E0F6713DD8C9D6767521C4BA880DA8D11C67753C8493D2C4C4F1443147550D0B25B7FAD04EAFA9F8AA60974C1365C8A794CFEECEB4279B1150909A97E5A7A10B5D91186CA5B25A612036631FE73529C8CFAE51E76FB704A772DE5320EFC1212E7A399B1FEBF57D014AF9129DFF5D2C5DFBBEEAC55F360CF6D22FA90B8E2E9AD0C71AB6495A9452A58D653B8CC26128C66B43EFBA6E39AEC5717A1A3C2AE1449FCABAFE1180B159DA55190CD81A3D9E8D798647E11B827F0A057D6DA5AAD78AB5112EE65E10E8B8B369BA24E1B8AD2CD8548C497016C07A143DE1232F8059BE303572456FA92E76A0F23D1340629228B7D27C02D3833A72745B91A3DBEB5E081117A9F19597F00E4277B414FAEA8C8CEB895C37F956A5A22F8D7A10ADA50B22BAB312504904511AA0EFDD4D3BF20ECB17E8A684564FFB5BBD5E22C429F9A75A4FB4AE468FE7612ED53C7A11212E7EF3435CC9CA6E7DB167B8CCE2BECF35F89013F8F876223C77FA81570970858663C6E32B91080AA47F9C90177F51E6FD7747B910C9489C7B6ACB070996198AD9A40A69711274159210A9A12DBAAA4FB4632446066AB70D735DC95F7C2BCE517E88C064D728DE82B1B043DF4AEE0EFF5131120A4E5B9B4180EB6F6B8A0D1491ABDA069058A9966B1A517D8E7B4997DC52A1E698FD79E271153DF1913FE6787A5D99DE69F39C3F22D26DC731CFBB33FF5C267D85D7A3DAE8E1C87E1DB2F1236212EF1942EA756967FB3D07D629E59EA4034D9A9B5E270DD4A31C8A3DFDA99C1094B5537132C196DA2AEAF5253A019B9AF25B5DCB0D4DD75C7C9C353DA9DAABFB23959A5455312E7E1C21268C1BC14E83DCFDF50C27FD3E8B4EDC04C5F3CB5FCFFF2B57151E1B1EE1A6456DC006BC43E1158674AA4CF7D146DE4A57103BE43ED130C8007294ED2418C7A2B769A7D20EBB5A8367A77B313F81BB119B9954305FF160FF83EED7F808EE6D340A5CCC000CF81AA497D315D350CCE4E86A31456B8AA85B677491FC662933DFA55EB5BFF64B8D85430D676A85D1CAFAFF383E68C4E6C22A51063739EC03FC58C36C07C44E54828BE2152B2E9AFB0F179B157D09B64C147B524BB5424BB1914419424D9100D06EDCFC718F4DF3D562E9E16C446663F35273CA7BC5426B868A80C8D415C9A12A1619CDB7CDB5BEBC70313150BDF8C3AB26B809FE62D28E798EF1EF98C410A2DA0A9071F82154AC569078B0E647E2C085D1D907E634453442803D0492D3D0C78CACB762020C0E589C8B0981321EA2771305FD0413F3B2963FCE9A232F6641DB7E12ADC009A032063C41756E5E19E5711DE12711F07AFE7545B4D83F3EFD7BFD0435297C89DF3D4AF96EBE2CE8D64B93E36EA5D7E5A0492151D0CAEE7449A7D35E1A3C83E22C3B35162C073CC3B1CF76FBDEE84270721FC042EAAEB7325110181415E2031CFB7462F15111291CDAC0560FF9F4C7341F2FA261B97CEF348D074AA2EB4DB153FE6B1410519DA4213B611999868F3B867A2B6D758D333C4989DE80782683CA26ECDE373C71524F01B76349CE8A07A5EBECBB42259CF970DDA756EC996B189FEA045FEE45F23D476960913106ECA2510B8517AA75D56FA4152B2BDDC212014E5D07FD964D6EE532F0616DF74E104659955132331FABF2D2AD265E71C93C648A956FA0A3DB21FF103D516527F2DA0E870340B61EE8A8ED913B60605EB5A67B834D0FC90564386012585609870FEF6530B3E3C037B55506F0B5694F6B0FC":38:MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
+mbedtls_mpi_is_prime_det:"155102B67930FBE8858DF6C0642D77D419A7B7968E622CC7500F3E3F2C5168368C50E0083187":"119B3E2C721834D83416239B04447AA18AE0163E61DCAE97054563D79E094A6FA4485BD6A0501445BF57FE9C058926CDB862E04CC1A95D79D61D9AB3466857A53E04F8D7470C9C86649B226A13DDC534E18DFD5C22FAEA317CA4D4960F18457FD6D2FFB5F3273F74C89980DC774590D8D30D1159CA81999ED94A042D67DA68C82616AD46C2C88288A8EBD0B37AC7C152D9522CA4544642AD1210F6B642FEBF43563FA872B0DEFAFC69D0B6570E8FEA9570D0AADCFA9B06CC8BFD62CEDC221541210EEEF9762448C6D49F26AA767A4D66CB168589E0201923015314E6CD4A480E5936E7CF145F73A564C5B782635B3AFC3028E2632C5D3458224A7C9E8BA1876E8F690463C878292D3DC011E9640331E7F7621F2B5E0F6713DD8C9D6767521C4BA880DA8D11C67753C8493D2C4C4F1443147550D0B25B7FAD04EAFA9F8AA60974C1365C8A794CFEECEB4279B1150909A97E5A7A10B5D91186CA5B25A612036631FE73529C8CFAE51E76FB704A772DE5320EFC1212E7A399B1FEBF57D014AF9129DFF5D2C5DFBBEEAC55F360CF6D22FA90B8E2E9AD0C71AB6495A9452A58D653B8CC26128C66B43EFBA6E39AEC5717A1A3C2AE1449FCABAFE1180B159DA55190CD81A3D9E8D798647E11B827F0A057D6DA5AAD78AB5112EE65E10E8B8B369BA24E1B8AD2CD8548C497016C07A143DE1232F8059BE303572456FA92E76A0F23D1340629228B7D27C02D3833A72745B91A3DBEB5E081117A9F19597F00E4277B414FAEA8C8CEB895C37F956A5A22F8D7A10ADA50B22BAB312504904511AA0EFDD4D3BF20ECB17E8A684564FFB5BBD5E22C429F9A75A4FB4AE468FE7612ED53C7A11212E7EF3435CC9CA6E7DB167B8CCE2BECF35F89013F8F876223C77FA81570970858663C6E32B91080AA47F9C90177F51E6FD7747B910C9489C7B6ACB070996198AD9A40A69711274159210A9A12DBAAA4FB4632446066AB70D735DC95F7C2BCE517E88C064D728DE82B1B043DF4AEE0EFF5131120A4E5B9B4180EB6F6B8A0D1491ABDA069058A9966B1A517D8E7B4997DC52A1E698FD79E271153DF1913FE6787A5D99DE69F39C3F22D26DC731CFBB33FF5C267D85D7A3DAE8E1C87E1DB2F1236212EF1942EA756967FB3D07D629E59EA4034D9A9B5E270DD4A31C8A3DFDA99C1094B5537132C196DA2AEAF5253A019B9AF25B5DCB0D4DD75C7C9C353DA9DAABFB23959A5455312E7E1C21268C1BC14E83DCFDF50C27FD3E8B4EDC04C5F3CB5FCFFF2B57151E1B1EE1A6456DC006BC43E1158674AA4CF7D146DE4A57103BE43ED130C8007294ED2418C7A2B769A7D20EBB5A8367A77B313F81BB119B9954305FF160FF83EED7F808EE6D340A5CCC000CF81AA497D315D350CCE4E86A31456B8AA85B677491FC662933DFA55EB5BFF64B8D85430D676A85D1CAFAFF383E68C4E6C22A51063739EC03FC58C36C07C44E54828BE2152B2E9AFB0F179B157D09B64C147B524BB5424BB1914419424D9100D06EDCFC718F4DF3D562E9E16C446663F35273CA7BC5426B868A80C8D415C9A12A1619CDB7CDB5BEBC70313150BDF8C3AB26B809FE62D28E798EF1EF98C410A2DA0A9071F82154AC569078B0E647E2C085D1D907E634453442803D0492D3D0C78CACB762020C0E589C8B0981321EA2771305FD0413F3B2963FCE9A232F6641DB7E12ADC009A032063C41756E5E19E5711DE12711F07AFE7545B4D83F3EFD7BFD0435297C89DF3D4AF96EBE2CE8D64B93E36EA5D7E5A0492151D0CAEE7449A7D35E1A3C83E22C3B35162C073CC3B1CF76FBDEE84270721FC042EAAEB7325110181415E2031CFB7462F15111291CDAC0560FF9F4C7341F2FA261B97CEF348D074AA2EB4DB153FE6B1410519DA4213B611999868F3B867A2B6D758D333C4989DE80782683CA26ECDE373C71524F01B76349CE8A07A5EBECBB42259CF970DDA756EC996B189FEA045FEE45F23D476960913106ECA2510B8517AA75D56FA4152B2BDDC212014E5D07FD964D6EE532F0616DF74E104659955132331FABF2D2AD265E71C93C648A956FA0A3DB21FF103D516527F2DA0E870340B61EE8A8ED913B60605EB5A67B834D0FC90564386012585609870FEF6530B3E3C037B55506F0B5694F6B0FC":38:40:MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
Test mbedtls_mpi_gen_prime (Too small)
depends_on:MBEDTLS_GENPRIME
diff --git a/tests/suites/test_suite_mpi.function b/tests/suites/test_suite_mpi.function
index c6548b1..95fe99c 100644
--- a/tests/suites/test_suite_mpi.function
+++ b/tests/suites/test_suite_mpi.function
@@ -843,7 +843,7 @@
mbedtls_mpi_init( &X );
TEST_ASSERT( mbedtls_mpi_read_string( &X, radix_X, input_X ) == 0 );
- res = mbedtls_mpi_is_prime( &X, rnd_std_rand, NULL );
+ res = mbedtls_mpi_is_prime_ext( &X, 40, rnd_std_rand, NULL );
TEST_ASSERT( res == div_result );
exit:
@@ -853,7 +853,7 @@
/* BEGIN_CASE depends_on:MBEDTLS_GENPRIME */
void mbedtls_mpi_is_prime_det( data_t * input_X, data_t * witnesses,
- int chunk_len, int div_result )
+ int chunk_len, int rounds, int div_result )
{
mbedtls_mpi X;
int res;
@@ -865,7 +865,8 @@
rand.chunk_len = chunk_len;
TEST_ASSERT( mbedtls_mpi_read_binary( &X, input_X->x, input_X->len ) == 0 );
- res = mbedtls_mpi_is_prime( &X, mbedtls_test_mpi_miller_rabin_determinizer,
+ res = mbedtls_mpi_is_prime_ext( &X, rounds,
+ mbedtls_test_mpi_miller_rabin_determinizer,
&rand );
TEST_ASSERT( res == div_result );
@@ -892,12 +893,14 @@
TEST_ASSERT( actual_bits >= (size_t) bits );
TEST_ASSERT( actual_bits <= (size_t) bits + 1 );
- TEST_ASSERT( mbedtls_mpi_is_prime( &X, rnd_std_rand, NULL ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_is_prime_ext( &X, 40, rnd_std_rand, NULL )
+ == 0 );
if( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH )
{
/* X = ( X - 1 ) / 2 */
TEST_ASSERT( mbedtls_mpi_shift_r( &X, 1 ) == 0 );
- TEST_ASSERT( mbedtls_mpi_is_prime( &X, rnd_std_rand, NULL ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_is_prime_ext( &X, 40, rnd_std_rand, NULL )
+ == 0 );
}
}