linux/crypto/ecrdsa.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0+
   2/*
   3 * Elliptic Curve (Russian) Digital Signature Algorithm for Cryptographic API
   4 *
   5 * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
   6 *
   7 * References:
   8 * GOST 34.10-2018, GOST R 34.10-2012, RFC 7091, ISO/IEC 14888-3:2018.
   9 *
  10 * Historical references:
  11 * GOST R 34.10-2001, RFC 4357, ISO/IEC 14888-3:2006/Amd 1:2010.
  12 *
  13 * This program is free software; you can redistribute it and/or modify it
  14 * under the terms of the GNU General Public License as published by the Free
  15 * Software Foundation; either version 2 of the License, or (at your option)
  16 * any later version.
  17 */
  18
  19#include <linux/module.h>
  20#include <linux/crypto.h>
  21#include <crypto/streebog.h>
  22#include <crypto/internal/akcipher.h>
  23#include <crypto/akcipher.h>
  24#include <linux/oid_registry.h>
  25#include <linux/scatterlist.h>
  26#include "ecrdsa_params.asn1.h"
  27#include "ecrdsa_pub_key.asn1.h"
  28#include "ecc.h"
  29#include "ecrdsa_defs.h"
  30
  31#define ECRDSA_MAX_SIG_SIZE (2 * 512 / 8)
  32#define ECRDSA_MAX_DIGITS (512 / 64)
  33
  34struct ecrdsa_ctx {
  35        enum OID algo_oid; /* overall public key oid */
  36        enum OID curve_oid; /* parameter */
  37        enum OID digest_oid; /* parameter */
  38        const struct ecc_curve *curve; /* curve from oid */
  39        unsigned int digest_len; /* parameter (bytes) */
  40        const char *digest; /* digest name from oid */
  41        unsigned int key_len; /* @key length (bytes) */
  42        const char *key; /* raw public key */
  43        struct ecc_point pub_key;
  44        u64 _pubp[2][ECRDSA_MAX_DIGITS]; /* point storage for @pub_key */
  45};
  46
  47static const struct ecc_curve *get_curve_by_oid(enum OID oid)
  48{
  49        switch (oid) {
  50        case OID_gostCPSignA:
  51        case OID_gostTC26Sign256B:
  52                return &gost_cp256a;
  53        case OID_gostCPSignB:
  54        case OID_gostTC26Sign256C:
  55                return &gost_cp256b;
  56        case OID_gostCPSignC:
  57        case OID_gostTC26Sign256D:
  58                return &gost_cp256c;
  59        case OID_gostTC26Sign512A:
  60                return &gost_tc512a;
  61        case OID_gostTC26Sign512B:
  62                return &gost_tc512b;
  63        /* The following two aren't implemented: */
  64        case OID_gostTC26Sign256A:
  65        case OID_gostTC26Sign512C:
  66        default:
  67                return NULL;
  68        }
  69}
  70
  71static int ecrdsa_verify(struct akcipher_request *req)
  72{
  73        struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
  74        struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
  75        unsigned char sig[ECRDSA_MAX_SIG_SIZE];
  76        unsigned char digest[STREEBOG512_DIGEST_SIZE];
  77        unsigned int ndigits = req->dst_len / sizeof(u64);
  78        u64 r[ECRDSA_MAX_DIGITS]; /* witness (r) */
  79        u64 _r[ECRDSA_MAX_DIGITS]; /* -r */
  80        u64 s[ECRDSA_MAX_DIGITS]; /* second part of sig (s) */
  81        u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q */
  82        u64 *v = e;               /* e^{-1} \mod q */
  83        u64 z1[ECRDSA_MAX_DIGITS];
  84        u64 *z2 = _r;
  85        struct ecc_point cc = ECC_POINT_INIT(s, e, ndigits); /* reuse s, e */
  86
  87        /*
  88         * Digest value, digest algorithm, and curve (modulus) should have the
  89         * same length (256 or 512 bits), public key and signature should be
  90         * twice bigger.
  91         */
  92        if (!ctx->curve ||
  93            !ctx->digest ||
  94            !req->src ||
  95            !ctx->pub_key.x ||
  96            req->dst_len != ctx->digest_len ||
  97            req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
  98            ctx->pub_key.ndigits != ctx->curve->g.ndigits ||
  99            req->dst_len * 2 != req->src_len ||
 100            WARN_ON(req->src_len > sizeof(sig)) ||
 101            WARN_ON(req->dst_len > sizeof(digest)))
 102                return -EBADMSG;
 103
 104        sg_copy_to_buffer(req->src, sg_nents_for_len(req->src, req->src_len),
 105                          sig, req->src_len);
 106        sg_pcopy_to_buffer(req->src,
 107                           sg_nents_for_len(req->src,
 108                                            req->src_len + req->dst_len),
 109                           digest, req->dst_len, req->src_len);
 110
 111        vli_from_be64(s, sig, ndigits);
 112        vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
 113
 114        /* Step 1: verify that 0 < r < q, 0 < s < q */
 115        if (vli_is_zero(r, ndigits) ||
 116            vli_cmp(r, ctx->curve->n, ndigits) == 1 ||
 117            vli_is_zero(s, ndigits) ||
 118            vli_cmp(s, ctx->curve->n, ndigits) == 1)
 119                return -EKEYREJECTED;
 120
 121        /* Step 2: calculate hash (h) of the message (passed as input) */
 122        /* Step 3: calculate e = h \mod q */
 123        vli_from_le64(e, digest, ndigits);
 124        if (vli_cmp(e, ctx->curve->n, ndigits) == 1)
 125                vli_sub(e, e, ctx->curve->n, ndigits);
 126        if (vli_is_zero(e, ndigits))
 127                e[0] = 1;
 128
 129        /* Step 4: calculate v = e^{-1} \mod q */
 130        vli_mod_inv(v, e, ctx->curve->n, ndigits);
 131
 132        /* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */
 133        vli_mod_mult_slow(z1, s, v, ctx->curve->n, ndigits);
 134        vli_sub(_r, ctx->curve->n, r, ndigits);
 135        vli_mod_mult_slow(z2, _r, v, ctx->curve->n, ndigits);
 136
 137        /* Step 6: calculate point C = z_1P + z_2Q, and R = x_c \mod q */
 138        ecc_point_mult_shamir(&cc, z1, &ctx->curve->g, z2, &ctx->pub_key,
 139                              ctx->curve);
 140        if (vli_cmp(cc.x, ctx->curve->n, ndigits) == 1)
 141                vli_sub(cc.x, cc.x, ctx->curve->n, ndigits);
 142
 143        /* Step 7: if R == r signature is valid */
 144        if (!vli_cmp(cc.x, r, ndigits))
 145                return 0;
 146        else
 147                return -EKEYREJECTED;
 148}
 149
 150int ecrdsa_param_curve(void *context, size_t hdrlen, unsigned char tag,
 151                       const void *value, size_t vlen)
 152{
 153        struct ecrdsa_ctx *ctx = context;
 154
 155        ctx->curve_oid = look_up_OID(value, vlen);
 156        if (!ctx->curve_oid)
 157                return -EINVAL;
 158        ctx->curve = get_curve_by_oid(ctx->curve_oid);
 159        return 0;
 160}
 161
 162/* Optional. If present should match expected digest algo OID. */
 163int ecrdsa_param_digest(void *context, size_t hdrlen, unsigned char tag,
 164                        const void *value, size_t vlen)
 165{
 166        struct ecrdsa_ctx *ctx = context;
 167        int digest_oid = look_up_OID(value, vlen);
 168
 169        if (digest_oid != ctx->digest_oid)
 170                return -EINVAL;
 171        return 0;
 172}
 173
 174int ecrdsa_parse_pub_key(void *context, size_t hdrlen, unsigned char tag,
 175                         const void *value, size_t vlen)
 176{
 177        struct ecrdsa_ctx *ctx = context;
 178
 179        ctx->key = value;
 180        ctx->key_len = vlen;
 181        return 0;
 182}
 183
 184static u8 *ecrdsa_unpack_u32(u32 *dst, void *src)
 185{
 186        memcpy(dst, src, sizeof(u32));
 187        return src + sizeof(u32);
 188}
 189
 190/* Parse BER encoded subjectPublicKey. */
 191static int ecrdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
 192                              unsigned int keylen)
 193{
 194        struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
 195        unsigned int ndigits;
 196        u32 algo, paramlen;
 197        u8 *params;
 198        int err;
 199
 200        err = asn1_ber_decoder(&ecrdsa_pub_key_decoder, ctx, key, keylen);
 201        if (err < 0)
 202                return err;
 203
 204        /* Key parameters is in the key after keylen. */
 205        params = ecrdsa_unpack_u32(&paramlen,
 206                          ecrdsa_unpack_u32(&algo, (u8 *)key + keylen));
 207
 208        if (algo == OID_gost2012PKey256) {
 209                ctx->digest     = "streebog256";
 210                ctx->digest_oid = OID_gost2012Digest256;
 211                ctx->digest_len = 256 / 8;
 212        } else if (algo == OID_gost2012PKey512) {
 213                ctx->digest     = "streebog512";
 214                ctx->digest_oid = OID_gost2012Digest512;
 215                ctx->digest_len = 512 / 8;
 216        } else
 217                return -ENOPKG;
 218        ctx->algo_oid = algo;
 219
 220        /* Parse SubjectPublicKeyInfo.AlgorithmIdentifier.parameters. */
 221        err = asn1_ber_decoder(&ecrdsa_params_decoder, ctx, params, paramlen);
 222        if (err < 0)
 223                return err;
 224        /*
 225         * Sizes of algo (set in digest_len) and curve should match
 226         * each other.
 227         */
 228        if (!ctx->curve ||
 229            ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
 230                return -ENOPKG;
 231        /*
 232         * Key is two 256- or 512-bit coordinates which should match
 233         * curve size.
 234         */
 235        if ((ctx->key_len != (2 * 256 / 8) &&
 236             ctx->key_len != (2 * 512 / 8)) ||
 237            ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
 238                return -ENOPKG;
 239
 240        ndigits = ctx->key_len / sizeof(u64) / 2;
 241        ctx->pub_key = ECC_POINT_INIT(ctx->_pubp[0], ctx->_pubp[1], ndigits);
 242        vli_from_le64(ctx->pub_key.x, ctx->key, ndigits);
 243        vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
 244                      ndigits);
 245
 246        if (ecc_is_pubkey_valid_partial(ctx->curve, &ctx->pub_key))
 247                return -EKEYREJECTED;
 248
 249        return 0;
 250}
 251
 252static unsigned int ecrdsa_max_size(struct crypto_akcipher *tfm)
 253{
 254        struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
 255
 256        /*
 257         * Verify doesn't need any output, so it's just informational
 258         * for keyctl to determine the key bit size.
 259         */
 260        return ctx->pub_key.ndigits * sizeof(u64);
 261}
 262
 263static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm)
 264{
 265}
 266
 267static struct akcipher_alg ecrdsa_alg = {
 268        .verify         = ecrdsa_verify,
 269        .set_pub_key    = ecrdsa_set_pub_key,
 270        .max_size       = ecrdsa_max_size,
 271        .exit           = ecrdsa_exit_tfm,
 272        .base = {
 273                .cra_name        = "ecrdsa",
 274                .cra_driver_name = "ecrdsa-generic",
 275                .cra_priority    = 100,
 276                .cra_module      = THIS_MODULE,
 277                .cra_ctxsize     = sizeof(struct ecrdsa_ctx),
 278        },
 279};
 280
 281static int __init ecrdsa_mod_init(void)
 282{
 283        return crypto_register_akcipher(&ecrdsa_alg);
 284}
 285
 286static void __exit ecrdsa_mod_fini(void)
 287{
 288        crypto_unregister_akcipher(&ecrdsa_alg);
 289}
 290
 291module_init(ecrdsa_mod_init);
 292module_exit(ecrdsa_mod_fini);
 293
 294MODULE_LICENSE("GPL");
 295MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.org>");
 296MODULE_DESCRIPTION("EC-RDSA generic algorithm");
 297MODULE_ALIAS_CRYPTO("ecrdsa-generic");
 298
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.