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 | |
34 | struct 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 | |
47 | static 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 | |
71 | static 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(sgl: req->src, nents: sg_nents_for_len(sg: req->src, len: req->src_len), |
105 | buf: sig, buflen: req->src_len); |
106 | sg_pcopy_to_buffer(sgl: req->src, |
107 | nents: sg_nents_for_len(sg: req->src, |
108 | len: req->src_len + req->dst_len), |
109 | buf: digest, buflen: req->dst_len, skip: req->src_len); |
110 | |
111 | vli_from_be64(dest: s, src: sig, ndigits); |
112 | vli_from_be64(dest: r, src: sig + ndigits * sizeof(u64), ndigits); |
113 | |
114 | /* Step 1: verify that 0 < r < q, 0 < s < q */ |
115 | if (vli_is_zero(vli: r, ndigits) || |
116 | vli_cmp(left: r, right: ctx->curve->n, ndigits) >= 0 || |
117 | vli_is_zero(vli: s, ndigits) || |
118 | vli_cmp(left: s, right: 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(dest: e, src: digest, ndigits); |
124 | if (vli_cmp(left: e, right: ctx->curve->n, ndigits) >= 0) |
125 | vli_sub(result: e, left: e, right: ctx->curve->n, ndigits); |
126 | if (vli_is_zero(vli: e, ndigits)) |
127 | e[0] = 1; |
128 | |
129 | /* Step 4: calculate v = e^{-1} \mod q */ |
130 | vli_mod_inv(result: v, input: e, mod: ctx->curve->n, ndigits); |
131 | |
132 | /* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */ |
133 | vli_mod_mult_slow(result: z1, left: s, right: v, mod: ctx->curve->n, ndigits); |
134 | vli_sub(result: _r, left: ctx->curve->n, right: r, ndigits); |
135 | vli_mod_mult_slow(result: z2, left: _r, right: v, mod: 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(result: &cc, x: z1, p: &ctx->curve->g, y: z2, q: &ctx->pub_key, |
139 | curve: ctx->curve); |
140 | if (vli_cmp(left: cc.x, right: ctx->curve->n, ndigits) >= 0) |
141 | vli_sub(result: cc.x, left: cc.x, right: ctx->curve->n, ndigits); |
142 | |
143 | /* Step 7: if R == r signature is valid */ |
144 | if (!vli_cmp(left: cc.x, right: r, ndigits)) |
145 | return 0; |
146 | else |
147 | return -EKEYREJECTED; |
148 | } |
149 | |
150 | int 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(data: value, datasize: vlen); |
156 | if (!ctx->curve_oid) |
157 | return -EINVAL; |
158 | ctx->curve = get_curve_by_oid(oid: ctx->curve_oid); |
159 | return 0; |
160 | } |
161 | |
162 | /* Optional. If present should match expected digest algo OID. */ |
163 | int 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(data: value, datasize: vlen); |
168 | |
169 | if (digest_oid != ctx->digest_oid) |
170 | return -EINVAL; |
171 | return 0; |
172 | } |
173 | |
174 | int 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 | |
184 | static 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. */ |
191 | static 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(dst: ¶mlen, |
206 | src: ecrdsa_unpack_u32(dst: &algo, src: (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(dest: ctx->pub_key.x, src: ctx->key, ndigits); |
243 | vli_from_le64(dest: ctx->pub_key.y, src: ctx->key + ndigits * sizeof(u64), |
244 | ndigits); |
245 | |
246 | if (ecc_is_pubkey_valid_partial(curve: ctx->curve, pk: &ctx->pub_key)) |
247 | return -EKEYREJECTED; |
248 | |
249 | return 0; |
250 | } |
251 | |
252 | static 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 | |
263 | static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm) |
264 | { |
265 | } |
266 | |
267 | static 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 | |
281 | static int __init ecrdsa_mod_init(void) |
282 | { |
283 | return crypto_register_akcipher(alg: &ecrdsa_alg); |
284 | } |
285 | |
286 | static void __exit ecrdsa_mod_fini(void) |
287 | { |
288 | crypto_unregister_akcipher(alg: &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-generic" ); |
298 | |