1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * Copyright (c) 2021 IBM Corporation
4  */
5 
6 #include <linux/module.h>
7 #include <crypto/internal/akcipher.h>
8 #include <crypto/internal/ecc.h>
9 #include <crypto/akcipher.h>
10 #include <crypto/ecdh.h>
11 #include <linux/asn1_decoder.h>
12 #include <linux/scatterlist.h>
13 
14 #include "ecdsasignature.asn1.h"
15 
16 struct ecc_ctx {
17 	unsigned int curve_id;
18 	const struct ecc_curve *curve;
19 
20 	bool pub_key_set;
21 	u64 x[ECC_MAX_DIGITS]; /* pub key x and y coordinates */
22 	u64 y[ECC_MAX_DIGITS];
23 	struct ecc_point pub_key;
24 };
25 
26 struct ecdsa_signature_ctx {
27 	const struct ecc_curve *curve;
28 	u64 r[ECC_MAX_DIGITS];
29 	u64 s[ECC_MAX_DIGITS];
30 };
31 
32 /*
33  * Get the r and s components of a signature from the X509 certificate.
34  */
ecdsa_get_signature_rs(u64 * dest,size_t hdrlen,unsigned char tag,const void * value,size_t vlen,unsigned int ndigits)35 static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
36 				  const void *value, size_t vlen, unsigned int ndigits)
37 {
38 	size_t keylen = ndigits * sizeof(u64);
39 	ssize_t diff = vlen - keylen;
40 	const char *d = value;
41 	u8 rs[ECC_MAX_BYTES];
42 
43 	if (!value || !vlen)
44 		return -EINVAL;
45 
46 	/* diff = 0: 'value' has exacly the right size
47 	 * diff > 0: 'value' has too many bytes; one leading zero is allowed that
48 	 *           makes the value a positive integer; error on more
49 	 * diff < 0: 'value' is missing leading zeros, which we add
50 	 */
51 	if (diff > 0) {
52 		/* skip over leading zeros that make 'value' a positive int */
53 		if (*d == 0) {
54 			vlen -= 1;
55 			diff--;
56 			d++;
57 		}
58 		if (diff)
59 			return -EINVAL;
60 	}
61 	if (-diff >= keylen)
62 		return -EINVAL;
63 
64 	if (diff) {
65 		/* leading zeros not given in 'value' */
66 		memset(rs, 0, -diff);
67 	}
68 
69 	memcpy(&rs[-diff], d, vlen);
70 
71 	ecc_swap_digits((u64 *)rs, dest, ndigits);
72 
73 	return 0;
74 }
75 
ecdsa_get_signature_r(void * context,size_t hdrlen,unsigned char tag,const void * value,size_t vlen)76 int ecdsa_get_signature_r(void *context, size_t hdrlen, unsigned char tag,
77 			  const void *value, size_t vlen)
78 {
79 	struct ecdsa_signature_ctx *sig = context;
80 
81 	return ecdsa_get_signature_rs(sig->r, hdrlen, tag, value, vlen,
82 				      sig->curve->g.ndigits);
83 }
84 
ecdsa_get_signature_s(void * context,size_t hdrlen,unsigned char tag,const void * value,size_t vlen)85 int ecdsa_get_signature_s(void *context, size_t hdrlen, unsigned char tag,
86 			  const void *value, size_t vlen)
87 {
88 	struct ecdsa_signature_ctx *sig = context;
89 
90 	return ecdsa_get_signature_rs(sig->s, hdrlen, tag, value, vlen,
91 				      sig->curve->g.ndigits);
92 }
93 
_ecdsa_verify(struct ecc_ctx * ctx,const u64 * hash,const u64 * r,const u64 * s)94 static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, const u64 *s)
95 {
96 	const struct ecc_curve *curve = ctx->curve;
97 	unsigned int ndigits = curve->g.ndigits;
98 	u64 s1[ECC_MAX_DIGITS];
99 	u64 u1[ECC_MAX_DIGITS];
100 	u64 u2[ECC_MAX_DIGITS];
101 	u64 x1[ECC_MAX_DIGITS];
102 	u64 y1[ECC_MAX_DIGITS];
103 	struct ecc_point res = ECC_POINT_INIT(x1, y1, ndigits);
104 
105 	/* 0 < r < n  and 0 < s < n */
106 	if (vli_is_zero(r, ndigits) || vli_cmp(r, curve->n, ndigits) >= 0 ||
107 	    vli_is_zero(s, ndigits) || vli_cmp(s, curve->n, ndigits) >= 0)
108 		return -EBADMSG;
109 
110 	/* hash is given */
111 	pr_devel("hash : %016llx %016llx ... %016llx\n",
112 		 hash[ndigits - 1], hash[ndigits - 2], hash[0]);
113 
114 	/* s1 = (s^-1) mod n */
115 	vli_mod_inv(s1, s, curve->n, ndigits);
116 	/* u1 = (hash * s1) mod n */
117 	vli_mod_mult_slow(u1, hash, s1, curve->n, ndigits);
118 	/* u2 = (r * s1) mod n */
119 	vli_mod_mult_slow(u2, r, s1, curve->n, ndigits);
120 	/* res = u1*G + u2 * pub_key */
121 	ecc_point_mult_shamir(&res, u1, &curve->g, u2, &ctx->pub_key, curve);
122 
123 	/* res.x = res.x mod n (if res.x > order) */
124 	if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
125 		/* faster alternative for NIST p384, p256 & p192 */
126 		vli_sub(res.x, res.x, curve->n, ndigits);
127 
128 	if (!vli_cmp(res.x, r, ndigits))
129 		return 0;
130 
131 	return -EKEYREJECTED;
132 }
133 
134 /*
135  * Verify an ECDSA signature.
136  */
ecdsa_verify(struct akcipher_request * req)137 static int ecdsa_verify(struct akcipher_request *req)
138 {
139 	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
140 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
141 	size_t keylen = ctx->curve->g.ndigits * sizeof(u64);
142 	struct ecdsa_signature_ctx sig_ctx = {
143 		.curve = ctx->curve,
144 	};
145 	u8 rawhash[ECC_MAX_BYTES];
146 	u64 hash[ECC_MAX_DIGITS];
147 	unsigned char *buffer;
148 	ssize_t diff;
149 	int ret;
150 
151 	if (unlikely(!ctx->pub_key_set))
152 		return -EINVAL;
153 
154 	buffer = kmalloc(req->src_len + req->dst_len, GFP_KERNEL);
155 	if (!buffer)
156 		return -ENOMEM;
157 
158 	sg_pcopy_to_buffer(req->src,
159 		sg_nents_for_len(req->src, req->src_len + req->dst_len),
160 		buffer, req->src_len + req->dst_len, 0);
161 
162 	ret = asn1_ber_decoder(&ecdsasignature_decoder, &sig_ctx,
163 			       buffer, req->src_len);
164 	if (ret < 0)
165 		goto error;
166 
167 	/* if the hash is shorter then we will add leading zeros to fit to ndigits */
168 	diff = keylen - req->dst_len;
169 	if (diff >= 0) {
170 		if (diff)
171 			memset(rawhash, 0, diff);
172 		memcpy(&rawhash[diff], buffer + req->src_len, req->dst_len);
173 	} else if (diff < 0) {
174 		/* given hash is longer, we take the left-most bytes */
175 		memcpy(&rawhash, buffer + req->src_len, keylen);
176 	}
177 
178 	ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);
179 
180 	ret = _ecdsa_verify(ctx, hash, sig_ctx.r, sig_ctx.s);
181 
182 error:
183 	kfree(buffer);
184 
185 	return ret;
186 }
187 
ecdsa_ecc_ctx_init(struct ecc_ctx * ctx,unsigned int curve_id)188 static int ecdsa_ecc_ctx_init(struct ecc_ctx *ctx, unsigned int curve_id)
189 {
190 	ctx->curve_id = curve_id;
191 	ctx->curve = ecc_get_curve(curve_id);
192 	if (!ctx->curve)
193 		return -EINVAL;
194 
195 	return 0;
196 }
197 
198 
ecdsa_ecc_ctx_deinit(struct ecc_ctx * ctx)199 static void ecdsa_ecc_ctx_deinit(struct ecc_ctx *ctx)
200 {
201 	ctx->pub_key_set = false;
202 }
203 
ecdsa_ecc_ctx_reset(struct ecc_ctx * ctx)204 static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
205 {
206 	unsigned int curve_id = ctx->curve_id;
207 	int ret;
208 
209 	ecdsa_ecc_ctx_deinit(ctx);
210 	ret = ecdsa_ecc_ctx_init(ctx, curve_id);
211 	if (ret == 0)
212 		ctx->pub_key = ECC_POINT_INIT(ctx->x, ctx->y,
213 					      ctx->curve->g.ndigits);
214 	return ret;
215 }
216 
217 /*
218  * Set the public key given the raw uncompressed key data from an X509
219  * certificate. The key data contain the concatenated X and Y coordinates of
220  * the public key.
221  */
ecdsa_set_pub_key(struct crypto_akcipher * tfm,const void * key,unsigned int keylen)222 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
223 {
224 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
225 	const unsigned char *d = key;
226 	const u64 *digits = (const u64 *)&d[1];
227 	unsigned int ndigits;
228 	int ret;
229 
230 	ret = ecdsa_ecc_ctx_reset(ctx);
231 	if (ret < 0)
232 		return ret;
233 
234 	if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
235 		return -EINVAL;
236 	/* we only accept uncompressed format indicated by '4' */
237 	if (d[0] != 4)
238 		return -EINVAL;
239 
240 	keylen--;
241 	ndigits = (keylen >> 1) / sizeof(u64);
242 	if (ndigits != ctx->curve->g.ndigits)
243 		return -EINVAL;
244 
245 	ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
246 	ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
247 	ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
248 
249 	ctx->pub_key_set = ret == 0;
250 
251 	return ret;
252 }
253 
ecdsa_exit_tfm(struct crypto_akcipher * tfm)254 static void ecdsa_exit_tfm(struct crypto_akcipher *tfm)
255 {
256 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
257 
258 	ecdsa_ecc_ctx_deinit(ctx);
259 }
260 
ecdsa_max_size(struct crypto_akcipher * tfm)261 static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
262 {
263 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
264 
265 	return ctx->pub_key.ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
266 }
267 
ecdsa_nist_p384_init_tfm(struct crypto_akcipher * tfm)268 static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
269 {
270 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
271 
272 	return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P384);
273 }
274 
275 static struct akcipher_alg ecdsa_nist_p384 = {
276 	.verify = ecdsa_verify,
277 	.set_pub_key = ecdsa_set_pub_key,
278 	.max_size = ecdsa_max_size,
279 	.init = ecdsa_nist_p384_init_tfm,
280 	.exit = ecdsa_exit_tfm,
281 	.base = {
282 		.cra_name = "ecdsa-nist-p384",
283 		.cra_driver_name = "ecdsa-nist-p384-generic",
284 		.cra_priority = 100,
285 		.cra_module = THIS_MODULE,
286 		.cra_ctxsize = sizeof(struct ecc_ctx),
287 	},
288 };
289 
ecdsa_nist_p256_init_tfm(struct crypto_akcipher * tfm)290 static int ecdsa_nist_p256_init_tfm(struct crypto_akcipher *tfm)
291 {
292 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
293 
294 	return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P256);
295 }
296 
297 static struct akcipher_alg ecdsa_nist_p256 = {
298 	.verify = ecdsa_verify,
299 	.set_pub_key = ecdsa_set_pub_key,
300 	.max_size = ecdsa_max_size,
301 	.init = ecdsa_nist_p256_init_tfm,
302 	.exit = ecdsa_exit_tfm,
303 	.base = {
304 		.cra_name = "ecdsa-nist-p256",
305 		.cra_driver_name = "ecdsa-nist-p256-generic",
306 		.cra_priority = 100,
307 		.cra_module = THIS_MODULE,
308 		.cra_ctxsize = sizeof(struct ecc_ctx),
309 	},
310 };
311 
ecdsa_nist_p192_init_tfm(struct crypto_akcipher * tfm)312 static int ecdsa_nist_p192_init_tfm(struct crypto_akcipher *tfm)
313 {
314 	struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
315 
316 	return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P192);
317 }
318 
319 static struct akcipher_alg ecdsa_nist_p192 = {
320 	.verify = ecdsa_verify,
321 	.set_pub_key = ecdsa_set_pub_key,
322 	.max_size = ecdsa_max_size,
323 	.init = ecdsa_nist_p192_init_tfm,
324 	.exit = ecdsa_exit_tfm,
325 	.base = {
326 		.cra_name = "ecdsa-nist-p192",
327 		.cra_driver_name = "ecdsa-nist-p192-generic",
328 		.cra_priority = 100,
329 		.cra_module = THIS_MODULE,
330 		.cra_ctxsize = sizeof(struct ecc_ctx),
331 	},
332 };
333 static bool ecdsa_nist_p192_registered;
334 
ecdsa_init(void)335 static int ecdsa_init(void)
336 {
337 	int ret;
338 
339 	/* NIST p192 may not be available in FIPS mode */
340 	ret = crypto_register_akcipher(&ecdsa_nist_p192);
341 	ecdsa_nist_p192_registered = ret == 0;
342 
343 	ret = crypto_register_akcipher(&ecdsa_nist_p256);
344 	if (ret)
345 		goto nist_p256_error;
346 
347 	ret = crypto_register_akcipher(&ecdsa_nist_p384);
348 	if (ret)
349 		goto nist_p384_error;
350 
351 	return 0;
352 
353 nist_p384_error:
354 	crypto_unregister_akcipher(&ecdsa_nist_p256);
355 
356 nist_p256_error:
357 	if (ecdsa_nist_p192_registered)
358 		crypto_unregister_akcipher(&ecdsa_nist_p192);
359 	return ret;
360 }
361 
ecdsa_exit(void)362 static void ecdsa_exit(void)
363 {
364 	if (ecdsa_nist_p192_registered)
365 		crypto_unregister_akcipher(&ecdsa_nist_p192);
366 	crypto_unregister_akcipher(&ecdsa_nist_p256);
367 	crypto_unregister_akcipher(&ecdsa_nist_p384);
368 }
369 
370 subsys_initcall(ecdsa_init);
371 module_exit(ecdsa_exit);
372 
373 MODULE_LICENSE("GPL");
374 MODULE_AUTHOR("Stefan Berger <stefanb@linux.ibm.com>");
375 MODULE_DESCRIPTION("ECDSA generic algorithm");
376 MODULE_ALIAS_CRYPTO("ecdsa-generic");
377