Branch data Line data Source code
1 : : /* crypto/dsa/dsa_ossl.c */
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 : : #define OPENSSL_FIPSAPI
62 : :
63 : : #include <stdio.h>
64 : : #include "cryptlib.h"
65 : : #include <openssl/bn.h>
66 : : #include <openssl/sha.h>
67 : : #include <openssl/dsa.h>
68 : : #include <openssl/rand.h>
69 : : #include <openssl/asn1.h>
70 : : #ifdef OPENSSL_FIPS
71 : : #include <openssl/fips.h>
72 : : #endif
73 : :
74 : : static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
75 : : static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
76 : : static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
77 : : BIGNUM **kinvp, BIGNUM **rp,
78 : : const unsigned char *dgst, int dlen);
79 : : static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
80 : : DSA *dsa);
81 : : static int dsa_init(DSA *dsa);
82 : : static int dsa_finish(DSA *dsa);
83 : :
84 : : static DSA_METHOD openssl_dsa_meth = {
85 : : "OpenSSL DSA method",
86 : : dsa_do_sign,
87 : : dsa_sign_setup_no_digest,
88 : : dsa_do_verify,
89 : : NULL, /* dsa_mod_exp, */
90 : : NULL, /* dsa_bn_mod_exp, */
91 : : dsa_init,
92 : : dsa_finish,
93 : : DSA_FLAG_FIPS_METHOD,
94 : : NULL,
95 : : NULL,
96 : : NULL
97 : : };
98 : :
99 : : /* These macro wrappers replace attempts to use the dsa_mod_exp() and
100 : : * bn_mod_exp() handlers in the DSA_METHOD structure. We avoid the problem of
101 : : * having a the macro work as an expression by bundling an "err_instr". So;
102 : : *
103 : : * if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx,
104 : : * dsa->method_mont_p)) goto err;
105 : : *
106 : : * can be replaced by;
107 : : *
108 : : * DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, &k, dsa->p, ctx,
109 : : * dsa->method_mont_p);
110 : : */
111 : :
112 : : #define DSA_MOD_EXP(err_instr,dsa,rr,a1,p1,a2,p2,m,ctx,in_mont) \
113 : : do { \
114 : : int _tmp_res53; \
115 : : if((dsa)->meth->dsa_mod_exp) \
116 : : _tmp_res53 = (dsa)->meth->dsa_mod_exp((dsa), (rr), (a1), (p1), \
117 : : (a2), (p2), (m), (ctx), (in_mont)); \
118 : : else \
119 : : _tmp_res53 = BN_mod_exp2_mont((rr), (a1), (p1), (a2), (p2), \
120 : : (m), (ctx), (in_mont)); \
121 : : if(!_tmp_res53) err_instr; \
122 : : } while(0)
123 : : #define DSA_BN_MOD_EXP(err_instr,dsa,r,a,p,m,ctx,m_ctx) \
124 : : do { \
125 : : int _tmp_res53; \
126 : : if((dsa)->meth->bn_mod_exp) \
127 : : _tmp_res53 = (dsa)->meth->bn_mod_exp((dsa), (r), (a), (p), \
128 : : (m), (ctx), (m_ctx)); \
129 : : else \
130 : : _tmp_res53 = BN_mod_exp_mont((r), (a), (p), (m), (ctx), (m_ctx)); \
131 : : if(!_tmp_res53) err_instr; \
132 : : } while(0)
133 : :
134 : 3642 : const DSA_METHOD *DSA_OpenSSL(void)
135 : : {
136 : 3642 : return &openssl_dsa_meth;
137 : : }
138 : :
139 : 41 : static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
140 : : {
141 : 41 : BIGNUM *kinv=NULL,*r=NULL,*s=NULL;
142 : : BIGNUM m;
143 : : BIGNUM xr;
144 : 41 : BN_CTX *ctx=NULL;
145 : 41 : int reason=ERR_R_BN_LIB;
146 : 41 : DSA_SIG *ret=NULL;
147 : 41 : int noredo = 0;
148 : :
149 : : #ifdef OPENSSL_FIPS
150 : : if(FIPS_selftest_failed())
151 : : {
152 : : FIPSerr(FIPS_F_DSA_DO_SIGN,FIPS_R_FIPS_SELFTEST_FAILED);
153 : : return NULL;
154 : : }
155 : :
156 : : if (FIPS_module_mode() && !(dsa->flags & DSA_FLAG_NON_FIPS_ALLOW)
157 : : && (BN_num_bits(dsa->p) < OPENSSL_DSA_FIPS_MIN_MODULUS_BITS))
158 : : {
159 : : DSAerr(DSA_F_DSA_DO_SIGN, DSA_R_KEY_SIZE_TOO_SMALL);
160 : : return NULL;
161 : : }
162 : : if (!fips_check_dsa_prng(dsa, 0, 0))
163 : : goto err;
164 : : #endif
165 : :
166 : 41 : BN_init(&m);
167 : 41 : BN_init(&xr);
168 : :
169 [ + - ][ + - ]: 41 : if (!dsa->p || !dsa->q || !dsa->g)
[ + - ]
170 : : {
171 : : reason=DSA_R_MISSING_PARAMETERS;
172 : : goto err;
173 : : }
174 : :
175 : 41 : s=BN_new();
176 [ + - ]: 41 : if (s == NULL) goto err;
177 : 41 : ctx=BN_CTX_new();
178 [ + - ]: 41 : if (ctx == NULL) goto err;
179 : : redo:
180 [ - + ][ # # ]: 41 : if ((dsa->kinv == NULL) || (dsa->r == NULL))
181 : : {
182 [ + - ]: 41 : if (!dsa_sign_setup(dsa,ctx,&kinv,&r,dgst,dlen))
183 : : goto err;
184 : : }
185 : : else
186 : : {
187 : 0 : kinv=dsa->kinv;
188 : 0 : dsa->kinv=NULL;
189 : 0 : r=dsa->r;
190 : 0 : dsa->r=NULL;
191 : 0 : noredo = 1;
192 : : }
193 : :
194 : :
195 [ - + ]: 41 : if (dlen > BN_num_bytes(dsa->q))
196 : : /* if the digest length is greater than the size of q use the
197 : : * BN_num_bits(dsa->q) leftmost bits of the digest, see
198 : : * fips 186-3, 4.2 */
199 : 0 : dlen = BN_num_bytes(dsa->q);
200 [ + - ]: 41 : if (BN_bin2bn(dgst,dlen,&m) == NULL)
201 : : goto err;
202 : :
203 : : /* Compute s = inv(k) (m + xr) mod q */
204 [ + - ]: 41 : if (!BN_mod_mul(&xr,dsa->priv_key,r,dsa->q,ctx)) goto err;/* s = xr */
205 [ + - ]: 41 : if (!BN_add(s, &xr, &m)) goto err; /* s = m + xr */
206 [ - + ]: 41 : if (BN_cmp(s,dsa->q) > 0)
207 [ # # ]: 0 : if (!BN_sub(s,s,dsa->q)) goto err;
208 [ + - ]: 41 : if (!BN_mod_mul(s,s,kinv,dsa->q,ctx)) goto err;
209 : :
210 : 41 : ret=DSA_SIG_new();
211 [ + - ]: 41 : if (ret == NULL) goto err;
212 : : /* Redo if r or s is zero as required by FIPS 186-3: this is
213 : : * very unlikely.
214 : : */
215 [ + - ][ - + ]: 41 : if (BN_is_zero(r) || BN_is_zero(s))
216 : : {
217 [ # # ]: 0 : if (noredo)
218 : : {
219 : : reason = DSA_R_NEED_NEW_SETUP_VALUES;
220 : : goto err;
221 : : }
222 : : goto redo;
223 : : }
224 : 41 : ret->r = r;
225 : 41 : ret->s = s;
226 : :
227 : : err:
228 [ - + ]: 41 : if (!ret)
229 : : {
230 : 0 : DSAerr(DSA_F_DSA_DO_SIGN,reason);
231 : 0 : BN_free(r);
232 : 0 : BN_free(s);
233 : : }
234 [ + - ]: 41 : if (ctx != NULL) BN_CTX_free(ctx);
235 : 41 : BN_clear_free(&m);
236 : 41 : BN_clear_free(&xr);
237 [ + - ]: 41 : if (kinv != NULL) /* dsa->kinv is NULL now if we used it */
238 : 41 : BN_clear_free(kinv);
239 : 41 : return(ret);
240 : : }
241 : :
242 : 0 : static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in,
243 : : BIGNUM **kinvp, BIGNUM **rp) {
244 : 0 : return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);
245 : : }
246 : :
247 : 41 : static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
248 : : BIGNUM **kinvp, BIGNUM **rp,
249 : : const unsigned char *dgst, int dlen)
250 : : {
251 : : BN_CTX *ctx;
252 : 41 : BIGNUM k,kq,*K,*kinv=NULL,*r=NULL;
253 : 41 : int ret=0;
254 : :
255 [ + - ][ + - ]: 41 : if (!dsa->p || !dsa->q || !dsa->g)
[ - + ]
256 : : {
257 : 0 : DSAerr(DSA_F_DSA_SIGN_SETUP,DSA_R_MISSING_PARAMETERS);
258 : 0 : return 0;
259 : : }
260 : :
261 : 41 : BN_init(&k);
262 : 41 : BN_init(&kq);
263 : :
264 [ - + ]: 41 : if (ctx_in == NULL)
265 : : {
266 [ # # ]: 0 : if ((ctx=BN_CTX_new()) == NULL) goto err;
267 : : }
268 : : else
269 : : ctx=ctx_in;
270 : :
271 [ + - ]: 41 : if ((r=BN_new()) == NULL) goto err;
272 : :
273 : : /* Get random k */
274 : : do
275 : : {
276 : : #ifndef OPENSSL_NO_SHA512
277 [ + - ]: 41 : if (dgst != NULL)
278 : : {
279 : : /* We calculate k from SHA512(private_key + H(message)
280 : : * + random). This protects the private key from a weak
281 : : * PRNG. */
282 [ + - ]: 41 : if (!BN_generate_dsa_nonce(&k, dsa->q, dsa->priv_key, dgst,
283 : : dlen, ctx))
284 : : goto err;
285 : : }
286 : : else
287 : : #endif
288 [ # # ]: 0 : if (!BN_rand_range(&k, dsa->q)) goto err;
289 [ - + ]: 41 : } while (BN_is_zero(&k));
290 : :
291 [ + + ]: 41 : if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0)
292 : : {
293 : 39 : BN_set_flags(&k, BN_FLG_CONSTTIME);
294 : : }
295 : :
296 [ + - ]: 41 : if (dsa->flags & DSA_FLAG_CACHE_MONT_P)
297 : : {
298 [ + - ]: 41 : if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
299 : : CRYPTO_LOCK_DSA,
300 : 41 : dsa->p, ctx))
301 : : goto err;
302 : : }
303 : :
304 : : /* Compute r = (g^k mod p) mod q */
305 : :
306 [ + + ]: 41 : if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0)
307 : : {
308 [ + - ]: 39 : if (!BN_copy(&kq, &k)) goto err;
309 : :
310 : : /* We do not want timing information to leak the length of k,
311 : : * so we compute g^k using an equivalent exponent of fixed length.
312 : : *
313 : : * (This is a kludge that we need because the BN_mod_exp_mont()
314 : : * does not let us specify the desired timing behaviour.) */
315 : :
316 [ + - ]: 39 : if (!BN_add(&kq, &kq, dsa->q)) goto err;
317 [ + + ]: 39 : if (BN_num_bits(&kq) <= BN_num_bits(dsa->q))
318 : : {
319 [ + - ]: 23 : if (!BN_add(&kq, &kq, dsa->q)) goto err;
320 : : }
321 : :
322 : : K = &kq;
323 : : }
324 : : else
325 : : {
326 : : K = &k;
327 : : }
328 [ - + ][ + - ]: 41 : DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, K, dsa->p, ctx,
329 : : dsa->method_mont_p);
330 [ + - ]: 41 : if (!BN_mod(r,r,dsa->q,ctx)) goto err;
331 : :
332 : : /* Compute part of 's = inv(k) (m + xr) mod q' */
333 [ + - ]: 41 : if ((kinv=BN_mod_inverse(NULL,&k,dsa->q,ctx)) == NULL) goto err;
334 : :
335 [ - + ]: 41 : if (*kinvp != NULL) BN_clear_free(*kinvp);
336 : 41 : *kinvp=kinv;
337 : 41 : kinv=NULL;
338 [ - + ]: 41 : if (*rp != NULL) BN_clear_free(*rp);
339 : 41 : *rp=r;
340 : 41 : ret=1;
341 : : err:
342 [ - + ]: 41 : if (!ret)
343 : : {
344 : 0 : DSAerr(DSA_F_DSA_SIGN_SETUP,ERR_R_BN_LIB);
345 [ # # ]: 0 : if (r != NULL)
346 : 0 : BN_clear_free(r);
347 : : }
348 [ - + ]: 41 : if (ctx_in == NULL) BN_CTX_free(ctx);
349 : 41 : BN_clear_free(&k);
350 : 41 : BN_clear_free(&kq);
351 : 41 : return(ret);
352 : : }
353 : :
354 : 45 : static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
355 : : DSA *dsa)
356 : : {
357 : : BN_CTX *ctx;
358 : : BIGNUM u1,u2,t1;
359 : 45 : BN_MONT_CTX *mont=NULL;
360 : 45 : int ret = -1, i;
361 [ + - ][ + - ]: 45 : if (!dsa->p || !dsa->q || !dsa->g)
[ - + ]
362 : : {
363 : 0 : DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MISSING_PARAMETERS);
364 : 0 : return -1;
365 : : }
366 : :
367 : 45 : i = BN_num_bits(dsa->q);
368 : : /* fips 186-3 allows only different sizes for q */
369 [ + + ][ - + ]: 45 : if (i != 160 && i != 224 && i != 256)
370 : : {
371 : 0 : DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_BAD_Q_VALUE);
372 : 0 : return -1;
373 : : }
374 : :
375 : : #ifdef OPENSSL_FIPS
376 : : if(FIPS_selftest_failed())
377 : : {
378 : : FIPSerr(FIPS_F_DSA_DO_VERIFY,FIPS_R_FIPS_SELFTEST_FAILED);
379 : : return -1;
380 : : }
381 : :
382 : : if (FIPS_module_mode() && !(dsa->flags & DSA_FLAG_NON_FIPS_ALLOW)
383 : : && (BN_num_bits(dsa->p) < OPENSSL_DSA_FIPS_MIN_MODULUS_BITS))
384 : : {
385 : : DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_KEY_SIZE_TOO_SMALL);
386 : : return -1;
387 : : }
388 : : #endif
389 : :
390 [ - + ]: 45 : if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS)
391 : : {
392 : 0 : DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MODULUS_TOO_LARGE);
393 : 0 : return -1;
394 : : }
395 : 45 : BN_init(&u1);
396 : 45 : BN_init(&u2);
397 : 45 : BN_init(&t1);
398 : :
399 [ + - ]: 45 : if ((ctx=BN_CTX_new()) == NULL) goto err;
400 : :
401 [ + - ]: 90 : if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
[ + - + - ]
402 : 45 : BN_ucmp(sig->r, dsa->q) >= 0)
403 : : {
404 : : ret = 0;
405 : : goto err;
406 : : }
407 [ + - ]: 90 : if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
[ + - + - ]
408 : 45 : BN_ucmp(sig->s, dsa->q) >= 0)
409 : : {
410 : : ret = 0;
411 : : goto err;
412 : : }
413 : :
414 : : /* Calculate W = inv(S) mod Q
415 : : * save W in u2 */
416 [ + - ]: 45 : if ((BN_mod_inverse(&u2,sig->s,dsa->q,ctx)) == NULL) goto err;
417 : :
418 : : /* save M in u1 */
419 [ - + ]: 45 : if (dgst_len > (i >> 3))
420 : : /* if the digest length is greater than the size of q use the
421 : : * BN_num_bits(dsa->q) leftmost bits of the digest, see
422 : : * fips 186-3, 4.2 */
423 : 0 : dgst_len = (i >> 3);
424 [ + - ]: 45 : if (BN_bin2bn(dgst,dgst_len,&u1) == NULL) goto err;
425 : :
426 : : /* u1 = M * w mod q */
427 [ + - ]: 45 : if (!BN_mod_mul(&u1,&u1,&u2,dsa->q,ctx)) goto err;
428 : :
429 : : /* u2 = r * w mod q */
430 [ + - ]: 45 : if (!BN_mod_mul(&u2,sig->r,&u2,dsa->q,ctx)) goto err;
431 : :
432 : :
433 [ + - ]: 45 : if (dsa->flags & DSA_FLAG_CACHE_MONT_P)
434 : : {
435 : 45 : mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
436 : 45 : CRYPTO_LOCK_DSA, dsa->p, ctx);
437 [ + - ]: 45 : if (!mont)
438 : : goto err;
439 : : }
440 : :
441 : :
442 [ - + ][ + - ]: 45 : DSA_MOD_EXP(goto err, dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, mont);
443 : : /* BN_copy(&u1,&t1); */
444 : : /* let u1 = u1 mod q */
445 [ + - ]: 45 : if (!BN_mod(&u1,&t1,dsa->q,ctx)) goto err;
446 : :
447 : : /* V is now in u1. If the signature is correct, it will be
448 : : * equal to R. */
449 : 45 : ret=(BN_ucmp(&u1, sig->r) == 0);
450 : :
451 : : err:
452 : : /* XXX: surely this is wrong - if ret is 0, it just didn't verify;
453 : : there is no error in BN. Test should be ret == -1 (Ben) */
454 [ - + ]: 45 : if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB);
455 [ + - ]: 45 : if (ctx != NULL) BN_CTX_free(ctx);
456 : 45 : BN_free(&u1);
457 : 45 : BN_free(&u2);
458 : 45 : BN_free(&t1);
459 : 45 : return(ret);
460 : : }
461 : :
462 : 118 : static int dsa_init(DSA *dsa)
463 : : {
464 : 118 : dsa->flags|=DSA_FLAG_CACHE_MONT_P;
465 : 118 : return(1);
466 : : }
467 : :
468 : 118 : static int dsa_finish(DSA *dsa)
469 : : {
470 [ + + ]: 118 : if(dsa->method_mont_p)
471 : 80 : BN_MONT_CTX_free(dsa->method_mont_p);
472 : 118 : return(1);
473 : : }
474 : :
|
