1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay (at) cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] 56 * 57 * The DSS routines are based on patches supplied by 58 * Steven Schoch <schoch (at) sheba.arc.nasa.gov>. */ 59 60 #include <openssl/dsa.h> 61 62 #include <string.h> 63 64 #include <openssl/bn.h> 65 #include <openssl/dh.h> 66 #include <openssl/digest.h> 67 #include <openssl/engine.h> 68 #include <openssl/err.h> 69 #include <openssl/ex_data.h> 70 #include <openssl/mem.h> 71 #include <openssl/rand.h> 72 #include <openssl/sha.h> 73 #include <openssl/thread.h> 74 75 #include "../fipsmodule/bn/internal.h" 76 #include "../internal.h" 77 78 79 #define OPENSSL_DSA_MAX_MODULUS_BITS 10000 80 81 /* Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of 82 * Rabin-Miller */ 83 #define DSS_prime_checks 50 84 85 static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT; 86 87 DSA *DSA_new(void) { 88 DSA *dsa = OPENSSL_malloc(sizeof(DSA)); 89 if (dsa == NULL) { 90 OPENSSL_PUT_ERROR(DSA, ERR_R_MALLOC_FAILURE); 91 return NULL; 92 } 93 94 OPENSSL_memset(dsa, 0, sizeof(DSA)); 95 96 dsa->references = 1; 97 98 CRYPTO_MUTEX_init(&dsa->method_mont_lock); 99 CRYPTO_new_ex_data(&dsa->ex_data); 100 101 return dsa; 102 } 103 104 void DSA_free(DSA *dsa) { 105 if (dsa == NULL) { 106 return; 107 } 108 109 if (!CRYPTO_refcount_dec_and_test_zero(&dsa->references)) { 110 return; 111 } 112 113 CRYPTO_free_ex_data(&g_ex_data_class, dsa, &dsa->ex_data); 114 115 BN_clear_free(dsa->p); 116 BN_clear_free(dsa->q); 117 BN_clear_free(dsa->g); 118 BN_clear_free(dsa->pub_key); 119 BN_clear_free(dsa->priv_key); 120 BN_clear_free(dsa->kinv); 121 BN_clear_free(dsa->r); 122 BN_MONT_CTX_free(dsa->method_mont_p); 123 BN_MONT_CTX_free(dsa->method_mont_q); 124 CRYPTO_MUTEX_cleanup(&dsa->method_mont_lock); 125 OPENSSL_free(dsa); 126 } 127 128 int DSA_up_ref(DSA *dsa) { 129 CRYPTO_refcount_inc(&dsa->references); 130 return 1; 131 } 132 133 void DSA_get0_key(const DSA *dsa, const BIGNUM **out_pub_key, 134 const BIGNUM **out_priv_key) { 135 if (out_pub_key != NULL) { 136 *out_pub_key = dsa->pub_key; 137 } 138 if (out_priv_key != NULL) { 139 *out_priv_key = dsa->priv_key; 140 } 141 } 142 143 void DSA_get0_pqg(const DSA *dsa, const BIGNUM **out_p, const BIGNUM **out_q, 144 const BIGNUM **out_g) { 145 if (out_p != NULL) { 146 *out_p = dsa->p; 147 } 148 if (out_q != NULL) { 149 *out_q = dsa->q; 150 } 151 if (out_g != NULL) { 152 *out_g = dsa->g; 153 } 154 } 155 156 int DSA_generate_parameters_ex(DSA *dsa, unsigned bits, const uint8_t *seed_in, 157 size_t seed_len, int *out_counter, 158 unsigned long *out_h, BN_GENCB *cb) { 159 int ok = 0; 160 unsigned char seed[SHA256_DIGEST_LENGTH]; 161 unsigned char md[SHA256_DIGEST_LENGTH]; 162 unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; 163 BIGNUM *r0, *W, *X, *c, *test; 164 BIGNUM *g = NULL, *q = NULL, *p = NULL; 165 BN_MONT_CTX *mont = NULL; 166 int k, n = 0, m = 0; 167 unsigned i; 168 int counter = 0; 169 int r = 0; 170 BN_CTX *ctx = NULL; 171 unsigned int h = 2; 172 unsigned qsize; 173 const EVP_MD *evpmd; 174 175 evpmd = (bits >= 2048) ? EVP_sha256() : EVP_sha1(); 176 qsize = EVP_MD_size(evpmd); 177 178 if (bits < 512) { 179 bits = 512; 180 } 181 182 bits = (bits + 63) / 64 * 64; 183 184 if (seed_in != NULL) { 185 if (seed_len < (size_t)qsize) { 186 return 0; 187 } 188 if (seed_len > (size_t)qsize) { 189 /* Only consume as much seed as is expected. */ 190 seed_len = qsize; 191 } 192 OPENSSL_memcpy(seed, seed_in, seed_len); 193 } 194 195 ctx = BN_CTX_new(); 196 if (ctx == NULL) { 197 goto err; 198 } 199 BN_CTX_start(ctx); 200 201 mont = BN_MONT_CTX_new(); 202 if (mont == NULL) { 203 goto err; 204 } 205 206 r0 = BN_CTX_get(ctx); 207 g = BN_CTX_get(ctx); 208 W = BN_CTX_get(ctx); 209 q = BN_CTX_get(ctx); 210 X = BN_CTX_get(ctx); 211 c = BN_CTX_get(ctx); 212 p = BN_CTX_get(ctx); 213 test = BN_CTX_get(ctx); 214 215 if (test == NULL || !BN_lshift(test, BN_value_one(), bits - 1)) { 216 goto err; 217 } 218 219 for (;;) { 220 /* Find q. */ 221 for (;;) { 222 /* step 1 */ 223 if (!BN_GENCB_call(cb, 0, m++)) { 224 goto err; 225 } 226 227 int use_random_seed = (seed_in == NULL); 228 if (use_random_seed) { 229 if (!RAND_bytes(seed, qsize)) { 230 goto err; 231 } 232 } else { 233 /* If we come back through, use random seed next time. */ 234 seed_in = NULL; 235 } 236 OPENSSL_memcpy(buf, seed, qsize); 237 OPENSSL_memcpy(buf2, seed, qsize); 238 /* precompute "SEED + 1" for step 7: */ 239 for (i = qsize - 1; i < qsize; i--) { 240 buf[i]++; 241 if (buf[i] != 0) { 242 break; 243 } 244 } 245 246 /* step 2 */ 247 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL) || 248 !EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) { 249 goto err; 250 } 251 for (i = 0; i < qsize; i++) { 252 md[i] ^= buf2[i]; 253 } 254 255 /* step 3 */ 256 md[0] |= 0x80; 257 md[qsize - 1] |= 0x01; 258 if (!BN_bin2bn(md, qsize, q)) { 259 goto err; 260 } 261 262 /* step 4 */ 263 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, use_random_seed, cb); 264 if (r > 0) { 265 break; 266 } 267 if (r != 0) { 268 goto err; 269 } 270 271 /* do a callback call */ 272 /* step 5 */ 273 } 274 275 if (!BN_GENCB_call(cb, 2, 0) || !BN_GENCB_call(cb, 3, 0)) { 276 goto err; 277 } 278 279 /* step 6 */ 280 counter = 0; 281 /* "offset = 2" */ 282 283 n = (bits - 1) / 160; 284 285 for (;;) { 286 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) { 287 goto err; 288 } 289 290 /* step 7 */ 291 BN_zero(W); 292 /* now 'buf' contains "SEED + offset - 1" */ 293 for (k = 0; k <= n; k++) { 294 /* obtain "SEED + offset + k" by incrementing: */ 295 for (i = qsize - 1; i < qsize; i--) { 296 buf[i]++; 297 if (buf[i] != 0) { 298 break; 299 } 300 } 301 302 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) { 303 goto err; 304 } 305 306 /* step 8 */ 307 if (!BN_bin2bn(md, qsize, r0) || 308 !BN_lshift(r0, r0, (qsize << 3) * k) || 309 !BN_add(W, W, r0)) { 310 goto err; 311 } 312 } 313 314 /* more of step 8 */ 315 if (!BN_mask_bits(W, bits - 1) || 316 !BN_copy(X, W) || 317 !BN_add(X, X, test)) { 318 goto err; 319 } 320 321 /* step 9 */ 322 if (!BN_lshift1(r0, q) || 323 !BN_mod(c, X, r0, ctx) || 324 !BN_sub(r0, c, BN_value_one()) || 325 !BN_sub(p, X, r0)) { 326 goto err; 327 } 328 329 /* step 10 */ 330 if (BN_cmp(p, test) >= 0) { 331 /* step 11 */ 332 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 333 if (r > 0) { 334 goto end; /* found it */ 335 } 336 if (r != 0) { 337 goto err; 338 } 339 } 340 341 /* step 13 */ 342 counter++; 343 /* "offset = offset + n + 1" */ 344 345 /* step 14 */ 346 if (counter >= 4096) { 347 break; 348 } 349 } 350 } 351 end: 352 if (!BN_GENCB_call(cb, 2, 1)) { 353 goto err; 354 } 355 356 /* We now need to generate g */ 357 /* Set r0=(p-1)/q */ 358 if (!BN_sub(test, p, BN_value_one()) || 359 !BN_div(r0, NULL, test, q, ctx)) { 360 goto err; 361 } 362 363 if (!BN_set_word(test, h) || 364 !BN_MONT_CTX_set(mont, p, ctx)) { 365 goto err; 366 } 367 368 for (;;) { 369 /* g=test^r0%p */ 370 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) { 371 goto err; 372 } 373 if (!BN_is_one(g)) { 374 break; 375 } 376 if (!BN_add(test, test, BN_value_one())) { 377 goto err; 378 } 379 h++; 380 } 381 382 if (!BN_GENCB_call(cb, 3, 1)) { 383 goto err; 384 } 385 386 ok = 1; 387 388 err: 389 if (ok) { 390 BN_free(dsa->p); 391 BN_free(dsa->q); 392 BN_free(dsa->g); 393 dsa->p = BN_dup(p); 394 dsa->q = BN_dup(q); 395 dsa->g = BN_dup(g); 396 if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) { 397 ok = 0; 398 goto err; 399 } 400 if (out_counter != NULL) { 401 *out_counter = counter; 402 } 403 if (out_h != NULL) { 404 *out_h = h; 405 } 406 } 407 408 if (ctx) { 409 BN_CTX_end(ctx); 410 BN_CTX_free(ctx); 411 } 412 413 BN_MONT_CTX_free(mont); 414 415 return ok; 416 } 417 418 DSA *DSAparams_dup(const DSA *dsa) { 419 DSA *ret = DSA_new(); 420 if (ret == NULL) { 421 return NULL; 422 } 423 ret->p = BN_dup(dsa->p); 424 ret->q = BN_dup(dsa->q); 425 ret->g = BN_dup(dsa->g); 426 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 427 DSA_free(ret); 428 return NULL; 429 } 430 return ret; 431 } 432 433 int DSA_generate_key(DSA *dsa) { 434 int ok = 0; 435 BN_CTX *ctx = NULL; 436 BIGNUM *pub_key = NULL, *priv_key = NULL; 437 438 ctx = BN_CTX_new(); 439 if (ctx == NULL) { 440 goto err; 441 } 442 443 priv_key = dsa->priv_key; 444 if (priv_key == NULL) { 445 priv_key = BN_new(); 446 if (priv_key == NULL) { 447 goto err; 448 } 449 } 450 451 if (!BN_rand_range_ex(priv_key, 1, dsa->q)) { 452 goto err; 453 } 454 455 pub_key = dsa->pub_key; 456 if (pub_key == NULL) { 457 pub_key = BN_new(); 458 if (pub_key == NULL) { 459 goto err; 460 } 461 } 462 463 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, &dsa->method_mont_lock, 464 dsa->p, ctx) || 465 !BN_mod_exp_mont_consttime(pub_key, dsa->g, priv_key, dsa->p, ctx, 466 dsa->method_mont_p)) { 467 goto err; 468 } 469 470 dsa->priv_key = priv_key; 471 dsa->pub_key = pub_key; 472 ok = 1; 473 474 err: 475 if (dsa->pub_key == NULL) { 476 BN_free(pub_key); 477 } 478 if (dsa->priv_key == NULL) { 479 BN_free(priv_key); 480 } 481 BN_CTX_free(ctx); 482 483 return ok; 484 } 485 486 DSA_SIG *DSA_SIG_new(void) { 487 DSA_SIG *sig; 488 sig = OPENSSL_malloc(sizeof(DSA_SIG)); 489 if (!sig) { 490 return NULL; 491 } 492 sig->r = NULL; 493 sig->s = NULL; 494 return sig; 495 } 496 497 void DSA_SIG_free(DSA_SIG *sig) { 498 if (!sig) { 499 return; 500 } 501 502 BN_free(sig->r); 503 BN_free(sig->s); 504 OPENSSL_free(sig); 505 } 506 507 DSA_SIG *DSA_do_sign(const uint8_t *digest, size_t digest_len, DSA *dsa) { 508 BIGNUM *kinv = NULL, *r = NULL, *s = NULL; 509 BIGNUM m; 510 BIGNUM xr; 511 BN_CTX *ctx = NULL; 512 int reason = ERR_R_BN_LIB; 513 DSA_SIG *ret = NULL; 514 int noredo = 0; 515 516 BN_init(&m); 517 BN_init(&xr); 518 519 if (!dsa->p || !dsa->q || !dsa->g) { 520 reason = DSA_R_MISSING_PARAMETERS; 521 goto err; 522 } 523 524 s = BN_new(); 525 if (s == NULL) { 526 goto err; 527 } 528 ctx = BN_CTX_new(); 529 if (ctx == NULL) { 530 goto err; 531 } 532 533 redo: 534 if (dsa->kinv == NULL || dsa->r == NULL) { 535 if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) { 536 goto err; 537 } 538 } else { 539 kinv = dsa->kinv; 540 dsa->kinv = NULL; 541 r = dsa->r; 542 dsa->r = NULL; 543 noredo = 1; 544 } 545 546 if (digest_len > BN_num_bytes(dsa->q)) { 547 /* if the digest length is greater than the size of q use the 548 * BN_num_bits(dsa->q) leftmost bits of the digest, see 549 * fips 186-3, 4.2 */ 550 digest_len = BN_num_bytes(dsa->q); 551 } 552 553 if (BN_bin2bn(digest, digest_len, &m) == NULL) { 554 goto err; 555 } 556 557 /* Compute s = inv(k) (m + xr) mod q */ 558 if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) { 559 goto err; /* s = xr */ 560 } 561 if (!BN_add(s, &xr, &m)) { 562 goto err; /* s = m + xr */ 563 } 564 if (BN_cmp(s, dsa->q) > 0) { 565 if (!BN_sub(s, s, dsa->q)) { 566 goto err; 567 } 568 } 569 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) { 570 goto err; 571 } 572 573 /* Redo if r or s is zero as required by FIPS 186-3: this is 574 * very unlikely. */ 575 if (BN_is_zero(r) || BN_is_zero(s)) { 576 if (noredo) { 577 reason = DSA_R_NEED_NEW_SETUP_VALUES; 578 goto err; 579 } 580 goto redo; 581 } 582 ret = DSA_SIG_new(); 583 if (ret == NULL) { 584 goto err; 585 } 586 ret->r = r; 587 ret->s = s; 588 589 err: 590 if (ret == NULL) { 591 OPENSSL_PUT_ERROR(DSA, reason); 592 BN_free(r); 593 BN_free(s); 594 } 595 BN_CTX_free(ctx); 596 BN_clear_free(&m); 597 BN_clear_free(&xr); 598 BN_clear_free(kinv); 599 600 return ret; 601 } 602 603 int DSA_do_verify(const uint8_t *digest, size_t digest_len, DSA_SIG *sig, 604 const DSA *dsa) { 605 int valid; 606 if (!DSA_do_check_signature(&valid, digest, digest_len, sig, dsa)) { 607 return -1; 608 } 609 return valid; 610 } 611 612 int DSA_do_check_signature(int *out_valid, const uint8_t *digest, 613 size_t digest_len, DSA_SIG *sig, const DSA *dsa) { 614 BN_CTX *ctx; 615 BIGNUM u1, u2, t1; 616 int ret = 0; 617 unsigned i; 618 619 *out_valid = 0; 620 621 if (!dsa->p || !dsa->q || !dsa->g) { 622 OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS); 623 return 0; 624 } 625 626 i = BN_num_bits(dsa->q); 627 /* fips 186-3 allows only different sizes for q */ 628 if (i != 160 && i != 224 && i != 256) { 629 OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE); 630 return 0; 631 } 632 633 if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { 634 OPENSSL_PUT_ERROR(DSA, DSA_R_MODULUS_TOO_LARGE); 635 return 0; 636 } 637 638 BN_init(&u1); 639 BN_init(&u2); 640 BN_init(&t1); 641 642 ctx = BN_CTX_new(); 643 if (ctx == NULL) { 644 goto err; 645 } 646 647 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 648 BN_ucmp(sig->r, dsa->q) >= 0) { 649 ret = 1; 650 goto err; 651 } 652 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || 653 BN_ucmp(sig->s, dsa->q) >= 0) { 654 ret = 1; 655 goto err; 656 } 657 658 /* Calculate W = inv(S) mod Q 659 * save W in u2 */ 660 if (BN_mod_inverse(&u2, sig->s, dsa->q, ctx) == NULL) { 661 goto err; 662 } 663 664 /* save M in u1 */ 665 if (digest_len > (i >> 3)) { 666 /* if the digest length is greater than the size of q use the 667 * BN_num_bits(dsa->q) leftmost bits of the digest, see 668 * fips 186-3, 4.2 */ 669 digest_len = (i >> 3); 670 } 671 672 if (BN_bin2bn(digest, digest_len, &u1) == NULL) { 673 goto err; 674 } 675 676 /* u1 = M * w mod q */ 677 if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) { 678 goto err; 679 } 680 681 /* u2 = r * w mod q */ 682 if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) { 683 goto err; 684 } 685 686 if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, 687 (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p, 688 ctx)) { 689 goto err; 690 } 691 692 if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, 693 dsa->method_mont_p)) { 694 goto err; 695 } 696 697 /* BN_copy(&u1,&t1); */ 698 /* let u1 = u1 mod q */ 699 if (!BN_mod(&u1, &t1, dsa->q, ctx)) { 700 goto err; 701 } 702 703 /* V is now in u1. If the signature is correct, it will be 704 * equal to R. */ 705 *out_valid = BN_ucmp(&u1, sig->r) == 0; 706 ret = 1; 707 708 err: 709 if (ret != 1) { 710 OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB); 711 } 712 BN_CTX_free(ctx); 713 BN_free(&u1); 714 BN_free(&u2); 715 BN_free(&t1); 716 717 return ret; 718 } 719 720 int DSA_sign(int type, const uint8_t *digest, size_t digest_len, 721 uint8_t *out_sig, unsigned int *out_siglen, DSA *dsa) { 722 DSA_SIG *s; 723 724 s = DSA_do_sign(digest, digest_len, dsa); 725 if (s == NULL) { 726 *out_siglen = 0; 727 return 0; 728 } 729 730 *out_siglen = i2d_DSA_SIG(s, &out_sig); 731 DSA_SIG_free(s); 732 return 1; 733 } 734 735 int DSA_verify(int type, const uint8_t *digest, size_t digest_len, 736 const uint8_t *sig, size_t sig_len, const DSA *dsa) { 737 int valid; 738 if (!DSA_check_signature(&valid, digest, digest_len, sig, sig_len, dsa)) { 739 return -1; 740 } 741 return valid; 742 } 743 744 int DSA_check_signature(int *out_valid, const uint8_t *digest, 745 size_t digest_len, const uint8_t *sig, size_t sig_len, 746 const DSA *dsa) { 747 DSA_SIG *s = NULL; 748 int ret = 0; 749 uint8_t *der = NULL; 750 751 s = DSA_SIG_new(); 752 if (s == NULL) { 753 goto err; 754 } 755 756 const uint8_t *sigp = sig; 757 if (d2i_DSA_SIG(&s, &sigp, sig_len) == NULL || sigp != sig + sig_len) { 758 goto err; 759 } 760 761 /* Ensure that the signature uses DER and doesn't have trailing garbage. */ 762 int der_len = i2d_DSA_SIG(s, &der); 763 if (der_len < 0 || (size_t)der_len != sig_len || 764 OPENSSL_memcmp(sig, der, sig_len)) { 765 goto err; 766 } 767 768 ret = DSA_do_check_signature(out_valid, digest, digest_len, s, dsa); 769 770 err: 771 OPENSSL_free(der); 772 DSA_SIG_free(s); 773 return ret; 774 } 775 776 /* der_len_len returns the number of bytes needed to represent a length of |len| 777 * in DER. */ 778 static size_t der_len_len(size_t len) { 779 if (len < 0x80) { 780 return 1; 781 } 782 size_t ret = 1; 783 while (len > 0) { 784 ret++; 785 len >>= 8; 786 } 787 return ret; 788 } 789 790 int DSA_size(const DSA *dsa) { 791 size_t order_len = BN_num_bytes(dsa->q); 792 /* Compute the maximum length of an |order_len| byte integer. Defensively 793 * assume that the leading 0x00 is included. */ 794 size_t integer_len = 1 /* tag */ + der_len_len(order_len + 1) + 1 + order_len; 795 if (integer_len < order_len) { 796 return 0; 797 } 798 /* A DSA signature is two INTEGERs. */ 799 size_t value_len = 2 * integer_len; 800 if (value_len < integer_len) { 801 return 0; 802 } 803 /* Add the header. */ 804 size_t ret = 1 /* tag */ + der_len_len(value_len) + value_len; 805 if (ret < value_len) { 806 return 0; 807 } 808 return ret; 809 } 810 811 int DSA_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv, 812 BIGNUM **out_r) { 813 BN_CTX *ctx; 814 BIGNUM k, kq, *kinv = NULL, *r = NULL; 815 int ret = 0; 816 817 if (!dsa->p || !dsa->q || !dsa->g) { 818 OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS); 819 return 0; 820 } 821 822 BN_init(&k); 823 BN_init(&kq); 824 825 ctx = ctx_in; 826 if (ctx == NULL) { 827 ctx = BN_CTX_new(); 828 if (ctx == NULL) { 829 goto err; 830 } 831 } 832 833 r = BN_new(); 834 if (r == NULL) { 835 goto err; 836 } 837 838 /* Get random k */ 839 if (!BN_rand_range_ex(&k, 1, dsa->q)) { 840 goto err; 841 } 842 843 if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, 844 (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p, 845 ctx) || 846 !BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_q, 847 (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->q, 848 ctx)) { 849 goto err; 850 } 851 852 /* Compute r = (g^k mod p) mod q */ 853 if (!BN_copy(&kq, &k)) { 854 goto err; 855 } 856 857 /* We do not want timing information to leak the length of k, 858 * so we compute g^k using an equivalent exponent of fixed length. 859 * 860 * (This is a kludge that we need because the BN_mod_exp_mont() 861 * does not let us specify the desired timing behaviour.) */ 862 863 if (!BN_add(&kq, &kq, dsa->q)) { 864 goto err; 865 } 866 if (BN_num_bits(&kq) <= BN_num_bits(dsa->q) && !BN_add(&kq, &kq, dsa->q)) { 867 goto err; 868 } 869 870 if (!BN_mod_exp_mont_consttime(r, dsa->g, &kq, dsa->p, ctx, 871 dsa->method_mont_p)) { 872 goto err; 873 } 874 if (!BN_mod(r, r, dsa->q, ctx)) { 875 goto err; 876 } 877 878 /* Compute part of 's = inv(k) (m + xr) mod q' using Fermat's Little 879 * Theorem. */ 880 kinv = BN_new(); 881 if (kinv == NULL || 882 !bn_mod_inverse_prime(kinv, &k, dsa->q, ctx, dsa->method_mont_q)) { 883 goto err; 884 } 885 886 BN_clear_free(*out_kinv); 887 *out_kinv = kinv; 888 kinv = NULL; 889 BN_clear_free(*out_r); 890 *out_r = r; 891 ret = 1; 892 893 err: 894 if (!ret) { 895 OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB); 896 if (r != NULL) { 897 BN_clear_free(r); 898 } 899 } 900 901 if (ctx_in == NULL) { 902 BN_CTX_free(ctx); 903 } 904 BN_clear_free(&k); 905 BN_clear_free(&kq); 906 BN_clear_free(kinv); 907 return ret; 908 } 909 910 int DSA_get_ex_new_index(long argl, void *argp, CRYPTO_EX_unused *unused, 911 CRYPTO_EX_dup *dup_unused, CRYPTO_EX_free *free_func) { 912 int index; 913 if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp, 914 free_func)) { 915 return -1; 916 } 917 return index; 918 } 919 920 int DSA_set_ex_data(DSA *d, int idx, void *arg) { 921 return CRYPTO_set_ex_data(&d->ex_data, idx, arg); 922 } 923 924 void *DSA_get_ex_data(const DSA *d, int idx) { 925 return CRYPTO_get_ex_data(&d->ex_data, idx); 926 } 927 928 DH *DSA_dup_DH(const DSA *r) { 929 DH *ret = NULL; 930 931 if (r == NULL) { 932 goto err; 933 } 934 ret = DH_new(); 935 if (ret == NULL) { 936 goto err; 937 } 938 if (r->q != NULL) { 939 ret->priv_length = BN_num_bits(r->q); 940 if ((ret->q = BN_dup(r->q)) == NULL) { 941 goto err; 942 } 943 } 944 if ((r->p != NULL && (ret->p = BN_dup(r->p)) == NULL) || 945 (r->g != NULL && (ret->g = BN_dup(r->g)) == NULL) || 946 (r->pub_key != NULL && (ret->pub_key = BN_dup(r->pub_key)) == NULL) || 947 (r->priv_key != NULL && (ret->priv_key = BN_dup(r->priv_key)) == NULL)) { 948 goto err; 949 } 950 951 return ret; 952 953 err: 954 DH_free(ret); 955 return NULL; 956 } 957
