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 "ecrdsa_params.asn1.h"
26 #include "ecrdsa_pub_key.asn1.h"
27 #include "ecc.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 
get_curve_by_oid(enum OID oid)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 
ecrdsa_verify(struct akcipher_request * req)70 static int ecrdsa_verify(struct akcipher_request *req)
71 {
72 	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
73 	struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
74 	unsigned char sig[ECRDSA_MAX_SIG_SIZE];
75 	unsigned char digest[STREEBOG512_DIGEST_SIZE];
76 	unsigned int ndigits = req->dst_len / sizeof(u64);
77 	u64 r[ECRDSA_MAX_DIGITS]; /* witness (r) */
78 	u64 _r[ECRDSA_MAX_DIGITS]; /* -r */
79 	u64 s[ECRDSA_MAX_DIGITS]; /* second part of sig (s) */
80 	u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q */
81 	u64 *v = e;		  /* e^{-1} \mod q */
82 	u64 z1[ECRDSA_MAX_DIGITS];
83 	u64 *z2 = _r;
84 	struct ecc_point cc = ECC_POINT_INIT(s, e, ndigits); /* reuse s, e */
85 
86 	/*
87 	 * Digest value, digest algorithm, and curve (modulus) should have the
88 	 * same length (256 or 512 bits), public key and signature should be
89 	 * twice bigger.
90 	 */
91 	if (!ctx->curve ||
92 	    !ctx->digest ||
93 	    !req->src ||
94 	    !ctx->pub_key.x ||
95 	    req->dst_len != ctx->digest_len ||
96 	    req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
97 	    ctx->pub_key.ndigits != ctx->curve->g.ndigits ||
98 	    req->dst_len * 2 != req->src_len ||
99 	    WARN_ON(req->src_len > sizeof(sig)) ||
100 	    WARN_ON(req->dst_len > sizeof(digest)))
101 		return -EBADMSG;
102 
103 	sg_copy_to_buffer(req->src, sg_nents_for_len(req->src, req->src_len),
104 			  sig, req->src_len);
105 	sg_pcopy_to_buffer(req->src,
106 			   sg_nents_for_len(req->src,
107 					    req->src_len + req->dst_len),
108 			   digest, req->dst_len, req->src_len);
109 
110 	vli_from_be64(s, sig, ndigits);
111 	vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
112 
113 	/* Step 1: verify that 0 < r < q, 0 < s < q */
114 	if (vli_is_zero(r, ndigits) ||
115 	    vli_cmp(r, ctx->curve->n, ndigits) == 1 ||
116 	    vli_is_zero(s, ndigits) ||
117 	    vli_cmp(s, ctx->curve->n, ndigits) == 1)
118 		return -EKEYREJECTED;
119 
120 	/* Step 2: calculate hash (h) of the message (passed as input) */
121 	/* Step 3: calculate e = h \mod q */
122 	vli_from_le64(e, digest, ndigits);
123 	if (vli_cmp(e, ctx->curve->n, ndigits) == 1)
124 		vli_sub(e, e, ctx->curve->n, ndigits);
125 	if (vli_is_zero(e, ndigits))
126 		e[0] = 1;
127 
128 	/* Step 4: calculate v = e^{-1} \mod q */
129 	vli_mod_inv(v, e, ctx->curve->n, ndigits);
130 
131 	/* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */
132 	vli_mod_mult_slow(z1, s, v, ctx->curve->n, ndigits);
133 	vli_sub(_r, ctx->curve->n, r, ndigits);
134 	vli_mod_mult_slow(z2, _r, v, ctx->curve->n, ndigits);
135 
136 	/* Step 6: calculate point C = z_1P + z_2Q, and R = x_c \mod q */
137 	ecc_point_mult_shamir(&cc, z1, &ctx->curve->g, z2, &ctx->pub_key,
138 			      ctx->curve);
139 	if (vli_cmp(cc.x, ctx->curve->n, ndigits) == 1)
140 		vli_sub(cc.x, cc.x, ctx->curve->n, ndigits);
141 
142 	/* Step 7: if R == r signature is valid */
143 	if (!vli_cmp(cc.x, r, ndigits))
144 		return 0;
145 	else
146 		return -EKEYREJECTED;
147 }
148 
ecrdsa_param_curve(void * context,size_t hdrlen,unsigned char tag,const void * value,size_t vlen)149 int ecrdsa_param_curve(void *context, size_t hdrlen, unsigned char tag,
150 		       const void *value, size_t vlen)
151 {
152 	struct ecrdsa_ctx *ctx = context;
153 
154 	ctx->curve_oid = look_up_OID(value, vlen);
155 	if (!ctx->curve_oid)
156 		return -EINVAL;
157 	ctx->curve = get_curve_by_oid(ctx->curve_oid);
158 	return 0;
159 }
160 
161 /* Optional. If present should match expected digest algo OID. */
ecrdsa_param_digest(void * context,size_t hdrlen,unsigned char tag,const void * value,size_t vlen)162 int ecrdsa_param_digest(void *context, size_t hdrlen, unsigned char tag,
163 			const void *value, size_t vlen)
164 {
165 	struct ecrdsa_ctx *ctx = context;
166 	int digest_oid = look_up_OID(value, vlen);
167 
168 	if (digest_oid != ctx->digest_oid)
169 		return -EINVAL;
170 	return 0;
171 }
172 
ecrdsa_parse_pub_key(void * context,size_t hdrlen,unsigned char tag,const void * value,size_t vlen)173 int ecrdsa_parse_pub_key(void *context, size_t hdrlen, unsigned char tag,
174 			 const void *value, size_t vlen)
175 {
176 	struct ecrdsa_ctx *ctx = context;
177 
178 	ctx->key = value;
179 	ctx->key_len = vlen;
180 	return 0;
181 }
182 
ecrdsa_unpack_u32(u32 * dst,void * src)183 static u8 *ecrdsa_unpack_u32(u32 *dst, void *src)
184 {
185 	memcpy(dst, src, sizeof(u32));
186 	return src + sizeof(u32);
187 }
188 
189 /* Parse BER encoded subjectPublicKey. */
ecrdsa_set_pub_key(struct crypto_akcipher * tfm,const void * key,unsigned int keylen)190 static int ecrdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
191 			      unsigned int keylen)
192 {
193 	struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
194 	unsigned int ndigits;
195 	u32 algo, paramlen;
196 	u8 *params;
197 	int err;
198 
199 	err = asn1_ber_decoder(&ecrdsa_pub_key_decoder, ctx, key, keylen);
200 	if (err < 0)
201 		return err;
202 
203 	/* Key parameters is in the key after keylen. */
204 	params = ecrdsa_unpack_u32(&paramlen,
205 			  ecrdsa_unpack_u32(&algo, (u8 *)key + keylen));
206 
207 	if (algo == OID_gost2012PKey256) {
208 		ctx->digest	= "streebog256";
209 		ctx->digest_oid	= OID_gost2012Digest256;
210 		ctx->digest_len	= 256 / 8;
211 	} else if (algo == OID_gost2012PKey512) {
212 		ctx->digest	= "streebog512";
213 		ctx->digest_oid	= OID_gost2012Digest512;
214 		ctx->digest_len	= 512 / 8;
215 	} else
216 		return -ENOPKG;
217 	ctx->algo_oid = algo;
218 
219 	/* Parse SubjectPublicKeyInfo.AlgorithmIdentifier.parameters. */
220 	err = asn1_ber_decoder(&ecrdsa_params_decoder, ctx, params, paramlen);
221 	if (err < 0)
222 		return err;
223 	/*
224 	 * Sizes of algo (set in digest_len) and curve should match
225 	 * each other.
226 	 */
227 	if (!ctx->curve ||
228 	    ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
229 		return -ENOPKG;
230 	/*
231 	 * Key is two 256- or 512-bit coordinates which should match
232 	 * curve size.
233 	 */
234 	if ((ctx->key_len != (2 * 256 / 8) &&
235 	     ctx->key_len != (2 * 512 / 8)) ||
236 	    ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
237 		return -ENOPKG;
238 
239 	ndigits = ctx->key_len / sizeof(u64) / 2;
240 	ctx->pub_key = ECC_POINT_INIT(ctx->_pubp[0], ctx->_pubp[1], ndigits);
241 	vli_from_le64(ctx->pub_key.x, ctx->key, ndigits);
242 	vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
243 		      ndigits);
244 
245 	if (ecc_is_pubkey_valid_partial(ctx->curve, &ctx->pub_key))
246 		return -EKEYREJECTED;
247 
248 	return 0;
249 }
250 
ecrdsa_max_size(struct crypto_akcipher * tfm)251 static unsigned int ecrdsa_max_size(struct crypto_akcipher *tfm)
252 {
253 	struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
254 
255 	/*
256 	 * Verify doesn't need any output, so it's just informational
257 	 * for keyctl to determine the key bit size.
258 	 */
259 	return ctx->pub_key.ndigits * sizeof(u64);
260 }
261 
ecrdsa_exit_tfm(struct crypto_akcipher * tfm)262 static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm)
263 {
264 }
265 
266 static struct akcipher_alg ecrdsa_alg = {
267 	.verify		= ecrdsa_verify,
268 	.set_pub_key	= ecrdsa_set_pub_key,
269 	.max_size	= ecrdsa_max_size,
270 	.exit		= ecrdsa_exit_tfm,
271 	.base = {
272 		.cra_name	 = "ecrdsa",
273 		.cra_driver_name = "ecrdsa-generic",
274 		.cra_priority	 = 100,
275 		.cra_module	 = THIS_MODULE,
276 		.cra_ctxsize	 = sizeof(struct ecrdsa_ctx),
277 	},
278 };
279 
ecrdsa_mod_init(void)280 static int __init ecrdsa_mod_init(void)
281 {
282 	return crypto_register_akcipher(&ecrdsa_alg);
283 }
284 
ecrdsa_mod_fini(void)285 static void __exit ecrdsa_mod_fini(void)
286 {
287 	crypto_unregister_akcipher(&ecrdsa_alg);
288 }
289 
290 module_init(ecrdsa_mod_init);
291 module_exit(ecrdsa_mod_fini);
292 
293 MODULE_LICENSE("GPL");
294 MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.org>");
295 MODULE_DESCRIPTION("EC-RDSA generic algorithm");
296 MODULE_ALIAS_CRYPTO("ecrdsa-generic");
297