From 7156543c59626a6be2cfd51be32491f24ef46afc Mon Sep 17 00:00:00 2001 From: Joachim Vandersmissen Date: Wed, 20 Mar 2024 00:13:38 -0500 Subject: crypto: ecc - update ecc_gen_privkey for FIPS 186-5 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 Signed-off-by: Herbert Xu --- crypto/ecc.c | 29 +++++++++++++++++------------ 1 file changed, 17 insertions(+), 12 deletions(-) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index f53fb4d6..3581027e 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; -- cgit v1.2.3 From 322035a7beec0f4e578e98c24d8925ac816f2b92 Mon Sep 17 00:00:00 2001 From: Roman Smirnov Date: Mon, 1 Apr 2024 15:16:23 +0300 Subject: crypto: ecc - remove checks in crypto_ecdh_shared_secret() and ecc_make_pub_key() With the current state of the code, ecc_get_curve() cannot return NULL in crypto_ecdh_shared_secret() and ecc_make_pub_key(). This is conditioned by the fact that they are only called from ecdh_compute_value(), which implements the kpp_alg::{generate_public_key,compute_shared_secret}() methods. Also ecdh implements the kpp_alg::init() method, which is called before the other methods and sets ecdh_ctx::curve_id to a valid value. Signed-off-by: Roman Smirnov Reviewed-by: Sergey Shtylyov Signed-off-by: Herbert Xu --- crypto/ecc.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index 3581027e..7c960e0d 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -1520,7 +1520,7 @@ int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits, u64 priv[ECC_MAX_DIGITS]; const struct ecc_curve *curve = ecc_get_curve(curve_id); - if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) { + if (!private_key || ndigits > ARRAY_SIZE(priv)) { ret = -EINVAL; goto out; } @@ -1622,7 +1622,7 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, unsigned int nbytes; const struct ecc_curve *curve = ecc_get_curve(curve_id); - if (!private_key || !public_key || !curve || + if (!private_key || !public_key || ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) { ret = -EINVAL; goto out; -- cgit v1.2.3 From 1d71b9824ec28c0f521f4092d7875464328b0722 Mon Sep 17 00:00:00 2001 From: Stefan Berger Date: Thu, 4 Apr 2024 10:18:44 -0400 Subject: crypto: ecc - Use ECC_CURVE_NIST_P192/256/384_DIGITS where possible Replace hard-coded numbers with ECC_CURVE_NIST_P192/256/384_DIGITS where possible. Tested-by: Lukas Wunner Reviewed-by: Jarkko Sakkinen Signed-off-by: Stefan Berger Signed-off-by: Herbert Xu --- crypto/ecc.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index 7c960e0d..e94183f6 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -689,7 +689,7 @@ static void vli_mmod_barrett(u64 *result, u64 *product, const u64 *mod, static void vli_mmod_fast_192(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { - const unsigned int ndigits = 3; + const unsigned int ndigits = ECC_CURVE_NIST_P192_DIGITS; int carry; vli_set(result, product, ndigits); @@ -717,7 +717,7 @@ static void vli_mmod_fast_256(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { int carry; - const unsigned int ndigits = 4; + const unsigned int ndigits = ECC_CURVE_NIST_P256_DIGITS; /* t */ vli_set(result, product, ndigits); @@ -800,7 +800,7 @@ static void vli_mmod_fast_384(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { int carry; - const unsigned int ndigits = 6; + const unsigned int ndigits = ECC_CURVE_NIST_P384_DIGITS; /* t */ vli_set(result, product, ndigits); @@ -932,13 +932,13 @@ static bool vli_mmod_fast(u64 *result, u64 *product, } switch (ndigits) { - case 3: + case ECC_CURVE_NIST_P192_DIGITS: vli_mmod_fast_192(result, product, curve_prime, tmp); break; - case 4: + case ECC_CURVE_NIST_P256_DIGITS: vli_mmod_fast_256(result, product, curve_prime, tmp); break; - case 6: + case ECC_CURVE_NIST_P384_DIGITS: vli_mmod_fast_384(result, product, curve_prime, tmp); break; default: -- cgit v1.2.3 From d2a3837737aa1fe32cd3a6719f921cb74512cfa2 Mon Sep 17 00:00:00 2001 From: Stefan Berger Date: Thu, 4 Apr 2024 10:18:49 -0400 Subject: crypto: ecc - Implement vli_mmod_fast_521 for NIST p521 Implement vli_mmod_fast_521 following the description for how to calculate the modulus for NIST P521 in the NIST publication "Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters" section G.1.4. NIST p521 requires 9 64bit digits, so increase the ECC_MAX_DIGITS so that the vli digit array provides enough elements to fit the larger integers required by this curve. Tested-by: Lukas Wunner Reviewed-by: Jarkko Sakkinen Signed-off-by: Stefan Berger Signed-off-by: Herbert Xu --- crypto/ecc.c | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index e94183f6..8914e437 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -902,6 +902,28 @@ static void vli_mmod_fast_384(u64 *result, const u64 *product, #undef AND64H #undef AND64L +/* + * Computes result = product % curve_prime + * from "Recommendations for Discrete Logarithm-Based Cryptography: + * Elliptic Curve Domain Parameters" section G.1.4 + */ +static void vli_mmod_fast_521(u64 *result, const u64 *product, + const u64 *curve_prime, u64 *tmp) +{ + const unsigned int ndigits = ECC_CURVE_NIST_P521_DIGITS; + size_t i; + + /* Initialize result with lowest 521 bits from product */ + vli_set(result, product, ndigits); + result[8] &= 0x1ff; + + for (i = 0; i < ndigits; i++) + tmp[i] = (product[8 + i] >> 9) | (product[9 + i] << 55); + tmp[8] &= 0x1ff; + + vli_mod_add(result, result, tmp, curve_prime, ndigits); +} + /* Computes result = product % curve_prime for different curve_primes. * * Note that curve_primes are distinguished just by heuristic check and @@ -941,6 +963,9 @@ static bool vli_mmod_fast(u64 *result, u64 *product, case ECC_CURVE_NIST_P384_DIGITS: vli_mmod_fast_384(result, product, curve_prime, tmp); break; + case ECC_CURVE_NIST_P521_DIGITS: + vli_mmod_fast_521(result, product, curve_prime, tmp); + break; default: pr_err_ratelimited("ecc: unsupported digits size!\n"); return false; -- cgit v1.2.3 From 0de2c02d3cf9af5f08ae135b0c5f1ffd6464ff19 Mon Sep 17 00:00:00 2001 From: Stefan Berger Date: Thu, 4 Apr 2024 10:18:50 -0400 Subject: crypto: ecc - Add special case for NIST P521 in ecc_point_mult In ecc_point_mult use the number of bits of the NIST P521 curve + 2. The change is required specifically for NIST P521 to pass mathematical tests on the public key. Tested-by: Lukas Wunner Reviewed-by: Jarkko Sakkinen Signed-off-by: Stefan Berger Signed-off-by: Herbert Xu --- crypto/ecc.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index 8914e437..d15ef074 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -1320,7 +1320,10 @@ static void ecc_point_mult(struct ecc_point *result, carry = vli_add(sk[0], scalar, curve->n, ndigits); vli_add(sk[1], sk[0], curve->n, ndigits); scalar = sk[!carry]; - num_bits = sizeof(u64) * ndigits * 8 + 1; + if (curve->nbits == 521) /* NIST P521 */ + num_bits = curve->nbits + 2; + else + num_bits = sizeof(u64) * ndigits * 8 + 1; vli_set(rx[1], point->x, ndigits); vli_set(ry[1], point->y, ndigits); -- cgit v1.2.3 From bf6dee7b3ce35bb8f1002a1833f42057e0983052 Mon Sep 17 00:00:00 2001 From: Stefan Berger Date: Thu, 4 Apr 2024 10:18:51 -0400 Subject: crypto: ecc - Add NIST P521 curve parameters Add the parameters for the NIST P521 curve and define a new curve ID for it. Make the curve available in ecc_get_curve. Tested-by: Lukas Wunner Reviewed-by: Jarkko Sakkinen Signed-off-by: Stefan Berger Signed-off-by: Herbert Xu --- crypto/ecc.c | 2 ++ crypto/ecc_curve_defs.h | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 47 insertions(+) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index d15ef074..2e05387b 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -60,6 +60,8 @@ const struct ecc_curve *ecc_get_curve(unsigned int curve_id) return &nist_p256; case ECC_CURVE_NIST_P384: return &nist_p384; + case ECC_CURVE_NIST_P521: + return &nist_p521; default: return NULL; } diff --git a/crypto/ecc_curve_defs.h b/crypto/ecc_curve_defs.h index ab1ef3d9..0ecade7d 100644 --- a/crypto/ecc_curve_defs.h +++ b/crypto/ecc_curve_defs.h @@ -89,6 +89,51 @@ static struct ecc_curve nist_p384 = { .b = nist_p384_b }; +/* NIST P-521 */ +static u64 nist_p521_g_x[] = { 0xf97e7e31c2e5bd66ull, 0x3348b3c1856a429bull, + 0xfe1dc127a2ffa8deull, 0xa14b5e77efe75928ull, + 0xf828af606b4d3dbaull, 0x9c648139053fb521ull, + 0x9e3ecb662395b442ull, 0x858e06b70404e9cdull, + 0xc6ull }; +static u64 nist_p521_g_y[] = { 0x88be94769fd16650ull, 0x353c7086a272c240ull, + 0xc550b9013fad0761ull, 0x97ee72995ef42640ull, + 0x17afbd17273e662cull, 0x98f54449579b4468ull, + 0x5c8a5fb42c7d1bd9ull, 0x39296a789a3bc004ull, + 0x118ull }; +static u64 nist_p521_p[] = { 0xffffffffffffffffull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0x1ffull }; +static u64 nist_p521_n[] = { 0xbb6fb71e91386409ull, 0x3bb5c9b8899c47aeull, + 0x7fcc0148f709a5d0ull, 0x51868783bf2f966bull, + 0xfffffffffffffffaull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0x1ffull }; +static u64 nist_p521_a[] = { 0xfffffffffffffffcull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0xffffffffffffffffull, 0xffffffffffffffffull, + 0x1ffull }; +static u64 nist_p521_b[] = { 0xef451fd46b503f00ull, 0x3573df883d2c34f1ull, + 0x1652c0bd3bb1bf07ull, 0x56193951ec7e937bull, + 0xb8b489918ef109e1ull, 0xa2da725b99b315f3ull, + 0x929a21a0b68540eeull, 0x953eb9618e1c9a1full, + 0x051ull }; +static struct ecc_curve nist_p521 = { + .name = "nist_521", + .nbits = 521, + .g = { + .x = nist_p521_g_x, + .y = nist_p521_g_y, + .ndigits = 9, + }, + .p = nist_p521_p, + .n = nist_p521_n, + .a = nist_p521_a, + .b = nist_p521_b +}; + /* curve25519 */ static u64 curve25519_g_x[] = { 0x0000000000000009, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000 }; -- cgit v1.2.3 From 210b65f5cb4a366976de0b3090021473a449712d Mon Sep 17 00:00:00 2001 From: Stefan Berger Date: Thu, 18 Apr 2024 11:24:45 -0400 Subject: crypto: ecdh - Initialize ctx->private_key in proper byte order The private key in ctx->private_key is currently initialized in reverse byte order in ecdh_set_secret and whenever the key is needed in proper byte order the variable priv is introduced and the bytes from ctx->private_key are copied into priv while being byte-swapped (ecc_swap_digits). To get rid of the unnecessary byte swapping initialize ctx->private_key in proper byte order and clean up all functions that were previously using priv or were called with ctx->private_key: - ecc_gen_privkey: Directly initialize the passed ctx->private_key with random bytes filling all the digits of the private key. Get rid of the priv variable. This function only has ecdh_set_secret as a caller to create NIST P192/256/384 private keys. - crypto_ecdh_shared_secret: Called only from ecdh_compute_value with ctx->private_key. Get rid of the priv variable and work with the passed private_key directly. - ecc_make_pub_key: Called only from ecdh_compute_value with ctx->private_key. Get rid of the priv variable and work with the passed private_key directly. Cc: Salvatore Benedetto Signed-off-by: Stefan Berger Acked-by: Jarkko Sakkinen Signed-off-by: Herbert Xu --- crypto/ecc.c | 29 ++++++++++------------------- crypto/ecdh.c | 8 +++----- 2 files changed, 13 insertions(+), 24 deletions(-) (limited to 'crypto/ecc.c') diff --git a/crypto/ecc.c b/crypto/ecc.c index 2e05387b..c1d2e884 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -1497,10 +1497,10 @@ EXPORT_SYMBOL(ecc_is_key_valid); * This method generates a private key uniformly distributed in the range * [2, n-3]. */ -int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey) +int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, + u64 *private_key) { const struct ecc_curve *curve = ecc_get_curve(curve_id); - u64 priv[ECC_MAX_DIGITS]; unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; unsigned int nbits = vli_num_bits(curve->n, ndigits); int err; @@ -1509,7 +1509,7 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey) * 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)) + if (nbits < 224) return -EINVAL; /* @@ -1527,17 +1527,16 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey) return -EFAULT; /* Step 3: obtain N returned_bits from the DRBG. */ - err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes); + err = crypto_rng_get_bytes(crypto_default_rng, + (u8 *)private_key, nbytes); crypto_put_default_rng(); if (err) return err; /* Step 4: make sure the private key is in the valid range. */ - if (__ecc_is_key_valid(curve, priv, ndigits)) + if (__ecc_is_key_valid(curve, private_key, ndigits)) return -EINVAL; - ecc_swap_digits(priv, privkey, ndigits); - return 0; } EXPORT_SYMBOL(ecc_gen_privkey); @@ -1547,23 +1546,20 @@ int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits, { int ret = 0; struct ecc_point *pk; - u64 priv[ECC_MAX_DIGITS]; const struct ecc_curve *curve = ecc_get_curve(curve_id); - if (!private_key || ndigits > ARRAY_SIZE(priv)) { + if (!private_key) { ret = -EINVAL; goto out; } - ecc_swap_digits(private_key, priv, ndigits); - pk = ecc_alloc_point(ndigits); if (!pk) { ret = -ENOMEM; goto out; } - ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits); + ecc_point_mult(pk, &curve->g, private_key, NULL, curve, ndigits); /* SP800-56A rev 3 5.6.2.1.3 key check */ if (ecc_is_pubkey_valid_full(curve, pk)) { @@ -1647,13 +1643,11 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, { int ret = 0; struct ecc_point *product, *pk; - u64 priv[ECC_MAX_DIGITS]; u64 rand_z[ECC_MAX_DIGITS]; unsigned int nbytes; const struct ecc_curve *curve = ecc_get_curve(curve_id); - if (!private_key || !public_key || - ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) { + if (!private_key || !public_key || ndigits > ARRAY_SIZE(rand_z)) { ret = -EINVAL; goto out; } @@ -1674,15 +1668,13 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, if (ret) goto err_alloc_product; - ecc_swap_digits(private_key, priv, ndigits); - product = ecc_alloc_point(ndigits); if (!product) { ret = -ENOMEM; goto err_alloc_product; } - ecc_point_mult(product, pk, priv, rand_z, curve, ndigits); + ecc_point_mult(product, pk, private_key, rand_z, curve, ndigits); if (ecc_point_is_zero(product)) { ret = -EFAULT; @@ -1692,7 +1684,6 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, ecc_swap_digits(product->x, secret, ndigits); err_validity: - memzero_explicit(priv, sizeof(priv)); memzero_explicit(rand_z, sizeof(rand_z)); ecc_free_point(product); err_alloc_product: diff --git a/crypto/ecdh.c b/crypto/ecdh.c index c02c9a2b..72cfd159 100644 --- a/crypto/ecdh.c +++ b/crypto/ecdh.c @@ -27,7 +27,6 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf, unsigned int len) { struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); - u64 priv[ECC_MAX_DIGITS]; struct ecdh params; int ret = 0; @@ -41,15 +40,14 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf, return ecc_gen_privkey(ctx->curve_id, ctx->ndigits, ctx->private_key); - memcpy(ctx->private_key, params.key, params.key_size); - ecc_swap_digits(ctx->private_key, priv, ctx->ndigits); + ecc_digits_from_bytes(params.key, params.key_size, + ctx->private_key, ctx->ndigits); if (ecc_is_key_valid(ctx->curve_id, ctx->ndigits, - priv, params.key_size) < 0) { + ctx->private_key, params.key_size) < 0) { memzero_explicit(ctx->private_key, params.key_size); ret = -EINVAL; } - memzero_explicit(priv, sizeof(priv)); return ret; } -- cgit v1.2.3