From: Joachim Vandersmissen <git@jvdsn.com>
To: linux-crypto@vger.kernel.org, Herbert Xu <herbert@gondor.apana.org.au>
Cc: Vitaly Chikunov <vt@altlinux.org>, Joachim Vandersmissen <git@jvdsn.com>
Subject: [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5
Date: Wed, 20 Mar 2024 00:13:38 -0500 [thread overview]
Message-ID: <20240320051558.62868-1-git@jvdsn.com> (raw)
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
next reply other threads:[~2024-03-20 5:16 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-20 5:13 Joachim Vandersmissen [this message]
2024-03-20 7:46 ` [PATCH] crypto: ecc - update ecc_gen_privkey for FIPS 186-5 Vitaly Chikunov
2024-03-21 3:33 ` Joachim Vandersmissen
2024-03-28 10:56 ` Herbert Xu
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240320051558.62868-1-git@jvdsn.com \
--to=git@jvdsn.com \
--cc=herbert@gondor.apana.org.au \
--cc=linux-crypto@vger.kernel.org \
--cc=vt@altlinux.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).