* [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5
@ 2024-03-20 5:13 Joachim Vandersmissen
2024-03-20 7:46 ` Vitaly Chikunov
2024-03-28 10:56 ` Herbert Xu
0 siblings, 2 replies; 4+ messages in thread
From: Joachim Vandersmissen @ 2024-03-20 5:13 UTC (permalink / raw
To: linux-crypto, Herbert Xu; +Cc: Vitaly Chikunov, Joachim Vandersmissen
FIPS 186-5 [1] was released approximately 1 year ago. The most
interesting change for ecc_gen_privkey is the removal of curves with
order < 224 bits. This is minimum is now checked in step 1. It is
unlikely that there is still any benefit in generating private keys for
curves with n < 224, as those curves provide less than 112 bits of
security strength and are therefore unsafe for any modern usage.
This patch also updates the documentation for __ecc_is_key_valid and
ecc_gen_privkey to clarify which FIPS 186-5 method is being used to
generate private keys. Previous documentation mentioned that "extra
random bits" was used. However, this did not match the code. Instead,
the code currently uses (and always has used) the "rejection sampling"
("testing candidates" in FIPS 186-4) method.
[1]: https://doi.org/10.6028/NIST.FIPS.186-5
Signed-off-by: Joachim Vandersmissen <git@jvdsn.com>
---
crypto/ecc.c | 29 +++++++++++++++++------------
1 file changed, 17 insertions(+), 12 deletions(-)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index f53fb4d6af99..3581027e9f92 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1416,6 +1416,12 @@ void ecc_point_mult_shamir(const struct ecc_point *result,
}
EXPORT_SYMBOL(ecc_point_mult_shamir);
+/*
+ * This function performs checks equivalent to Appendix A.4.2 of FIPS 186-5.
+ * Whereas A.4.2 results in an integer in the interval [1, n-1], this function
+ * ensures that the integer is in the range of [2, n-3]. We are slightly
+ * stricter because of the currently used scalar multiplication algorithm.
+ */
static int __ecc_is_key_valid(const struct ecc_curve *curve,
const u64 *private_key, unsigned int ndigits)
{
@@ -1455,16 +1461,11 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
EXPORT_SYMBOL(ecc_is_key_valid);
/*
- * ECC private keys are generated using the method of extra random bits,
- * equivalent to that described in FIPS 186-4, Appendix B.4.1.
- *
- * d = (c mod(n–1)) + 1 where c is a string of random bits, 64 bits longer
- * than requested
- * 0 <= c mod(n-1) <= n-2 and implies that
- * 1 <= d <= n-1
+ * ECC private keys are generated using the method of rejection sampling,
+ * equivalent to that described in FIPS 186-5, Appendix A.2.2.
*
* This method generates a private key uniformly distributed in the range
- * [1, n-1].
+ * [2, n-3].
*/
int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
{
@@ -1474,12 +1475,15 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
unsigned int nbits = vli_num_bits(curve->n, ndigits);
int err;
- /* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */
- if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
+ /*
+ * Step 1 & 2: check that N is included in Table 1 of FIPS 186-5,
+ * section 6.1.1.
+ */
+ if (nbits < 224 || ndigits > ARRAY_SIZE(priv))
return -EINVAL;
/*
- * FIPS 186-4 recommends that the private key should be obtained from a
+ * FIPS 186-5 recommends that the private key should be obtained from a
* RBG with a security strength equal to or greater than the security
* strength associated with N.
*
@@ -1492,12 +1496,13 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
if (crypto_get_default_rng())
return -EFAULT;
+ /* Step 3: obtain N returned_bits from the DRBG. */
err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes);
crypto_put_default_rng();
if (err)
return err;
- /* Make sure the private key is in the valid range. */
+ /* Step 4: make sure the private key is in the valid range. */
if (__ecc_is_key_valid(curve, priv, ndigits))
return -EINVAL;
--
2.44.0
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5
2024-03-20 5:13 [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5 Joachim Vandersmissen
@ 2024-03-20 7:46 ` Vitaly Chikunov
2024-03-21 3:33 ` Joachim Vandersmissen
2024-03-28 10:56 ` Herbert Xu
1 sibling, 1 reply; 4+ messages in thread
From: Vitaly Chikunov @ 2024-03-20 7:46 UTC (permalink / raw
To: Joachim Vandersmissen; +Cc: linux-crypto, Herbert Xu
Joachim,
On Wed, Mar 20, 2024 at 12:13:38AM -0500, Joachim Vandersmissen wrote:
> FIPS 186-5 [1] was released approximately 1 year ago. The most
> interesting change for ecc_gen_privkey is the removal of curves with
> order < 224 bits. This is minimum is now checked in step 1. It is
> unlikely that there is still any benefit in generating private keys for
> curves with n < 224, as those curves provide less than 112 bits of
> security strength and are therefore unsafe for any modern usage.
>
> This patch also updates the documentation for __ecc_is_key_valid and
> ecc_gen_privkey to clarify which FIPS 186-5 method is being used to
> generate private keys. Previous documentation mentioned that "extra
> random bits" was used. However, this did not match the code. Instead,
> the code currently uses (and always has used) the "rejection sampling"
> ("testing candidates" in FIPS 186-4) method.
>
> [1]: https://doi.org/10.6028/NIST.FIPS.186-5
>
> Signed-off-by: Joachim Vandersmissen <git@jvdsn.com>
> ---
> crypto/ecc.c | 29 +++++++++++++++++------------
> 1 file changed, 17 insertions(+), 12 deletions(-)
>
> diff --git a/crypto/ecc.c b/crypto/ecc.c
> index f53fb4d6af99..3581027e9f92 100644
> --- a/crypto/ecc.c
> +++ b/crypto/ecc.c
> @@ -1416,6 +1416,12 @@ void ecc_point_mult_shamir(const struct ecc_point *result,
> }
> EXPORT_SYMBOL(ecc_point_mult_shamir);
>
> +/*
> + * This function performs checks equivalent to Appendix A.4.2 of FIPS 186-5.
> + * Whereas A.4.2 results in an integer in the interval [1, n-1], this function
> + * ensures that the integer is in the range of [2, n-3]. We are slightly
> + * stricter because of the currently used scalar multiplication algorithm.
> + */
> static int __ecc_is_key_valid(const struct ecc_curve *curve,
> const u64 *private_key, unsigned int ndigits)
> {
> @@ -1455,16 +1461,11 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
> EXPORT_SYMBOL(ecc_is_key_valid);
>
> /*
> - * ECC private keys are generated using the method of extra random bits,
> - * equivalent to that described in FIPS 186-4, Appendix B.4.1.
> - *
> - * d = (c mod(n–1)) + 1 where c is a string of random bits, 64 bits longer
> - * than requested
> - * 0 <= c mod(n-1) <= n-2 and implies that
> - * 1 <= d <= n-1
Looks like method of extra random bits was never used.
But I am not sure that reference to FIPS 186-5 is correct since it's
about DSS while this function is only used for ECDH, which is perhaps
regulated by NIST SP 800-186 and 800-56A. Still, 3.1.2 of 800-186
suggests that for 'EC key establishment' listed curves with bit lengths
from 224 are allowed to be used.
Thanks,
> + * ECC private keys are generated using the method of rejection sampling,
> + * equivalent to that described in FIPS 186-5, Appendix A.2.2.
> *
> * This method generates a private key uniformly distributed in the range
> - * [1, n-1].
> + * [2, n-3].
> */
> int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
> {
> @@ -1474,12 +1475,15 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
> unsigned int nbits = vli_num_bits(curve->n, ndigits);
> int err;
>
> - /* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */
> - if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
> + /*
> + * Step 1 & 2: check that N is included in Table 1 of FIPS 186-5,
> + * section 6.1.1.
> + */
> + if (nbits < 224 || ndigits > ARRAY_SIZE(priv))
> return -EINVAL;
>
> /*
> - * FIPS 186-4 recommends that the private key should be obtained from a
> + * FIPS 186-5 recommends that the private key should be obtained from a
> * RBG with a security strength equal to or greater than the security
> * strength associated with N.
> *
> @@ -1492,12 +1496,13 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
> if (crypto_get_default_rng())
> return -EFAULT;
>
> + /* Step 3: obtain N returned_bits from the DRBG. */
> err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes);
> crypto_put_default_rng();
> if (err)
> return err;
>
> - /* Make sure the private key is in the valid range. */
> + /* Step 4: make sure the private key is in the valid range. */
> if (__ecc_is_key_valid(curve, priv, ndigits))
> return -EINVAL;
>
> --
> 2.44.0
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5
2024-03-20 7:46 ` Vitaly Chikunov
@ 2024-03-21 3:33 ` Joachim Vandersmissen
0 siblings, 0 replies; 4+ messages in thread
From: Joachim Vandersmissen @ 2024-03-21 3:33 UTC (permalink / raw
To: Vitaly Chikunov; +Cc: linux-crypto, Herbert Xu
Hi Vitaly,
On 3/20/24 02:46, Vitaly Chikunov wrote:
> Joachim,
>
> On Wed, Mar 20, 2024 at 12:13:38AM -0500, Joachim Vandersmissen wrote:
>> FIPS 186-5 [1] was released approximately 1 year ago. The most
>> interesting change for ecc_gen_privkey is the removal of curves with
>> order < 224 bits. This is minimum is now checked in step 1. It is
>> unlikely that there is still any benefit in generating private keys for
>> curves with n < 224, as those curves provide less than 112 bits of
>> security strength and are therefore unsafe for any modern usage.
>>
>> This patch also updates the documentation for __ecc_is_key_valid and
>> ecc_gen_privkey to clarify which FIPS 186-5 method is being used to
>> generate private keys. Previous documentation mentioned that "extra
>> random bits" was used. However, this did not match the code. Instead,
>> the code currently uses (and always has used) the "rejection sampling"
>> ("testing candidates" in FIPS 186-4) method.
>>
>> [1]: https://doi.org/10.6028/NIST.FIPS.186-5
>>
>> Signed-off-by: Joachim Vandersmissen <git@jvdsn.com>
>> ---
>> crypto/ecc.c | 29 +++++++++++++++++------------
>> 1 file changed, 17 insertions(+), 12 deletions(-)
>>
>> diff --git a/crypto/ecc.c b/crypto/ecc.c
>> index f53fb4d6af99..3581027e9f92 100644
>> --- a/crypto/ecc.c
>> +++ b/crypto/ecc.c
>> @@ -1416,6 +1416,12 @@ void ecc_point_mult_shamir(const struct ecc_point *result,
>> }
>> EXPORT_SYMBOL(ecc_point_mult_shamir);
>>
>> +/*
>> + * This function performs checks equivalent to Appendix A.4.2 of FIPS 186-5.
>> + * Whereas A.4.2 results in an integer in the interval [1, n-1], this function
>> + * ensures that the integer is in the range of [2, n-3]. We are slightly
>> + * stricter because of the currently used scalar multiplication algorithm.
>> + */
>> static int __ecc_is_key_valid(const struct ecc_curve *curve,
>> const u64 *private_key, unsigned int ndigits)
>> {
>> @@ -1455,16 +1461,11 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
>> EXPORT_SYMBOL(ecc_is_key_valid);
>>
>> /*
>> - * ECC private keys are generated using the method of extra random bits,
>> - * equivalent to that described in FIPS 186-4, Appendix B.4.1.
>> - *
>> - * d = (c mod(n–1)) + 1 where c is a string of random bits, 64 bits longer
>> - * than requested
>> - * 0 <= c mod(n-1) <= n-2 and implies that
>> - * 1 <= d <= n-1
> Looks like method of extra random bits was never used.
>
> But I am not sure that reference to FIPS 186-5 is correct since it's
> about DSS while this function is only used for ECDH, which is perhaps
> regulated by NIST SP 800-186 and 800-56A. Still, 3.1.2 of 800-186
> suggests that for 'EC key establishment' listed curves with bit lengths
> from 224 are allowed to be used.
Thanks for your review. To me it seems like ecc_gen_privkey is
externally accessible, and could therefore be considered a
general-purpose function. However, you are right that it is currently
only used in the kernel for ECDH key pair generation, which falls under
SP 800-56Ar3. Perhaps that would be a more suitable reference, but I did
not want to make any drastic changes to the documentation.
Moreover, the procedure described in SP 800-56Ar3 (Section 5.6.1.2.2) is
functionally equivalent to the procedure from FIPS 186-5. This is also
supported by the fact that NIST's Cryptographic Algorithm Validation
Program (CAVP) does not have a separate test for EC key pair generation
from SP 800-56Ar3. Instead, the test for ECDSA key pair generation is
re-used (see e.g.
https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/details?validation=36423).
In any case, compliance with FIPS 186-5 or SP 800-56Ar3 would require n
>= 224, as you pointed out.
>
> Thanks,
>
>
>> + * ECC private keys are generated using the method of rejection sampling,
>> + * equivalent to that described in FIPS 186-5, Appendix A.2.2.
>> *
>> * This method generates a private key uniformly distributed in the range
>> - * [1, n-1].
>> + * [2, n-3].
>> */
>> int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
>> {
>> @@ -1474,12 +1475,15 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
>> unsigned int nbits = vli_num_bits(curve->n, ndigits);
>> int err;
>>
>> - /* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */
>> - if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
>> + /*
>> + * Step 1 & 2: check that N is included in Table 1 of FIPS 186-5,
>> + * section 6.1.1.
>> + */
>> + if (nbits < 224 || ndigits > ARRAY_SIZE(priv))
>> return -EINVAL;
>>
>> /*
>> - * FIPS 186-4 recommends that the private key should be obtained from a
>> + * FIPS 186-5 recommends that the private key should be obtained from a
>> * RBG with a security strength equal to or greater than the security
>> * strength associated with N.
>> *
>> @@ -1492,12 +1496,13 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
>> if (crypto_get_default_rng())
>> return -EFAULT;
>>
>> + /* Step 3: obtain N returned_bits from the DRBG. */
>> err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes);
>> crypto_put_default_rng();
>> if (err)
>> return err;
>>
>> - /* Make sure the private key is in the valid range. */
>> + /* Step 4: make sure the private key is in the valid range. */
>> if (__ecc_is_key_valid(curve, priv, ndigits))
>> return -EINVAL;
>>
>> --
>> 2.44.0
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5
2024-03-20 5:13 [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5 Joachim Vandersmissen
2024-03-20 7:46 ` Vitaly Chikunov
@ 2024-03-28 10:56 ` Herbert Xu
1 sibling, 0 replies; 4+ messages in thread
From: Herbert Xu @ 2024-03-28 10:56 UTC (permalink / raw
To: Joachim Vandersmissen; +Cc: linux-crypto, Vitaly Chikunov
On Wed, Mar 20, 2024 at 12:13:38AM -0500, Joachim Vandersmissen wrote:
> FIPS 186-5 [1] was released approximately 1 year ago. The most
> interesting change for ecc_gen_privkey is the removal of curves with
> order < 224 bits. This is minimum is now checked in step 1. It is
> unlikely that there is still any benefit in generating private keys for
> curves with n < 224, as those curves provide less than 112 bits of
> security strength and are therefore unsafe for any modern usage.
>
> This patch also updates the documentation for __ecc_is_key_valid and
> ecc_gen_privkey to clarify which FIPS 186-5 method is being used to
> generate private keys. Previous documentation mentioned that "extra
> random bits" was used. However, this did not match the code. Instead,
> the code currently uses (and always has used) the "rejection sampling"
> ("testing candidates" in FIPS 186-4) method.
>
> [1]: https://doi.org/10.6028/NIST.FIPS.186-5
>
> Signed-off-by: Joachim Vandersmissen <git@jvdsn.com>
> ---
> crypto/ecc.c | 29 +++++++++++++++++------------
> 1 file changed, 17 insertions(+), 12 deletions(-)
Patch applied. Thanks.
--
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2024-03-28 10:55 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-03-20 5:13 [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5 Joachim Vandersmissen
2024-03-20 7:46 ` Vitaly Chikunov
2024-03-21 3:33 ` Joachim Vandersmissen
2024-03-28 10:56 ` Herbert Xu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).