the-tree/crypto/ecdsa.c

0001 // SPDX-License-Identifier: GPL-2.0+
0002 /*
0003  * Copyright (c) 2021 IBM Corporation
0004  */
0005
0006 #include <linux/module.h>
0007 #include <crypto/internal/akcipher.h>
0008 #include <crypto/internal/ecc.h>
0009 #include <crypto/akcipher.h>
0010 #include <crypto/ecdh.h>
0011 #include <linux/asn1_decoder.h>
0012 #include <linux/scatterlist.h>
0013
0014 #include "ecdsasignature.asn1.h"
0015
0016 struct ecc_ctx {
0017     unsigned int curve_id;
0018     const struct ecc_curve *curve;
0019
0020     bool pub_key_set;
0021     u64 x[ECC_MAX_DIGITS]; /* pub key x and y coordinates */
0022     u64 y[ECC_MAX_DIGITS];
0023     struct ecc_point pub_key;
0024 };
0025
0026 struct ecdsa_signature_ctx {
0027     const struct ecc_curve *curve;
0028     u64 r[ECC_MAX_DIGITS];
0029     u64 s[ECC_MAX_DIGITS];
0030 };
0031
0032 /*
0033  * Get the r and s components of a signature from the X509 certificate.
0034  */
0035 static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
0036                   const void *value, size_t vlen, unsigned int ndigits)
0037 {
0038     size_t keylen = ndigits * sizeof(u64);
0039     ssize_t diff = vlen - keylen;
0040     const char *d = value;
0041     u8 rs[ECC_MAX_BYTES];
0042
0043     if (!value || !vlen)
0044         return -EINVAL;
0045
0046     /* diff = 0: 'value' has exacly the right size
0047      * diff > 0: 'value' has too many bytes; one leading zero is allowed that
0048      *           makes the value a positive integer; error on more
0049      * diff < 0: 'value' is missing leading zeros, which we add
0050      */
0051     if (diff > 0) {
0052         /* skip over leading zeros that make 'value' a positive int */
0053         if (*d == 0) {
0054             vlen -= 1;
0055             diff--;
0056             d++;
0057         }
0058         if (diff)
0059             return -EINVAL;
0060     }
0061     if (-diff >= keylen)
0062         return -EINVAL;
0063
0064     if (diff) {
0065         /* leading zeros not given in 'value' */
0066         memset(rs, 0, -diff);
0067     }
0068
0069     memcpy(&rs[-diff], d, vlen);
0070
0071     ecc_swap_digits((u64 *)rs, dest, ndigits);
0072
0073     return 0;
0074 }
0075
0076 int ecdsa_get_signature_r(void *context, size_t hdrlen, unsigned char tag,
0077               const void *value, size_t vlen)
0078 {
0079     struct ecdsa_signature_ctx *sig = context;
0080
0081     return ecdsa_get_signature_rs(sig->r, hdrlen, tag, value, vlen,
0082                       sig->curve->g.ndigits);
0083 }
0084
0085 int ecdsa_get_signature_s(void *context, size_t hdrlen, unsigned char tag,
0086               const void *value, size_t vlen)
0087 {
0088     struct ecdsa_signature_ctx *sig = context;
0089
0090     return ecdsa_get_signature_rs(sig->s, hdrlen, tag, value, vlen,
0091                       sig->curve->g.ndigits);
0092 }
0093
0094 static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, const u64 *s)
0095 {
0096     const struct ecc_curve *curve = ctx->curve;
0097     unsigned int ndigits = curve->g.ndigits;
0098     u64 s1[ECC_MAX_DIGITS];
0099     u64 u1[ECC_MAX_DIGITS];
0100     u64 u2[ECC_MAX_DIGITS];
0101     u64 x1[ECC_MAX_DIGITS];
0102     u64 y1[ECC_MAX_DIGITS];
0103     struct ecc_point res = ECC_POINT_INIT(x1, y1, ndigits);
0104
0105     /* 0 < r < n  and 0 < s < n */
0106     if (vli_is_zero(r, ndigits) || vli_cmp(r, curve->n, ndigits) >= 0 ||
0107         vli_is_zero(s, ndigits) || vli_cmp(s, curve->n, ndigits) >= 0)
0108         return -EBADMSG;
0109
0110     /* hash is given */
0111     pr_devel("hash : %016llx %016llx ... %016llx\n",
0112          hash[ndigits - 1], hash[ndigits - 2], hash[0]);
0113
0114     /* s1 = (s^-1) mod n */
0115     vli_mod_inv(s1, s, curve->n, ndigits);
0116     /* u1 = (hash * s1) mod n */
0117     vli_mod_mult_slow(u1, hash, s1, curve->n, ndigits);
0118     /* u2 = (r * s1) mod n */
0119     vli_mod_mult_slow(u2, r, s1, curve->n, ndigits);
0120     /* res = u1*G + u2 * pub_key */
0121     ecc_point_mult_shamir(&res, u1, &curve->g, u2, &ctx->pub_key, curve);
0122
0123     /* res.x = res.x mod n (if res.x > order) */
0124     if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
0125         /* faster alternative for NIST p384, p256 & p192 */
0126         vli_sub(res.x, res.x, curve->n, ndigits);
0127
0128     if (!vli_cmp(res.x, r, ndigits))
0129         return 0;
0130
0131     return -EKEYREJECTED;
0132 }
0133
0134 /*
0135  * Verify an ECDSA signature.
0136  */
0137 static int ecdsa_verify(struct akcipher_request *req)
0138 {
0139     struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
0140     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0141     size_t keylen = ctx->curve->g.ndigits * sizeof(u64);
0142     struct ecdsa_signature_ctx sig_ctx = {
0143         .curve = ctx->curve,
0144     };
0145     u8 rawhash[ECC_MAX_BYTES];
0146     u64 hash[ECC_MAX_DIGITS];
0147     unsigned char *buffer;
0148     ssize_t diff;
0149     int ret;
0150
0151     if (unlikely(!ctx->pub_key_set))
0152         return -EINVAL;
0153
0154     buffer = kmalloc(req->src_len + req->dst_len, GFP_KERNEL);
0155     if (!buffer)
0156         return -ENOMEM;
0157
0158     sg_pcopy_to_buffer(req->src,
0159         sg_nents_for_len(req->src, req->src_len + req->dst_len),
0160         buffer, req->src_len + req->dst_len, 0);
0161
0162     ret = asn1_ber_decoder(&ecdsasignature_decoder, &sig_ctx,
0163                    buffer, req->src_len);
0164     if (ret < 0)
0165         goto error;
0166
0167     /* if the hash is shorter then we will add leading zeros to fit to ndigits */
0168     diff = keylen - req->dst_len;
0169     if (diff >= 0) {
0170         if (diff)
0171             memset(rawhash, 0, diff);
0172         memcpy(&rawhash[diff], buffer + req->src_len, req->dst_len);
0173     } else if (diff < 0) {
0174         /* given hash is longer, we take the left-most bytes */
0175         memcpy(&rawhash, buffer + req->src_len, keylen);
0176     }
0177
0178     ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);
0179
0180     ret = _ecdsa_verify(ctx, hash, sig_ctx.r, sig_ctx.s);
0181
0182 error:
0183     kfree(buffer);
0184
0185     return ret;
0186 }
0187
0188 static int ecdsa_ecc_ctx_init(struct ecc_ctx *ctx, unsigned int curve_id)
0189 {
0190     ctx->curve_id = curve_id;
0191     ctx->curve = ecc_get_curve(curve_id);
0192     if (!ctx->curve)
0193         return -EINVAL;
0194
0195     return 0;
0196 }
0197
0198
0199 static void ecdsa_ecc_ctx_deinit(struct ecc_ctx *ctx)
0200 {
0201     ctx->pub_key_set = false;
0202 }
0203
0204 static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
0205 {
0206     unsigned int curve_id = ctx->curve_id;
0207     int ret;
0208
0209     ecdsa_ecc_ctx_deinit(ctx);
0210     ret = ecdsa_ecc_ctx_init(ctx, curve_id);
0211     if (ret == 0)
0212         ctx->pub_key = ECC_POINT_INIT(ctx->x, ctx->y,
0213                           ctx->curve->g.ndigits);
0214     return ret;
0215 }
0216
0217 /*
0218  * Set the public key given the raw uncompressed key data from an X509
0219  * certificate. The key data contain the concatenated X and Y coordinates of
0220  * the public key.
0221  */
0222 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
0223 {
0224     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0225     const unsigned char *d = key;
0226     const u64 *digits = (const u64 *)&d[1];
0227     unsigned int ndigits;
0228     int ret;
0229
0230     ret = ecdsa_ecc_ctx_reset(ctx);
0231     if (ret < 0)
0232         return ret;
0233
0234     if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
0235         return -EINVAL;
0236     /* we only accept uncompressed format indicated by '4' */
0237     if (d[0] != 4)
0238         return -EINVAL;
0239
0240     keylen--;
0241     ndigits = (keylen >> 1) / sizeof(u64);
0242     if (ndigits != ctx->curve->g.ndigits)
0243         return -EINVAL;
0244
0245     ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
0246     ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
0247     ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
0248
0249     ctx->pub_key_set = ret == 0;
0250
0251     return ret;
0252 }
0253
0254 static void ecdsa_exit_tfm(struct crypto_akcipher *tfm)
0255 {
0256     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0257
0258     ecdsa_ecc_ctx_deinit(ctx);
0259 }
0260
0261 static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
0262 {
0263     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0264
0265     return ctx->pub_key.ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
0266 }
0267
0268 static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
0269 {
0270     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0271
0272     return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P384);
0273 }
0274
0275 static struct akcipher_alg ecdsa_nist_p384 = {
0276     .verify = ecdsa_verify,
0277     .set_pub_key = ecdsa_set_pub_key,
0278     .max_size = ecdsa_max_size,
0279     .init = ecdsa_nist_p384_init_tfm,
0280     .exit = ecdsa_exit_tfm,
0281     .base = {
0282         .cra_name = "ecdsa-nist-p384",
0283         .cra_driver_name = "ecdsa-nist-p384-generic",
0284         .cra_priority = 100,
0285         .cra_module = THIS_MODULE,
0286         .cra_ctxsize = sizeof(struct ecc_ctx),
0287     },
0288 };
0289
0290 static int ecdsa_nist_p256_init_tfm(struct crypto_akcipher *tfm)
0291 {
0292     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0293
0294     return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P256);
0295 }
0296
0297 static struct akcipher_alg ecdsa_nist_p256 = {
0298     .verify = ecdsa_verify,
0299     .set_pub_key = ecdsa_set_pub_key,
0300     .max_size = ecdsa_max_size,
0301     .init = ecdsa_nist_p256_init_tfm,
0302     .exit = ecdsa_exit_tfm,
0303     .base = {
0304         .cra_name = "ecdsa-nist-p256",
0305         .cra_driver_name = "ecdsa-nist-p256-generic",
0306         .cra_priority = 100,
0307         .cra_module = THIS_MODULE,
0308         .cra_ctxsize = sizeof(struct ecc_ctx),
0309     },
0310 };
0311
0312 static int ecdsa_nist_p192_init_tfm(struct crypto_akcipher *tfm)
0313 {
0314     struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
0315
0316     return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P192);
0317 }
0318
0319 static struct akcipher_alg ecdsa_nist_p192 = {
0320     .verify = ecdsa_verify,
0321     .set_pub_key = ecdsa_set_pub_key,
0322     .max_size = ecdsa_max_size,
0323     .init = ecdsa_nist_p192_init_tfm,
0324     .exit = ecdsa_exit_tfm,
0325     .base = {
0326         .cra_name = "ecdsa-nist-p192",
0327         .cra_driver_name = "ecdsa-nist-p192-generic",
0328         .cra_priority = 100,
0329         .cra_module = THIS_MODULE,
0330         .cra_ctxsize = sizeof(struct ecc_ctx),
0331     },
0332 };
0333 static bool ecdsa_nist_p192_registered;
0334
0335 static int ecdsa_init(void)
0336 {
0337     int ret;
0338
0339     /* NIST p192 may not be available in FIPS mode */
0340     ret = crypto_register_akcipher(&ecdsa_nist_p192);
0341     ecdsa_nist_p192_registered = ret == 0;
0342
0343     ret = crypto_register_akcipher(&ecdsa_nist_p256);
0344     if (ret)
0345         goto nist_p256_error;
0346
0347     ret = crypto_register_akcipher(&ecdsa_nist_p384);
0348     if (ret)
0349         goto nist_p384_error;
0350
0351     return 0;
0352
0353 nist_p384_error:
0354     crypto_unregister_akcipher(&ecdsa_nist_p256);
0355
0356 nist_p256_error:
0357     if (ecdsa_nist_p192_registered)
0358         crypto_unregister_akcipher(&ecdsa_nist_p192);
0359     return ret;
0360 }
0361
0362 static void ecdsa_exit(void)
0363 {
0364     if (ecdsa_nist_p192_registered)
0365         crypto_unregister_akcipher(&ecdsa_nist_p192);
0366     crypto_unregister_akcipher(&ecdsa_nist_p256);
0367     crypto_unregister_akcipher(&ecdsa_nist_p384);
0368 }
0369
0370 subsys_initcall(ecdsa_init);
0371 module_exit(ecdsa_exit);
0372
0373 MODULE_LICENSE("GPL");
0374 MODULE_AUTHOR("Stefan Berger <stefanb@linux.ibm.com>");
0375 MODULE_DESCRIPTION("ECDSA generic algorithm");
0376 MODULE_ALIAS_CRYPTO("ecdsa-generic");