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