Templatize ecdsa signature decoding

If <linux/asn1_decoder.h> is the first header included from a .c file (due to headers being sorted alphabetically), the compiler complains:

include/linux/asn1_decoder.h:18:29: error: unknown type name 'size_t'

Fix it.

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

---
  include/linux/asn1_decoder.h | 1 +
  1 file changed, 1 insertion(+)

include/linux/asn1_decoder.h +1 -0

index 83f9c6e1e5e9..b41bce82a191 100644
@@ -9,6 +9,7 @@
  #define _LINUX_ASN1_DECODER_H
 
  #include <linux/asn1.h>
+#include <linux/types.h>
 
  struct asn1_decoder;
 

If <linux/asn1_decoder.h> is the first header included from a .c file (due to headers being sorted alphabetically), the compiler complains:

include/linux/asn1_decoder.h:18:29: error: unknown type name 'size_t'

Fix it.

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

---
 include/linux/asn1_decoder.h | 1 +
 1 file changed, 1 insertion(+)

include/linux/asn1_decoder.h +1 -0

index 83f9c6e1e5e9..b41bce82a191 100644
@@ -9,6 +9,7 @@
 #define _LINUX_ASN1_DECODER_H
 
 #include <linux/asn1.h>
+#include <linux/types.h>
 
 struct asn1_decoder;
 

Commit 6cb8815f41a9 ("crypto: sig - Add interface for sign/verify") introduced an API which accepts kernel buffers instead of sglists for signature generation and verification.

Commit 63ba4d67594a ("KEYS: asymmetric: Use new crypto interface without scatterlists") converted the sole user in the tree to the new API.

Although the API externally accepts kernel buffers, internally it still converts them to sglists, which results in overhead for asymmetric algorithms because they need to copy the sglists back into kernel buffers.

Take the next step and switch signature verification over to using kernel buffers internally, thereby avoiding the sglists overhead.

Because all ->verify implementations are synchronous, forego invocation of crypto_akcipher_sync_{prep,post}() and call crypto_akcipher_verify() directly from crypto_sig_verify().

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

include/crypto/akcipher.h +22 -15

index 18a10cad07aa..2c5bc35d297a 100644
@@ -16,28 +16,39 @@
  *
  * @base:	Common attributes for async crypto requests
  * @src:	Source data
- *		For verify op this is signature + digest, in that case
- *		total size of @src is @src_len + @dst_len.
- * @dst:	Destination data (Should be NULL for verify op)
+ * @dst:	Destination data
  * @src_len:	Size of the input buffer
- *		For verify op it's size of signature part of @src, this part
- *		is supposed to be operated by cipher.
- * @dst_len:	Size of @dst buffer (for all ops except verify).
+ * @dst_len:	Size of @dst buffer
  *		It needs to be at least	as big as the expected result
  *		depending on the operation.
  *		After operation it will be updated with the actual size of the
  *		result.
  *		In case of error where the dst sgl size was insufficient,
  *		it will be updated to the size required for the operation.
- *		For verify op this is size of digest part in @src.
+ * @sig:	Signature
+ * @digest:	Digest
+ * @sig_len:	Size of @sig
+ * @digest_len:	Size of @digest
  * @__ctx:	Start of private context data
  */
 struct akcipher_request {
 	struct crypto_async_request base;
-	struct scatterlist *src;
-	struct scatterlist *dst;
-	unsigned int src_len;
-	unsigned int dst_len;
+	union {
+		struct {
+			/* sign, encrypt, decrypt operations */
+			struct scatterlist *src;
+			struct scatterlist *dst;
+			unsigned int src_len;
+			unsigned int dst_len;
+		};
+		struct {
+			/* verify operation */
+			const void *sig;
+			const void *digest;
+			unsigned int sig_len;
+			unsigned int digest_len;
+		};
+	};
 	void *__ctx[] CRYPTO_MINALIGN_ATTR;
 };
 

@@ -242,20 +253,18 @@ static inline void akcipher_request_set_callback(struct akcipher_request *req,
  * Sets parameters required by crypto operation
  *
  * @req:	public key request
- * @src:	ptr to input scatter list
- * @dst:	ptr to output scatter list or NULL for verify op
- * @src_len:	size of the src input scatter list to be processed
- * @dst_len:	size of the dst output scatter list or size of signature

include/crypto/akcipher.h +2 -6

 					      unsigned int src_len,
 					      unsigned int dst_len)
 {
-	req->src = src;
-	req->dst = dst;
+	req->sig = src;
+	req->digest = dst;
 	req->src_len = src_len;
 	req->dst_len = dst_len;
 }

@@ -372,10 +381,6 @@ static inline int crypto_akcipher_sign(struct akcipher_request *req)
  *
  * @req:	asymmetric key request
  *
- * Note: req->dst should be NULL, req->src should point to SG of size
- * (req->src_size + req->dst_size), containing signature (of req->src_size
- * length) with appended digest (of req->dst_size length).
- *
  * Return: zero on verification success; error code in case of error.
  */
 static inline int crypto_akcipher_verify(struct akcipher_request *req)

Quoted 12 lines · On Mon, 29 Jul 2024 15:48:00 +0200 Lukas Wunner <[email protected]> wrote:

Commit 6cb8815f41a9 ("crypto: sig - Add interface for sign/verify") introduced an API which accepts kernel buffers instead of sglists for signature generation and verification.

Commit 63ba4d67594a ("KEYS: asymmetric: Use new crypto interface without scatterlists") converted the sole user in the tree to the new API.

Although the API externally accepts kernel buffers, internally it still converts them to sglists, which results in overhead for asymmetric algorithms because they need to copy the sglists back into kernel buffers.

Quoted 6 lines

Take the next step and switch signature verification over to using kernel buffers internally, thereby avoiding the sglists overhead.

Because all ->verify implementations are synchronous, forego invocation of crypto_akcipher_sync_{prep,post}() and call crypto_akcipher_verify() directly from crypto_sig_verify().

Rather than passing scatter lists and buffers
via the same function void akcipher_request_set_crypt()
why not add a variant that takes buffers for signing cases so that you can maintain the scatterlist pointers for the encrypt/decrypt cases?

Maybe it's worth a 'special' variant.
static inline void akcipher_request_set_crypt_for_verify() so that you can keep the other list typed and not rely on overlapping pointer fields via the union.

Commit 6cb8815f41a9 ("crypto: sig - Add interface for sign/verify") introduced an API which accepts kernel buffers instead of sglists for signature generation and verification.

Commit 63ba4d67594a ("KEYS: asymmetric: Use new crypto interface without scatterlists") converted the sole user in the tree to the new API.

Although the API externally accepts kernel buffers, internally it still converts them to sglists, which results in overhead for asymmetric algorithms because they need to copy the sglists back into kernel buffers.

Take the next step and switch signature verification over to using kernel buffers internally, thereby avoiding the sglists overhead.

Because all ->verify implementations are synchronous, forego invocation of crypto_akcipher_sync_{prep,post}() and call crypto_akcipher_verify() directly from crypto_sig_verify().

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

---
 crypto/akcipher.c         | 11 +++-----
 crypto/ecdsa.c            | 27 +++++---------------
 crypto/ecrdsa.c           | 28 +++++++--------------
 crypto/rsa-pkcs1pad.c     | 27 ++++++++------------
 crypto/sig.c              | 24 +++++++++---------
 crypto/testmgr.c          | 12 ++++-----
 include/crypto/akcipher.h | 53 +++++++++++++++++++++------------------
 7 files changed, 76 insertions(+), 106 deletions(-)

Quoted 12 lines · Lukas Wunner

Commit 6cb8815f41a9 ("crypto: sig - Add interface for sign/verify") introduced an API which accepts kernel buffers instead of sglists for signature generation and verification.

Commit 63ba4d67594a ("KEYS: asymmetric: Use new crypto interface without scatterlists") converted the sole user in the tree to the new API.

Although the API externally accepts kernel buffers, internally it still converts them to sglists, which results in overhead for asymmetric algorithms because they need to copy the sglists back into kernel buffers.

Quoted 6 lines

Take the next step and switch signature verification over to using kernel buffers internally, thereby avoiding the sglists overhead.

Because all ->verify implementations are synchronous, forego invocation of crypto_akcipher_sync_{prep,post}() and call crypto_akcipher_verify() directly from crypto_sig_verify().

The link between sig and akcipher is meant to be temporary. The plan is to create a new low-level API for sig and then migrate the signature code over to that from akcipher.

Yes we do want to get rid of the unnecessary SG list ops but is it possible to side-step this for your work? If not perhaps you could help by creating the low-level API for sig? :)

I'm looking through the code right now to understand what would be necessary to get there.

One issue I see is an algorithm name collision in rsa-pkcs1pad.c:
I think I'd have to register two instances in pkcs1pad_create(), an akcipher_instance and a sig_instance.

The last couple of days I've been contemplating amending struct akcipher_alg with additional callbacks to get the max_sig_size and max_data_size. For RSA it's the same as the keysize (which is available through the existing ->max_size callback), but for ECDSA it's different depending on the template. Adding those new callbacks to a new struct sig_alg would be cleaner of course than shoehorning them into struct akcipher_alg.

The link between sig and akcipher is meant to be temporary. The plan is to create a new low-level API for sig and then migrate the signature code over to that from akcipher.

Yes we do want to get rid of the unnecessary SG list ops but is it possible to side-step this for your work? If not perhaps you could help by creating the low-level API for sig? :)

That's user space ABI, so we're stuck with it. The user space ABI combines sign/verify and encrypt/decrypt in common structs.

When extracting a signature component r or s from an ASN.1-encoded integer, ecdsa_get_signature_rs() subtracts the expected length "bufsize" from the ASN.1 length "vlen" (both of unsigned type size_t) and stores the result in "diff" (of signed type ssize_t).

This results in a signed integer overflow if vlen > SSIZE_MAX + bufsize.

The kernel is compiled with -fno-strict-overflow, which implies -fwrapv, meaning signed integer overflow is not undefined behavior. And the function does check for overflow:

if (-diff >= bufsize)
return -EINVAL;

So the code is fine in principle but not very obvious. In the future it might trigger a false-positive with CONFIG_UBSAN_SIGNED_WRAP=y.

Avoid by comparing the two unsigned variables directly and erroring out if "vlen" is too large.

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

---
  crypto/ecdsa.c | 17 ++++-------------
  1 file changed, 4 insertions(+), 13 deletions(-)

crypto/ecdsa.c +0 -1

index f63731fb7535..03f608132242 100644
@@ -35,29 +35,20 @@ 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 bufsize = ndigits * sizeof(u64);
-	ssize_t diff = vlen - bufsize;
  	const char *d = value;
 

crypto/ecdsa.c +0 -1

  		/* skip over leading zeros that make 'value' a positive int */
  		if (*d == 0) {
  			vlen -= 1;
-			diff--;

When extracting a signature component r or s from an ASN.1-encoded integer, ecdsa_get_signature_rs() subtracts the expected length "bufsize" from the ASN.1 length "vlen" (both of unsigned type size_t) and stores the result in "diff" (of signed type ssize_t).

This results in a signed integer overflow if vlen > SSIZE_MAX + bufsize.

The kernel is compiled with -fno-strict-overflow, which implies -fwrapv, meaning signed integer overflow is not undefined behavior. And the function does check for overflow:

if (-diff >= bufsize)
return -EINVAL;

So the code is fine in principle but not very obvious. In the future it might trigger a false-positive with CONFIG_UBSAN_SIGNED_WRAP=y.

Avoid by comparing the two unsigned variables directly and erroring out if "vlen" is too large.

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

---
 crypto/ecdsa.c | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

crypto/ecdsa.c +0 -0

index f63731fb7535..03f608132242 100644

crypto/ecdsa.c +3 -11

 		return -EINVAL;
 
-	/* diff = 0: 'value' has exacly the right size
-	 * diff > 0: 'value' has too many bytes; one leading zero is allowed that
-	 *           makes the value a positive integer; error on more
-	 * diff < 0: 'value' is missing leading zeros
-	 */
-	if (diff > 0) {
+	if (vlen > bufsize) {
 		/* skip over leading zeros that make 'value' a positive int */
 		if (*d == 0) {
 			vlen -= 1;
-			diff--;
 			d++;
-		}
-		if (diff)
+		} else {
 			return -EINVAL;
+		}
 	}
-	if (-diff >= bufsize)
-		return -EINVAL;
 
 	ecc_digits_from_bytes(d, vlen, dest, ndigits);
 

Unlike the rsa driver, which separates signature decoding and signature verification into two steps, the ecdsa driver does both in one.

This restricts users to the one signature format currently supported (X9.62) and prevents addition of others such as P1363, which is needed by the forthcoming SPDM library (Security Protocol and Data Model) for PCI device authentication.

Per Herbert's suggestion, change ecdsa to use a "raw" signature encoding and then implement X9.62 and P1363 as templates which convert their respective encodings to the raw one. One may then specify "x962(ecdsa-nist-XXX)" or "p1363(ecdsa-nist-XXX)" to pick the encoding.

The present commit moves X9.62 decoding to a template. A separate commit is going to introduce another template for P1363 decoding.

The ecdsa driver internally represents a signature as two u64 arrays of size ECC_MAX_BYTES. This appears to be the most natural choice for the raw format as it can directly be used for verification without having to further decode signature data or copy it around.

Repurpose all the existing test vectors for "x962(ecdsa-nist-XXX)" and create a duplicate of them to test the raw encoding.

Link https://lore.kernel.org/all/[email protected]/ open here

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

---
 crypto/Makefile                     |   3 +-
 crypto/asymmetric_keys/public_key.c |   3 +
 crypto/ecdsa-x962.c                 | 211 ++++++++
 crypto/ecdsa.c                      |  86 +--
 crypto/testmgr.c                    |  27 +
 crypto/testmgr.h                    | 813 +++++++++++++++++++++++++++-
 include/crypto/internal/ecc.h       |   1 +
 7 files changed, 1077 insertions(+), 67 deletions(-)
 create mode 100644 crypto/ecdsa-x962.c

crypto/ecdsa-x962.c new file +27 -0

new file mode 100644
index 000000000000..ff2da5be1355
@@ -0,0 +1,211 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * ECDSA X9.62 signature encoding
+ *
+ * Copyright (c) 2021 IBM Corporation
+ * Copyright (c) 2024 Intel Corporation
+ */
+
+#include <linux/asn1_decoder.h>
+#include <linux/err.h>
+#include <linux/module.h>
+#include <crypto/akcipher.h>
+#include <crypto/algapi.h>
+#include <crypto/internal/akcipher.h>
+#include <crypto/internal/ecc.h>
+
+#include "ecdsasignature.asn1.h"
+
+struct ecdsa_x962_ctx {
+	struct crypto_akcipher *child;
+};
+
+struct ecdsa_x962_request {
+	u64 r[ECC_MAX_DIGITS];
+	u64 s[ECC_MAX_DIGITS];
+	struct akcipher_request child_req;
+};

crypto/ecdsa-x962.c new file +17 -0

+		return -EINVAL;
+
+	if (vlen > bufsize) {
+		/* skip over leading zeros that make 'value' a positive int */
+		if (*d == 0) {
+			vlen -= 1;
+			d++;
+		} else {
+			return -EINVAL;
+		}
+	}
+
+	ecc_digits_from_bytes(d, vlen, dest, ndigits);
+
+	return 0;
+}
+

crypto/ecdsa-x962.c new file +19 -0

+static int ecdsa_x962_create(struct crypto_template *tmpl, struct rtattr **tb)
+{
+	struct crypto_akcipher_spawn *spawn;
+	struct akcipher_instance *inst;
+	struct akcipher_alg *ecdsa_alg;
+	u32 mask;
+	int err;
+
+	err = crypto_check_attr_type(tb, CRYPTO_ALG_TYPE_AKCIPHER, &mask);
+	if (err)
+		return err;
+
+	inst = kzalloc(sizeof(*inst) + sizeof(*spawn), GFP_KERNEL);
+	if (!inst)
+		return -ENOMEM;
+
+	spawn = akcipher_instance_ctx(inst);
+
+	err = crypto_grab_akcipher(spawn, akcipher_crypto_instance(inst),

crypto/ecdsa-x962.c new file +13 -0

+	err = crypto_inst_setname(akcipher_crypto_instance(inst), tmpl->name,
+				  &ecdsa_alg->base);
+	if (err)
+		goto err_free_inst;
+
+	inst->alg.base.cra_priority = ecdsa_alg->base.cra_priority;
+	inst->alg.base.cra_ctxsize = sizeof(struct ecdsa_x962_ctx);
+
+	inst->alg.init = ecdsa_x962_init_tfm;
+	inst->alg.exit = ecdsa_x962_exit_tfm;
+
+	inst->alg.verify = ecdsa_x962_verify;
+	inst->alg.max_size = ecdsa_x962_max_size;

crypto/ecdsa-x962.c new file +2 -0

+}
+

crypto/ecdsa-x962.c line 37

Quoted 8 lines · On Mon, 29 Jul 2024 15:50:00 +0200 Lukas Wunner <[email protected]> wrote:

crypto/ecdsa-x962.c new file +8 -0

+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 bufsize = ndigits * sizeof(u64);
+	const char *d = value;
+
+	if (!value || !vlen || vlen > bufsize + 1)

Assuming previous musing correct middle test isn't needed. Maybe want to keep it though. Up to you.

crypto/ecdsa-x962.c line 179

Quoted 4 lines

crypto/ecdsa-x962.c new file +4 -0

+	err = -EINVAL;
+	if (strncmp(ecdsa_alg->base.cra_name, "ecdsa", 5) != 0)
+		goto err_free_inst;
+

	if (cmp(ecdsa_alg->base.cra_name, "ecdsa", 5) != 0) {
		err = -EINVAL;
		goto err_free_inst;
	}

Seems more readable to me.

crypto/ecdsa-x962.c line 202

Quoted 6 lines

crypto/ecdsa-x962.c new file +6 -0

+	err = akcipher_register_instance(tmpl, inst);
+	if (err) {
+err_free_inst:
+		ecdsa_x962_free(inst);
+	}
+	return err;

I'd rather see a separate error path even if it's a little more code.

	if (err)
		goto err_free_inst;

	return 0;

err_free_inst:

	ecdsa_x862_free(inst)
	return err;

Quoted 1 line

+}

Alternatively to the X9.62 encoding of ecdsa signatures, which uses ASN.1 and is already supported by the kernel, there's another common encoding called P1363. It stores r and s as the concatenation of two big endian, unsigned integers. The name originates from IEEE P1363.

Add a P1363 template in support of the forthcoming SPDM library (Security Protocol and Data Model) for PCI device authentication.

P1363 is prescribed by SPDM 1.2.1 margin no 44:

"For ECDSA signatures, excluding SM2, in SPDM, the signature shall be
the concatenation of r and s. The size of r shall be the size of the selected curve. Likewise, the size of s shall be the size of the selected curve. See BaseAsymAlgo in NEGOTIATE_ALGORITHMS for the size of r and s. The byte order for r and s shall be in big endian order. When placing ECDSA signatures into an SPDM signature field, r shall come first followed by s."

Link https://www.dmtf.org/sites/default/files/standards/documents/DSP0274_1.2.1.pdf

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

crypto/ecdsa-p1363.c new file +39 -0

new file mode 100644
index 000000000000..c0610d88aa9e
@@ -0,0 +1,155 @@
 
+static int ecdsa_p1363_create(struct crypto_template *tmpl, struct rtattr **tb)
+{
+	struct crypto_akcipher_spawn *spawn;
+	struct akcipher_instance *inst;
+	struct akcipher_alg *ecdsa_alg;
+	u32 mask;
+	int err;
+
+	err = crypto_check_attr_type(tb, CRYPTO_ALG_TYPE_AKCIPHER, &mask);
+	if (err)
+		return err;
+
+	inst = kzalloc(sizeof(*inst) + sizeof(*spawn), GFP_KERNEL);
+	if (!inst)
+		return -ENOMEM;
+
+	spawn = akcipher_instance_ctx(inst);
+
+	err = crypto_grab_akcipher(spawn, akcipher_crypto_instance(inst),
+				   crypto_attr_alg_name(tb[1]), 0, mask);
+	if (err)
+		goto err_free_inst;
+
+	ecdsa_alg = crypto_spawn_akcipher_alg(spawn);
+
+	err = -EINVAL;
+	if (strncmp(ecdsa_alg->base.cra_name, "ecdsa", 5) != 0)
+		goto err_free_inst;
+
+	err = crypto_inst_setname(akcipher_crypto_instance(inst), tmpl->name,
+				  &ecdsa_alg->base);
+	if (err)
+		goto err_free_inst;
+
+	inst->alg.base.cra_priority = ecdsa_alg->base.cra_priority;
+	inst->alg.base.cra_ctxsize = sizeof(struct ecdsa_p1363_ctx);
+
+	inst->alg.init = ecdsa_p1363_init_tfm;
+	inst->alg.exit = ecdsa_p1363_exit_tfm;

crypto/ecdsa-p1363.c new file +4 -0

+		ecdsa_p1363_free(inst);
+	}
+	return err;
+}