LXR linux/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/akcipher.h>
   9#include <crypto/ecdh.h>
  10#include <linux/asn1_decoder.h>
  11#include <linux/scatterlist.h>
  12
  13#include "ecc.h"
  14#include "ecdsasignature.asn1.h"
  15
  16struct 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
  26struct 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 */
  35static 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 keylen = ndigits * sizeof(u64);
  39        ssize_t diff = vlen - keylen;
  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 >= keylen)
  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
  76int 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
  85int 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
  94static 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 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 */
 137static 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 keylen = 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 = keylen - 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, keylen);
 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
 182error:
 183        kfree(buffer);
 184
 185        return ret;
 186}
 187
 188static 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
 199static void ecdsa_ecc_ctx_deinit(struct ecc_ctx *ctx)
 200{
 201        ctx->pub_key_set = false;
 202}
 203
 204static 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 */
 222static 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        const unsigned char *d = key;
 226        const u64 *digits = (const u64 *)&d[1];
 227        unsigned int ndigits;
 228        int ret;
 229
 230        ret = ecdsa_ecc_ctx_reset(ctx);
 231        if (ret < 0)
 232                return ret;
 233
 234        if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
 235                return -EINVAL;
 236        /* we only accept uncompressed format indicated by '4' */
 237        if (d[0] != 4)
 238                return -EINVAL;
 239
 240        keylen--;
 241        ndigits = (keylen >> 1) / sizeof(u64);
 242        if (ndigits != ctx->curve->g.ndigits)
 243                return -EINVAL;
 244
 245        ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
 246        ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
 247        ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
 248
 249        ctx->pub_key_set = ret == 0;
 250
 251        return ret;
 252}
 253
 254static void ecdsa_exit_tfm(struct crypto_akcipher *tfm)
 255{
 256        struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 257
 258        ecdsa_ecc_ctx_deinit(ctx);
 259}
 260
 261static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
 262{
 263        struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 264
 265        return ctx->pub_key.ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
 266}
 267
 268static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
 269{
 270        struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 271
 272        return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P384);
 273}
 274
 275static struct akcipher_alg ecdsa_nist_p384 = {
 276        .verify = ecdsa_verify,
 277        .set_pub_key = ecdsa_set_pub_key,
 278        .max_size = ecdsa_max_size,
 279        .init = ecdsa_nist_p384_init_tfm,
 280        .exit = ecdsa_exit_tfm,
 281        .base = {
 282                .cra_name = "ecdsa-nist-p384",
 283                .cra_driver_name = "ecdsa-nist-p384-generic",
 284                .cra_priority = 100,
 285                .cra_module = THIS_MODULE,
 286                .cra_ctxsize = sizeof(struct ecc_ctx),
 287        },
 288};
 289
 290static int ecdsa_nist_p256_init_tfm(struct crypto_akcipher *tfm)
 291{
 292        struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 293
 294        return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P256);
 295}
 296
 297static struct akcipher_alg ecdsa_nist_p256 = {
 298        .verify = ecdsa_verify,
 299        .set_pub_key = ecdsa_set_pub_key,
 300        .max_size = ecdsa_max_size,
 301        .init = ecdsa_nist_p256_init_tfm,
 302        .exit = ecdsa_exit_tfm,
 303        .base = {
 304                .cra_name = "ecdsa-nist-p256",
 305                .cra_driver_name = "ecdsa-nist-p256-generic",
 306                .cra_priority = 100,
 307                .cra_module = THIS_MODULE,
 308                .cra_ctxsize = sizeof(struct ecc_ctx),
 309        },
 310};
 311
 312static int ecdsa_nist_p192_init_tfm(struct crypto_akcipher *tfm)
 313{
 314        struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
 315
 316        return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P192);
 317}
 318
 319static struct akcipher_alg ecdsa_nist_p192 = {
 320        .verify = ecdsa_verify,
 321        .set_pub_key = ecdsa_set_pub_key,
 322        .max_size = ecdsa_max_size,
 323        .init = ecdsa_nist_p192_init_tfm,
 324        .exit = ecdsa_exit_tfm,
 325        .base = {
 326                .cra_name = "ecdsa-nist-p192",
 327                .cra_driver_name = "ecdsa-nist-p192-generic",
 328                .cra_priority = 100,
 329                .cra_module = THIS_MODULE,
 330                .cra_ctxsize = sizeof(struct ecc_ctx),
 331        },
 332};
 333static bool ecdsa_nist_p192_registered;
 334
 335static int ecdsa_init(void)
 336{
 337        int ret;
 338
 339        /* NIST p192 may not be available in FIPS mode */
 340        ret = crypto_register_akcipher(&ecdsa_nist_p192);
 341        ecdsa_nist_p192_registered = ret == 0;
 342
 343        ret = crypto_register_akcipher(&ecdsa_nist_p256);
 344        if (ret)
 345                goto nist_p256_error;
 346
 347        ret = crypto_register_akcipher(&ecdsa_nist_p384);
 348        if (ret)
 349                goto nist_p384_error;
 350
 351        return 0;
 352
 353nist_p384_error:
 354        crypto_unregister_akcipher(&ecdsa_nist_p256);
 355
 356nist_p256_error:
 357        if (ecdsa_nist_p192_registered)
 358                crypto_unregister_akcipher(&ecdsa_nist_p192);
 359        return ret;
 360}
 361
 362static void ecdsa_exit(void)
 363{
 364        if (ecdsa_nist_p192_registered)
 365                crypto_unregister_akcipher(&ecdsa_nist_p192);
 366        crypto_unregister_akcipher(&ecdsa_nist_p256);
 367        crypto_unregister_akcipher(&ecdsa_nist_p384);
 368}
 369
 370subsys_initcall(ecdsa_init);
 371module_exit(ecdsa_exit);
 372
 373MODULE_LICENSE("GPL");
 374MODULE_AUTHOR("Stefan Berger <stefanb@linux.ibm.com>");
 375MODULE_DESCRIPTION("ECDSA generic algorithm");
 376MODULE_ALIAS_CRYPTO("ecdsa-generic");
 377