* [PATCH v4 1/3] crypto: Add support for ECDSA signature verification
2021-01-28 0:14 [PATCH v4 0/3] Add support for x509 certs with NIST p256 and p192 keys Stefan Berger
@ 2021-01-28 0:14 ` Stefan Berger
2021-01-29 1:34 ` Herbert Xu
2021-01-28 0:14 ` [PATCH v4 2/3] x509: Detect sm2 keys by their parameters OID Stefan Berger
` (2 subsequent siblings)
3 siblings, 1 reply; 9+ messages in thread
From: Stefan Berger @ 2021-01-28 0:14 UTC (permalink / raw)
To: keyrings, linux-crypto
Cc: linux-kernel, patrick, Stefan Berger, Herbert Xu, David S. Miller
From: Stefan Berger <stefanb@linux.ibm.com>
Add support for parsing the parameters of a NIST P256 or NIST P192 key.
Enable signature verification using these keys.
Signed-off-by: Stefan Berger <stefanb@linux.ibm.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: linux-crypto@vger.kernel.org
---
crypto/Makefile | 9 +-
crypto/ecc.c | 279 +++++++++++++++++++++++++++++++++++++
crypto/ecc.h | 2 +
crypto/ecdsasignature.asn1 | 4 +
4 files changed, 293 insertions(+), 1 deletion(-)
create mode 100644 crypto/ecdsasignature.asn1
diff --git a/crypto/Makefile b/crypto/Makefile
index b279483fba50..767f6b71aa20 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -50,6 +50,14 @@ sm2_generic-y += sm2.o
obj-$(CONFIG_CRYPTO_SM2) += sm2_generic.o
+$(obj)/ecdsasignature.asn1.o: $(obj)/ecdsasignature.asn1.c $(obj)/ecdsasignature.asn1.h
+$(obj)/ecc.o: $(obj)/ecdsasignature.asn1.h
+
+ecc_generic-y += ecdsasignature.asn1.o
+ecc_generic-y += ecc.o
+
+obj-$(CONFIG_CRYPTO_ECC) += ecc_generic.o
+
crypto_acompress-y := acompress.o
crypto_acompress-y += scompress.o
obj-$(CONFIG_CRYPTO_ACOMP2) += crypto_acompress.o
@@ -172,7 +180,6 @@ obj-$(CONFIG_CRYPTO_USER_API_RNG) += algif_rng.o
obj-$(CONFIG_CRYPTO_USER_API_AEAD) += algif_aead.o
obj-$(CONFIG_CRYPTO_ZSTD) += zstd.o
obj-$(CONFIG_CRYPTO_OFB) += ofb.o
-obj-$(CONFIG_CRYPTO_ECC) += ecc.o
obj-$(CONFIG_CRYPTO_ESSIV) += essiv.o
obj-$(CONFIG_CRYPTO_CURVE25519) += curve25519-generic.o
diff --git a/crypto/ecc.c b/crypto/ecc.c
index c80aa25994a0..3636f9d17eaf 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -29,13 +29,18 @@
#include <linux/slab.h>
#include <linux/swab.h>
#include <linux/fips.h>
+#include <crypto/internal/akcipher.h>
+#include <crypto/akcipher.h>
#include <crypto/ecdh.h>
#include <crypto/rng.h>
#include <asm/unaligned.h>
#include <linux/ratelimit.h>
+#include <linux/asn1_decoder.h>
+#include <linux/scatterlist.h>
#include "ecc.h"
#include "ecc_curve_defs.h"
+#include "ecdsasignature.asn1.h"
typedef struct {
u64 m_low;
@@ -1542,4 +1547,278 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
}
EXPORT_SYMBOL(crypto_ecdh_shared_secret);
+struct ecc_ctx {
+ const struct ecc_curve *curve;
+ struct ecc_point *pub_key;
+};
+
+struct ecdsa_signature_ctx {
+ const struct ecc_curve *curve;
+ u64 r[ECC_MAX_DIGITS];
+ u64 s[ECC_MAX_DIGITS];
+};
+
+/*
+ * Get the r and s components of a signature from the X509 certificate.
+ */
+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;
+ const char *d = value;
+ u8 rs[ECC_MAX_BYTES];
+
+ if (!value || !vlen)
+ 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, which we add
+ */
+ if (diff > 0) {
+ /* skip over leading zeros that make 'value' a positive int */
+ if (*d == 0) {
+ vlen -= 1;
+ diff--;
+ d++;
+ }
+ if (diff)
+ return -EINVAL;
+ }
+ if (-diff >= keylen)
+ return -EINVAL;
+
+ if (diff) {
+ /* leading zeros not given in 'value' */
+ memset(rs, 0, -diff);
+ }
+
+ memcpy(&rs[-diff], d, vlen);
+
+ ecc_swap_digits((u64 *)rs, dest, ndigits);
+
+ return 0;
+}
+
+int ecdsa_get_signature_r(void *context, size_t hdrlen, unsigned char tag,
+ const void *value, size_t vlen)
+{
+ struct ecdsa_signature_ctx *sig = context;
+
+ return ecdsa_get_signature_rs(sig->r, hdrlen, tag, value, vlen,
+ sig->curve->g.ndigits);
+}
+
+int ecdsa_get_signature_s(void *context, size_t hdrlen, unsigned char tag,
+ const void *value, size_t vlen)
+{
+ struct ecdsa_signature_ctx *sig = context;
+
+ return ecdsa_get_signature_rs(sig->s, hdrlen, tag, value, vlen,
+ sig->curve->g.ndigits);
+}
+
+static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash,
+ const u64 *r, const u64 *s)
+{
+ const struct ecc_curve *curve = ctx->curve;
+ unsigned int ndigits = curve->g.ndigits;
+ u64 s1[ECC_MAX_DIGITS];
+ u64 u1[ECC_MAX_DIGITS];
+ u64 u2[ECC_MAX_DIGITS];
+ u64 x1[ECC_MAX_DIGITS];
+ u64 y1[ECC_MAX_DIGITS];
+ struct ecc_point res = ECC_POINT_INIT(x1, y1, ndigits);
+
+ /* 0 < r < n and 0 < s < n */
+ if (vli_is_zero(r, ndigits) || vli_cmp(r, curve->n, ndigits) >= 0 ||
+ vli_is_zero(s, ndigits) || vli_cmp(s, curve->n, ndigits) >= 0)
+ return -EBADMSG;
+
+ /* hash is given */
+ pr_devel("hash : %016llx %016llx ... %016llx\n",
+ hash[ndigits - 1], hash[ndigits - 2], hash[0]);
+
+ /* s1 = (s^-1) mod n */
+ vli_mod_inv(s1, s, curve->n, ndigits);
+ /* u1 = (hash * s1) mod n */
+ vli_mod_mult_slow(u1, hash, s1, curve->n, ndigits);
+ /* u2 = (r * s1) mod n */
+ vli_mod_mult_slow(u2, r, s1, curve->n, ndigits);
+ /* res = u1*G + u2 * pub_key */
+ ecc_point_mult_shamir(&res, u1, &curve->g, u2, ctx->pub_key, curve);
+
+ /* res.x = res.x mod n (if res.x > order) */
+ if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
+ /* faster alternative for NIST p256 & p192 */
+ vli_sub(res.x, res.x, curve->n, ndigits);
+
+ if (!vli_cmp(res.x, r, ndigits))
+ return 0;
+
+ return -EKEYREJECTED;
+}
+
+/*
+ * Verify an ECDSA signature.
+ */
+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);
+ struct ecdsa_signature_ctx sig_ctx = {
+ .curve = ctx->curve,
+ };
+ u8 rawhash[ECC_MAX_BYTES];
+ u64 hash[ECC_MAX_DIGITS];
+ unsigned char *buffer;
+ ssize_t diff;
+ int ret;
+
+ if (unlikely(!ctx->pub_key))
+ return -EINVAL;
+
+ buffer = kmalloc(req->src_len + req->dst_len, GFP_KERNEL);
+ if (!buffer)
+ return -ENOMEM;
+
+ sg_pcopy_to_buffer(req->src,
+ sg_nents_for_len(req->src, req->src_len + req->dst_len),
+ buffer, req->src_len + req->dst_len, 0);
+
+ ret = asn1_ber_decoder(&ecdsasignature_decoder, &sig_ctx,
+ buffer, req->src_len);
+ if (ret < 0)
+ goto error;
+
+ /* if the hash is shorter then we will add leading zeros to fit to ndigits */
+ diff = keylen - 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);
+ }
+
+ ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);
+
+ ret = _ecdsa_verify(ctx, hash, sig_ctx.r, sig_ctx.s);
+
+error:
+ kfree(buffer);
+
+ return ret;
+}
+
+static void ecdsa_ec_ctx_deinit(struct ecc_ctx *ctx)
+{
+ ecc_free_point(ctx->pub_key);
+ ctx->pub_key = NULL;
+}
+
+static int ecdsa_ec_ctx_reset(struct ecc_ctx *ctx)
+{
+ ecdsa_ec_ctx_deinit(ctx);
+ return 0;
+}
+
+/*
+ * Set the public key given the raw uncompressed key data from an X509
+ * certificate. The key data contain the concatenated X and Y coordinates of
+ * the public key.
+ */
+static int ecdsa_set_pub_key(struct crypto_akcipher *tfm,
+ const void *key, unsigned int keylen)
+{
+ struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+ const unsigned char *d = key;
+ const u64 *digits = (const u64 *)&d[1];
+ unsigned int ndigits;
+ int ret;
+
+ ret = ecdsa_ec_ctx_reset(ctx);
+ if (ret < 0)
+ return ret;
+
+ if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
+ return -EINVAL;
+ /* we only accept uncompressed format */
+ if (d[0] != 4)
+ return -EINVAL;
+
+ keylen--;
+ ndigits = (keylen >> 1) / sizeof(u64);
+ switch (ndigits) {
+ case 3:
+ ctx->curve = ecc_get_curve(ECC_CURVE_NIST_P192);
+ break;
+ case 4:
+ ctx->curve = ecc_get_curve(ECC_CURVE_NIST_P256);
+ break;
+ }
+ if (!ctx->curve)
+ return -EINVAL;
+
+ ctx->pub_key = ecc_alloc_point(ndigits);
+ if (!ctx->pub_key)
+ return -ENOMEM;
+
+ ecc_swap_digits(digits, ctx->pub_key->x, ndigits);
+ ecc_swap_digits(&digits[ndigits], ctx->pub_key->y, ndigits);
+ return ecc_is_pubkey_valid_full(ctx->curve, ctx->pub_key);
+}
+
+static void ecdsa_exit_tfm(struct crypto_akcipher *tfm)
+{
+ struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
+
+ ecdsa_ec_ctx_deinit(ctx);
+}
+
+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;
+}
+
+static int ecdsa_init_tfm(struct crypto_akcipher *tfm)
+{
+ return 0;
+}
+
+static struct akcipher_alg ecdsa = {
+ .verify = ecdsa_verify,
+ .set_pub_key = ecdsa_set_pub_key,
+ .max_size = ecdsa_max_size,
+ .init = ecdsa_init_tfm,
+ .exit = ecdsa_exit_tfm,
+ .base = {
+ .cra_name = "ecdsa",
+ .cra_driver_name = "ecdsa-generic",
+ .cra_priority = 100,
+ .cra_module = THIS_MODULE,
+ .cra_ctxsize = sizeof(struct ecc_ctx),
+ },
+};
+
+static int ecdsa_init(void)
+{
+ return crypto_register_akcipher(&ecdsa);
+}
+
+static void ecdsa_exit(void)
+{
+ crypto_unregister_akcipher(&ecdsa);
+}
+
+subsys_initcall(ecdsa_init);
+module_exit(ecdsa_exit);
+
MODULE_LICENSE("Dual BSD/GPL");
diff --git a/crypto/ecc.h b/crypto/ecc.h
index d4e546b9ad79..26d7c83908bc 100644
--- a/crypto/ecc.h
+++ b/crypto/ecc.h
@@ -33,6 +33,8 @@
#define ECC_DIGITS_TO_BYTES_SHIFT 3
+#define ECC_MAX_BYTES (ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT)
+
/**
* struct ecc_point - elliptic curve point in affine coordinates
*
diff --git a/crypto/ecdsasignature.asn1 b/crypto/ecdsasignature.asn1
new file mode 100644
index 000000000000..621ab754fb9f
--- /dev/null
+++ b/crypto/ecdsasignature.asn1
@@ -0,0 +1,4 @@
+ECDSASignature ::= SEQUENCE {
+ r INTEGER ({ ecdsa_get_signature_r }),
+ s INTEGER ({ ecdsa_get_signature_s })
+}
--
2.26.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH v4 3/3] x509: Add support for parsing x509 certs with ECDSA keys
2021-01-28 0:14 [PATCH v4 0/3] Add support for x509 certs with NIST p256 and p192 keys Stefan Berger
2021-01-28 0:14 ` [PATCH v4 1/3] crypto: Add support for ECDSA signature verification Stefan Berger
2021-01-28 0:14 ` [PATCH v4 2/3] x509: Detect sm2 keys by their parameters OID Stefan Berger
@ 2021-01-28 0:14 ` Stefan Berger
2021-01-28 9:19 ` [PATCH v4 0/3] Add support for x509 certs with NIST p256 and p192 keys David Howells
3 siblings, 0 replies; 9+ messages in thread
From: Stefan Berger @ 2021-01-28 0:14 UTC (permalink / raw)
To: keyrings, linux-crypto
Cc: linux-kernel, patrick, Stefan Berger, David Howells
From: Stefan Berger <stefanb@linux.ibm.com>
This patch adds support for parsing of x509 certificates that contain
ECDSA keys, such as NIST P256, that have been signed by a CA using any
of the current SHA hash algorithms.
Signed-off-by: Stefan Berger <stefanb@linux.ibm.com>
Cc: David Howells <dhowells@redhat.com>
Cc: keyrings@vger.kernel.org
---
crypto/asymmetric_keys/public_key.c | 17 ++++++++++++
crypto/asymmetric_keys/x509_cert_parser.c | 32 ++++++++++++++++++++++-
include/linux/oid_registry.h | 6 +++++
3 files changed, 54 insertions(+), 1 deletion(-)
diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
index 8892908ad58c..cc5d59d2b35d 100644
--- a/crypto/asymmetric_keys/public_key.c
+++ b/crypto/asymmetric_keys/public_key.c
@@ -90,6 +90,23 @@ int software_key_determine_akcipher(const char *encoding,
return 0;
}
+ if (strcmp(encoding, "x962") == 0) {
+ enum OID oid;
+
+ if (pkey->paramlen < 2)
+ return -EINVAL;
+
+ oid = look_up_OID(pkey->params + 2, pkey->paramlen - 2);
+ switch (oid) {
+ case OID_id_prime192v1:
+ case OID_id_prime256v1:
+ strcpy(alg_name, "ecdsa");
+ return 0;
+ default:
+ return -EINVAL;
+ }
+ }
+
return -ENOPKG;
}
diff --git a/crypto/asymmetric_keys/x509_cert_parser.c b/crypto/asymmetric_keys/x509_cert_parser.c
index 4643fe5ed69a..5ff891f8235d 100644
--- a/crypto/asymmetric_keys/x509_cert_parser.c
+++ b/crypto/asymmetric_keys/x509_cert_parser.c
@@ -227,6 +227,26 @@ int x509_note_pkey_algo(void *context, size_t hdrlen,
ctx->cert->sig->hash_algo = "sha224";
goto rsa_pkcs1;
+ case OID_id_ecdsa_with_sha1:
+ ctx->cert->sig->hash_algo = "sha1";
+ goto ecdsa;
+
+ case OID_id_ecdsa_with_sha224:
+ ctx->cert->sig->hash_algo = "sha224";
+ goto ecdsa;
+
+ case OID_id_ecdsa_with_sha256:
+ ctx->cert->sig->hash_algo = "sha256";
+ goto ecdsa;
+
+ case OID_id_ecdsa_with_sha384:
+ ctx->cert->sig->hash_algo = "sha384";
+ goto ecdsa;
+
+ case OID_id_ecdsa_with_sha512:
+ ctx->cert->sig->hash_algo = "sha512";
+ goto ecdsa;
+
case OID_gost2012Signature256:
ctx->cert->sig->hash_algo = "streebog256";
goto ecrdsa;
@@ -255,6 +275,11 @@ int x509_note_pkey_algo(void *context, size_t hdrlen,
ctx->cert->sig->encoding = "raw";
ctx->algo_oid = ctx->last_oid;
return 0;
+ecdsa:
+ ctx->cert->sig->pkey_algo = "ecdsa";
+ ctx->cert->sig->encoding = "x962";
+ ctx->algo_oid = ctx->last_oid;
+ return 0;
}
/*
@@ -276,7 +301,8 @@ int x509_note_signature(void *context, size_t hdrlen,
if (strcmp(ctx->cert->sig->pkey_algo, "rsa") == 0 ||
strcmp(ctx->cert->sig->pkey_algo, "ecrdsa") == 0 ||
- strcmp(ctx->cert->sig->pkey_algo, "sm2") == 0) {
+ strcmp(ctx->cert->sig->pkey_algo, "sm2") == 0 ||
+ strcmp(ctx->cert->sig->pkey_algo, "ecdsa") == 0) {
/* Discard the BIT STRING metadata */
if (vlen < 1 || *(const u8 *)value != 0)
return -EBADMSG;
@@ -479,6 +505,10 @@ int x509_extract_key_data(void *context, size_t hdrlen,
case OID_sm2:
ctx->cert->pub->pkey_algo = "sm2";
break;
+ case OID_id_prime192v1:
+ case OID_id_prime256v1:
+ ctx->cert->pub->pkey_algo = "ecdsa";
+ break;
default:
return -ENOPKG;
}
diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h
index 4462ed2c18cd..e8071133d0e2 100644
--- a/include/linux/oid_registry.h
+++ b/include/linux/oid_registry.h
@@ -21,6 +21,12 @@ enum OID {
OID_id_dsa, /* 1.2.840.10040.4.1 */
OID_id_ecdsa_with_sha1, /* 1.2.840.10045.4.1 */
OID_id_ecPublicKey, /* 1.2.840.10045.2.1 */
+ OID_id_prime192v1, /* 1.2.840.10045.3.1.1 */
+ OID_id_prime256v1, /* 1.2.840.10045.3.1.7 */
+ OID_id_ecdsa_with_sha224, /* 1.2.840.10045.4.3.1 */
+ OID_id_ecdsa_with_sha256, /* 1.2.840.10045.4.3.2 */
+ OID_id_ecdsa_with_sha384, /* 1.2.840.10045.4.3.3 */
+ OID_id_ecdsa_with_sha512, /* 1.2.840.10045.4.3.4 */
/* PKCS#1 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1)} */
OID_rsaEncryption, /* 1.2.840.113549.1.1.1 */
--
2.26.2
^ permalink raw reply related [flat|nested] 9+ messages in thread