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 <[email protected]>
>> ---
>> 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