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/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 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) >= 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	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