the-tree/crypto/ecrdsa.c

0001 // SPDX-License-Identifier: GPL-2.0+
0002 /*
0003  * Elliptic Curve (Russian) Digital Signature Algorithm for Cryptographic API
0004  *
0005  * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
0006  *
0007  * References:
0008  * GOST 34.10-2018, GOST R 34.10-2012, RFC 7091, ISO/IEC 14888-3:2018.
0009  *
0010  * Historical references:
0011  * GOST R 34.10-2001, RFC 4357, ISO/IEC 14888-3:2006/Amd 1:2010.
0012  *
0013  * This program is free software; you can redistribute it and/or modify it
0014  * under the terms of the GNU General Public License as published by the Free
0015  * Software Foundation; either version 2 of the License, or (at your option)
0016  * any later version.
0017  */
0018
0019 #include <linux/module.h>
0020 #include <linux/crypto.h>
0021 #include <crypto/streebog.h>
0022 #include <crypto/internal/akcipher.h>
0023 #include <crypto/internal/ecc.h>
0024 #include <crypto/akcipher.h>
0025 #include <linux/oid_registry.h>
0026 #include <linux/scatterlist.h>
0027 #include "ecrdsa_params.asn1.h"
0028 #include "ecrdsa_pub_key.asn1.h"
0029 #include "ecrdsa_defs.h"
0030
0031 #define ECRDSA_MAX_SIG_SIZE (2 * 512 / 8)
0032 #define ECRDSA_MAX_DIGITS (512 / 64)
0033
0034 struct ecrdsa_ctx {
0035     enum OID algo_oid; /* overall public key oid */
0036     enum OID curve_oid; /* parameter */
0037     enum OID digest_oid; /* parameter */
0038     const struct ecc_curve *curve; /* curve from oid */
0039     unsigned int digest_len; /* parameter (bytes) */
0040     const char *digest; /* digest name from oid */
0041     unsigned int key_len; /* @key length (bytes) */
0042     const char *key; /* raw public key */
0043     struct ecc_point pub_key;
0044     u64 _pubp[2][ECRDSA_MAX_DIGITS]; /* point storage for @pub_key */
0045 };
0046
0047 static const struct ecc_curve *get_curve_by_oid(enum OID oid)
0048 {
0049     switch (oid) {
0050     case OID_gostCPSignA:
0051     case OID_gostTC26Sign256B:
0052         return &gost_cp256a;
0053     case OID_gostCPSignB:
0054     case OID_gostTC26Sign256C:
0055         return &gost_cp256b;
0056     case OID_gostCPSignC:
0057     case OID_gostTC26Sign256D:
0058         return &gost_cp256c;
0059     case OID_gostTC26Sign512A:
0060         return &gost_tc512a;
0061     case OID_gostTC26Sign512B:
0062         return &gost_tc512b;
0063     /* The following two aren't implemented: */
0064     case OID_gostTC26Sign256A:
0065     case OID_gostTC26Sign512C:
0066     default:
0067         return NULL;
0068     }
0069 }
0070
0071 static int ecrdsa_verify(struct akcipher_request *req)
0072 {
0073     struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
0074     struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
0075     unsigned char sig[ECRDSA_MAX_SIG_SIZE];
0076     unsigned char digest[STREEBOG512_DIGEST_SIZE];
0077     unsigned int ndigits = req->dst_len / sizeof(u64);
0078     u64 r[ECRDSA_MAX_DIGITS]; /* witness (r) */
0079     u64 _r[ECRDSA_MAX_DIGITS]; /* -r */
0080     u64 s[ECRDSA_MAX_DIGITS]; /* second part of sig (s) */
0081     u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q */
0082     u64 *v = e;       /* e^{-1} \mod q */
0083     u64 z1[ECRDSA_MAX_DIGITS];
0084     u64 *z2 = _r;
0085     struct ecc_point cc = ECC_POINT_INIT(s, e, ndigits); /* reuse s, e */
0086
0087     /*
0088      * Digest value, digest algorithm, and curve (modulus) should have the
0089      * same length (256 or 512 bits), public key and signature should be
0090      * twice bigger.
0091      */
0092     if (!ctx->curve ||
0093         !ctx->digest ||
0094         !req->src ||
0095         !ctx->pub_key.x ||
0096         req->dst_len != ctx->digest_len ||
0097         req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
0098         ctx->pub_key.ndigits != ctx->curve->g.ndigits ||
0099         req->dst_len * 2 != req->src_len ||
0100         WARN_ON(req->src_len > sizeof(sig)) ||
0101         WARN_ON(req->dst_len > sizeof(digest)))
0102         return -EBADMSG;
0103
0104     sg_copy_to_buffer(req->src, sg_nents_for_len(req->src, req->src_len),
0105               sig, req->src_len);
0106     sg_pcopy_to_buffer(req->src,
0107                sg_nents_for_len(req->src,
0108                         req->src_len + req->dst_len),
0109                digest, req->dst_len, req->src_len);
0110
0111     vli_from_be64(s, sig, ndigits);
0112     vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
0113
0114     /* Step 1: verify that 0 < r < q, 0 < s < q */
0115     if (vli_is_zero(r, ndigits) ||
0116         vli_cmp(r, ctx->curve->n, ndigits) >= 0 ||
0117         vli_is_zero(s, ndigits) ||
0118         vli_cmp(s, ctx->curve->n, ndigits) >= 0)
0119         return -EKEYREJECTED;
0120
0121     /* Step 2: calculate hash (h) of the message (passed as input) */
0122     /* Step 3: calculate e = h \mod q */
0123     vli_from_le64(e, digest, ndigits);
0124     if (vli_cmp(e, ctx->curve->n, ndigits) >= 0)
0125         vli_sub(e, e, ctx->curve->n, ndigits);
0126     if (vli_is_zero(e, ndigits))
0127         e[0] = 1;
0128
0129     /* Step 4: calculate v = e^{-1} \mod q */
0130     vli_mod_inv(v, e, ctx->curve->n, ndigits);
0131
0132     /* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */
0133     vli_mod_mult_slow(z1, s, v, ctx->curve->n, ndigits);
0134     vli_sub(_r, ctx->curve->n, r, ndigits);
0135     vli_mod_mult_slow(z2, _r, v, ctx->curve->n, ndigits);
0136
0137     /* Step 6: calculate point C = z_1P + z_2Q, and R = x_c \mod q */
0138     ecc_point_mult_shamir(&cc, z1, &ctx->curve->g, z2, &ctx->pub_key,
0139                   ctx->curve);
0140     if (vli_cmp(cc.x, ctx->curve->n, ndigits) >= 0)
0141         vli_sub(cc.x, cc.x, ctx->curve->n, ndigits);
0142
0143     /* Step 7: if R == r signature is valid */
0144     if (!vli_cmp(cc.x, r, ndigits))
0145         return 0;
0146     else
0147         return -EKEYREJECTED;
0148 }
0149
0150 int ecrdsa_param_curve(void *context, size_t hdrlen, unsigned char tag,
0151                const void *value, size_t vlen)
0152 {
0153     struct ecrdsa_ctx *ctx = context;
0154
0155     ctx->curve_oid = look_up_OID(value, vlen);
0156     if (!ctx->curve_oid)
0157         return -EINVAL;
0158     ctx->curve = get_curve_by_oid(ctx->curve_oid);
0159     return 0;
0160 }
0161
0162 /* Optional. If present should match expected digest algo OID. */
0163 int ecrdsa_param_digest(void *context, size_t hdrlen, unsigned char tag,
0164             const void *value, size_t vlen)
0165 {
0166     struct ecrdsa_ctx *ctx = context;
0167     int digest_oid = look_up_OID(value, vlen);
0168
0169     if (digest_oid != ctx->digest_oid)
0170         return -EINVAL;
0171     return 0;
0172 }
0173
0174 int ecrdsa_parse_pub_key(void *context, size_t hdrlen, unsigned char tag,
0175              const void *value, size_t vlen)
0176 {
0177     struct ecrdsa_ctx *ctx = context;
0178
0179     ctx->key = value;
0180     ctx->key_len = vlen;
0181     return 0;
0182 }
0183
0184 static u8 *ecrdsa_unpack_u32(u32 *dst, void *src)
0185 {
0186     memcpy(dst, src, sizeof(u32));
0187     return src + sizeof(u32);
0188 }
0189
0190 /* Parse BER encoded subjectPublicKey. */
0191 static int ecrdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
0192                   unsigned int keylen)
0193 {
0194     struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
0195     unsigned int ndigits;
0196     u32 algo, paramlen;
0197     u8 *params;
0198     int err;
0199
0200     err = asn1_ber_decoder(&ecrdsa_pub_key_decoder, ctx, key, keylen);
0201     if (err < 0)
0202         return err;
0203
0204     /* Key parameters is in the key after keylen. */
0205     params = ecrdsa_unpack_u32(&paramlen,
0206               ecrdsa_unpack_u32(&algo, (u8 *)key + keylen));
0207
0208     if (algo == OID_gost2012PKey256) {
0209         ctx->digest = "streebog256";
0210         ctx->digest_oid = OID_gost2012Digest256;
0211         ctx->digest_len = 256 / 8;
0212     } else if (algo == OID_gost2012PKey512) {
0213         ctx->digest = "streebog512";
0214         ctx->digest_oid = OID_gost2012Digest512;
0215         ctx->digest_len = 512 / 8;
0216     } else
0217         return -ENOPKG;
0218     ctx->algo_oid = algo;
0219
0220     /* Parse SubjectPublicKeyInfo.AlgorithmIdentifier.parameters. */
0221     err = asn1_ber_decoder(&ecrdsa_params_decoder, ctx, params, paramlen);
0222     if (err < 0)
0223         return err;
0224     /*
0225      * Sizes of algo (set in digest_len) and curve should match
0226      * each other.
0227      */
0228     if (!ctx->curve ||
0229         ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
0230         return -ENOPKG;
0231     /*
0232      * Key is two 256- or 512-bit coordinates which should match
0233      * curve size.
0234      */
0235     if ((ctx->key_len != (2 * 256 / 8) &&
0236          ctx->key_len != (2 * 512 / 8)) ||
0237         ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
0238         return -ENOPKG;
0239
0240     ndigits = ctx->key_len / sizeof(u64) / 2;
0241     ctx->pub_key = ECC_POINT_INIT(ctx->_pubp[0], ctx->_pubp[1], ndigits);
0242     vli_from_le64(ctx->pub_key.x, ctx->key, ndigits);
0243     vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
0244               ndigits);
0245
0246     if (ecc_is_pubkey_valid_partial(ctx->curve, &ctx->pub_key))
0247         return -EKEYREJECTED;
0248
0249     return 0;
0250 }
0251
0252 static unsigned int ecrdsa_max_size(struct crypto_akcipher *tfm)
0253 {
0254     struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
0255
0256     /*
0257      * Verify doesn't need any output, so it's just informational
0258      * for keyctl to determine the key bit size.
0259      */
0260     return ctx->pub_key.ndigits * sizeof(u64);
0261 }
0262
0263 static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm)
0264 {
0265 }
0266
0267 static struct akcipher_alg ecrdsa_alg = {
0268     .verify     = ecrdsa_verify,
0269     .set_pub_key    = ecrdsa_set_pub_key,
0270     .max_size   = ecrdsa_max_size,
0271     .exit       = ecrdsa_exit_tfm,
0272     .base = {
0273         .cra_name    = "ecrdsa",
0274         .cra_driver_name = "ecrdsa-generic",
0275         .cra_priority    = 100,
0276         .cra_module  = THIS_MODULE,
0277         .cra_ctxsize     = sizeof(struct ecrdsa_ctx),
0278     },
0279 };
0280
0281 static int __init ecrdsa_mod_init(void)
0282 {
0283     return crypto_register_akcipher(&ecrdsa_alg);
0284 }
0285
0286 static void __exit ecrdsa_mod_fini(void)
0287 {
0288     crypto_unregister_akcipher(&ecrdsa_alg);
0289 }
0290
0291 module_init(ecrdsa_mod_init);
0292 module_exit(ecrdsa_mod_fini);
0293
0294 MODULE_LICENSE("GPL");
0295 MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.org>");
0296 MODULE_DESCRIPTION("EC-RDSA generic algorithm");
0297 MODULE_ALIAS_CRYPTO("ecrdsa-generic");