1/*
2 * Copyright (c) 2011-12 Apple Inc. All Rights Reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23
24/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
25 * All rights reserved.
26 *
27 * This package is an SSL implementation written
28 * by Eric Young (eay@cryptsoft.com).
29 * The implementation was written so as to conform with Netscapes SSL.
30 *
31 * This library is free for commercial and non-commercial use as long as
32 * the following conditions are aheared to.  The following conditions
33 * apply to all code found in this distribution, be it the RC4, RSA,
34 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
35 * included with this distribution is covered by the same copyright terms
36 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
37 *
38 * Copyright remains Eric Young's, and as such any Copyright notices in
39 * the code are not to be removed.
40 * If this package is used in a product, Eric Young should be given attribution
41 * as the author of the parts of the library used.
42 * This can be in the form of a textual message at program startup or
43 * in documentation (online or textual) provided with the package.
44 *
45 * Redistribution and use in source and binary forms, with or without
46 * modification, are permitted provided that the following conditions
47 * are met:
48 * 1. Redistributions of source code must retain the copyright
49 *    notice, this list of conditions and the following disclaimer.
50 * 2. Redistributions in binary form must reproduce the above copyright
51 *    notice, this list of conditions and the following disclaimer in the
52 *    documentation and/or other materials provided with the distribution.
53 * 3. All advertising materials mentioning features or use of this software
54 *    must display the following acknowledgement:
55 *    "This product includes cryptographic software written by
56 *     Eric Young (eay@cryptsoft.com)"
57 *    The word 'cryptographic' can be left out if the rouines from the library
58 *    being used are not cryptographic related :-).
59 * 4. If you include any Windows specific code (or a derivative thereof) from
60 *    the apps directory (application code) you must include an acknowledgement:
61 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
62 *
63 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
64 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
65 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
66 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
67 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
68 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
69 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
70 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
71 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
72 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
73 * SUCH DAMAGE.
74 *
75 * The licence and distribution terms for any publically available version or
76 * derivative of this code cannot be changed.  i.e. this code cannot simply be
77 * copied and put under another distribution licence
78 * [including the GNU Public Licence.]
79 */
80
81/* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
82
83#include "ossl-config.h"
84
85#include <stdio.h>
86#include <stdlib.h>
87#include <string.h>
88
89#include "ossl-bn.h"
90#include "ossl-dsa.h"
91#include "ossl-rand.h"
92
93#if !defined(PR_10488503_FIXED)
94
95#define DSA_MAX_MODULUS_BITS    10000
96
97static DSA_SIG *eay_dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
98static int eay_dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
99static int eay_dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
100    DSA *dsa);
101static int eay_dsa_init(DSA *dsa);
102static int eay_dsa_finish(DSA *dsa);
103
104/* These macro wrappers replace attempts to use the dsa_mod_exp() and
105 * bn_mod_exp() handlers in the DSA_METHOD structure. We avoid the problem of
106 * having a the macro work as an expression by bundling an "err_instr". So;
107 *
108 *     if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx,
109 *                 dsa->method_mont_p)) goto err;
110 *
111 * can be replaced by;
112 *
113 *     DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, &k, dsa->p, ctx,
114 *                 dsa->method_mont_p);
115 */
116#define DSA_MOD_EXP(err_instr, dsa, rr, a1, p1, a2, p2, m, ctx, in_mont)	       \
117	do {									       \
118		int _tmp_res53;							       \
119		if ((dsa)->meth->dsa_mod_exp) {					       \
120			_tmp_res53 = (dsa)->meth->dsa_mod_exp((dsa), (rr), (a1), (p1), \
121				(a2), (p2), (m), (ctx), (in_mont)); }		       \
122		else{								       \
123			_tmp_res53 = BN_mod_exp2_mont((rr), (a1), (p1), (a2), (p2),    \
124				(m), (ctx), (in_mont)); }			       \
125		if (!_tmp_res53) { err_instr; }					       \
126	}									       \
127	while (0)
128#define DSA_BN_MOD_EXP(err_instr, dsa, r, a, p, m, ctx, m_ctx)				    \
129	do {										    \
130		int _tmp_res53;								    \
131		if ((dsa)->meth->bn_mod_exp) {						    \
132			_tmp_res53 = (dsa)->meth->bn_mod_exp((dsa), (r), (a), (p),	    \
133				(m), (ctx), (m_ctx)); }					    \
134		else{									    \
135			_tmp_res53 = BN_mod_exp_mont((r), (a), (p), (m), (ctx), (m_ctx)); } \
136		if (!_tmp_res53) { err_instr; }						    \
137	}										    \
138	while (0)
139
140static DSA_SIG *
141eay_dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
142{
143	BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
144	BIGNUM m;
145	BIGNUM xr;
146	BN_CTX *ctx = NULL;
147	int i /* , reason = ERR_R_BN_LIB */;
148	DSA_SIG *ret = NULL;
149
150	BN_init(&m);
151	BN_init(&xr);
152
153	if (!dsa->p || !dsa->q || !dsa->g) {
154		/* reason = DSA_R_MISSING_PARAMETERS; */
155		goto err;
156	}
157
158	s = BN_new();
159	if (s == NULL) {
160		goto err;
161	}
162
163	i = BN_num_bytes(dsa->q); /* should be 20 */
164	if ((dlen > i) || (dlen > 50)) {
165		/* reason=DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE; */
166		goto err;
167	}
168
169	ctx = BN_CTX_new();
170	if (ctx == NULL) {
171		goto err;
172	}
173
174	if ((dsa->kinv == NULL) || (dsa->r == NULL)) {
175		if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) {
176			goto err;
177		}
178	} else {
179		kinv = dsa->kinv;
180		dsa->kinv = NULL;
181		r = dsa->r;
182		dsa->r = NULL;
183	}
184
185	if (BN_bin2bn(dgst, dlen, &m) == NULL) {
186		goto err;
187	}
188
189	/* Compute  s = inv(k) (m + xr) mod q */
190	if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) {
191		goto err;                                             /* s = xr */
192	}
193	if (!BN_add(s, &xr, &m)) {
194		goto err;                               /* s = m + xr */
195	}
196	if (BN_cmp(s, dsa->q) > 0) {
197		if (!BN_sub(s, s, dsa->q)) {
198			goto err;
199		}
200	}
201	if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) {
202		goto err;
203	}
204
205	ret = DSA_SIG_new();
206	if (ret == NULL) {
207		goto err;
208	}
209	ret->r = r;
210	ret->s = s;
211
212err:
213	if (!ret) {
214		/* DSAerr(DSA_F_DSA_DO_SIGN,reason); */
215		BN_free(r);
216		BN_free(s);
217	}
218	if (ctx != NULL) {
219		BN_CTX_free(ctx);
220	}
221	BN_clear_free(&m);
222	BN_clear_free(&xr);
223	if (kinv != NULL) { /* dsa->kinv is NULL now if we used it */
224		BN_clear_free(kinv);
225	}
226	return (ret);
227}
228
229
230static int
231eay_dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
232{
233	BN_CTX *ctx;
234	BIGNUM k, kq, *K, *kinv = NULL, *r = NULL;
235	int ret = 0;
236
237	if (!dsa->p || !dsa->q || !dsa->g) {
238		/* DSAerr(DSA_F_DSA_SIGN_SETUP,DSA_R_MISSING_PARAMETERS); */
239		return (0);
240	}
241
242	BN_init(&k);
243	BN_init(&kq);
244
245	if (ctx_in == NULL) {
246		if ((ctx = BN_CTX_new()) == NULL) {
247			goto err;
248		}
249	} else{
250		ctx = ctx_in;
251	}
252
253	if ((r = BN_new()) == NULL) {
254		goto err;
255	}
256
257	/* Get random k */
258	do {
259		if (!BN_rand_range(&k, dsa->q)) {
260			goto err;
261		}
262	} while (BN_is_zero(&k));
263	if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
264		BN_set_flags(&k, BN_FLG_CONSTTIME);
265	}
266
267#if 0
268	if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
269		if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
270		    CRYPTO_LOCK_DSA,
271		    dsa->p, ctx)) {
272			goto err;
273		}
274	}
275#endif
276
277	/* Compute r = (g^k mod p) mod q */
278
279	if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
280		if (!BN_copy(&kq, &k)) {
281			goto err;
282		}
283
284		/* We do not want timing information to leak the length of k,
285		 * so we compute g^k using an equivalent exponent of fixed length.
286		 *
287		 * (This is a kludge that we need because the BN_mod_exp_mont()
288		 * does not let us specify the desired timing behaviour.) */
289
290		if (!BN_add(&kq, &kq, dsa->q)) {
291			goto err;
292		}
293		if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) {
294			if (!BN_add(&kq, &kq, dsa->q)) {
295				goto err;
296			}
297		}
298
299		K = &kq;
300	} else {
301		K = &k;
302	}
303#if 1
304	DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, K, dsa->p, ctx,
305	    dsa->method_mont_p);
306#else
307	if (!BN_mod_exp(r, dsa->g, K, dsa->p, ctx)) {
308		goto err;
309	}
310#endif
311	if (!BN_mod(r, r, dsa->q, ctx)) {
312		goto err;
313	}
314
315	/* Compute  part of 's = inv(k) (m + xr) mod q' */
316	if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL) {
317		goto err;
318	}
319
320	if (*kinvp != NULL) {
321		BN_clear_free(*kinvp);
322	}
323	*kinvp = kinv;
324	kinv = NULL;
325	if (*rp != NULL) {
326		BN_clear_free(*rp);
327	}
328	*rp = r;
329	ret = 1;
330err:
331	if (!ret) {
332		/* DSAerr(DSA_F_DSA_SIGN_SETUP,ERR_R_BN_LIB); */
333		if (kinv != NULL) {
334			BN_clear_free(kinv);
335		}
336		if (r != NULL) {
337			BN_clear_free(r);
338		}
339	}
340	if (ctx_in == NULL) {
341		BN_CTX_free(ctx);
342	}
343	if (kinv != NULL) {
344		BN_clear_free(kinv);
345	}
346	BN_clear_free(&k);
347	BN_clear_free(&kq);
348
349	return (ret);
350}
351
352
353static int
354eay_dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
355{
356	BN_CTX *ctx;
357	BIGNUM u1, u2, t1;
358	BN_MONT_CTX *mont = NULL;
359	int ret = -1;
360
361	if (!dsa->p || !dsa->q || !dsa->g) {
362		/* DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MISSING_PARAMETERS); */
363		return (-1);
364	}
365
366	if (BN_num_bits(dsa->q) != 160) {
367		/* DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_BAD_Q_VALUE); */
368		return (-1);
369	}
370
371	if (BN_num_bits(dsa->p) > DSA_MAX_MODULUS_BITS) {
372		/* DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MODULUS_TOO_LARGE); */
373		return (-1);
374	}
375
376	BN_init(&u1);
377	BN_init(&u2);
378	BN_init(&t1);
379
380	if ((ctx = BN_CTX_new()) == NULL) {
381		goto err;
382	}
383
384	if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
385	    (BN_ucmp(sig->r, dsa->q) >= 0)) {
386		ret = 0;
387		goto err;
388	}
389	if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
390	    (BN_ucmp(sig->s, dsa->q) >= 0)) {
391		ret = 0;
392		goto err;
393	}
394
395	/* Calculate W = inv(S) mod Q
396	 * save W in u2 */
397	if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL) {
398		goto err;
399	}
400
401	/* save M in u1 */
402	if (BN_bin2bn(dgst, dgst_len, &u1) == NULL) {
403		goto err;
404	}
405
406	/* u1 = M * w mod q */
407	if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) {
408		goto err;
409	}
410
411	/* u2 = r * w mod q */
412	if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) {
413		goto err;
414	}
415
416
417#if 0
418	if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
419		mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
420			CRYPTO_LOCK_DSA, dsa->p, ctx);
421		if (!mont) {
422			goto err;
423		}
424	}
425#endif
426
427	/* v = g^u1 * y^u2 mod p mod q */
428#if 1
429	DSA_MOD_EXP(goto err, dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, mont);
430#else
431	/* u1 = g^u1 mod p */
432	if (!BN_mod_exp(&u1, dsa->g, &u1, dsa->p, ctx)) {
433		goto err;
434	}
435	/* u2 = y^u2 mod p */
436	if (!BN_mod_exp(&u2, dsa->pub_key, &u2, dsa->p, ctx)) {
437		goto err;
438	}
439	/* t1 = u1 * u2 mod p */
440	if (!BN_mod_mul(&t1, &u1, &u2, dsa->p, ctx)) {
441		goto err;
442	}
443#endif
444	/* BN_copy(&u1,&t1); */
445	/* let u1 = u1 mod q */
446	if (!BN_mod(&u1, &t1, dsa->q, ctx)) {
447		goto err;
448	}
449
450	/* V is now in u1.  If the signature is correct, it will be
451	 * equal to R. */
452	ret = (BN_ucmp(&u1, sig->r) == 0);
453
454err:
455
456	/* XXX: surely this is wrong - if ret is 0, it just didn't verify;
457	 * there is no error in BN. Test should be ret == -1 (Ben) */
458	/* if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB); */
459	if (ctx != NULL) {
460		BN_CTX_free(ctx);
461	}
462	BN_free(&u1);
463	BN_free(&u2);
464	BN_free(&t1);
465	return (ret);
466}
467
468
469static int dsa_init(DSA *dsa)
470{
471	/* dsa->flags|=DSA_FLAG_CACHE_MONT_P; */
472	return (1);
473}
474
475
476static int dsa_finish(DSA *dsa)
477{
478	if (dsa->method_mont_p) {
479		BN_MONT_CTX_free(dsa->method_mont_p);
480	}
481	return (1);
482}
483
484
485const DSA_METHOD _ossl_dsa_eay_method =
486{
487	.name		= "EAY DSA",
488	.dsa_do_sign	= eay_dsa_do_sign,
489	.dsa_sign_setup = eay_dsa_sign_setup,
490	.dsa_do_verify	= eay_dsa_do_verify,
491	.dsa_mod_exp	= NULL,                 /* dsa_mod_exp, */
492	.bn_mod_exp	= NULL,                 /* dsa_bn_mod_exp, */
493	.init		= dsa_init,
494	.finish		= dsa_finish,
495	.flags		=		   0,
496	.app_data	= NULL,
497	.dsa_paramgen	= NULL,
498	.dsa_keygen	= NULL
499};
500
501#endif /* ! defined(PR_10488503_FIXED) */
502
503const DSA_METHOD *
504DSA_eay_method(void)
505{
506#if !defined(PR_10488503_FIXED)
507	return (&_ossl_dsa_eay_method);
508
509#else
510	return (NULL);
511#endif
512}
513