GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/dsa/dsa_ossl.c Lines: 99 130 76.2 %
Date: 2017-11-13 Branches: 62 128 48.4 %

Line Branch Exec Source
1
/* $OpenBSD: dsa_ossl.c,v 1.30 2017/01/29 17:49:22 beck Exp $ */
2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3
 * All rights reserved.
4
 *
5
 * This package is an SSL implementation written
6
 * by Eric Young (eay@cryptsoft.com).
7
 * The implementation was written so as to conform with Netscapes SSL.
8
 *
9
 * This library is free for commercial and non-commercial use as long as
10
 * the following conditions are aheared to.  The following conditions
11
 * apply to all code found in this distribution, be it the RC4, RSA,
12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13
 * included with this distribution is covered by the same copyright terms
14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15
 *
16
 * Copyright remains Eric Young's, and as such any Copyright notices in
17
 * the code are not to be removed.
18
 * If this package is used in a product, Eric Young should be given attribution
19
 * as the author of the parts of the library used.
20
 * This can be in the form of a textual message at program startup or
21
 * in documentation (online or textual) provided with the package.
22
 *
23
 * Redistribution and use in source and binary forms, with or without
24
 * modification, are permitted provided that the following conditions
25
 * are met:
26
 * 1. Redistributions of source code must retain the copyright
27
 *    notice, this list of conditions and the following disclaimer.
28
 * 2. Redistributions in binary form must reproduce the above copyright
29
 *    notice, this list of conditions and the following disclaimer in the
30
 *    documentation and/or other materials provided with the distribution.
31
 * 3. All advertising materials mentioning features or use of this software
32
 *    must display the following acknowledgement:
33
 *    "This product includes cryptographic software written by
34
 *     Eric Young (eay@cryptsoft.com)"
35
 *    The word 'cryptographic' can be left out if the rouines from the library
36
 *    being used are not cryptographic related :-).
37
 * 4. If you include any Windows specific code (or a derivative thereof) from
38
 *    the apps directory (application code) you must include an acknowledgement:
39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40
 *
41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51
 * SUCH DAMAGE.
52
 *
53
 * The licence and distribution terms for any publically available version or
54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
55
 * copied and put under another distribution licence
56
 * [including the GNU Public Licence.]
57
 */
58
59
/* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
60
61
#include <stdio.h>
62
63
#include <openssl/asn1.h>
64
#include <openssl/bn.h>
65
#include <openssl/dsa.h>
66
#include <openssl/err.h>
67
#include <openssl/sha.h>
68
69
#include "bn_lcl.h"
70
71
static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
72
static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
73
	    BIGNUM **rp);
74
static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
75
	    DSA *dsa);
76
static int dsa_init(DSA *dsa);
77
static int dsa_finish(DSA *dsa);
78
79
static DSA_METHOD openssl_dsa_meth = {
80
	.name = "OpenSSL DSA method",
81
	.dsa_do_sign = dsa_do_sign,
82
	.dsa_sign_setup = dsa_sign_setup,
83
	.dsa_do_verify = dsa_do_verify,
84
	.init = dsa_init,
85
	.finish = dsa_finish
86
};
87
88
const DSA_METHOD *
89
DSA_OpenSSL(void)
90
{
91
60
	return &openssl_dsa_meth;
92
}
93
94
static DSA_SIG *
95
dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
96
{
97
16
	BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
98
8
	BIGNUM m;
99
8
	BIGNUM xr;
100
	BN_CTX *ctx = NULL;
101
	int reason = ERR_R_BN_LIB;
102
	DSA_SIG *ret = NULL;
103
	int noredo = 0;
104
105
8
	BN_init(&m);
106
8
	BN_init(&xr);
107
108

24
	if (!dsa->p || !dsa->q || !dsa->g) {
109
		reason = DSA_R_MISSING_PARAMETERS;
110
		goto err;
111
	}
112
113
8
	s = BN_new();
114
8
	if (s == NULL)
115
		goto err;
116
8
	ctx = BN_CTX_new();
117
16
	if (ctx == NULL)
118
		goto err;
119
redo:
120

8
	if (dsa->kinv == NULL || dsa->r == NULL) {
121
8
		if (!DSA_sign_setup(dsa, ctx, &kinv, &r))
122
			goto err;
123
	} else {
124
		kinv = dsa->kinv;
125
		dsa->kinv = NULL;
126
		r = dsa->r;
127
		dsa->r = NULL;
128
		noredo = 1;
129
	}
130
131
132
	/*
133
	 * If the digest length is greater than the size of q use the
134
	 * BN_num_bits(dsa->q) leftmost bits of the digest, see
135
	 * fips 186-3, 4.2
136
	 */
137
8
	if (dlen > BN_num_bytes(dsa->q))
138
2
		dlen = BN_num_bytes(dsa->q);
139
8
	if (BN_bin2bn(dgst,dlen,&m) == NULL)
140
		goto err;
141
142
	/* Compute  s = inv(k) (m + xr) mod q */
143
8
	if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx))	/* s = xr */
144
		goto err;
145
8
	if (!BN_add(s, &xr, &m))				/* s = m + xr */
146
		goto err;
147
8
	if (BN_cmp(s, dsa->q) > 0)
148
1
		if (!BN_sub(s, s, dsa->q))
149
			goto err;
150
8
	if (!BN_mod_mul(s, s, kinv, dsa->q, ctx))
151
		goto err;
152
153
8
	ret = DSA_SIG_new();
154
8
	if (ret == NULL)
155
		goto err;
156
	/*
157
	 * Redo if r or s is zero as required by FIPS 186-3: this is
158
	 * very unlikely.
159
	 */
160

16
	if (BN_is_zero(r) || BN_is_zero(s)) {
161
		if (noredo) {
162
			reason = DSA_R_NEED_NEW_SETUP_VALUES;
163
			goto err;
164
		}
165
		goto redo;
166
	}
167
8
	ret->r = r;
168
8
	ret->s = s;
169
170
err:
171
8
	if (!ret) {
172
		DSAerror(reason);
173
		BN_free(r);
174
		BN_free(s);
175
	}
176
8
	BN_CTX_free(ctx);
177
8
	BN_clear_free(&m);
178
8
	BN_clear_free(&xr);
179
8
	BN_clear_free(kinv);
180
8
	return ret;
181
8
}
182
183
static int
184
dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
185
{
186
	BN_CTX *ctx;
187
16
	BIGNUM k, *kinv = NULL, *r = NULL;
188
	int ret = 0;
189
190

24
	if (!dsa->p || !dsa->q || !dsa->g) {
191
		DSAerror(DSA_R_MISSING_PARAMETERS);
192
		return 0;
193
	}
194
195
8
	BN_init(&k);
196
197
8
	if (ctx_in == NULL) {
198
		if ((ctx = BN_CTX_new()) == NULL)
199
			goto err;
200
	} else
201
		ctx = ctx_in;
202
203
8
	if ((r = BN_new()) == NULL)
204
		goto err;
205
206
	/* Get random k */
207
8
	do {
208
8
		if (!BN_rand_range(&k, dsa->q))
209
			goto err;
210
8
	} while (BN_is_zero(&k));
211
212
8
	BN_set_flags(&k, BN_FLG_CONSTTIME);
213
214
8
	if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
215
16
		if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
216
8
		    CRYPTO_LOCK_DSA, dsa->p, ctx))
217
			goto err;
218
	}
219
220
	/* Compute r = (g^k mod p) mod q */
221
222
	/*
223
	 * We do not want timing information to leak the length of k,
224
	 * so we compute g^k using an equivalent exponent of fixed
225
	 * length.
226
	 *
227
	 * (This is a kludge that we need because the BN_mod_exp_mont()
228
	 * does not let us specify the desired timing behaviour.)
229
	 */
230
231
8
	if (!BN_add(&k, &k, dsa->q))
232
		goto err;
233
8
	if (BN_num_bits(&k) <= BN_num_bits(dsa->q)) {
234
5
		if (!BN_add(&k, &k, dsa->q))
235
			goto err;
236
	}
237
238
8
	if (dsa->meth->bn_mod_exp != NULL) {
239
		if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, &k, dsa->p, ctx,
240
					dsa->method_mont_p))
241
			goto err;
242
	} else {
243
8
		if (!BN_mod_exp_mont_ct(r, dsa->g, &k, dsa->p, ctx, dsa->method_mont_p))
244
			goto err;
245
	}
246
247
8
	if (!BN_mod_ct(r,r,dsa->q,ctx))
248
		goto err;
249
250
	/* Compute  part of 's = inv(k) (m + xr) mod q' */
251
8
	if ((kinv = BN_mod_inverse_ct(NULL, &k, dsa->q, ctx)) == NULL)
252
		goto err;
253
254
8
	BN_clear_free(*kinvp);
255
8
	*kinvp = kinv;
256
	kinv = NULL;
257
8
	BN_clear_free(*rp);
258
8
	*rp = r;
259
8
	ret = 1;
260
err:
261
8
	if (!ret) {
262
		DSAerror(ERR_R_BN_LIB);
263
		BN_clear_free(r);
264
	}
265
8
	if (ctx_in == NULL)
266
		BN_CTX_free(ctx);
267
8
	BN_clear_free(&k);
268
8
	return ret;
269
8
}
270
271
static int
272
dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
273
{
274
	BN_CTX *ctx;
275
12
	BIGNUM u1, u2, t1;
276
	BN_MONT_CTX *mont = NULL;
277
	int ret = -1, i;
278
279

18
	if (!dsa->p || !dsa->q || !dsa->g) {
280
		DSAerror(DSA_R_MISSING_PARAMETERS);
281
		return -1;
282
	}
283
284
6
	i = BN_num_bits(dsa->q);
285
	/* fips 186-3 allows only different sizes for q */
286
6
	if (i != 160 && i != 224 && i != 256) {
287
		DSAerror(DSA_R_BAD_Q_VALUE);
288
		return -1;
289
	}
290
291
6
	if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
292
		DSAerror(DSA_R_MODULUS_TOO_LARGE);
293
		return -1;
294
	}
295
6
	BN_init(&u1);
296
6
	BN_init(&u2);
297
6
	BN_init(&t1);
298
299
6
	if ((ctx = BN_CTX_new()) == NULL)
300
		goto err;
301
302

18
	if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
303
6
	    BN_ucmp(sig->r, dsa->q) >= 0) {
304
		ret = 0;
305
		goto err;
306
	}
307

18
	if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
308
6
	    BN_ucmp(sig->s, dsa->q) >= 0) {
309
		ret = 0;
310
		goto err;
311
	}
312
313
	/* Calculate W = inv(S) mod Q
314
	 * save W in u2 */
315
6
	if ((BN_mod_inverse_ct(&u2, sig->s, dsa->q, ctx)) == NULL)
316
		goto err;
317
318
	/* save M in u1 */
319
	/*
320
	 * If the digest length is greater than the size of q use the
321
	 * BN_num_bits(dsa->q) leftmost bits of the digest, see
322
	 * fips 186-3, 4.2
323
	 */
324
6
	if (dgst_len > (i >> 3))
325
		dgst_len = (i >> 3);
326
6
	if (BN_bin2bn(dgst, dgst_len, &u1) == NULL)
327
		goto err;
328
329
	/* u1 = M * w mod q */
330
6
	if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx))
331
		goto err;
332
333
	/* u2 = r * w mod q */
334
6
	if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx))
335
		goto err;
336
337
338
6
	if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
339
12
		mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
340
6
		    CRYPTO_LOCK_DSA, dsa->p, ctx);
341
6
		if (!mont)
342
			goto err;
343
	}
344
345
6
	if (dsa->meth->dsa_mod_exp != NULL) {
346
		if (!dsa->meth->dsa_mod_exp(dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2,
347
						dsa->p, ctx, mont))
348
			goto err;
349
	} else {
350
6
		if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx,
351
						mont))
352
			goto err;
353
	}
354
355
	/* BN_copy(&u1,&t1); */
356
	/* let u1 = u1 mod q */
357
6
	if (!BN_mod_ct(&u1, &t1, dsa->q, ctx))
358
		goto err;
359
360
	/* V is now in u1.  If the signature is correct, it will be
361
	 * equal to R. */
362
6
	ret = BN_ucmp(&u1, sig->r) == 0;
363
364
err:
365
6
	if (ret < 0)
366
		DSAerror(ERR_R_BN_LIB);
367
6
	BN_CTX_free(ctx);
368
6
	BN_free(&u1);
369
6
	BN_free(&u2);
370
6
	BN_free(&t1);
371
6
	return ret;
372
6
}
373
374
static int
375
dsa_init(DSA *dsa)
376
{
377
92
	dsa->flags |= DSA_FLAG_CACHE_MONT_P;
378
46
	return 1;
379
}
380
381
static int
382
dsa_finish(DSA *dsa)
383
{
384
92
	BN_MONT_CTX_free(dsa->method_mont_p);
385
46
	return 1;
386
}
387