1 /* $OpenBSD: gostr341001.c,v 1.9 2022/01/07 09:40:03 tb Exp $ */
2 /*
3  * Copyright (c) 2014 Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
4  * Copyright (c) 2005-2006 Cryptocom LTD
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  *
18  * 3. All advertising materials mentioning features or use of this
19  *    software must display the following acknowledgment:
20  *    "This product includes software developed by the OpenSSL Project
21  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
22  *
23  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
24  *    endorse or promote products derived from this software without
25  *    prior written permission. For written permission, please contact
26  *    openssl-core@openssl.org.
27  *
28  * 5. Products derived from this software may not be called "OpenSSL"
29  *    nor may "OpenSSL" appear in their names without prior written
30  *    permission of the OpenSSL Project.
31  *
32  * 6. Redistributions of any form whatsoever must retain the following
33  *    acknowledgment:
34  *    "This product includes software developed by the OpenSSL Project
35  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
36  *
37  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
38  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
40  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
43  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
44  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
45  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
46  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
47  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
48  * OF THE POSSIBILITY OF SUCH DAMAGE.
49  * ====================================================================
50  */
51 
52 #include <string.h>
53 
54 #include <openssl/opensslconf.h>
55 
56 #ifndef OPENSSL_NO_GOST
57 #include <openssl/bn.h>
58 #include <openssl/err.h>
59 #include <openssl/gost.h>
60 
61 #include "bn_lcl.h"
62 #include "ecs_locl.h"
63 #include "gost_locl.h"
64 
65 /* Convert little-endian byte array into bignum */
66 BIGNUM *
67 GOST_le2bn(const unsigned char *buf, size_t len, BIGNUM *bn)
68 {
69 	unsigned char temp[64];
70 	int i;
71 
72 	if (len > 64)
73 		return NULL;
74 
75 	for (i = 0; i < len; i++) {
76 		temp[len - 1 - i] = buf[i];
77 	}
78 
79 	return BN_bin2bn(temp, len, bn);
80 }
81 
82 int
83 GOST_bn2le(BIGNUM *bn, unsigned char *buf, int len)
84 {
85 	unsigned char temp[64];
86 	int i, bytes;
87 
88 	bytes = BN_num_bytes(bn);
89 	if (len > 64 || bytes > len)
90 		return 0;
91 
92 	BN_bn2bin(bn, temp);
93 
94 	for (i = 0; i < bytes; i++) {
95 		buf[bytes - 1 - i] = temp[i];
96 	}
97 
98 	memset(buf + bytes, 0, len - bytes);
99 
100 	return 1;
101 }
102 
103 int
104 gost2001_compute_public(GOST_KEY *ec)
105 {
106 	const EC_GROUP *group = GOST_KEY_get0_group(ec);
107 	EC_POINT *pub_key = NULL;
108 	const BIGNUM *priv_key = NULL;
109 	BN_CTX *ctx = NULL;
110 	int ok = 0;
111 
112 	if (group == NULL) {
113 		GOSTerror(GOST_R_KEY_IS_NOT_INITIALIZED);
114 		return 0;
115 	}
116 	ctx = BN_CTX_new();
117 	if (ctx == NULL) {
118 		GOSTerror(ERR_R_MALLOC_FAILURE);
119 		return 0;
120 	}
121 	BN_CTX_start(ctx);
122 	if ((priv_key = GOST_KEY_get0_private_key(ec)) == NULL)
123 		goto err;
124 
125 	pub_key = EC_POINT_new(group);
126 	if (pub_key == NULL)
127 		goto err;
128 	if (EC_POINT_mul(group, pub_key, priv_key, NULL, NULL, ctx) == 0)
129 		goto err;
130 	if (GOST_KEY_set_public_key(ec, pub_key) == 0)
131 		goto err;
132 	ok = 1;
133 
134 	if (ok == 0) {
135 err:
136 		GOSTerror(ERR_R_EC_LIB);
137 	}
138 	EC_POINT_free(pub_key);
139 	if (ctx != NULL) {
140 		BN_CTX_end(ctx);
141 		BN_CTX_free(ctx);
142 	}
143 	return ok;
144 }
145 
146 ECDSA_SIG *
147 gost2001_do_sign(BIGNUM *md, GOST_KEY *eckey)
148 {
149 	ECDSA_SIG *newsig = NULL;
150 	BIGNUM *order = NULL;
151 	const EC_GROUP *group;
152 	const BIGNUM *priv_key;
153 	BIGNUM *r = NULL, *s = NULL, *X = NULL, *tmp = NULL, *tmp2 = NULL, *k =
154 	    NULL, *e = NULL;
155 	EC_POINT *C = NULL;
156 	BN_CTX *ctx = BN_CTX_new();
157 	int ok = 0;
158 
159 	if (ctx == NULL) {
160 		GOSTerror(ERR_R_MALLOC_FAILURE);
161 		return NULL;
162 	}
163 	BN_CTX_start(ctx);
164 	newsig = ECDSA_SIG_new();
165 	if (newsig == NULL) {
166 		GOSTerror(ERR_R_MALLOC_FAILURE);
167 		goto err;
168 	}
169 	s = newsig->s;
170 	r = newsig->r;
171 	group = GOST_KEY_get0_group(eckey);
172 	if ((order = BN_CTX_get(ctx)) == NULL)
173 		goto err;
174 	if (EC_GROUP_get_order(group, order, ctx) == 0)
175 		goto err;
176 	priv_key = GOST_KEY_get0_private_key(eckey);
177 	if ((e = BN_CTX_get(ctx)) == NULL)
178 		goto err;
179 	if (BN_mod_ct(e, md, order, ctx) == 0)
180 		goto err;
181 	if (BN_is_zero(e))
182 		BN_one(e);
183 	if ((k = BN_CTX_get(ctx)) == NULL)
184 		goto err;
185 	if ((X = BN_CTX_get(ctx)) == NULL)
186 		goto err;
187 	if ((C = EC_POINT_new(group)) == NULL)
188 		goto err;
189 	do {
190 		do {
191 			if (!BN_rand_range(k, order)) {
192 				GOSTerror(GOST_R_RANDOM_NUMBER_GENERATOR_FAILED);
193 				goto err;
194 			}
195 			/*
196 			 * We do not want timing information to leak the length
197 			 * of k, so we compute G*k using an equivalent scalar
198 			 * of fixed bit-length.
199 			 */
200 			if (BN_add(k, k, order) == 0)
201 				goto err;
202 			if (BN_num_bits(k) <= BN_num_bits(order))
203 				if (BN_add(k, k, order) == 0)
204 					goto err;
205 
206 			if (EC_POINT_mul(group, C, k, NULL, NULL, ctx) == 0) {
207 				GOSTerror(ERR_R_EC_LIB);
208 				goto err;
209 			}
210 			if (EC_POINT_get_affine_coordinates(group, C, X,
211 			    NULL, ctx) == 0) {
212 				GOSTerror(ERR_R_EC_LIB);
213 				goto err;
214 			}
215 			if (BN_nnmod(r, X, order, ctx) == 0)
216 				goto err;
217 		} while (BN_is_zero(r));
218 		/* s = (r*priv_key+k*e) mod order */
219 		if (tmp == NULL) {
220 			if ((tmp = BN_CTX_get(ctx)) == NULL)
221 				goto err;
222 		}
223 		if (BN_mod_mul(tmp, priv_key, r, order, ctx) == 0)
224 			goto err;
225 		if (tmp2 == NULL) {
226 			if ((tmp2 = BN_CTX_get(ctx)) == NULL)
227 				goto err;
228 		}
229 		if (BN_mod_mul(tmp2, k, e, order, ctx) == 0)
230 			goto err;
231 		if (BN_mod_add(s, tmp, tmp2, order, ctx) == 0)
232 			goto err;
233 	} while (BN_is_zero(s));
234 	ok = 1;
235 
236 err:
237 	EC_POINT_free(C);
238 	if (ctx != NULL) {
239 		BN_CTX_end(ctx);
240 		BN_CTX_free(ctx);
241 	}
242 	if (ok == 0) {
243 		ECDSA_SIG_free(newsig);
244 		newsig = NULL;
245 	}
246 	return newsig;
247 }
248 
249 int
250 gost2001_do_verify(BIGNUM *md, ECDSA_SIG *sig, GOST_KEY *ec)
251 {
252 	BN_CTX *ctx = BN_CTX_new();
253 	const EC_GROUP *group = GOST_KEY_get0_group(ec);
254 	BIGNUM *order;
255 	BIGNUM *e = NULL, *R = NULL, *v = NULL, *z1 = NULL, *z2 = NULL;
256 	BIGNUM *X = NULL, *tmp = NULL;
257 	EC_POINT *C = NULL;
258 	const EC_POINT *pub_key = NULL;
259 	int ok = 0;
260 
261 	if (ctx == NULL)
262 		goto err;
263 	BN_CTX_start(ctx);
264 	if ((order = BN_CTX_get(ctx)) == NULL)
265 		goto err;
266 	if ((e = BN_CTX_get(ctx)) == NULL)
267 		goto err;
268 	if ((z1 = BN_CTX_get(ctx)) == NULL)
269 		goto err;
270 	if ((z2 = BN_CTX_get(ctx)) == NULL)
271 		goto err;
272 	if ((tmp = BN_CTX_get(ctx)) == NULL)
273 		goto err;
274 	if ((X = BN_CTX_get(ctx)) == NULL)
275 		goto err;
276 	if ((R = BN_CTX_get(ctx)) == NULL)
277 		goto err;
278 	if ((v = BN_CTX_get(ctx)) == NULL)
279 		goto err;
280 
281 	if (EC_GROUP_get_order(group, order, ctx) == 0)
282 		goto err;
283 	pub_key = GOST_KEY_get0_public_key(ec);
284 	if (BN_is_zero(sig->s) || BN_is_zero(sig->r) ||
285 	    BN_cmp(sig->s, order) >= 1 || BN_cmp(sig->r, order) >= 1) {
286 		GOSTerror(GOST_R_SIGNATURE_PARTS_GREATER_THAN_Q);
287 		goto err;
288 	}
289 
290 	if (BN_mod_ct(e, md, order, ctx) == 0)
291 		goto err;
292 	if (BN_is_zero(e))
293 		BN_one(e);
294 	if ((v = BN_mod_inverse_ct(v, e, order, ctx)) == NULL)
295 		goto err;
296 	if (BN_mod_mul(z1, sig->s, v, order, ctx) == 0)
297 		goto err;
298 	if (BN_sub(tmp, order, sig->r) == 0)
299 		goto err;
300 	if (BN_mod_mul(z2, tmp, v, order, ctx) == 0)
301 		goto err;
302 	if ((C = EC_POINT_new(group)) == NULL)
303 		goto err;
304 	if (EC_POINT_mul(group, C, z1, pub_key, z2, ctx) == 0) {
305 		GOSTerror(ERR_R_EC_LIB);
306 		goto err;
307 	}
308 	if (EC_POINT_get_affine_coordinates(group, C, X, NULL, ctx) == 0) {
309 		GOSTerror(ERR_R_EC_LIB);
310 		goto err;
311 	}
312 	if (BN_mod_ct(R, X, order, ctx) == 0)
313 		goto err;
314 	if (BN_cmp(R, sig->r) != 0) {
315 		GOSTerror(GOST_R_SIGNATURE_MISMATCH);
316 	} else {
317 		ok = 1;
318 	}
319 err:
320 	EC_POINT_free(C);
321 	if (ctx != NULL) {
322 		BN_CTX_end(ctx);
323 		BN_CTX_free(ctx);
324 	}
325 	return ok;
326 }
327 
328 /* Implementation of CryptoPro VKO 34.10-2001 algorithm */
329 int
330 VKO_compute_key(BIGNUM *X, BIGNUM *Y, const GOST_KEY *pkey, GOST_KEY *priv_key,
331     const BIGNUM *ukm)
332 {
333 	BIGNUM *p = NULL, *order = NULL;
334 	const BIGNUM *key = GOST_KEY_get0_private_key(priv_key);
335 	const EC_GROUP *group = GOST_KEY_get0_group(priv_key);
336 	const EC_POINT *pub_key = GOST_KEY_get0_public_key(pkey);
337 	EC_POINT *pnt;
338 	BN_CTX *ctx = NULL;
339 	int ok = 0;
340 
341 	pnt = EC_POINT_new(group);
342 	if (pnt == NULL)
343 		goto err;
344 	ctx = BN_CTX_new();
345 	if (ctx == NULL)
346 		goto err;
347 	BN_CTX_start(ctx);
348 	if ((p = BN_CTX_get(ctx)) == NULL)
349 		goto err;
350 	if ((order = BN_CTX_get(ctx)) == NULL)
351 		goto err;
352 	if (EC_GROUP_get_order(group, order, ctx) == 0)
353 		goto err;
354 	if (BN_mod_mul(p, key, ukm, order, ctx) == 0)
355 		goto err;
356 	if (EC_POINT_mul(group, pnt, NULL, pub_key, p, ctx) == 0)
357 		goto err;
358 	if (EC_POINT_get_affine_coordinates(group, pnt, X, Y, ctx) == 0)
359 		goto err;
360 	ok = 1;
361 
362 err:
363 	if (ctx != NULL) {
364 		BN_CTX_end(ctx);
365 		BN_CTX_free(ctx);
366 	}
367 	EC_POINT_free(pnt);
368 	return ok;
369 }
370 
371 int
372 gost2001_keygen(GOST_KEY *ec)
373 {
374 	BIGNUM *order = BN_new(), *d = BN_new();
375 	const EC_GROUP *group = GOST_KEY_get0_group(ec);
376 	int rc = 0;
377 
378 	if (order == NULL || d == NULL)
379 		goto err;
380 	if (EC_GROUP_get_order(group, order, NULL) == 0)
381 		goto err;
382 
383 	do {
384 		if (BN_rand_range(d, order) == 0) {
385 			GOSTerror(GOST_R_RANDOM_NUMBER_GENERATOR_FAILED);
386 			goto err;
387 		}
388 	} while (BN_is_zero(d));
389 
390 	if (GOST_KEY_set_private_key(ec, d) == 0)
391 		goto err;
392 	rc = gost2001_compute_public(ec);
393 
394 err:
395 	BN_free(d);
396 	BN_free(order);
397 	return rc;
398 }
399 #endif
400