crypto/ecdsa.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (c) 2021 IBM Corporation
   4  */
   5
   6 #include <linux/module.h>
   7 #include <crypto/internal/akcipher.h>
   8 #include <crypto/internal/ecc.h>
   9 #include <crypto/akcipher.h>
  10 #include <crypto/ecdh.h>
  11 #include <linux/asn1_decoder.h>
  12 #include <linux/scatterlist.h>
  13
  14 #include "ecdsasignature.asn1.h"
  15
  16 struct ecc_ctx {
  17         unsigned int curve_id;
  18         const struct ecc_curve *curve;
  19
  20         bool pub_key_set;
  21         u64 x[ECC_MAX_DIGITS]; /* pub key x and y coordinates */
  22         u64 y[ECC_MAX_DIGITS];
  23         struct ecc_point pub_key;
  24 };
  25
  26 struct ecdsa_signature_ctx {
  27         const struct ecc_curve *curve;
  28         u64 r[ECC_MAX_DIGITS];
  29         u64 s[ECC_MAX_DIGITS];
  30 };
  31
  32 /*
  33  * Get the r and s components of a signature from the X509 certificate.
  34  */
  35 static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
  36                                   const void *value, size_t vlen, unsigned int ndigits)
  37 {
  38         size_t bufsize = ndigits * sizeof(u64);
  39         ssize_t diff = vlen - bufsize;
  40         const char *d = value;
  41         u8 rs[ECC_MAX_BYTES];
  42
  43         if (!value || !vlen)
  44                 return -EINVAL;
  45
  46         /* diff = 0: 'value' has exacly the right size
  47          * diff > 0: 'value' has too many bytes; one leading zero is allowed that
  48          *           makes the value a positive integer; error on more
  49          * diff < 0: 'value' is missing leading zeros, which we add
  50          */
  51         if (diff > 0) {
  52                 /* skip over leading zeros that make 'value' a positive int */
  53                 if (*d == 0) {
  54                         vlen -= 1;
  55                         diff--;
  56                         d++;
  57                 }
  58                 if (diff)
  59                         return -EINVAL;
  60         }
  61         if (-diff >= bufsize)
  62                 return -EINVAL;
  63
  64         if (diff) {
  65                 /* leading zeros not given in 'value' */
  66                 memset(rs, 0, -diff);
  67         }
  68
  69         memcpy(&rs[-diff], d, vlen);
  70
  71         ecc_swap_digits((u64 *)rs, dest, ndigits);
  72
  73         return 0;
  74 }
  75
  76 int ecdsa_get_signature_r(void *context, size_t hdrlen, unsigned char tag,
  77                           const void *value, size_t vlen)
  78 {
  79         struct ecdsa_signature_ctx *sig = context;
  80
  81         return ecdsa_get_signature_rs(sig->r, hdrlen, tag, value, vlen,
  82                                       sig->curve->g.ndigits);
  83 }
  84
  85 int ecdsa_get_signature_s(void *context, size_t hdrlen, unsigned char tag,
  86                           const void *value, size_t vlen)
  87 {
  88         struct ecdsa_signature_ctx *sig = context;
  89
  90         return ecdsa_get_signature_rs(sig->s, hdrlen, tag, value, vlen,
  91                                       sig->curve->g.ndigits);
  92 }
  93
  94 static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, const u64 *s)
  95 {
  96         const struct ecc_curve *curve = ctx->curve;
  97         unsigned int ndigits = curve->g.ndigits;
  98         u64 s1[ECC_MAX_DIGITS];
  99         u64 u1[ECC_MAX_DIGITS];
 100         u64 u2[ECC_MAX_DIGITS];
 101         u64 x1[ECC_MAX_DIGITS];
 102         u64 y1[ECC_MAX_DIGITS];
 103         struct ecc_point res = ECC_POINT_INIT(x1, y1, ndigits);
 104
 105         /* 0 < r < n  and 0 < s < n */
 106         if (vli_is_zero(r, ndigits) || vli_cmp(r, curve->n, ndigits) >= 0 ||
 107             vli_is_zero(s, ndigits) || vli_cmp(s, curve->n, ndigits) >= 0)
 108                 return -EBADMSG;
 109
 110         /* hash is given */
 111         pr_devel("hash : %016llx %016llx ... %016llx\n",
 112                  hash[ndigits - 1], hash[ndigits - 2], hash[0]);
 113
 114         /* s1 = (s^-1) mod n */
 115         vli_mod_inv(s1, s, curve->n, ndigits);
 116         /* u1 = (hash * s1) mod n */
 117         vli_mod_mult_slow(u1, hash, s1, curve->n, ndigits);
 118         /* u2 = (r * s1) mod n */
 119         vli_mod_mult_slow(u2, r, s1, curve->n, ndigits);
 120         /* res = u1*G + u2 * pub_key */
 121         ecc_point_mult_shamir(&res, u1, &curve->g, u2, &ctx->pub_key, curve);
 122
 123         /* res.x = res.x mod n (if res.x > order) */
 124         if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
 125                 /* faster alternative for NIST p521, p384, p256 & p192 */
 126                 vli_sub(res.x, res.x, curve->n, ndigits);
 127
 128         if (!vli_cmp(res.x, r, ndigits))
 129                 return 0;
 130
 131         return -EKEYREJECTED;
 132 }
 133
 134 /*
 135  * Verify an ECDSA signature.
 136  */
 137 static int ecdsa_verify(struct akcipher_request *req)
 138 {
 139         struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
 140         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 141         size_t bufsize = ctx->curve->g.ndigits * sizeof(u64);
 142         struct ecdsa_signature_ctx sig_ctx = {
 143                 .curve = ctx->curve,
 144         };
 145         u8 rawhash[ECC_MAX_BYTES];
 146         u64 hash[ECC_MAX_DIGITS];
 147         unsigned char *buffer;
 148         ssize_t diff;
 149         int ret;
 150
 151         if (unlikely(!ctx->pub_key_set))
 152                 return -EINVAL;
 153
 154         buffer = kmalloc(req->src_len + req->dst_len, GFP_KERNEL);
 155         if (!buffer)
 156                 return -ENOMEM;
 157
 158         sg_pcopy_to_buffer(req->src,
 159                 sg_nents_for_len(req->src, req->src_len + req->dst_len),
 160                 buffer, req->src_len + req->dst_len, 0);
 161
 162         ret = asn1_ber_decoder(&ecdsasignature_decoder, &sig_ctx,
 163                                buffer, req->src_len);
 164         if (ret < 0)
 165                 goto error;
 166
 167         /* if the hash is shorter then we will add leading zeros to fit to ndigits */
 168         diff = bufsize - req->dst_len;
 169         if (diff >= 0) {
 170                 if (diff)
 171                         memset(rawhash, 0, diff);
 172                 memcpy(&rawhash[diff], buffer + req->src_len, req->dst_len);
 173         } else if (diff < 0) {
 174                 /* given hash is longer, we take the left-most bytes */
 175                 memcpy(&rawhash, buffer + req->src_len, bufsize);
 176         }
 177
 178         ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);
 179
 180         ret = _ecdsa_verify(ctx, hash, sig_ctx.r, sig_ctx.s);
 181
 182 error:
 183         kfree(buffer);
 184
 185         return ret;
 186 }
 187
 188 static int ecdsa_ecc_ctx_init(struct ecc_ctx *ctx, unsigned int curve_id)
 189 {
 190         ctx->curve_id = curve_id;
 191         ctx->curve = ecc_get_curve(curve_id);
 192         if (!ctx->curve)
 193                 return -EINVAL;
 194
 195         return 0;
 196 }
 197
 198
 199 static void ecdsa_ecc_ctx_deinit(struct ecc_ctx *ctx)
 200 {
 201         ctx->pub_key_set = false;
 202 }
 203
 204 static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
 205 {
 206         unsigned int curve_id = ctx->curve_id;
 207         int ret;
 208
 209         ecdsa_ecc_ctx_deinit(ctx);
 210         ret = ecdsa_ecc_ctx_init(ctx, curve_id);
 211         if (ret == 0)
 212                 ctx->pub_key = ECC_POINT_INIT(ctx->x, ctx->y,
 213                                               ctx->curve->g.ndigits);
 214         return ret;
 215 }
 216
 217 /*
 218  * Set the public key given the raw uncompressed key data from an X509
 219  * certificate. The key data contain the concatenated X and Y coordinates of
 220  * the public key.
 221  */
 222 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
 223 {
 224         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 225         unsigned int digitlen, ndigits;
 226         const unsigned char *d = key;
 227         int ret;
 228
 229         ret = ecdsa_ecc_ctx_reset(ctx);
 230         if (ret < 0)
 231                 return ret;
 232
 233         if (keylen < 1 || ((keylen - 1) & 1) != 0)
 234                 return -EINVAL;
 235         /* we only accept uncompressed format indicated by '4' */
 236         if (d[0] != 4)
 237                 return -EINVAL;
 238
 239         keylen--;
 240         digitlen = keylen >> 1;
 241
 242         ndigits = DIV_ROUND_UP(digitlen, sizeof(u64));
 243         if (ndigits != ctx->curve->g.ndigits)
 244                 return -EINVAL;
 245
 246         d++;
 247
 248         ecc_digits_from_bytes(d, digitlen, ctx->pub_key.x, ndigits);
 249         ecc_digits_from_bytes(&d[digitlen], digitlen, ctx->pub_key.y, ndigits);
 250
 251         ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
 252
 253         ctx->pub_key_set = ret == 0;
 254
 255         return ret;
 256 }
 257
 258 static void ecdsa_exit_tfm(struct crypto_akcipher *tfm)
 259 {
 260         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 261
 262         ecdsa_ecc_ctx_deinit(ctx);
 263 }
 264
 265 static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
 266 {
 267         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 268
 269         return DIV_ROUND_UP(ctx->curve->nbits, 8);
 270 }
 271
 272 static int ecdsa_nist_p521_init_tfm(struct crypto_akcipher *tfm)
 273 {
 274         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 275
 276         return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P521);
 277 }
 278
 279 static struct akcipher_alg ecdsa_nist_p521 = {
 280         .verify = ecdsa_verify,
 281         .set_pub_key = ecdsa_set_pub_key,
 282         .max_size = ecdsa_max_size,
 283         .init = ecdsa_nist_p521_init_tfm,
 284         .exit = ecdsa_exit_tfm,
 285         .base = {
 286                 .cra_name = "ecdsa-nist-p521",
 287                 .cra_driver_name = "ecdsa-nist-p521-generic",
 288                 .cra_priority = 100,
 289                 .cra_module = THIS_MODULE,
 290                 .cra_ctxsize = sizeof(struct ecc_ctx),
 291         },
 292 };
 293
 294 static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
 295 {
 296         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 297
 298         return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P384);
 299 }
 300
 301 static struct akcipher_alg ecdsa_nist_p384 = {
 302         .verify = ecdsa_verify,
 303         .set_pub_key = ecdsa_set_pub_key,
 304         .max_size = ecdsa_max_size,
 305         .init = ecdsa_nist_p384_init_tfm,
 306         .exit = ecdsa_exit_tfm,
 307         .base = {
 308                 .cra_name = "ecdsa-nist-p384",
 309                 .cra_driver_name = "ecdsa-nist-p384-generic",
 310                 .cra_priority = 100,
 311                 .cra_module = THIS_MODULE,
 312                 .cra_ctxsize = sizeof(struct ecc_ctx),
 313         },
 314 };
 315
 316 static int ecdsa_nist_p256_init_tfm(struct crypto_akcipher *tfm)
 317 {
 318         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 319
 320         return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P256);
 321 }
 322
 323 static struct akcipher_alg ecdsa_nist_p256 = {
 324         .verify = ecdsa_verify,
 325         .set_pub_key = ecdsa_set_pub_key,
 326         .max_size = ecdsa_max_size,
 327         .init = ecdsa_nist_p256_init_tfm,
 328         .exit = ecdsa_exit_tfm,
 329         .base = {
 330                 .cra_name = "ecdsa-nist-p256",
 331                 .cra_driver_name = "ecdsa-nist-p256-generic",
 332                 .cra_priority = 100,
 333                 .cra_module = THIS_MODULE,
 334                 .cra_ctxsize = sizeof(struct ecc_ctx),
 335         },
 336 };
 337
 338 static int ecdsa_nist_p192_init_tfm(struct crypto_akcipher *tfm)
 339 {
 340         struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 341
 342         return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P192);
 343 }
 344
 345 static struct akcipher_alg ecdsa_nist_p192 = {
 346         .verify = ecdsa_verify,
 347         .set_pub_key = ecdsa_set_pub_key,
 348         .max_size = ecdsa_max_size,
 349         .init = ecdsa_nist_p192_init_tfm,
 350         .exit = ecdsa_exit_tfm,
 351         .base = {
 352                 .cra_name = "ecdsa-nist-p192",
 353                 .cra_driver_name = "ecdsa-nist-p192-generic",
 354                 .cra_priority = 100,
 355                 .cra_module = THIS_MODULE,
 356                 .cra_ctxsize = sizeof(struct ecc_ctx),
 357         },
 358 };
 359 static bool ecdsa_nist_p192_registered;
 360
 361 static int __init ecdsa_init(void)
 362 {
 363         int ret;
 364
 365         /* NIST p192 may not be available in FIPS mode */
 366         ret = crypto_register_akcipher(&ecdsa_nist_p192);
 367         ecdsa_nist_p192_registered = ret == 0;
 368
 369         ret = crypto_register_akcipher(&ecdsa_nist_p256);
 370         if (ret)
 371                 goto nist_p256_error;
 372
 373         ret = crypto_register_akcipher(&ecdsa_nist_p384);
 374         if (ret)
 375                 goto nist_p384_error;
 376
 377         ret = crypto_register_akcipher(&ecdsa_nist_p521);
 378         if (ret)
 379                 goto nist_p521_error;
 380
 381         return 0;
 382
 383 nist_p521_error:
 384         crypto_unregister_akcipher(&ecdsa_nist_p384);
 385
 386 nist_p384_error:
 387         crypto_unregister_akcipher(&ecdsa_nist_p256);
 388
 389 nist_p256_error:
 390         if (ecdsa_nist_p192_registered)
 391                 crypto_unregister_akcipher(&ecdsa_nist_p192);
 392         return ret;
 393 }
 394
 395 static void __exit ecdsa_exit(void)
 396 {
 397         if (ecdsa_nist_p192_registered)
 398                 crypto_unregister_akcipher(&ecdsa_nist_p192);
 399         crypto_unregister_akcipher(&ecdsa_nist_p256);
 400         crypto_unregister_akcipher(&ecdsa_nist_p384);
 401         crypto_unregister_akcipher(&ecdsa_nist_p521);
 402 }
 403
 404 subsys_initcall(ecdsa_init);
 405 module_exit(ecdsa_exit);
 406
 407 MODULE_LICENSE("GPL");
 408 MODULE_AUTHOR("Stefan Berger <stefanb@linux.ibm.com>");
 409 MODULE_DESCRIPTION("ECDSA generic algorithm");
 410 MODULE_ALIAS_CRYPTO("ecdsa-nist-p192");
 411 MODULE_ALIAS_CRYPTO("ecdsa-nist-p256");
 412 MODULE_ALIAS_CRYPTO("ecdsa-nist-p384");
 413 MODULE_ALIAS_CRYPTO("ecdsa-nist-p521");
 414 MODULE_ALIAS_CRYPTO("ecdsa-generic");