1 // SPDX-License-Identifier: GPL-2.0+ 1 // SPDX-License-Identifier: GPL-2.0+
2 /* 2 /*
3 * Elliptic Curve (Russian) Digital Signature 3 * Elliptic Curve (Russian) Digital Signature Algorithm for Cryptographic API
4 * 4 *
5 * Copyright (c) 2019 Vitaly Chikunov <vt@altl 5 * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
6 * 6 *
7 * References: 7 * References:
8 * GOST 34.10-2018, GOST R 34.10-2012, RFC 709 8 * GOST 34.10-2018, GOST R 34.10-2012, RFC 7091, ISO/IEC 14888-3:2018.
9 * 9 *
10 * Historical references: 10 * Historical references:
11 * GOST R 34.10-2001, RFC 4357, ISO/IEC 14888- 11 * GOST R 34.10-2001, RFC 4357, ISO/IEC 14888-3:2006/Amd 1:2010.
12 * 12 *
13 * This program is free software; you can redi 13 * This program is free software; you can redistribute it and/or modify it
14 * under the terms of the GNU General Public L 14 * under the terms of the GNU General Public License as published by the Free
15 * Software Foundation; either version 2 of th 15 * Software Foundation; either version 2 of the License, or (at your option)
16 * any later version. 16 * any later version.
17 */ 17 */
18 18
19 #include <linux/module.h> 19 #include <linux/module.h>
20 #include <linux/crypto.h> 20 #include <linux/crypto.h>
21 #include <crypto/streebog.h> 21 #include <crypto/streebog.h>
22 #include <crypto/internal/akcipher.h> 22 #include <crypto/internal/akcipher.h>
23 #include <crypto/internal/ecc.h> <<
24 #include <crypto/akcipher.h> 23 #include <crypto/akcipher.h>
25 #include <linux/oid_registry.h> 24 #include <linux/oid_registry.h>
26 #include <linux/scatterlist.h> <<
27 #include "ecrdsa_params.asn1.h" 25 #include "ecrdsa_params.asn1.h"
28 #include "ecrdsa_pub_key.asn1.h" 26 #include "ecrdsa_pub_key.asn1.h"
>> 27 #include "ecc.h"
29 #include "ecrdsa_defs.h" 28 #include "ecrdsa_defs.h"
30 29
31 #define ECRDSA_MAX_SIG_SIZE (2 * 512 / 8) 30 #define ECRDSA_MAX_SIG_SIZE (2 * 512 / 8)
32 #define ECRDSA_MAX_DIGITS (512 / 64) 31 #define ECRDSA_MAX_DIGITS (512 / 64)
33 32
34 struct ecrdsa_ctx { 33 struct ecrdsa_ctx {
35 enum OID algo_oid; /* overall public k 34 enum OID algo_oid; /* overall public key oid */
36 enum OID curve_oid; /* parameter */ 35 enum OID curve_oid; /* parameter */
37 enum OID digest_oid; /* parameter */ 36 enum OID digest_oid; /* parameter */
38 const struct ecc_curve *curve; /* curv 37 const struct ecc_curve *curve; /* curve from oid */
39 unsigned int digest_len; /* parameter 38 unsigned int digest_len; /* parameter (bytes) */
40 const char *digest; /* digest name fro 39 const char *digest; /* digest name from oid */
41 unsigned int key_len; /* @key length ( 40 unsigned int key_len; /* @key length (bytes) */
42 const char *key; /* raw public key */ 41 const char *key; /* raw public key */
43 struct ecc_point pub_key; 42 struct ecc_point pub_key;
44 u64 _pubp[2][ECRDSA_MAX_DIGITS]; /* po 43 u64 _pubp[2][ECRDSA_MAX_DIGITS]; /* point storage for @pub_key */
45 }; 44 };
46 45
47 static const struct ecc_curve *get_curve_by_oi 46 static const struct ecc_curve *get_curve_by_oid(enum OID oid)
48 { 47 {
49 switch (oid) { 48 switch (oid) {
50 case OID_gostCPSignA: 49 case OID_gostCPSignA:
51 case OID_gostTC26Sign256B: 50 case OID_gostTC26Sign256B:
52 return &gost_cp256a; 51 return &gost_cp256a;
53 case OID_gostCPSignB: 52 case OID_gostCPSignB:
54 case OID_gostTC26Sign256C: 53 case OID_gostTC26Sign256C:
55 return &gost_cp256b; 54 return &gost_cp256b;
56 case OID_gostCPSignC: 55 case OID_gostCPSignC:
57 case OID_gostTC26Sign256D: 56 case OID_gostTC26Sign256D:
58 return &gost_cp256c; 57 return &gost_cp256c;
59 case OID_gostTC26Sign512A: 58 case OID_gostTC26Sign512A:
60 return &gost_tc512a; 59 return &gost_tc512a;
61 case OID_gostTC26Sign512B: 60 case OID_gostTC26Sign512B:
62 return &gost_tc512b; 61 return &gost_tc512b;
63 /* The following two aren't implemente 62 /* The following two aren't implemented: */
64 case OID_gostTC26Sign256A: 63 case OID_gostTC26Sign256A:
65 case OID_gostTC26Sign512C: 64 case OID_gostTC26Sign512C:
66 default: 65 default:
67 return NULL; 66 return NULL;
68 } 67 }
69 } 68 }
70 69
71 static int ecrdsa_verify(struct akcipher_reque 70 static int ecrdsa_verify(struct akcipher_request *req)
72 { 71 {
73 struct crypto_akcipher *tfm = crypto_a 72 struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
74 struct ecrdsa_ctx *ctx = akcipher_tfm_ 73 struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
75 unsigned char sig[ECRDSA_MAX_SIG_SIZE] 74 unsigned char sig[ECRDSA_MAX_SIG_SIZE];
76 unsigned char digest[STREEBOG512_DIGES 75 unsigned char digest[STREEBOG512_DIGEST_SIZE];
77 unsigned int ndigits = req->dst_len / 76 unsigned int ndigits = req->dst_len / sizeof(u64);
78 u64 r[ECRDSA_MAX_DIGITS]; /* witness ( 77 u64 r[ECRDSA_MAX_DIGITS]; /* witness (r) */
79 u64 _r[ECRDSA_MAX_DIGITS]; /* -r */ 78 u64 _r[ECRDSA_MAX_DIGITS]; /* -r */
80 u64 s[ECRDSA_MAX_DIGITS]; /* second pa 79 u64 s[ECRDSA_MAX_DIGITS]; /* second part of sig (s) */
81 u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q 80 u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q */
82 u64 *v = e; /* e^{-1} \m 81 u64 *v = e; /* e^{-1} \mod q */
83 u64 z1[ECRDSA_MAX_DIGITS]; 82 u64 z1[ECRDSA_MAX_DIGITS];
84 u64 *z2 = _r; 83 u64 *z2 = _r;
85 struct ecc_point cc = ECC_POINT_INIT(s 84 struct ecc_point cc = ECC_POINT_INIT(s, e, ndigits); /* reuse s, e */
86 85
87 /* 86 /*
88 * Digest value, digest algorithm, and 87 * Digest value, digest algorithm, and curve (modulus) should have the
89 * same length (256 or 512 bits), publ 88 * same length (256 or 512 bits), public key and signature should be
90 * twice bigger. 89 * twice bigger.
91 */ 90 */
92 if (!ctx->curve || 91 if (!ctx->curve ||
93 !ctx->digest || 92 !ctx->digest ||
94 !req->src || 93 !req->src ||
95 !ctx->pub_key.x || 94 !ctx->pub_key.x ||
96 req->dst_len != ctx->digest_len || 95 req->dst_len != ctx->digest_len ||
97 req->dst_len != ctx->curve->g.ndig 96 req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
98 ctx->pub_key.ndigits != ctx->curve 97 ctx->pub_key.ndigits != ctx->curve->g.ndigits ||
99 req->dst_len * 2 != req->src_len | 98 req->dst_len * 2 != req->src_len ||
100 WARN_ON(req->src_len > sizeof(sig) 99 WARN_ON(req->src_len > sizeof(sig)) ||
101 WARN_ON(req->dst_len > sizeof(dige 100 WARN_ON(req->dst_len > sizeof(digest)))
102 return -EBADMSG; 101 return -EBADMSG;
103 102
104 sg_copy_to_buffer(req->src, sg_nents_f 103 sg_copy_to_buffer(req->src, sg_nents_for_len(req->src, req->src_len),
105 sig, req->src_len); 104 sig, req->src_len);
106 sg_pcopy_to_buffer(req->src, 105 sg_pcopy_to_buffer(req->src,
107 sg_nents_for_len(re 106 sg_nents_for_len(req->src,
108 re 107 req->src_len + req->dst_len),
109 digest, req->dst_le 108 digest, req->dst_len, req->src_len);
110 109
111 vli_from_be64(s, sig, ndigits); 110 vli_from_be64(s, sig, ndigits);
112 vli_from_be64(r, sig + ndigits * sizeo 111 vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
113 112
114 /* Step 1: verify that 0 < r < q, 0 < 113 /* Step 1: verify that 0 < r < q, 0 < s < q */
115 if (vli_is_zero(r, ndigits) || 114 if (vli_is_zero(r, ndigits) ||
116 vli_cmp(r, ctx->curve->n, ndigits) !! 115 vli_cmp(r, ctx->curve->n, ndigits) == 1 ||
117 vli_is_zero(s, ndigits) || 116 vli_is_zero(s, ndigits) ||
118 vli_cmp(s, ctx->curve->n, ndigits) !! 117 vli_cmp(s, ctx->curve->n, ndigits) == 1)
119 return -EKEYREJECTED; 118 return -EKEYREJECTED;
120 119
121 /* Step 2: calculate hash (h) of the m 120 /* Step 2: calculate hash (h) of the message (passed as input) */
122 /* Step 3: calculate e = h \mod q */ 121 /* Step 3: calculate e = h \mod q */
123 vli_from_le64(e, digest, ndigits); 122 vli_from_le64(e, digest, ndigits);
124 if (vli_cmp(e, ctx->curve->n, ndigits) !! 123 if (vli_cmp(e, ctx->curve->n, ndigits) == 1)
125 vli_sub(e, e, ctx->curve->n, n 124 vli_sub(e, e, ctx->curve->n, ndigits);
126 if (vli_is_zero(e, ndigits)) 125 if (vli_is_zero(e, ndigits))
127 e[0] = 1; 126 e[0] = 1;
128 127
129 /* Step 4: calculate v = e^{-1} \mod q 128 /* Step 4: calculate v = e^{-1} \mod q */
130 vli_mod_inv(v, e, ctx->curve->n, ndigi 129 vli_mod_inv(v, e, ctx->curve->n, ndigits);
131 130
132 /* Step 5: calculate z_1 = sv \mod q, 131 /* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */
133 vli_mod_mult_slow(z1, s, v, ctx->curve 132 vli_mod_mult_slow(z1, s, v, ctx->curve->n, ndigits);
134 vli_sub(_r, ctx->curve->n, r, ndigits) 133 vli_sub(_r, ctx->curve->n, r, ndigits);
135 vli_mod_mult_slow(z2, _r, v, ctx->curv 134 vli_mod_mult_slow(z2, _r, v, ctx->curve->n, ndigits);
136 135
137 /* Step 6: calculate point C = z_1P + 136 /* Step 6: calculate point C = z_1P + z_2Q, and R = x_c \mod q */
138 ecc_point_mult_shamir(&cc, z1, &ctx->c 137 ecc_point_mult_shamir(&cc, z1, &ctx->curve->g, z2, &ctx->pub_key,
139 ctx->curve); 138 ctx->curve);
140 if (vli_cmp(cc.x, ctx->curve->n, ndigi !! 139 if (vli_cmp(cc.x, ctx->curve->n, ndigits) == 1)
141 vli_sub(cc.x, cc.x, ctx->curve 140 vli_sub(cc.x, cc.x, ctx->curve->n, ndigits);
142 141
143 /* Step 7: if R == r signature is vali 142 /* Step 7: if R == r signature is valid */
144 if (!vli_cmp(cc.x, r, ndigits)) 143 if (!vli_cmp(cc.x, r, ndigits))
145 return 0; 144 return 0;
146 else 145 else
147 return -EKEYREJECTED; 146 return -EKEYREJECTED;
148 } 147 }
149 148
150 int ecrdsa_param_curve(void *context, size_t h 149 int ecrdsa_param_curve(void *context, size_t hdrlen, unsigned char tag,
151 const void *value, size 150 const void *value, size_t vlen)
152 { 151 {
153 struct ecrdsa_ctx *ctx = context; 152 struct ecrdsa_ctx *ctx = context;
154 153
155 ctx->curve_oid = look_up_OID(value, vl 154 ctx->curve_oid = look_up_OID(value, vlen);
156 if (!ctx->curve_oid) 155 if (!ctx->curve_oid)
157 return -EINVAL; 156 return -EINVAL;
158 ctx->curve = get_curve_by_oid(ctx->cur 157 ctx->curve = get_curve_by_oid(ctx->curve_oid);
159 return 0; 158 return 0;
160 } 159 }
161 160
162 /* Optional. If present should match expected 161 /* Optional. If present should match expected digest algo OID. */
163 int ecrdsa_param_digest(void *context, size_t 162 int ecrdsa_param_digest(void *context, size_t hdrlen, unsigned char tag,
164 const void *value, siz 163 const void *value, size_t vlen)
165 { 164 {
166 struct ecrdsa_ctx *ctx = context; 165 struct ecrdsa_ctx *ctx = context;
167 int digest_oid = look_up_OID(value, vl 166 int digest_oid = look_up_OID(value, vlen);
168 167
169 if (digest_oid != ctx->digest_oid) 168 if (digest_oid != ctx->digest_oid)
170 return -EINVAL; 169 return -EINVAL;
171 return 0; 170 return 0;
172 } 171 }
173 172
174 int ecrdsa_parse_pub_key(void *context, size_t 173 int ecrdsa_parse_pub_key(void *context, size_t hdrlen, unsigned char tag,
175 const void *value, si 174 const void *value, size_t vlen)
176 { 175 {
177 struct ecrdsa_ctx *ctx = context; 176 struct ecrdsa_ctx *ctx = context;
178 177
179 ctx->key = value; 178 ctx->key = value;
180 ctx->key_len = vlen; 179 ctx->key_len = vlen;
181 return 0; 180 return 0;
182 } 181 }
183 182
184 static u8 *ecrdsa_unpack_u32(u32 *dst, void *s 183 static u8 *ecrdsa_unpack_u32(u32 *dst, void *src)
185 { 184 {
186 memcpy(dst, src, sizeof(u32)); 185 memcpy(dst, src, sizeof(u32));
187 return src + sizeof(u32); 186 return src + sizeof(u32);
188 } 187 }
189 188
190 /* Parse BER encoded subjectPublicKey. */ 189 /* Parse BER encoded subjectPublicKey. */
191 static int ecrdsa_set_pub_key(struct crypto_ak 190 static int ecrdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
192 unsigned int key 191 unsigned int keylen)
193 { 192 {
194 struct ecrdsa_ctx *ctx = akcipher_tfm_ 193 struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
195 unsigned int ndigits; 194 unsigned int ndigits;
196 u32 algo, paramlen; 195 u32 algo, paramlen;
197 u8 *params; 196 u8 *params;
198 int err; 197 int err;
199 198
200 err = asn1_ber_decoder(&ecrdsa_pub_key 199 err = asn1_ber_decoder(&ecrdsa_pub_key_decoder, ctx, key, keylen);
201 if (err < 0) 200 if (err < 0)
202 return err; 201 return err;
203 202
204 /* Key parameters is in the key after 203 /* Key parameters is in the key after keylen. */
205 params = ecrdsa_unpack_u32(¶mlen, 204 params = ecrdsa_unpack_u32(¶mlen,
206 ecrdsa_unpack_u32(&a 205 ecrdsa_unpack_u32(&algo, (u8 *)key + keylen));
207 206
208 if (algo == OID_gost2012PKey256) { 207 if (algo == OID_gost2012PKey256) {
209 ctx->digest = "streebog256 208 ctx->digest = "streebog256";
210 ctx->digest_oid = OID_gost2012 209 ctx->digest_oid = OID_gost2012Digest256;
211 ctx->digest_len = 256 / 8; 210 ctx->digest_len = 256 / 8;
212 } else if (algo == OID_gost2012PKey512 211 } else if (algo == OID_gost2012PKey512) {
213 ctx->digest = "streebog512 212 ctx->digest = "streebog512";
214 ctx->digest_oid = OID_gost2012 213 ctx->digest_oid = OID_gost2012Digest512;
215 ctx->digest_len = 512 / 8; 214 ctx->digest_len = 512 / 8;
216 } else 215 } else
217 return -ENOPKG; 216 return -ENOPKG;
218 ctx->algo_oid = algo; 217 ctx->algo_oid = algo;
219 218
220 /* Parse SubjectPublicKeyInfo.Algorith 219 /* Parse SubjectPublicKeyInfo.AlgorithmIdentifier.parameters. */
221 err = asn1_ber_decoder(&ecrdsa_params_ 220 err = asn1_ber_decoder(&ecrdsa_params_decoder, ctx, params, paramlen);
222 if (err < 0) 221 if (err < 0)
223 return err; 222 return err;
224 /* 223 /*
225 * Sizes of algo (set in digest_len) a 224 * Sizes of algo (set in digest_len) and curve should match
226 * each other. 225 * each other.
227 */ 226 */
228 if (!ctx->curve || 227 if (!ctx->curve ||
229 ctx->curve->g.ndigits * sizeof(u64 228 ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
230 return -ENOPKG; 229 return -ENOPKG;
231 /* 230 /*
232 * Key is two 256- or 512-bit coordina 231 * Key is two 256- or 512-bit coordinates which should match
233 * curve size. 232 * curve size.
234 */ 233 */
235 if ((ctx->key_len != (2 * 256 / 8) && 234 if ((ctx->key_len != (2 * 256 / 8) &&
236 ctx->key_len != (2 * 512 / 8)) || 235 ctx->key_len != (2 * 512 / 8)) ||
237 ctx->key_len != ctx->curve->g.ndig 236 ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
238 return -ENOPKG; 237 return -ENOPKG;
239 238
240 ndigits = ctx->key_len / sizeof(u64) / 239 ndigits = ctx->key_len / sizeof(u64) / 2;
241 ctx->pub_key = ECC_POINT_INIT(ctx->_pu 240 ctx->pub_key = ECC_POINT_INIT(ctx->_pubp[0], ctx->_pubp[1], ndigits);
242 vli_from_le64(ctx->pub_key.x, ctx->key 241 vli_from_le64(ctx->pub_key.x, ctx->key, ndigits);
243 vli_from_le64(ctx->pub_key.y, ctx->key 242 vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
244 ndigits); 243 ndigits);
245 244
246 if (ecc_is_pubkey_valid_partial(ctx->c 245 if (ecc_is_pubkey_valid_partial(ctx->curve, &ctx->pub_key))
247 return -EKEYREJECTED; 246 return -EKEYREJECTED;
248 247
249 return 0; 248 return 0;
250 } 249 }
251 250
252 static unsigned int ecrdsa_max_size(struct cry 251 static unsigned int ecrdsa_max_size(struct crypto_akcipher *tfm)
253 { 252 {
254 struct ecrdsa_ctx *ctx = akcipher_tfm_ 253 struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
255 254
256 /* 255 /*
257 * Verify doesn't need any output, so 256 * Verify doesn't need any output, so it's just informational
258 * for keyctl to determine the key bit 257 * for keyctl to determine the key bit size.
259 */ 258 */
260 return ctx->pub_key.ndigits * sizeof(u 259 return ctx->pub_key.ndigits * sizeof(u64);
261 } 260 }
262 261
263 static void ecrdsa_exit_tfm(struct crypto_akci 262 static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm)
264 { 263 {
265 } 264 }
266 265
267 static struct akcipher_alg ecrdsa_alg = { 266 static struct akcipher_alg ecrdsa_alg = {
268 .verify = ecrdsa_verify, 267 .verify = ecrdsa_verify,
269 .set_pub_key = ecrdsa_set_pub_key, 268 .set_pub_key = ecrdsa_set_pub_key,
270 .max_size = ecrdsa_max_size, 269 .max_size = ecrdsa_max_size,
271 .exit = ecrdsa_exit_tfm, 270 .exit = ecrdsa_exit_tfm,
272 .base = { 271 .base = {
273 .cra_name = "ecrdsa", 272 .cra_name = "ecrdsa",
274 .cra_driver_name = "ecrdsa-gen 273 .cra_driver_name = "ecrdsa-generic",
275 .cra_priority = 100, 274 .cra_priority = 100,
276 .cra_module = THIS_MODULE 275 .cra_module = THIS_MODULE,
277 .cra_ctxsize = sizeof(stru 276 .cra_ctxsize = sizeof(struct ecrdsa_ctx),
278 }, 277 },
279 }; 278 };
280 279
281 static int __init ecrdsa_mod_init(void) 280 static int __init ecrdsa_mod_init(void)
282 { 281 {
283 return crypto_register_akcipher(&ecrds 282 return crypto_register_akcipher(&ecrdsa_alg);
284 } 283 }
285 284
286 static void __exit ecrdsa_mod_fini(void) 285 static void __exit ecrdsa_mod_fini(void)
287 { 286 {
288 crypto_unregister_akcipher(&ecrdsa_alg 287 crypto_unregister_akcipher(&ecrdsa_alg);
289 } 288 }
290 289
291 module_init(ecrdsa_mod_init); 290 module_init(ecrdsa_mod_init);
292 module_exit(ecrdsa_mod_fini); 291 module_exit(ecrdsa_mod_fini);
293 292
294 MODULE_LICENSE("GPL"); 293 MODULE_LICENSE("GPL");
295 MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.or 294 MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.org>");
296 MODULE_DESCRIPTION("EC-RDSA generic algorithm" 295 MODULE_DESCRIPTION("EC-RDSA generic algorithm");
297 MODULE_ALIAS_CRYPTO("ecrdsa"); <<
298 MODULE_ALIAS_CRYPTO("ecrdsa-generic"); 296 MODULE_ALIAS_CRYPTO("ecrdsa-generic");
299 297
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.