GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/ecdsa/ecs_ossl.c Lines: 106 190 55.8 %
Date: 2017-11-13 Branches: 66 132 50.0 %

Line Branch Exec Source
1
/* $OpenBSD: ecs_ossl.c,v 1.9 2017/01/29 17:49:23 beck Exp $ */
2
/*
3
 * Written by Nils Larsch for the OpenSSL project
4
 */
5
/* ====================================================================
6
 * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
7
 *
8
 * Redistribution and use in source and binary forms, with or without
9
 * modification, are permitted provided that the following conditions
10
 * are met:
11
 *
12
 * 1. Redistributions of source code must retain the above copyright
13
 *    notice, this list of conditions and the following disclaimer.
14
 *
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in
17
 *    the documentation and/or other materials provided with the
18
 *    distribution.
19
 *
20
 * 3. All advertising materials mentioning features or use of this
21
 *    software must display the following acknowledgment:
22
 *    "This product includes software developed by the OpenSSL Project
23
 *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
24
 *
25
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26
 *    endorse or promote products derived from this software without
27
 *    prior written permission. For written permission, please contact
28
 *    openssl-core@OpenSSL.org.
29
 *
30
 * 5. Products derived from this software may not be called "OpenSSL"
31
 *    nor may "OpenSSL" appear in their names without prior written
32
 *    permission of the OpenSSL Project.
33
 *
34
 * 6. Redistributions of any form whatsoever must retain the following
35
 *    acknowledgment:
36
 *    "This product includes software developed by the OpenSSL Project
37
 *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
38
 *
39
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
43
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50
 * OF THE POSSIBILITY OF SUCH DAMAGE.
51
 * ====================================================================
52
 *
53
 * This product includes cryptographic software written by Eric Young
54
 * (eay@cryptsoft.com).  This product includes software written by Tim
55
 * Hudson (tjh@cryptsoft.com).
56
 *
57
 */
58
59
#include <openssl/opensslconf.h>
60
61
#include <openssl/err.h>
62
#include <openssl/obj_mac.h>
63
#include <openssl/bn.h>
64
65
#include "bn_lcl.h"
66
#include "ecs_locl.h"
67
68
static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen,
69
    const BIGNUM *, const BIGNUM *, EC_KEY *eckey);
70
static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
71
    BIGNUM **rp);
72
static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
73
    const ECDSA_SIG *sig, EC_KEY *eckey);
74
75
static ECDSA_METHOD openssl_ecdsa_meth = {
76
	.name = "OpenSSL ECDSA method",
77
	.ecdsa_do_sign = ecdsa_do_sign,
78
	.ecdsa_sign_setup = ecdsa_sign_setup,
79
	.ecdsa_do_verify = ecdsa_do_verify
80
};
81
82
const ECDSA_METHOD *
83
ECDSA_OpenSSL(void)
84
{
85
6
	return &openssl_ecdsa_meth;
86
}
87
88
static int
89
ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
90
{
91
	BN_CTX   *ctx = NULL;
92
	BIGNUM	 *k = NULL, *r = NULL, *order = NULL, *X = NULL;
93
	EC_POINT *tmp_point = NULL;
94
	const EC_GROUP *group;
95
	int 	 ret = 0;
96
97

684
	if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
98
		ECDSAerror(ERR_R_PASSED_NULL_PARAMETER);
99
		return 0;
100
	}
101
102
228
	if (ctx_in == NULL) {
103
		if ((ctx = BN_CTX_new()) == NULL) {
104
			ECDSAerror(ERR_R_MALLOC_FAILURE);
105
			return 0;
106
		}
107
	} else
108
		ctx = ctx_in;
109
110
228
	k = BN_new();	/* this value is later returned in *kinvp */
111
228
	r = BN_new();	/* this value is later returned in *rp    */
112
228
	order = BN_new();
113
228
	X = BN_new();
114
228
	if (!k || !r || !order || !X) {
115
		ECDSAerror(ERR_R_MALLOC_FAILURE);
116
		goto err;
117
	}
118
228
	if ((tmp_point = EC_POINT_new(group)) == NULL) {
119
		ECDSAerror(ERR_R_EC_LIB);
120
		goto err;
121
	}
122
228
	if (!EC_GROUP_get_order(group, order, ctx)) {
123
		ECDSAerror(ERR_R_EC_LIB);
124
		goto err;
125
	}
126
127
228
	do {
128
		/* get random k */
129
228
		do
130

456
			if (!BN_rand_range(k, order)) {
131
				ECDSAerror(ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
132
				goto err;
133
			}
134
228
		while (BN_is_zero(k));
135
136
		/* We do not want timing information to leak the length of k,
137
		 * so we compute G*k using an equivalent scalar of fixed
138
		 * bit-length. */
139
228
		if (!BN_add(k, k, order))
140
			goto err;
141
228
		if (BN_num_bits(k) <= BN_num_bits(order))
142
122
			if (!BN_add(k, k, order))
143
				goto err;
144
145
228
		BN_set_flags(k, BN_FLG_CONSTTIME);
146
147
		/* compute r the x-coordinate of generator * k */
148
228
		if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
149
			ECDSAerror(ERR_R_EC_LIB);
150
			goto err;
151
		}
152
228
		if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
153
		    NID_X9_62_prime_field) {
154
126
			if (!EC_POINT_get_affine_coordinates_GFp(group,
155
			    tmp_point, X, NULL, ctx)) {
156
				ECDSAerror(ERR_R_EC_LIB);
157
				goto err;
158
			}
159
		}
160
#ifndef OPENSSL_NO_EC2M
161
		else /* NID_X9_62_characteristic_two_field */
162
		{
163
102
			if (!EC_POINT_get_affine_coordinates_GF2m(group,
164
			    tmp_point, X, NULL, ctx)) {
165
				ECDSAerror(ERR_R_EC_LIB);
166
				goto err;
167
			}
168
		}
169
#endif
170
228
		if (!BN_nnmod(r, X, order, ctx)) {
171
			ECDSAerror(ERR_R_BN_LIB);
172
			goto err;
173
		}
174
228
	} while (BN_is_zero(r));
175
176
	/* compute the inverse of k */
177
228
	if (!BN_mod_inverse_ct(k, k, order, ctx)) {
178
		ECDSAerror(ERR_R_BN_LIB);
179
		goto err;
180
	}
181
	/* clear old values if necessary */
182
228
	BN_clear_free(*rp);
183
228
	BN_clear_free(*kinvp);
184
	/* save the pre-computed values  */
185
228
	*rp = r;
186
228
	*kinvp = k;
187
228
	ret = 1;
188
189
err:
190
228
	if (!ret) {
191
		BN_clear_free(k);
192
		BN_clear_free(r);
193
	}
194
228
	if (ctx_in == NULL)
195
		BN_CTX_free(ctx);
196
228
	BN_free(order);
197
228
	EC_POINT_free(tmp_point);
198
228
	BN_clear_free(X);
199
228
	return (ret);
200
228
}
201
202
203
static ECDSA_SIG *
204
ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
205
    const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey)
206
{
207
	int     ok = 0, i;
208
456
	BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL, *order = NULL;
209
	const BIGNUM *ckinv;
210
	BN_CTX     *ctx = NULL;
211
	const EC_GROUP   *group;
212
	ECDSA_SIG  *ret;
213
	ECDSA_DATA *ecdsa;
214
	const BIGNUM *priv_key;
215
216
228
	ecdsa = ecdsa_check(eckey);
217
228
	group = EC_KEY_get0_group(eckey);
218
228
	priv_key = EC_KEY_get0_private_key(eckey);
219
220
228
	if (group == NULL || priv_key == NULL || ecdsa == NULL) {
221
		ECDSAerror(ERR_R_PASSED_NULL_PARAMETER);
222
		return NULL;
223
	}
224
225
228
	ret = ECDSA_SIG_new();
226
228
	if (!ret) {
227
		ECDSAerror(ERR_R_MALLOC_FAILURE);
228
		return NULL;
229
	}
230
228
	s = ret->s;
231
232

684
	if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
233
456
	    (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) {
234
		ECDSAerror(ERR_R_MALLOC_FAILURE);
235
		goto err;
236
	}
237
238
228
	if (!EC_GROUP_get_order(group, order, ctx)) {
239
		ECDSAerror(ERR_R_EC_LIB);
240
		goto err;
241
	}
242
228
	i = BN_num_bits(order);
243
	/* Need to truncate digest if it is too long: first truncate whole
244
	 * bytes.
245
	 */
246
228
	if (8 * dgst_len > i)
247
		dgst_len = (i + 7)/8;
248
228
	if (!BN_bin2bn(dgst, dgst_len, m)) {
249
		ECDSAerror(ERR_R_BN_LIB);
250
		goto err;
251
	}
252
	/* If still too long truncate remaining bits with a shift */
253

228
	if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
254
		ECDSAerror(ERR_R_BN_LIB);
255
		goto err;
256
	}
257
228
	do {
258
228
		if (in_kinv == NULL || in_r == NULL) {
259
228
			if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) {
260
				ECDSAerror(ERR_R_ECDSA_LIB);
261
				goto err;
262
			}
263
228
			ckinv = kinv;
264
228
		} else {
265
			ckinv = in_kinv;
266
			if (BN_copy(ret->r, in_r) == NULL) {
267
				ECDSAerror(ERR_R_MALLOC_FAILURE);
268
				goto err;
269
			}
270
		}
271
272
228
		if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) {
273
			ECDSAerror(ERR_R_BN_LIB);
274
			goto err;
275
		}
276
228
		if (!BN_mod_add_quick(s, tmp, m, order)) {
277
			ECDSAerror(ERR_R_BN_LIB);
278
			goto err;
279
		}
280
228
		if (!BN_mod_mul(s, s, ckinv, order, ctx)) {
281
			ECDSAerror(ERR_R_BN_LIB);
282
			goto err;
283
		}
284
228
		if (BN_is_zero(s)) {
285
			/* if kinv and r have been supplied by the caller
286
			 * don't to generate new kinv and r values */
287
			if (in_kinv != NULL && in_r != NULL) {
288
				ECDSAerror(ECDSA_R_NEED_NEW_SETUP_VALUES);
289
				goto err;
290
			}
291
		} else
292
			/* s != 0 => we have a valid signature */
293
			break;
294
	} while (1);
295
296
228
	ok = 1;
297
298
err:
299
228
	if (!ok) {
300
		ECDSA_SIG_free(ret);
301
		ret = NULL;
302
	}
303
228
	BN_CTX_free(ctx);
304
228
	BN_clear_free(m);
305
228
	BN_clear_free(tmp);
306
228
	BN_free(order);
307
228
	BN_clear_free(kinv);
308
228
	return ret;
309
228
}
310
311
static int
312
ecdsa_do_verify(const unsigned char *dgst, int dgst_len, const ECDSA_SIG *sig,
313
    EC_KEY *eckey)
314
{
315
	int ret = -1, i;
316
	BN_CTX   *ctx;
317
	BIGNUM   *order, *u1, *u2, *m, *X;
318
	EC_POINT *point = NULL;
319
	const EC_GROUP *group;
320
	const EC_POINT *pub_key;
321
322
	/* check input values */
323

3420
	if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
324
1140
	    (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) {
325
		ECDSAerror(ECDSA_R_MISSING_PARAMETERS);
326
		return -1;
327
	}
328
329
1140
	ctx = BN_CTX_new();
330
1140
	if (!ctx) {
331
		ECDSAerror(ERR_R_MALLOC_FAILURE);
332
		return -1;
333
	}
334
1140
	BN_CTX_start(ctx);
335
1140
	order = BN_CTX_get(ctx);
336
1140
	u1 = BN_CTX_get(ctx);
337
1140
	u2 = BN_CTX_get(ctx);
338
1140
	m = BN_CTX_get(ctx);
339
1140
	X = BN_CTX_get(ctx);
340
1140
	if (!X) {
341
		ECDSAerror(ERR_R_BN_LIB);
342
		goto err;
343
	}
344
345
1140
	if (!EC_GROUP_get_order(group, order, ctx)) {
346
		ECDSAerror(ERR_R_EC_LIB);
347
		goto err;
348
	}
349
350

3418
	if (BN_is_zero(sig->r)          || BN_is_negative(sig->r) ||
351

2278
	    BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s)  ||
352
2276
	    BN_is_negative(sig->s)      || BN_ucmp(sig->s, order) >= 0) {
353
4
		ECDSAerror(ECDSA_R_BAD_SIGNATURE);
354
		ret = 0;	/* signature is invalid */
355
4
		goto err;
356
	}
357
	/* calculate tmp1 = inv(S) mod order */
358
1136
	if (!BN_mod_inverse_ct(u2, sig->s, order, ctx)) {
359
		ECDSAerror(ERR_R_BN_LIB);
360
		goto err;
361
	}
362
	/* digest -> m */
363
1136
	i = BN_num_bits(order);
364
	/* Need to truncate digest if it is too long: first truncate whole
365
	 * bytes.
366
	 */
367
1136
	if (8 * dgst_len > i)
368
		dgst_len = (i + 7)/8;
369
1136
	if (!BN_bin2bn(dgst, dgst_len, m)) {
370
		ECDSAerror(ERR_R_BN_LIB);
371
		goto err;
372
	}
373
	/* If still too long truncate remaining bits with a shift */
374

1136
	if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
375
		ECDSAerror(ERR_R_BN_LIB);
376
		goto err;
377
	}
378
	/* u1 = m * tmp mod order */
379
1136
	if (!BN_mod_mul(u1, m, u2, order, ctx)) {
380
		ECDSAerror(ERR_R_BN_LIB);
381
		goto err;
382
	}
383
	/* u2 = r * w mod q */
384
1136
	if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) {
385
		ECDSAerror(ERR_R_BN_LIB);
386
		goto err;
387
	}
388
389
1136
	if ((point = EC_POINT_new(group)) == NULL) {
390
		ECDSAerror(ERR_R_MALLOC_FAILURE);
391
		goto err;
392
	}
393
1136
	if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) {
394
		ECDSAerror(ERR_R_EC_LIB);
395
		goto err;
396
	}
397
1136
	if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
398
	    NID_X9_62_prime_field) {
399
630
		if (!EC_POINT_get_affine_coordinates_GFp(group,
400
		    point, X, NULL, ctx)) {
401
			ECDSAerror(ERR_R_EC_LIB);
402
			goto err;
403
		}
404
	}
405
#ifndef OPENSSL_NO_EC2M
406
	else /* NID_X9_62_characteristic_two_field */
407
	{
408
506
		if (!EC_POINT_get_affine_coordinates_GF2m(group,
409
		    point, X, NULL, ctx)) {
410
			ECDSAerror(ERR_R_EC_LIB);
411
			goto err;
412
		}
413
	}
414
#endif
415
1136
	if (!BN_nnmod(u1, X, order, ctx)) {
416
		ECDSAerror(ERR_R_BN_LIB);
417
		goto err;
418
	}
419
	/*  if the signature is correct u1 is equal to sig->r */
420
1136
	ret = (BN_ucmp(u1, sig->r) == 0);
421
422
err:
423
1140
	BN_CTX_end(ctx);
424
1140
	BN_CTX_free(ctx);
425
1140
	EC_POINT_free(point);
426
1140
	return ret;
427
1140
}