GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/crypto/../../libssl/src/crypto/ecdsa/ecs_ossl.c Lines: 113 199 56.8 %
Date: 2016-12-06 Branches: 69 138 50.0 %

Line Branch Exec Source
1
/* $OpenBSD: ecs_ossl.c,v 1.6 2015/02/08 13:35:07 jsing 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 "ecs_locl.h"
62
#include <openssl/err.h>
63
#include <openssl/obj_mac.h>
64
#include <openssl/bn.h>
65
66
static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen,
67
    const BIGNUM *, const BIGNUM *, EC_KEY *eckey);
68
static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
69
    BIGNUM **rp);
70
static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
71
    const ECDSA_SIG *sig, EC_KEY *eckey);
72
73
static ECDSA_METHOD openssl_ecdsa_meth = {
74
	.name = "OpenSSL ECDSA method",
75
	.ecdsa_do_sign = ecdsa_do_sign,
76
	.ecdsa_sign_setup = ecdsa_sign_setup,
77
	.ecdsa_do_verify = ecdsa_do_verify
78
};
79
80
const ECDSA_METHOD *
81
ECDSA_OpenSSL(void)
82
2
{
83
2
	return &openssl_ecdsa_meth;
84
}
85
86
static int
87
ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
88
76
{
89
76
	BN_CTX   *ctx = NULL;
90
76
	BIGNUM	 *k = NULL, *r = NULL, *order = NULL, *X = NULL;
91
76
	EC_POINT *tmp_point = NULL;
92
	const EC_GROUP *group;
93
76
	int 	 ret = 0;
94
95

76
	if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
96
		ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
97
		return 0;
98
	}
99
100
76
	if (ctx_in == NULL) {
101
		if ((ctx = BN_CTX_new()) == NULL) {
102
			ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
103
			    ERR_R_MALLOC_FAILURE);
104
			return 0;
105
		}
106
	} else
107
76
		ctx = ctx_in;
108
109
76
	k = BN_new();	/* this value is later returned in *kinvp */
110
76
	r = BN_new();	/* this value is later returned in *rp    */
111
76
	order = BN_new();
112
76
	X = BN_new();
113

76
	if (!k || !r || !order || !X) {
114
		ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
115
		goto err;
116
	}
117
76
	if ((tmp_point = EC_POINT_new(group)) == NULL) {
118
		ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
119
		goto err;
120
	}
121
76
	if (!EC_GROUP_get_order(group, order, ctx)) {
122
		ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
123
		goto err;
124
	}
125
126
	do {
127
		/* get random k */
128
		do
129
76
			if (!BN_rand_range(k, order)) {
130
				ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
131
				    ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
132
				goto err;
133
			}
134
76
		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
76
		if (!BN_add(k, k, order))
140
			goto err;
141
76
		if (BN_num_bits(k) <= BN_num_bits(order))
142
39
			if (!BN_add(k, k, order))
143
				goto err;
144
145
		/* compute r the x-coordinate of generator * k */
146
76
		if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
147
			ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
148
			goto err;
149
		}
150
76
		if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
151
		    NID_X9_62_prime_field) {
152
42
			if (!EC_POINT_get_affine_coordinates_GFp(group,
153
			    tmp_point, X, NULL, ctx)) {
154
				ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
155
				    ERR_R_EC_LIB);
156
				goto err;
157
			}
158
		}
159
#ifndef OPENSSL_NO_EC2M
160
		else /* NID_X9_62_characteristic_two_field */
161
		{
162
34
			if (!EC_POINT_get_affine_coordinates_GF2m(group,
163
			    tmp_point, X, NULL, ctx)) {
164
				ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
165
				    ERR_R_EC_LIB);
166
				goto err;
167
			}
168
		}
169
#endif
170
76
		if (!BN_nnmod(r, X, order, ctx)) {
171
			ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
172
			goto err;
173
		}
174
76
	} while (BN_is_zero(r));
175
176
	/* compute the inverse of k */
177
76
	if (!BN_mod_inverse(k, k, order, ctx)) {
178
		ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
179
		goto err;
180
	}
181
	/* clear old values if necessary */
182
76
	BN_clear_free(*rp);
183
76
	BN_clear_free(*kinvp);
184
	/* save the pre-computed values  */
185
76
	*rp = r;
186
76
	*kinvp = k;
187
76
	ret = 1;
188
189
76
err:
190
76
	if (!ret) {
191
		BN_clear_free(k);
192
		BN_clear_free(r);
193
	}
194
76
	if (ctx_in == NULL)
195
		BN_CTX_free(ctx);
196
76
	BN_free(order);
197
76
	EC_POINT_free(tmp_point);
198
76
	BN_clear_free(X);
199
76
	return (ret);
200
}
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
76
{
207
76
	int     ok = 0, i;
208
76
	BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL, *order = NULL;
209
	const BIGNUM *ckinv;
210
76
	BN_CTX     *ctx = NULL;
211
	const EC_GROUP   *group;
212
	ECDSA_SIG  *ret;
213
	ECDSA_DATA *ecdsa;
214
	const BIGNUM *priv_key;
215
216
76
	ecdsa = ecdsa_check(eckey);
217
76
	group = EC_KEY_get0_group(eckey);
218
76
	priv_key = EC_KEY_get0_private_key(eckey);
219
220

76
	if (group == NULL || priv_key == NULL || ecdsa == NULL) {
221
		ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER);
222
		return NULL;
223
	}
224
225
76
	ret = ECDSA_SIG_new();
226
76
	if (!ret) {
227
		ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
228
		return NULL;
229
	}
230
76
	s = ret->s;
231
232


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

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


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



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

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