1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay@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@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@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@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@sheba.arc.nasa.gov>. */ 59 60#include <openssl/dsa.h> 61 62#include <openssl/bn.h> 63#include <openssl/digest.h> 64#include <openssl/err.h> 65#include <openssl/rand.h> 66#include <openssl/sha.h> 67 68#include "internal.h" 69 70#define OPENSSL_DSA_MAX_MODULUS_BITS 10000 71 72/* Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of 73 * Rabin-Miller */ 74#define DSS_prime_checks 50 75 76static int sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, 77 BIGNUM **rp, const uint8_t *digest, size_t digest_len) { 78 BN_CTX *ctx; 79 BIGNUM k, kq, *K, *kinv = NULL, *r = NULL; 80 int ret = 0; 81 82 if (!dsa->p || !dsa->q || !dsa->g) { 83 OPENSSL_PUT_ERROR(DSA, sign_setup, DSA_R_MISSING_PARAMETERS); 84 return 0; 85 } 86 87 BN_init(&k); 88 BN_init(&kq); 89 90 ctx = ctx_in; 91 if (ctx == NULL) { 92 ctx = BN_CTX_new(); 93 if (ctx == NULL) { 94 goto err; 95 } 96 } 97 98 r = BN_new(); 99 if (r == NULL) { 100 goto err; 101 } 102 103 /* Get random k */ 104 do { 105 /* If possible, we'll include the private key and message digest in the k 106 * generation. The |digest| argument is only empty if |DSA_sign_setup| is 107 * being used. */ 108 int ok; 109 110 if (digest_len > 0) { 111 ok = BN_generate_dsa_nonce(&k, dsa->q, dsa->priv_key, digest, digest_len, 112 ctx); 113 } else { 114 ok = BN_rand_range(&k, dsa->q); 115 } 116 if (!ok) { 117 goto err; 118 } 119 } while (BN_is_zero(&k)); 120 121 BN_set_flags(&k, BN_FLG_CONSTTIME); 122 123 if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, 124 CRYPTO_LOCK_DSA, dsa->p, ctx)) { 125 goto err; 126 } 127 128 /* Compute r = (g^k mod p) mod q */ 129 if (!BN_copy(&kq, &k)) 130 goto err; 131 132 /* We do not want timing information to leak the length of k, 133 * so we compute g^k using an equivalent exponent of fixed length. 134 * 135 * (This is a kludge that we need because the BN_mod_exp_mont() 136 * does not let us specify the desired timing behaviour.) */ 137 138 if (!BN_add(&kq, &kq, dsa->q)) 139 goto err; 140 if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) { 141 if (!BN_add(&kq, &kq, dsa->q)) 142 goto err; 143 } 144 145 K = &kq; 146 147 if (!BN_mod_exp_mont(r, dsa->g, K, dsa->p, ctx, dsa->method_mont_p)) { 148 goto err; 149 } 150 if (!BN_mod(r, r, dsa->q, ctx)) { 151 goto err; 152 } 153 154 /* Compute part of 's = inv(k) (m + xr) mod q' */ 155 kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx); 156 if (kinv == NULL) { 157 goto err; 158 } 159 160 if (*kinvp != NULL) { 161 BN_clear_free(*kinvp); 162 } 163 *kinvp = kinv; 164 kinv = NULL; 165 if (*rp != NULL) { 166 BN_clear_free(*rp); 167 } 168 *rp = r; 169 ret = 1; 170 171err: 172 if (!ret) { 173 OPENSSL_PUT_ERROR(DSA, sign_setup, ERR_R_BN_LIB); 174 if (r != NULL) { 175 BN_clear_free(r); 176 } 177 } 178 179 if (ctx_in == NULL) { 180 BN_CTX_free(ctx); 181 } 182 BN_clear_free(&k); 183 BN_clear_free(&kq); 184 return ret; 185} 186 187static DSA_SIG *sign(const uint8_t *digest, size_t digest_len, DSA *dsa) { 188 BIGNUM *kinv = NULL, *r = NULL, *s = NULL; 189 BIGNUM m; 190 BIGNUM xr; 191 BN_CTX *ctx = NULL; 192 int reason = ERR_R_BN_LIB; 193 DSA_SIG *ret = NULL; 194 int noredo = 0; 195 196 BN_init(&m); 197 BN_init(&xr); 198 199 if (!dsa->p || !dsa->q || !dsa->g) { 200 reason = DSA_R_MISSING_PARAMETERS; 201 goto err; 202 } 203 204 s = BN_new(); 205 if (s == NULL) { 206 goto err; 207 } 208 ctx = BN_CTX_new(); 209 if (ctx == NULL) { 210 goto err; 211 } 212 213redo: 214 if (dsa->kinv == NULL || dsa->r == NULL) { 215 if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) { 216 goto err; 217 } 218 } else { 219 kinv = dsa->kinv; 220 dsa->kinv = NULL; 221 r = dsa->r; 222 dsa->r = NULL; 223 noredo = 1; 224 } 225 226 if (digest_len > BN_num_bytes(dsa->q)) { 227 /* if the digest length is greater than the size of q use the 228 * BN_num_bits(dsa->q) leftmost bits of the digest, see 229 * fips 186-3, 4.2 */ 230 digest_len = BN_num_bytes(dsa->q); 231 } 232 233 if (BN_bin2bn(digest, digest_len, &m) == NULL) { 234 goto err; 235 } 236 237 /* Compute s = inv(k) (m + xr) mod q */ 238 if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) { 239 goto err; /* s = xr */ 240 } 241 if (!BN_add(s, &xr, &m)) { 242 goto err; /* s = m + xr */ 243 } 244 if (BN_cmp(s, dsa->q) > 0) { 245 if (!BN_sub(s, s, dsa->q)) { 246 goto err; 247 } 248 } 249 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) { 250 goto err; 251 } 252 253 ret = DSA_SIG_new(); 254 if (ret == NULL) { 255 goto err; 256 } 257 /* Redo if r or s is zero as required by FIPS 186-3: this is 258 * very unlikely. */ 259 if (BN_is_zero(r) || BN_is_zero(s)) { 260 if (noredo) { 261 reason = DSA_R_NEED_NEW_SETUP_VALUES; 262 goto err; 263 } 264 goto redo; 265 } 266 ret->r = r; 267 ret->s = s; 268 269err: 270 if (!ret) { 271 OPENSSL_PUT_ERROR(DSA, sign, reason); 272 BN_free(r); 273 BN_free(s); 274 } 275 if (ctx != NULL) { 276 BN_CTX_free(ctx); 277 } 278 BN_clear_free(&m); 279 BN_clear_free(&xr); 280 if (kinv != NULL) { 281 /* dsa->kinv is NULL now if we used it */ 282 BN_clear_free(kinv); 283 } 284 285 return ret; 286} 287 288static int verify(int *out_valid, const uint8_t *dgst, size_t digest_len, 289 DSA_SIG *sig, const DSA *dsa) { 290 BN_CTX *ctx; 291 BIGNUM u1, u2, t1; 292 BN_MONT_CTX *mont = NULL; 293 int ret = 0; 294 unsigned i; 295 296 *out_valid = 0; 297 298 if (!dsa->p || !dsa->q || !dsa->g) { 299 OPENSSL_PUT_ERROR(DSA, verify, DSA_R_MISSING_PARAMETERS); 300 return 0; 301 } 302 303 i = BN_num_bits(dsa->q); 304 /* fips 186-3 allows only different sizes for q */ 305 if (i != 160 && i != 224 && i != 256) { 306 OPENSSL_PUT_ERROR(DSA, verify, DSA_R_BAD_Q_VALUE); 307 return 0; 308 } 309 310 if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { 311 OPENSSL_PUT_ERROR(DSA, verify, DSA_R_MODULUS_TOO_LARGE); 312 return 0; 313 } 314 315 BN_init(&u1); 316 BN_init(&u2); 317 BN_init(&t1); 318 319 ctx = BN_CTX_new(); 320 if (ctx == NULL) { 321 goto err; 322 } 323 324 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 325 BN_ucmp(sig->r, dsa->q) >= 0) { 326 ret = 1; 327 goto err; 328 } 329 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || 330 BN_ucmp(sig->s, dsa->q) >= 0) { 331 ret = 1; 332 goto err; 333 } 334 335 /* Calculate W = inv(S) mod Q 336 * save W in u2 */ 337 if (BN_mod_inverse(&u2, sig->s, dsa->q, ctx) == NULL) { 338 goto err; 339 } 340 341 /* save M in u1 */ 342 if (digest_len > (i >> 3)) { 343 /* if the digest length is greater than the size of q use the 344 * BN_num_bits(dsa->q) leftmost bits of the digest, see 345 * fips 186-3, 4.2 */ 346 digest_len = (i >> 3); 347 } 348 349 if (BN_bin2bn(dgst, digest_len, &u1) == NULL) { 350 goto err; 351 } 352 353 /* u1 = M * w mod q */ 354 if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) { 355 goto err; 356 } 357 358 /* u2 = r * w mod q */ 359 if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) { 360 goto err; 361 } 362 363 mont = BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, 364 CRYPTO_LOCK_DSA, dsa->p, ctx); 365 if (!mont) { 366 goto err; 367 } 368 369 if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, mont)) { 370 goto err; 371 } 372 373 /* BN_copy(&u1,&t1); */ 374 /* let u1 = u1 mod q */ 375 if (!BN_mod(&u1, &t1, dsa->q, ctx)) { 376 goto err; 377 } 378 379 /* V is now in u1. If the signature is correct, it will be 380 * equal to R. */ 381 *out_valid = BN_ucmp(&u1, sig->r) == 0; 382 ret = 1; 383 384err: 385 if (ret != 1) { 386 OPENSSL_PUT_ERROR(DSA, verify, ERR_R_BN_LIB); 387 } 388 if (ctx != NULL) { 389 BN_CTX_free(ctx); 390 } 391 BN_free(&u1); 392 BN_free(&u2); 393 BN_free(&t1); 394 395 return ret; 396} 397 398static int keygen(DSA *dsa) { 399 int ok = 0; 400 BN_CTX *ctx = NULL; 401 BIGNUM *pub_key = NULL, *priv_key = NULL; 402 BIGNUM prk; 403 404 ctx = BN_CTX_new(); 405 if (ctx == NULL) { 406 goto err; 407 } 408 409 priv_key = dsa->priv_key; 410 if (priv_key == NULL) { 411 priv_key = BN_new(); 412 if (priv_key == NULL) { 413 goto err; 414 } 415 } 416 417 do { 418 if (!BN_rand_range(priv_key, dsa->q)) { 419 goto err; 420 } 421 } while (BN_is_zero(priv_key)); 422 423 pub_key = dsa->pub_key; 424 if (pub_key == NULL) { 425 pub_key = BN_new(); 426 if (pub_key == NULL) { 427 goto err; 428 } 429 } 430 431 BN_init(&prk); 432 BN_with_flags(&prk, priv_key, BN_FLG_CONSTTIME); 433 434 if (!BN_mod_exp(pub_key, dsa->g, &prk, dsa->p, ctx)) { 435 goto err; 436 } 437 438 dsa->priv_key = priv_key; 439 dsa->pub_key = pub_key; 440 ok = 1; 441 442err: 443 if (pub_key != NULL && dsa->pub_key == NULL) { 444 BN_free(pub_key); 445 } 446 if (priv_key != NULL && dsa->priv_key == NULL) { 447 BN_free(priv_key); 448 } 449 if (ctx != NULL) { 450 BN_CTX_free(ctx); 451 } 452 453 return ok; 454} 455 456static int paramgen(DSA *ret, unsigned bits, const uint8_t *seed_in, 457 size_t seed_len, int *counter_ret, unsigned long *h_ret, 458 BN_GENCB *cb) { 459 int ok = 0; 460 unsigned char seed[SHA256_DIGEST_LENGTH]; 461 unsigned char md[SHA256_DIGEST_LENGTH]; 462 unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; 463 BIGNUM *r0, *W, *X, *c, *test; 464 BIGNUM *g = NULL, *q = NULL, *p = NULL; 465 BN_MONT_CTX *mont = NULL; 466 int k, n = 0, m = 0; 467 unsigned i; 468 int counter = 0; 469 int r = 0; 470 BN_CTX *ctx = NULL; 471 unsigned int h = 2; 472 unsigned qbits, qsize; 473 const EVP_MD *evpmd; 474 475 if (bits >= 2048) { 476 qbits = 256; 477 evpmd = EVP_sha256(); 478 } else { 479 qbits = 160; 480 evpmd = EVP_sha1(); 481 } 482 qsize = qbits / 8; 483 484 if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH && 485 qsize != SHA256_DIGEST_LENGTH) 486 /* invalid q size */ 487 return 0; 488 489 if (bits < 512) 490 bits = 512; 491 492 bits = (bits + 63) / 64 * 64; 493 494 /* NB: seed_len == 0 is special case: copy generated seed to 495 * seed_in if it is not NULL. */ 496 if (seed_len && (seed_len < (size_t)qsize)) 497 seed_in = NULL; /* seed buffer too small -- ignore */ 498 if (seed_len > (size_t)qsize) 499 seed_len = qsize; /* App. 2.2 of FIPS PUB 186 allows larger SEED, 500 * but our internal buffers are restricted to 160 bits*/ 501 if (seed_in != NULL) 502 memcpy(seed, seed_in, seed_len); 503 504 if ((ctx = BN_CTX_new()) == NULL) 505 goto err; 506 507 if ((mont = BN_MONT_CTX_new()) == NULL) 508 goto err; 509 510 BN_CTX_start(ctx); 511 r0 = BN_CTX_get(ctx); 512 g = BN_CTX_get(ctx); 513 W = BN_CTX_get(ctx); 514 q = BN_CTX_get(ctx); 515 X = BN_CTX_get(ctx); 516 c = BN_CTX_get(ctx); 517 p = BN_CTX_get(ctx); 518 test = BN_CTX_get(ctx); 519 520 if (!BN_lshift(test, BN_value_one(), bits - 1)) 521 goto err; 522 523 for (;;) { 524 for (;;) /* find q */ 525 { 526 int seed_is_random; 527 528 /* step 1 */ 529 if (!BN_GENCB_call(cb, 0, m++)) 530 goto err; 531 532 if (!seed_len) { 533 RAND_pseudo_bytes(seed, qsize); 534 seed_is_random = 1; 535 } else { 536 seed_is_random = 0; 537 seed_len = 0; /* use random seed if 'seed_in' turns out to be bad*/ 538 } 539 memcpy(buf, seed, qsize); 540 memcpy(buf2, seed, qsize); 541 /* precompute "SEED + 1" for step 7: */ 542 for (i = qsize - 1; i < qsize; i--) { 543 buf[i]++; 544 if (buf[i] != 0) 545 break; 546 } 547 548 /* step 2 */ 549 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) 550 goto err; 551 if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) 552 goto err; 553 for (i = 0; i < qsize; i++) 554 md[i] ^= buf2[i]; 555 556 /* step 3 */ 557 md[0] |= 0x80; 558 md[qsize - 1] |= 0x01; 559 if (!BN_bin2bn(md, qsize, q)) 560 goto err; 561 562 /* step 4 */ 563 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, seed_is_random, cb); 564 if (r > 0) 565 break; 566 if (r != 0) 567 goto err; 568 569 /* do a callback call */ 570 /* step 5 */ 571 } 572 573 if (!BN_GENCB_call(cb, 2, 0)) 574 goto err; 575 if (!BN_GENCB_call(cb, 3, 0)) 576 goto err; 577 578 /* step 6 */ 579 counter = 0; 580 /* "offset = 2" */ 581 582 n = (bits - 1) / 160; 583 584 for (;;) { 585 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) 586 goto err; 587 588 /* step 7 */ 589 BN_zero(W); 590 /* now 'buf' contains "SEED + offset - 1" */ 591 for (k = 0; k <= n; k++) { 592 /* obtain "SEED + offset + k" by incrementing: */ 593 for (i = qsize - 1; i < qsize; i--) { 594 buf[i]++; 595 if (buf[i] != 0) 596 break; 597 } 598 599 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) 600 goto err; 601 602 /* step 8 */ 603 if (!BN_bin2bn(md, qsize, r0)) 604 goto err; 605 if (!BN_lshift(r0, r0, (qsize << 3) * k)) 606 goto err; 607 if (!BN_add(W, W, r0)) 608 goto err; 609 } 610 611 /* more of step 8 */ 612 if (!BN_mask_bits(W, bits - 1)) 613 goto err; 614 if (!BN_copy(X, W)) 615 goto err; 616 if (!BN_add(X, X, test)) 617 goto err; 618 619 /* step 9 */ 620 if (!BN_lshift1(r0, q)) 621 goto err; 622 if (!BN_mod(c, X, r0, ctx)) 623 goto err; 624 if (!BN_sub(r0, c, BN_value_one())) 625 goto err; 626 if (!BN_sub(p, X, r0)) 627 goto err; 628 629 /* step 10 */ 630 if (BN_cmp(p, test) >= 0) { 631 /* step 11 */ 632 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 633 if (r > 0) 634 goto end; /* found it */ 635 if (r != 0) 636 goto err; 637 } 638 639 /* step 13 */ 640 counter++; 641 /* "offset = offset + n + 1" */ 642 643 /* step 14 */ 644 if (counter >= 4096) 645 break; 646 } 647 } 648end: 649 if (!BN_GENCB_call(cb, 2, 1)) 650 goto err; 651 652 /* We now need to generate g */ 653 /* Set r0=(p-1)/q */ 654 if (!BN_sub(test, p, BN_value_one())) 655 goto err; 656 if (!BN_div(r0, NULL, test, q, ctx)) 657 goto err; 658 659 if (!BN_set_word(test, h)) 660 goto err; 661 if (!BN_MONT_CTX_set(mont, p, ctx)) 662 goto err; 663 664 for (;;) { 665 /* g=test^r0%p */ 666 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) 667 goto err; 668 if (!BN_is_one(g)) 669 break; 670 if (!BN_add(test, test, BN_value_one())) 671 goto err; 672 h++; 673 } 674 675 if (!BN_GENCB_call(cb, 3, 1)) 676 goto err; 677 678 ok = 1; 679 680err: 681 if (ok) { 682 if (ret->p) 683 BN_free(ret->p); 684 if (ret->q) 685 BN_free(ret->q); 686 if (ret->g) 687 BN_free(ret->g); 688 ret->p = BN_dup(p); 689 ret->q = BN_dup(q); 690 ret->g = BN_dup(g); 691 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 692 ok = 0; 693 goto err; 694 } 695 if (counter_ret != NULL) 696 *counter_ret = counter; 697 if (h_ret != NULL) 698 *h_ret = h; 699 } 700 701 if (ctx) { 702 BN_CTX_end(ctx); 703 BN_CTX_free(ctx); 704 } 705 706 if (mont != NULL) 707 BN_MONT_CTX_free(mont); 708 709 return ok; 710} 711 712static int finish(DSA *dsa) { 713 BN_MONT_CTX_free(dsa->method_mont_p); 714 dsa->method_mont_p = NULL; 715 return 1; 716} 717 718const struct dsa_method DSA_default_method = { 719 { 720 0 /* references */, 721 1 /* is_static */, 722 }, 723 NULL /* app_data */, 724 725 NULL /* init */, 726 finish /* finish */, 727 728 sign, 729 sign_setup, 730 verify, 731 732 paramgen, 733 keygen, 734}; 735