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