Skip to contentSkip to conversation

Add support for NIST P521 to ecdsa

PATCH Superseded Stefan Berger 4 participants 29 messages Mar 1, 2024 – Mar 4, 2024

Subsystems (6)
Crypto API Arm STM32 Keys/keyrings Asymmetric keys +2 more subsystems

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Stefan Berger

author reviewer
#0 lore raw

v4 cover Add support for NIST P521 to ecdsa

This series adds support for the NIST P521 curve to the ecdsa module to enable signature verification with it.

An issue with the current code in ecdsa is that it assumes that input arrays providing key coordinates for example, are arrays of digits (a 'digit' is a 'u64'). This works well for all currently supported curves, such as NIST P192/256/384, but does not work for NIST P521 where coordinates are 8 digits + 2 bytes long. So some of the changes deal with converting byte arrays to digits and adjusting tests on input byte array lengths to tolerate arrays not providing multiples of 8 bytes.

Regards,
Stefan

v4:
- Followed suggestions by Lukas Wummer (1,5,8/12)
- Use nbits rather than ndigits where needed (8/12)
- Renaming 'keylen' variablest to bufsize where necessary (9/12)
- Adjust signature size calculation for NIST P521 (11/12)

v3:
- Dropped ecdh support
- Use ecc_get_curve_nbits for getting number of bits in NIST P521 curve in ecc_point_mult (7/10)

v2:
- Reformulated some patch descriptions
- Fixed issue detected by krobot
- Some other small changes to the code

Stefan Berger (12):
crypto: ecdsa - Convert byte arrays with key coordinates to digits
crypto: ecdsa - Adjust tests on length of key parameters
crypto: ecdsa - Extend res.x mod n calculation for NIST P521
crypto: ecc - Implement vli_mmod_fast_521 for NIST p521
crypto: ecc - Add nbits field to ecc_curve structure
crypto: ecc - Add special case for NIST P521 in ecc_point_mult
crypto: ecc - Add NIST P521 curve parameters
crypto: ecdsa - Replace ndigits with nbits where precision is needed
crypto: ecdsa - Rename keylen to bufsize where necessary
crypto: ecdsa - Register NIST P521 and extend test suite
crypto: asymmetric_keys - Adjust signature size calculation for NIST

    P521

crypto: x509 - Add OID for NIST P521 and extend parser for it

 crypto/asymmetric_keys/public_key.c       |  14 ++-
 crypto/asymmetric_keys/x509_cert_parser.c |   3 +
 crypto/ecc.c                              |  38 +++++-
 crypto/ecc_curve_defs.h                   |  49 ++++++++
 crypto/ecdsa.c                            |  62 ++++++---
 crypto/ecrdsa_defs.h                      |   5 +
 crypto/testmgr.c                          |   7 ++
 crypto/testmgr.h                          | 146 ++++++++++++++++++++++
 include/crypto/ecc_curve.h                |   3 +
 include/crypto/ecdh.h                     |   1 +
 include/crypto/internal/ecc.h             |  27 +++-
 include/linux/oid_registry.h              |   1 +
 12 files changed, 339 insertions(+), 17 deletions(-)
Signature · 1 line
2.43.0
author reviewer
#1 lore raw

PATCH v4 1/12 crypto: ecdsa - Convert byte arrays with key coordinates to digits

For NIST P192/256/384 the public key's x and y parameters could be copied directly from a given array since both parameters filled 'ndigits' of digits (a 'digit' is a u64). For support of NIST P521 the key parameters need to have leading zeros prepended to the most significant digit since only 2 bytes of the most significant digit are provided.

Therefore, implement ecc_digits_from_bytes to convert a byte array into an array of digits and use this function in ecdsa_set_pub_key where an input byte array needs to be converted into digits.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c                | 14 +++++++++-----
 include/crypto/internal/ecc.h | 25 +++++++++++++++++++++++++
 2 files changed, 34 insertions(+), 5 deletions(-)
crypto/ecdsa.c +9 -5
index fbd76498aba8..6653dec17327 100644
@@ -222,9 +222,8 @@ static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
 {
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+	unsigned int digitlen, ndigits;
 	const unsigned char *d = key;
-	const u64 *digits = (const u64 *)&d[1];
-	unsigned int ndigits;
 	int ret;
 
 	ret = ecdsa_ecc_ctx_reset(ctx);

@@ -238,12 +237,17 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig
 		return -EINVAL;
 
 	keylen--;
-	ndigits = (keylen >> 1) / sizeof(u64);
+	digitlen = keylen >> 1;
+
+	ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));
 	if (ndigits != ctx->curve->g.ndigits)
 		return -EINVAL;
 
-	ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
-	ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
+	d++;
+
+	ecc_digits_from_bytes(d, digitlen, ctx->pub_key.x, ndigits);
+	ecc_digits_from_bytes(&d[digitlen], digitlen, ctx->pub_key.y, ndigits);
+
 	ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
 
 	ctx->pub_key_set = ret == 0;
include/crypto/internal/ecc.h +25 -0
index 4f6c1a68882f..48a04605da7f 100644
@@ -56,6 +56,31 @@ static inline void ecc_swap_digits(const void *in, u64 *out, unsigned int ndigit
 		out[i] = get_unaligned_be64(&src[ndigits - 1 - i]);
 }
 
+/**
+ * ecc_digits_from_bytes() - Create ndigits-sized digits array from byte array
+ * @in:       Input byte array
+ * @nbytes    Size of input byte array
+ * @out       Output digits array
+ * @ndigits:  Number of digits to create from byte array
+ */
+static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
+					 u64 *out, unsigned int ndigits)
+{
+	unsigned int o = nbytes & 7;
+	u64 msd = 0;
+	size_t i;
+
+	if (o == 0) {
+		ecc_swap_digits(in, out, ndigits);
+	} else {
+		/* if key length is not a multiple of 64 bits (NIST P521) */
+		for (i = 0; i < o; i++)
+			msd = (msd << 8) | in[i];
+		out[ndigits - 1] = msd;
+		ecc_swap_digits(&in[o], out, (nbytes - o) >> 3);
+	}
+}
+
 /**
  * ecc_is_key_valid() - Validate a given ECDH private key
  *
Signature · 1 line
2.43.0
maintainer
#2 lore raw

Re: [PATCH v4 01/12] crypto: ecdsa - Convert byte arrays with key coordinates to digits

Quoted 73 lines · Stefan Berger

For NIST P192/256/384 the public key's x and y parameters could be copied directly from a given array since both parameters filled 'ndigits' of digits (a 'digit' is a u64). For support of NIST P521 the key parameters need to have leading zeros prepended to the most significant digit since only 2 bytes of the most significant digit are provided.

Therefore, implement ecc_digits_from_bytes to convert a byte array into an array of digits and use this function in ecdsa_set_pub_key where an input byte array needs to be converted into digits.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c                | 14 +++++++++-----
 include/crypto/internal/ecc.h | 25 +++++++++++++++++++++++++
 2 files changed, 34 insertions(+), 5 deletions(-)
crypto/ecdsa.c +9 -5
index fbd76498aba8..6653dec17327 100644
@@ -222,9 +222,8 @@ static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
 {
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+	unsigned int digitlen, ndigits;
 	const unsigned char *d = key;
-	const u64 *digits = (const u64 *)&d[1];
-	unsigned int ndigits;
 	int ret;
 
 	ret = ecdsa_ecc_ctx_reset(ctx);

@@ -238,12 +237,17 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig
 		return -EINVAL;
 
 	keylen--;
-	ndigits = (keylen >> 1) / sizeof(u64);
+	digitlen = keylen >> 1;
+
+	ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));
 	if (ndigits != ctx->curve->g.ndigits)
 		return -EINVAL;
 
-	ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
-	ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
+	d++;
+
+	ecc_digits_from_bytes(d, digitlen, ctx->pub_key.x, ndigits);
+	ecc_digits_from_bytes(&d[digitlen], digitlen, ctx->pub_key.y, ndigits);
+
 	ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
 
 	ctx->pub_key_set = ret == 0;
include/crypto/internal/ecc.h +13 -0
index 4f6c1a68882f..48a04605da7f 100644
@@ -56,6 +56,31 @@ static inline void ecc_swap_digits(const void *in, u64 *out, unsigned int ndigit
 		out[i] = get_unaligned_be64(&src[ndigits - 1 - i]);
 }
 
+/**
+ * ecc_digits_from_bytes() - Create ndigits-sized digits array from byte array
+ * @in:       Input byte array
+ * @nbytes    Size of input byte array
+ * @out       Output digits array
+ * @ndigits:  Number of digits to create from byte array
+ */
+static inline void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
+					 u64 *out, unsigned int ndigits)
+{
+	unsigned int o = nbytes & 7;
+	u64 msd = 0;
+	size_t i;

include/crypto/internal/ecc.h static inline void ecc_swap_digits(const void *in, u64 *out, unsigned int ndigit · line 81

Quoted 10 lines
include/crypto/internal/ecc.h +10 -0
+
+	if (o == 0) {
+		ecc_swap_digits(in, out, ndigits);
+	} else {
+		/* if key length is not a multiple of 64 bits (NIST P521) */
+		for (i = 0; i < o; i++)
+			msd = (msd << 8) | in[i];
+		out[ndigits - 1] = msd;
+		ecc_swap_digits(&in[o], out, (nbytes - o) >> 3);
+	}

https://lore.kernel.org/keyrings/CZIOY02QS2QC.LV0A0HNT7VKM@suppilovahvero/

BR, Jarkko

maintainer
#3 lore raw

Re: [PATCH v4 01/12] crypto: ecdsa - Convert byte arrays with key coordinates to digits

In reply to Stefan Berger

crypto/ecdsa.c static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx) · line 229

Quoted 13 lines · Stefan Berger
crypto/ecdsa.c +1 -2
@@ -222,9 +222,8 @@ static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
 {
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+	unsigned int digitlen, ndigits;
 	const unsigned char *d = key;
-	const u64 *digits = (const u64 *)&d[1];
-	unsigned int ndigits;
 	int ret;
 
 	ret = ecdsa_ecc_ctx_reset(ctx);

Hm, the removal of digits isn't strictly necessary. If you would keep it, the patch would become simpler (fewer lines changes).

crypto/ecdsa.c static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig · line 242

Quoted 8 lines
crypto/ecdsa.c +3 -1
@@ -238,12 +237,17 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig
 		return -EINVAL;
 
 	keylen--;
-	ndigits = (keylen >> 1) / sizeof(u64);
+	digitlen = keylen >> 1;
+
+	ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));

Instead of introducing an additional digitlen variable, you could just use keylen. It seems it's not used in the remainder of the function, so modifying it is harmless:

keylen--;
+ keylen >>= 1;
- ndigits = (keylen >> 1) / sizeof(u64);
+ ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));

Just a suggestion.

Thanks,

Lukas

#4 lore raw

Re: [PATCH v4 01/12] crypto: ecdsa - Convert byte arrays with key coordinates to digits

Quoted 1 line · Lukas Wunner

On Thu, Feb 29, 2024 at 09:19:56PM -0500, Stefan Berger wrote:

[...]

Quoted 14 lines
Quoted 9 lines
(quoted diff) +0 -0
@@ -238,12 +237,17 @@ static int ecdsa_set_pub_key(struct

crypto_akcipher *tfm, const void *key, unsig return -EINVAL;

        keylen--;
-       ndigits = (keylen >> 1) / sizeof(u64); +       digitlen = keylen >> 1;
+
+       ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));

Instead of introducing an additional digitlen variable, you could just use keylen.  It seems it's not used in the remainder of the function, so modifying it is harmless:

Quoted 6 lines

        keylen--;
+       keylen >>= 1;
-       ndigits = (keylen >> 1) / sizeof(u64); +       ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));

Just a suggestion.

The compiler will optimize the variables like this anyway (reuse registers or frames after a current consumer becomes unused) so there's no requirement to do this for efficiency, the only real question is whether using digitlen is clearer than reusing keylen, which I'll leave to the author.

James

author reviewer
#5 lore raw

Re: [PATCH v4 01/12] crypto: ecdsa - Convert byte arrays with key coordinates to digits

In reply to Lukas Wunner
Quoted 37 lines · Lukas Wunner

crypto/ecdsa.c static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx) · line 229

Quoted 13 lines · Stefan Berger
crypto/ecdsa.c +1 -2
@@ -222,9 +222,8 @@ static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
  static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
  {
  	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+	unsigned int digitlen, ndigits;
  	const unsigned char *d = key;
-	const u64 *digits = (const u64 *)&d[1];
-	unsigned int ndigits;
  	int ret;
 
  	ret = ecdsa_ecc_ctx_reset(ctx);

Hm, the removal of digits isn't strictly necessary. If you would keep it, the patch would become simpler (fewer lines changes).

crypto/ecdsa.c static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig · line 242

Quoted 8 lines
crypto/ecdsa.c +3 -1
@@ -238,12 +237,17 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig
  		return -EINVAL;
 
  	keylen--;
-	ndigits = (keylen >> 1) / sizeof(u64);
+	digitlen = keylen >> 1;
+
+	ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));

Instead of introducing an additional digitlen variable, you could just use keylen. It seems it's not used in the remainder of the function, so modifying it is harmless:

keylen--;

crypto/ecdsa.c +2 -1
+ 	keylen >>= 1;
-	ndigits = (keylen >> 1) / sizeof(u64);
+	ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));
Quoted 1 line

Just a suggestion.

I would prefer 'digitlen' rather than repurposing keylen and giving it a different meaning...

Stefan

Quoted 4 lines

Thanks,

Lukas

author reviewer
#6 lore raw

PATCH v4 2/12 crypto: ecdsa - Adjust tests on length of key parameters

In reply to Stefan Berger

In preparation for support of NIST P521, adjust the basic tests on the length of the provided key parameters to only ensure that the length of the x plus y coordinates parameter array is not an odd number and that each coordinate fits into an array of 'ndigits' digits. Mathematical tests on the key's parameters are then done in ecc_is_pubkey_valid_full rejecting invalid keys.

The change is necessary since NIST P521 keys do not have keys with coordinates that each fully require 'full' digits (= u64), unlike NIST P192/256/384 that all require multiple 'full' digits.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
crypto/ecdsa.c +1 -1
index 6653dec17327..64e1e69d53ba 100644
@@ -230,7 +230,7 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig
 	if (ret < 0)
 		return ret;
 
-	if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
+	if (keylen < 1 || ((keylen - 1) & 1) != 0)
 		return -EINVAL;
 	/* we only accept uncompressed format indicated by '4' */
 	if (d[0] != 4)
Signature · 1 line
2.43.0
author reviewer
#7 lore raw

PATCH v4 3/12 crypto: ecdsa - Extend res.x mod n calculation for NIST P521

In reply to Stefan Berger

res.x has been calculated by ecc_point_mult_shamir, which uses 'mod curve_prime'. The curve_prime 'p' is typically larger than the curve_order 'n' and therefore it is possible that p > res.x >= n.

If res.x >= n then res.x mod n can be calculated by iteratively sub- tracting n from res.x until n > res.x. For NIST P192/256/384 this can be done in a single subtraction. This can also be done in a single subtraction for NIST P521.

The mathematical reason why a single subtraction is sufficient is due to the values of 'p' and 'n' of the NIST curves where the following holds true:

note: max(res.x) = p - 1

max(res.x) - n < n
p - 1 - n < n
p - 1 < 2n => true for the NIST curves

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
crypto/ecdsa.c +1 -1
index 64e1e69d53ba..1814f009f971 100644
@@ -122,7 +122,7 @@ static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, con
 
 	/* res.x = res.x mod n (if res.x > order) */
 	if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
-		/* faster alternative for NIST p384, p256 & p192 */
+		/* faster alternative for NIST p521, p384, p256 & p192 */
 		vli_sub(res.x, res.x, curve->n, ndigits);
 
 	if (!vli_cmp(res.x, r, ndigits))
Signature · 1 line
2.43.0
author reviewer
#8 lore raw

PATCH v4 4/12 crypto: ecc - Implement vli_mmod_fast_521 for NIST p521

In reply to Stefan Berger

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 arrays fit the larger numbers.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecc.c                  | 31 +++++++++++++++++++++++++++++++
 include/crypto/internal/ecc.h |  2 +-
 2 files changed, 32 insertions(+), 1 deletion(-)
crypto/ecc.c +31 -0
index f53fb4d6af99..ea7b28b5e00e 100644
@@ -902,6 +902,31 @@ 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" G.1.4
+ */
+static void vli_mmod_fast_521(u64 *result, const u64 *product,
+				const u64 *curve_prime, u64 *tmp)
+{
+	const unsigned int ndigits = 9;
+	size_t i;
+
+	for (i = 0; i < ndigits; i++)
+		tmp[i] = product[i];
+	tmp[8] &= 0x1ff;
+
+	vli_set(result, tmp, ndigits);
+
+
+	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 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
 	case 6:
 		vli_mmod_fast_384(result, product, curve_prime, tmp);
 		break;
+	case 9:
+		if (!strcmp(curve->name, "nist_521")) {
+			vli_mmod_fast_521(result, product, curve_prime, tmp);
+			break;
+		}
+		fallthrough;
 	default:
 		pr_err_ratelimited("ecc: unsupported digits size!\n");
 		return false;
include/crypto/internal/ecc.h +1 -1
index 48a04605da7f..b63238b12204 100644
@@ -33,7 +33,7 @@
 #define ECC_CURVE_NIST_P192_DIGITS  3
 #define ECC_CURVE_NIST_P256_DIGITS  4
 #define ECC_CURVE_NIST_P384_DIGITS  6
-#define ECC_MAX_DIGITS              (512 / 64) /* due to ecrdsa */
+#define ECC_MAX_DIGITS              (576 / 64) /* due to NIST P521 */
 
 #define ECC_DIGITS_TO_BYTES_SHIFT 3
Signature · 1 line
2.43.0
maintainer
#9 lore raw

Re: [PATCH v4 04/12] crypto: ecc - Implement vli_mmod_fast_521 for NIST p521

crypto/ecc.c static void vli_mmod_fast_384(u64 *result, const u64 *product, · line 917

Quoted 9 lines · Stefan Berger
crypto/ecc.c +9 -0
+static void vli_mmod_fast_521(u64 *result, const u64 *product,
+				const u64 *curve_prime, u64 *tmp)
+{
+	const unsigned int ndigits = 9;
+	size_t i;
+
+	for (i = 0; i < ndigits; i++)
+		tmp[i] = product[i];
+	tmp[8] &= 0x1ff;

Hm, the other vli_mmod_fast_*() functions manually unroll those loops. Wondering if that would make sense here as well? It's also possible to tell gcc to unroll a loop with a per-function...

    __attribute__((optimize("unroll-loops")))

...but I'm not sure about clang portability.

crypto/ecc.c static bool vli_mmod_fast(u64 *result, u64 *product, · line 971

Quoted 7 lines
crypto/ecc.c +6 -0
@@ -941,6 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
+	case 9:
+		if (!strcmp(curve->name, "nist_521")) {
+			vli_mmod_fast_521(result, product, curve_prime, tmp);
+			break;
+		}
+		fallthrough;

If you reorder patch 4 and 5, you could check for curve->nbits == 521 here, which might be cheaper than the string comparison.

include/crypto/internal/ecc.h line 36

Quoted 2 lines
include/crypto/internal/ecc.h +1 -1
-#define ECC_MAX_DIGITS              (512 / 64) /* due to ecrdsa */
+#define ECC_MAX_DIGITS              (576 / 64) /* due to NIST P521 */

Maybe DIV_ROUND_UP(521, 64) for clarity?

Thanks,

Lukas

author reviewer
#10 lore raw

Re: [PATCH v4 04/12] crypto: ecc - Implement vli_mmod_fast_521 for NIST p521

Quoted 13 lines · Lukas Wunner

crypto/ecc.c static void vli_mmod_fast_384(u64 *result, const u64 *product, · line 917

Quoted 9 lines · Stefan Berger
crypto/ecc.c +9 -0
+static void vli_mmod_fast_521(u64 *result, const u64 *product,
+				const u64 *curve_prime, u64 *tmp)
+{
+	const unsigned int ndigits = 9;
+	size_t i;
+
+	for (i = 0; i < ndigits; i++)
+		tmp[i] = product[i];
+	tmp[8] &= 0x1ff;

Hm, the other vli_mmod_fast_*() functions manually unroll those loops. Wondering if that would make sense here as well? It's also possible

Why would we do this? One could also argue why not use vli_set() instead of the loop...

Quoted 6 lines

to tell gcc to unroll a loop with a per-function...

     __attribute__((optimize("unroll-loops")))

...but I'm not sure about clang portability. >

Quoted 10 lines

crypto/ecc.c static bool vli_mmod_fast(u64 *result, u64 *product, · line 971

Quoted 7 lines
crypto/ecc.c +6 -0
@@ -941,6 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,
+	case 9:
+		if (!strcmp(curve->name, "nist_521")) {
+			vli_mmod_fast_521(result, product, curve_prime, tmp);
+			break;
+		}
+		fallthrough;

If you reorder patch 4 and 5, you could check for curve->nbits == 521 here, which might be cheaper than the string comparison.

Sure. I thought it's a nist spec for this particular curve, so compare against 'nist' in the string. Though comparing against nbits also works, of course.

Quoted 6 lines

include/crypto/internal/ecc.h line 36

Quoted 4 lines
include/crypto/internal/ecc.h +1 -1
-#define ECC_MAX_DIGITS              (512 / 64) /* due to ecrdsa */
+#define ECC_MAX_DIGITS              (576 / 64) /* due to NIST P521 */

Maybe DIV_ROUND_UP(521, 64) for clarity?

Ok, will adjust.

Regards,
Stefan

Quoted 5 lines

Thanks,

Lukas

author reviewer
#11 lore raw

PATCH v4 5/12 crypto: ecc - Add nbits field to ecc_curve structure

In reply to Stefan Berger

Add the number of bits a curve has to the ecc_curve definition and set it on all cruve definitions.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecc_curve_defs.h    | 4 ++++
 crypto/ecrdsa_defs.h       | 5 +++++
 include/crypto/ecc_curve.h | 3 +++
 3 files changed, 12 insertions(+)
crypto/ecc_curve_defs.h +4 -0
index 9719934c9428..ab1ef3d94be5 100644
@@ -17,6 +17,7 @@ static u64 nist_p192_b[] = { 0xFEB8DEECC146B9B1ull, 0x0FA7E9AB72243049ull,
 				0x64210519E59C80E7ull };
 static struct ecc_curve nist_p192 = {
 	.name = "nist_192",
+	.nbits = 192,
 	.g = {
 		.x = nist_p192_g_x,
 		.y = nist_p192_g_y,

@@ -43,6 +44,7 @@ static u64 nist_p256_b[] = { 0x3BCE3C3E27D2604Bull, 0x651D06B0CC53B0F6ull,
 				0xB3EBBD55769886BCull, 0x5AC635D8AA3A93E7ull };
 static struct ecc_curve nist_p256 = {
 	.name = "nist_256",
+	.nbits = 256,
 	.g = {
 		.x = nist_p256_g_x,
 		.y = nist_p256_g_y,

@@ -75,6 +77,7 @@ static u64 nist_p384_b[] = { 0x2a85c8edd3ec2aefull, 0xc656398d8a2ed19dull,
 				0x988e056be3f82d19ull, 0xb3312fa7e23ee7e4ull };
 static struct ecc_curve nist_p384 = {
 	.name = "nist_384",
+	.nbits = 384,
 	.g = {
 		.x = nist_p384_g_x,
 		.y = nist_p384_g_y,

@@ -95,6 +98,7 @@ static u64 curve25519_a[] = { 0x000000000001DB41, 0x0000000000000000,
 				0x0000000000000000, 0x0000000000000000 };
 static const struct ecc_curve ecc_25519 = {
 	.name = "curve25519",
+	.nbits = 255,
 	.g = {
 		.x = curve25519_g_x,
 		.ndigits = 4,
crypto/ecrdsa_defs.h +5 -0
index 0056335b9d03..1c2c2449e331 100644
@@ -47,6 +47,7 @@ static u64 cp256a_b[] = {
 
 static struct ecc_curve gost_cp256a = {
 	.name = "cp256a",
+	.nbits = 256,
 	.g = {
 		.x = cp256a_g_x,
 		.y = cp256a_g_y,

@@ -80,6 +81,7 @@ static u64 cp256b_b[] = {
 
 static struct ecc_curve gost_cp256b = {
 	.name = "cp256b",
+	.nbits = 256,
 	.g = {
 		.x = cp256b_g_x,
 		.y = cp256b_g_y,

@@ -117,6 +119,7 @@ static u64 cp256c_b[] = {
 
 static struct ecc_curve gost_cp256c = {
 	.name = "cp256c",
+	.nbits = 256,
 	.g = {
 		.x = cp256c_g_x,
 		.y = cp256c_g_y,

@@ -166,6 +169,7 @@ static u64 tc512a_b[] = {
 
 static struct ecc_curve gost_tc512a = {
 	.name = "tc512a",
+	.nbits = 512,
 	.g = {
 		.x = tc512a_g_x,
 		.y = tc512a_g_y,

@@ -211,6 +215,7 @@ static u64 tc512b_b[] = {
 
 static struct ecc_curve gost_tc512b = {
 	.name = "tc512b",
+	.nbits = 512,
 	.g = {
 		.x = tc512b_g_x,
 		.y = tc512b_g_y,
include/crypto/ecc_curve.h +3 -0
index 70964781eb68..337a44956926 100644
@@ -23,6 +23,8 @@ struct ecc_point {
  * struct ecc_curve - definition of elliptic curve
  *
  * @name:	Short name of the curve.
+ * @nbits:      Curves that do not use all bits in their ndigits must specify
+ *              their number of bits here, otherwise can leave at 0.
  * @g:		Generator point of the curve.
  * @p:		Prime number, if Barrett's reduction is used for this curve
  *		pre-calculated value 'mu' is appended to the @p after ndigits.

@@ -34,6 +36,7 @@ struct ecc_point {
  */
 struct ecc_curve {
 	char *name;
+	unsigned int nbits;
 	struct ecc_point g;
 	u64 *p;
 	u64 *n;
Signature · 1 line
2.43.0
maintainer
#12 lore raw

Re: [PATCH v4 05/12] crypto: ecc - Add nbits field to ecc_curve structure

Quoted 2 lines · Stefan Berger

Add the number of bits a curve has to the ecc_curve definition and set it on all cruve definitions.

Nit: s/cruve/curve/

include/crypto/ecc_curve.h struct ecc_point { · line 30

Quoted 11 lines
include/crypto/ecc_curve.h +2 -0
@@ -23,6 +23,8 @@ struct ecc_point {
  * struct ecc_curve - definition of elliptic curve
  *
  * @name:	Short name of the curve.
+ * @nbits:      Curves that do not use all bits in their ndigits must specify
+ *              their number of bits here, otherwise can leave at 0.
  * @g:		Generator point of the curve.
  * @p:		Prime number, if Barrett's reduction is used for this curve
  *		pre-calculated value 'mu' is appended to the @p after ndigits.

Nit: Looks like this kernel-doc uses 1 tab instead of blanks.

author reviewer
#13 lore raw

Re: [PATCH v4 05/12] crypto: ecc - Add nbits field to ecc_curve structure

Quoted 7 lines · Lukas Wunner
Quoted 2 lines · Stefan Berger

Add the number of bits a curve has to the ecc_curve definition and set it on all cruve definitions.

Nit: s/cruve/curve/

Quoted 14 lines

include/crypto/ecc_curve.h struct ecc_point { · line 30

Quoted 11 lines
include/crypto/ecc_curve.h +2 -0
@@ -23,6 +23,8 @@ struct ecc_point {
   * struct ecc_curve - definition of elliptic curve
   *
   * @name:	Short name of the curve.
+ * @nbits:      Curves that do not use all bits in their ndigits must specify
+ *              their number of bits here, otherwise can leave at 0.
   * @g:		Generator point of the curve.
   * @p:		Prime number, if Barrett's reduction is used for this curve
   *		pre-calculated value 'mu' is appended to the @p after ndigits.

Nit: Looks like this kernel-doc uses 1 tab instead of blanks.

Fixed.

author reviewer
#14 lore raw

PATCH v4 6/12 crypto: ecc - Add special case for NIST P521 in ecc_point_mult

In reply to Stefan Berger

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.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecc.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
crypto/ecc.c +4 -1
index ea7b28b5e00e..3430c2c4e62c 100644
@@ -1326,7 +1326,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 (ndigits == 9 && !strcmp(curve->name, "nist_521"))
+		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);
Signature · 1 line
2.43.0
author reviewer
#15 lore raw

PATCH v4 7/12 crypto: ecc - Add NIST P521 curve parameters

In reply to Stefan Berger

Add the parameters for the NIST P521 curve and define a new curve ID for it. Make the curve available in ecc_get_curve.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecc.c            |  2 ++
 crypto/ecc_curve_defs.h | 45 +++++++++++++++++++++++++++++++++++++++++
 include/crypto/ecdh.h   |  1 +
 3 files changed, 48 insertions(+)
crypto/ecc.c +2 -0
index 3430c2c4e62c..a62c2dd352b7 100644
@@ -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;
 	}
crypto/ecc_curve_defs.h +45 -0

51 lines not on this page · raw message

include/crypto/ecdh.h +1 -0
index a9f98078d29c..9784ecdd2fb4 100644
@@ -26,6 +26,7 @@
 #define ECC_CURVE_NIST_P192	0x0001
 #define ECC_CURVE_NIST_P256	0x0002
 #define ECC_CURVE_NIST_P384	0x0003
+#define ECC_CURVE_NIST_P521	0x0004
 
 /**
  * struct ecdh - define an ECDH private key
Signature · 1 line
2.43.0
author reviewer
#16 lore raw

PATCH v4 8/12 crypto: ecdsa - Replace ndigits with nbits where precision is needed

In reply to Stefan Berger

Replace the usage of ndigits with nbits where more precise space calculations are needed, such as in ecdsa_max_size where the length of a coordinate is determined.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
crypto/ecdsa.c +1 -1
index 1814f009f971..4daefb40c37a 100644
@@ -266,7 +266,7 @@ static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
 {
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 
-	return ctx->pub_key.ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+	return DIV_ROUND_UP(ctx->curve->nbits, 8);
 }
 
 static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
Signature · 1 line
2.43.0
author reviewer
#17 lore raw

PATCH v4 9/12 crypto: ecdsa - Rename keylen to bufsize where necessary

In reply to Stefan Berger

In some cases the name keylen does not reflect the purpose of the variable anymore once NIST P521 is used but it is the size of the buffer. There- for, rename keylen to bufsize where appropriate.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
crypto/ecdsa.c +6 -6
index 4daefb40c37a..4e847b59622a 100644
@@ -35,8 +35,8 @@ struct ecdsa_signature_ctx {
 static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
 				  const void *value, size_t vlen, unsigned int ndigits)
 {
-	size_t keylen = ndigits * sizeof(u64);
-	ssize_t diff = vlen - keylen;
+	size_t bufsize = ndigits * sizeof(u64);
+	ssize_t diff = vlen - bufsize;
 	const char *d = value;
 	u8 rs[ECC_MAX_BYTES];
 

@@ -58,7 +58,7 @@ static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
 		if (diff)
 			return -EINVAL;
 	}
-	if (-diff >= keylen)
+	if (-diff >= bufsize)
 		return -EINVAL;
 
 	if (diff) {

@@ -138,7 +138,7 @@ static int ecdsa_verify(struct akcipher_request *req)
 {
 	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
-	size_t keylen = ctx->curve->g.ndigits * sizeof(u64);
+	size_t bufsize = ctx->curve->g.ndigits * sizeof(u64);
 	struct ecdsa_signature_ctx sig_ctx = {
 		.curve = ctx->curve,
 	};

@@ -165,14 +165,14 @@ static int ecdsa_verify(struct akcipher_request *req)
 		goto error;
 
 	/* if the hash is shorter then we will add leading zeros to fit to ndigits */
-	diff = keylen - req->dst_len;
+	diff = bufsize - req->dst_len;
 	if (diff >= 0) {
 		if (diff)
 			memset(rawhash, 0, diff);
 		memcpy(&rawhash[diff], buffer + req->src_len, req->dst_len);
 	} else if (diff < 0) {
 		/* given hash is longer, we take the left-most bytes */
-		memcpy(&rawhash, buffer + req->src_len, keylen);
+		memcpy(&rawhash, buffer + req->src_len, bufsize);
 	}
 
 	ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);
Signature · 1 line
2.43.0
maintainer
#18 lore raw

Re: [PATCH v4 09/12] crypto: ecdsa - Rename keylen to bufsize where necessary

Quoted 14 lines · Stefan Berger

In some cases the name keylen does not reflect the purpose of the variable anymore once NIST P521 is used but it is the size of the buffer. There- for, rename keylen to bufsize where appropriate.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
crypto/ecdsa.c +0 -0
index 4daefb40c37a..4e847b59622a 100644

crypto/ecdsa.c struct ecdsa_signature_ctx { · line 38

Quoted 6 lines
crypto/ecdsa.c +1 -2
@@ -35,8 +35,8 @@ struct ecdsa_signature_ctx {
 static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
 				  const void *value, size_t vlen, unsigned int ndigits)
 {
-	size_t keylen = ndigits * sizeof(u64);
-	ssize_t diff = vlen - keylen;
+	size_t bufsize = ndigits * sizeof(u64);

why not just "* 8"? using sizeof here makes this function only unreadable.

Quoted 29 lines
crypto/ecdsa.c +4 -3
+	ssize_t diff = vlen - bufsize;
 	const char *d = value;
 	u8 rs[ECC_MAX_BYTES];
 

@@ -58,7 +58,7 @@ static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
 		if (diff)
 			return -EINVAL;
 	}
-	if (-diff >= keylen)
+	if (-diff >= bufsize)
 		return -EINVAL;
 
 	if (diff) {

@@ -138,7 +138,7 @@ static int ecdsa_verify(struct akcipher_request *req)
 {
 	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
-	size_t keylen = ctx->curve->g.ndigits * sizeof(u64);
+	size_t bufsize = ctx->curve->g.ndigits * sizeof(u64);
 	struct ecdsa_signature_ctx sig_ctx = {
 		.curve = ctx->curve,
 	};

@@ -165,14 +165,14 @@ static int ecdsa_verify(struct akcipher_request *req)
 		goto error;
 
 	/* if the hash is shorter then we will add leading zeros to fit to ndigits */
-	diff = keylen - req->dst_len;
+	diff = bufsize - req->dst_len;
 	if (diff >= 0) {

crypto/ecdsa.c static int ecdsa_verify(struct akcipher_request *req) · line 178

Quoted 10 lines
crypto/ecdsa.c +1 -1
 		if (diff)
 			memset(rawhash, 0, diff);
 		memcpy(&rawhash[diff], buffer + req->src_len, req->dst_len);
 	} else if (diff < 0) {
 		/* given hash is longer, we take the left-most bytes */
-		memcpy(&rawhash, buffer + req->src_len, keylen);
+		memcpy(&rawhash, buffer + req->src_len, bufsize);
 	}
 
 	ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);

BR, Jarkko

author reviewer
#19 lore raw

Re: [PATCH v4 09/12] crypto: ecdsa - Rename keylen to bufsize where necessary

Quoted 10 lines · Jarkko Sakkinen
Quoted 9 lines · Stefan Berger

In some cases the name keylen does not reflect the purpose of the variable anymore once NIST P521 is used but it is the size of the buffer. There- for, rename keylen to bufsize where appropriate.

Signed-off-by Stefan Berger <[email protected]>
---
  crypto/ecdsa.c | 12 ++++++------
  1 file changed, 6 insertions(+), 6 deletions(-)
Quoted 13 lines

crypto/ecdsa.c struct ecdsa_signature_ctx { · line 38

Quoted 11 lines
crypto/ecdsa.c +1 -2
index 4daefb40c37a..4e847b59622a 100644
@@ -35,8 +35,8 @@ struct ecdsa_signature_ctx {
  static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
  				  const void *value, size_t vlen, unsigned int ndigits)
  {
-	size_t keylen = ndigits * sizeof(u64);
-	ssize_t diff = vlen - keylen;
+	size_t bufsize = ndigits * sizeof(u64);

why not just "* 8"? using sizeof here makes this function only unreadable.

'unreadable' is a 'strong' word ...

# grep -r -E "ndigits \*" crypto/ | grep sizeof
crypto/ecrdsa.c:            req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
crypto/ecrdsa.c:        vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
crypto/ecrdsa.c:            ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
crypto/ecrdsa.c:            ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
crypto/ecrdsa.c:        vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
crypto/ecrdsa.c:        return ctx->pub_key.ndigits * sizeof(u64);
crypto/ecc.c:   size_t len = ndigits * sizeof(u64);
crypto/ecc.c:   num_bits = sizeof(u64) * ndigits * 8 + 1;
crypto/ecdsa.c: size_t keylen = ndigits * sizeof(u64);
crypto/ecdsa.c: size_t keylen = ctx->curve->g.ndigits * sizeof(u64);

Stefan

maintainer
#20 lore raw

Re: [PATCH v4 09/12] crypto: ecdsa - Rename keylen to bufsize where necessary

Quoted 27 lines · Stefan Berger
Quoted 10 lines · Jarkko Sakkinen
Quoted 9 lines · Stefan Berger

In some cases the name keylen does not reflect the purpose of the variable anymore once NIST P521 is used but it is the size of the buffer. There- for, rename keylen to bufsize where appropriate.

Signed-off-by Stefan Berger <[email protected]>
---
  crypto/ecdsa.c | 12 ++++++------
  1 file changed, 6 insertions(+), 6 deletions(-)
Quoted 13 lines

crypto/ecdsa.c struct ecdsa_signature_ctx { · line 38

Quoted 11 lines
crypto/ecdsa.c +1 -2
index 4daefb40c37a..4e847b59622a 100644
@@ -35,8 +35,8 @@ struct ecdsa_signature_ctx {
  static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
  				  const void *value, size_t vlen, unsigned int ndigits)
  {
-	size_t keylen = ndigits * sizeof(u64);
-	ssize_t diff = vlen - keylen;
+	size_t bufsize = ndigits * sizeof(u64);

why not just "* 8"? using sizeof here makes this function only unreadable.

Quoted 1 line

'unreadable' is a 'strong' word ...

so what is the gain when writing sizeof(u64)?

BR, Jarkko

author reviewer
#21 lore raw

Re: [PATCH v4 09/12] crypto: ecdsa - Rename keylen to bufsize where necessary

Quoted 28 lines · Jarkko Sakkinen
Quoted 27 lines · Stefan Berger
Quoted 23 lines · Jarkko Sakkinen
Quoted 14 lines · Stefan Berger

In some cases the name keylen does not reflect the purpose of the variable anymore once NIST P521 is used but it is the size of the buffer. There- for, rename keylen to bufsize where appropriate.

Signed-off-by Stefan Berger <[email protected]>
---
   crypto/ecdsa.c | 12 ++++++------
   1 file changed, 6 insertions(+), 6 deletions(-)
crypto/ecdsa.c +0 -0
index 4daefb40c37a..4e847b59622a 100644

crypto/ecdsa.c struct ecdsa_signature_ctx { · line 38

Quoted 6 lines
crypto/ecdsa.c +1 -2
@@ -35,8 +35,8 @@ struct ecdsa_signature_ctx {
   static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
   				  const void *value, size_t vlen, unsigned int ndigits)
   {
-	size_t keylen = ndigits * sizeof(u64);
-	ssize_t diff = vlen - keylen;
+	size_t bufsize = ndigits * sizeof(u64);

why not just "* 8"? using sizeof here makes this function only unreadable.

Quoted 3 lines
Quoted 1 line

'unreadable' is a 'strong' word ...

so what is the gain when writing sizeof(u64)?

It matches existing code and a digit is a 'u64'.

Quoted 2 lines

BR, Jarkko

author reviewer
#22 lore raw

PATCH v4 10/12 crypto: ecdsa - Register NIST P521 and extend test suite

In reply to Stefan Berger

Register NIST P521 as an akcipher and extend the testmgr with NIST P521-specific test vectors.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/ecdsa.c   |  30 ++++++++++
 crypto/testmgr.c |   7 +++
 crypto/testmgr.h | 146 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 183 insertions(+)
crypto/ecdsa.c +30 -0
index 4e847b59622a..894599f1885f 100644
@@ -269,6 +269,28 @@ static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
 	return DIV_ROUND_UP(ctx->curve->nbits, 8);
 }
 
+static int ecdsa_nist_p521_init_tfm(struct crypto_akcipher *tfm)
+{
+	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+
+	return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P521);
+}
+
+static struct akcipher_alg ecdsa_nist_p521 = {
+	.verify = ecdsa_verify,
+	.set_pub_key = ecdsa_set_pub_key,
+	.max_size = ecdsa_max_size,
+	.init = ecdsa_nist_p521_init_tfm,
+	.exit = ecdsa_exit_tfm,
+	.base = {
+		.cra_name = "ecdsa-nist-p521",
+		.cra_driver_name = "ecdsa-nist-p521-generic",
+		.cra_priority = 100,
+		.cra_module = THIS_MODULE,
+		.cra_ctxsize = sizeof(struct ecc_ctx),
+	},
+};
+
 static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
 {
 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);

@@ -352,8 +374,15 @@ static int __init ecdsa_init(void)
 	if (ret)
 		goto nist_p384_error;
 
+	ret = crypto_register_akcipher(&ecdsa_nist_p521);
+	if (ret)
+		goto nist_p521_error;
+
 	return 0;
 
+nist_p521_error:
+	crypto_unregister_akcipher(&ecdsa_nist_p384);
+
 nist_p384_error:
 	crypto_unregister_akcipher(&ecdsa_nist_p256);
 

@@ -369,6 +398,7 @@ static void __exit ecdsa_exit(void)
 		crypto_unregister_akcipher(&ecdsa_nist_p192);
 	crypto_unregister_akcipher(&ecdsa_nist_p256);
 	crypto_unregister_akcipher(&ecdsa_nist_p384);
+	crypto_unregister_akcipher(&ecdsa_nist_p521);
 }
 
 subsys_initcall(ecdsa_init);
crypto/testmgr.c +7 -0
index c26aeda85787..a017b4ad119b 100644
@@ -5097,6 +5097,13 @@ static const struct alg_test_desc alg_test_descs[] = {
 		.suite = {
 			.akcipher = __VECS(ecdsa_nist_p384_tv_template)
 		}
+	}, {
+		.alg = "ecdsa-nist-p521",
+		.test = alg_test_akcipher,
+		.fips_allowed = 1,
+		.suite = {
+			.akcipher = __VECS(ecdsa_nist_p521_tv_template)
+		}
 	}, {
 		.alg = "ecrdsa",
 		.test = alg_test_akcipher,
crypto/testmgr.h +146 -0

152 lines not on this page · raw message

Signature · 1 line
2.43.0
author reviewer
#23 lore raw

PATCH v4 11/12 crypto: asymmetric_keys - Adjust signature size calculation for NIST P521

In reply to Stefan Berger

Adjust the calculation of the maximum signature size for support of NIST P521. While existing curves may prepend a 0 byte to their coordinates (to make the number positive), NIST P521 will not do this since only the first bit in the most significant byte is used.

If the encoding of the x & y coordinates requires more than 128 bytes then an additional byte is needed for the encoding of the length. Take this into account when calculating the maximum signature size.

Signed-off-by Stefan Berger <[email protected]>
---
 crypto/asymmetric_keys/public_key.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)
crypto/asymmetric_keys/public_key.c +13 -1
index e5f22691febd..247d42580f7c 100644
@@ -233,6 +233,7 @@ static int software_key_query(const struct kernel_pkey_params *params,
 	info->key_size = len * 8;
 
 	if (strncmp(pkey->pkey_algo, "ecdsa", 5) == 0) {
+		int slen = len;
 		/*
 		 * ECDSA key sizes are much smaller than RSA, and thus could
 		 * operate on (hashed) inputs that are larger than key size.

@@ -246,8 +247,19 @@ static int software_key_query(const struct kernel_pkey_params *params,
 		 * Verify takes ECDSA-Sig (described in RFC 5480) as input,
 		 * which is actually 2 'key_size'-bit integers encoded in
 		 * ASN.1.  Account for the ASN.1 encoding overhead here.
+		 *
+		 * NIST P192/256/384 may prepend a '0' to a coordinate to
+		 * indicate a positive integer. NIST P521 never needs it.
 		 */
-		info->max_sig_size = 2 * (len + 3) + 2;
+		if (strcmp(pkey->pkey_algo, "ecdsa-nist-p521") != 0)
+			slen += 1;
+		/* Length of encoding the x & y coordinates */
+		slen = 2 * (slen + 2);
+		/*
+		 * If coordinate encoding takes more than 128 bytes then an
+		 * additional byte for length encoding is needed.
+		 */
+		info->max_sig_size = 1 + (slen >= 128) + 1 + slen;
 	} else {
 		info->max_data_size = len;
 		info->max_sig_size = len;
Signature · 1 line
2.43.0
maintainer Reviewed-by on v4 11/12
#24 lore raw

Re: [PATCH v4 11/12] crypto: asymmetric_keys - Adjust signature size calculation for NIST P521

Quoted 10 lines · Stefan Berger

Adjust the calculation of the maximum signature size for support of NIST P521. While existing curves may prepend a 0 byte to their coordinates (to make the number positive), NIST P521 will not do this since only the first bit in the most significant byte is used.

If the encoding of the x & y coordinates requires more than 128 bytes then an additional byte is needed for the encoding of the length. Take this into account when calculating the maximum signature size.

Signed-off-by Stefan Berger <[email protected]>
Reviewed-by Lukas Wunner <[email protected]>
author reviewer
#25 lore raw

Re: [PATCH v4 11/12] crypto: asymmetric_keys - Adjust signature size calculation for NIST P521

Quoted 6 lines · Lukas Wunner
Quoted 5 lines · Stefan Berger

Adjust the calculation of the maximum signature size for support of NIST P521. While existing curves may prepend a 0 byte to their coordinates (to make the number positive), NIST P521 will not do this since only the first bit in the most significant byte is used.

Quoted 8 lines
Quoted 5 lines

If the encoding of the x & y coordinates requires more than 128 bytes then an additional byte is needed for the encoding of the length. Take this into account when calculating the maximum signature size.

Signed-off-by Stefan Berger <[email protected]>
Reviewed-by Lukas Wunner <[email protected]>

Thanks. I have to adjust the commit text and comment in the patch, though. It should be '... requires at least 128 bytes then ...'

author reviewer
#26 lore raw

PATCH v4 12/12 crypto: x509 - Add OID for NIST P521 and extend parser for it

In reply to Stefan Berger

Enable the x509 parser to accept NIST P521 certificates and add the OID for ansip521r1, which is the identifier for NIST P521.

Cc David Howells <[email protected]>
Signed-off-by Stefan Berger <[email protected]>
---
 crypto/asymmetric_keys/x509_cert_parser.c | 3 +++
 include/linux/oid_registry.h              | 1 +
 2 files changed, 4 insertions(+)
crypto/asymmetric_keys/x509_cert_parser.c +3 -0
index 487204d39426..99f809b7910b 100644
@@ -538,6 +538,9 @@ int x509_extract_key_data(void *context, size_t hdrlen,
 		case OID_id_ansip384r1:
 			ctx->cert->pub->pkey_algo = "ecdsa-nist-p384";
 			break;
+		case OID_id_ansip521r1:
+			ctx->cert->pub->pkey_algo = "ecdsa-nist-p521";
+			break;
 		default:
 			return -ENOPKG;
 		}
include/linux/oid_registry.h +1 -0
index 3921fbed0b28..af16d96fbbf2 100644
@@ -65,6 +65,7 @@ enum OID {
 	OID_Scram,			/* 1.3.6.1.5.5.14 */
 	OID_certAuthInfoAccess,		/* 1.3.6.1.5.5.7.1.1 */
 	OID_id_ansip384r1,		/* 1.3.132.0.34 */
+	OID_id_ansip521r1,		/* 1.3.132.0.35 */
 	OID_sha256,			/* 2.16.840.1.101.3.4.2.1 */
 	OID_sha384,			/* 2.16.840.1.101.3.4.2.2 */
 	OID_sha512,			/* 2.16.840.1.101.3.4.2.3 */
Signature · 1 line
2.43.0
maintainer Tested-by on the v4 series
#27 lore raw
In reply to Stefan Berger
Quoted 10 lines · Stefan Berger

This series adds support for the NIST P521 curve to the ecdsa module to enable signature verification with it.

An issue with the current code in ecdsa is that it assumes that input arrays providing key coordinates for example, are arrays of digits (a 'digit' is a 'u64'). This works well for all currently supported curves, such as NIST P192/256/384, but does not work for NIST P521 where coordinates are 8 digits + 2 bytes long. So some of the changes deal with converting byte arrays to digits and adjusting tests on input byte array lengths to tolerate arrays not providing multiples of 8 bytes.

When respinning this series as v5, feel free to add my

Tested-by Lukas Wunner <[email protected]>

I cherry-picked the commits from your nist_p521.v5 branch...

https://github.com/stefanberger/linux-ima-namespaces/commits/nist_p521.v5/

...onto my development branch for PCI device authentication...

https://github.com/l1k/linux/commits/doe

...and tested against qemu+libspdm that an emulated NVMe drive is able to present a valid signature using NIST P521 + SHA384 which can be verified correctly by the kernel.

I needed to fix up two of my patches, one which adds P1363 signature format support to the kernel and another fixup to add NIST P521 support to the in-kernel SPDM library (two top-most commits on my above-linked development branch).

I performed this test against your f81547267725 head and notice that you pushed a new version today (with "curve->nbits == 521" instead of strcmp), but I'm confident those two small changes wouldn't alter the outcone, hence my Tested-by stands.

Thanks,

Lukas

author reviewer
#28 lore raw
Quoted 12 lines · Lukas Wunner
Quoted 10 lines · Stefan Berger

This series adds support for the NIST P521 curve to the ecdsa module to enable signature verification with it.

An issue with the current code in ecdsa is that it assumes that input arrays providing key coordinates for example, are arrays of digits (a 'digit' is a 'u64'). This works well for all currently supported curves, such as NIST P192/256/384, but does not work for NIST P521 where coordinates are 8 digits + 2 bytes long. So some of the changes deal with converting byte arrays to digits and adjusting tests on input byte array lengths to tolerate arrays not providing multiples of 8 bytes.

Quoted 3 lines

When respinning this series as v5, feel free to add my

Tested-by Lukas Wunner <[email protected]>

Thanks.

Quoted 6 lines

I cherry-picked the commits from your nist_p521.v5 branch...

https://github.com/stefanberger/linux-ima-namespaces/commits/nist_p521.v5/

Quoted 7 lines

...onto my development branch for PCI device authentication...

https://github.com/l1k/linux/commits/doe

...and tested against qemu+libspdm that an emulated NVMe drive is able to present a valid signature using NIST P521 + SHA384 which can be verified correctly by the kernel.

FYI: I have a PR for a test suite here as well:

https://github.com/stefanberger/eckey-testing/pull/1

Quoted 15 lines

I needed to fix up two of my patches, one which adds P1363 signature format support to the kernel and another fixup to add NIST P521 support to the in-kernel SPDM library (two top-most commits on my above-linked development branch).

I performed this test against your f81547267725 head and notice that you pushed a new version today (with "curve->nbits == 521" instead of strcmp), but I'm confident those two small changes wouldn't alter the outcone, hence my Tested-by stands.

Thanks,

Lukas