299 lines · c
1// SPDX-License-Identifier: GPL-2.0+2/*3 * Elliptic Curve (Russian) Digital Signature Algorithm for Cryptographic API4 *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 it14 * under the terms of the GNU General Public License as published by the Free15 * 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/internal/ecc.h>24#include <crypto/akcipher.h>25#include <linux/oid_registry.h>26#include <linux/scatterlist.h>27#include "ecrdsa_params.asn1.h"28#include "ecrdsa_pub_key.asn1.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 the89 * same length (256 or 512 bits), public key and signature should be90 * 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) >= 0 ||117 vli_is_zero(s, ndigits) ||118 vli_cmp(s, ctx->curve->n, ndigits) >= 0)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) >= 0)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) >= 0)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 else147 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(¶mlen,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 } else217 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 match226 * 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 match233 * 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 informational258 * 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");298MODULE_ALIAS_CRYPTO("ecrdsa-generic");299