Re: [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5

[Joachim Vandersmissen <git@jvdsn.com>]

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