crypto/ecrdsa.c

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