1 /* 2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 /* 11 * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186, 12 * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB 13 * 180-1) 14 */ 15 #define xxxHASH EVP_sha1() 16 17 #include <openssl/opensslconf.h> 18 #include <stdio.h> 19 #include "internal/cryptlib.h" 20 #include <openssl/evp.h> 21 #include <openssl/bn.h> 22 #include <openssl/rand.h> 23 #include <openssl/sha.h> 24 #include "dsa_locl.h" 25 26 int DSA_generate_parameters_ex(DSA *ret, int bits, 27 const unsigned char *seed_in, int seed_len, 28 int *counter_ret, unsigned long *h_ret, 29 BN_GENCB *cb) 30 { 31 if (ret->meth->dsa_paramgen) 32 return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len, 33 counter_ret, h_ret, cb); 34 else { 35 const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1(); 36 size_t qbits = EVP_MD_size(evpmd) * 8; 37 38 return dsa_builtin_paramgen(ret, bits, qbits, evpmd, 39 seed_in, seed_len, NULL, counter_ret, 40 h_ret, cb); 41 } 42 } 43 44 int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, 45 const EVP_MD *evpmd, const unsigned char *seed_in, 46 size_t seed_len, unsigned char *seed_out, 47 int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) 48 { 49 int ok = 0; 50 unsigned char seed[SHA256_DIGEST_LENGTH]; 51 unsigned char md[SHA256_DIGEST_LENGTH]; 52 unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; 53 BIGNUM *r0, *W, *X, *c, *test; 54 BIGNUM *g = NULL, *q = NULL, *p = NULL; 55 BN_MONT_CTX *mont = NULL; 56 int i, k, n = 0, m = 0, qsize = qbits >> 3; 57 int counter = 0; 58 int r = 0; 59 BN_CTX *ctx = NULL; 60 unsigned int h = 2; 61 62 if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH && 63 qsize != SHA256_DIGEST_LENGTH) 64 /* invalid q size */ 65 return 0; 66 67 if (evpmd == NULL) 68 /* use SHA1 as default */ 69 evpmd = EVP_sha1(); 70 71 if (bits < 512) 72 bits = 512; 73 74 bits = (bits + 63) / 64 * 64; 75 76 if (seed_in != NULL) { 77 if (seed_len < (size_t)qsize) { 78 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL); 79 return 0; 80 } 81 if (seed_len > (size_t)qsize) { 82 /* Only consume as much seed as is expected. */ 83 seed_len = qsize; 84 } 85 memcpy(seed, seed_in, seed_len); 86 } 87 88 if ((mont = BN_MONT_CTX_new()) == NULL) 89 goto err; 90 91 if ((ctx = BN_CTX_new()) == NULL) 92 goto err; 93 94 BN_CTX_start(ctx); 95 96 r0 = BN_CTX_get(ctx); 97 g = BN_CTX_get(ctx); 98 W = BN_CTX_get(ctx); 99 q = BN_CTX_get(ctx); 100 X = BN_CTX_get(ctx); 101 c = BN_CTX_get(ctx); 102 p = BN_CTX_get(ctx); 103 test = BN_CTX_get(ctx); 104 105 if (test == NULL) 106 goto err; 107 108 if (!BN_lshift(test, BN_value_one(), bits - 1)) 109 goto err; 110 111 for (;;) { 112 for (;;) { /* find q */ 113 int use_random_seed = (seed_in == NULL); 114 115 /* step 1 */ 116 if (!BN_GENCB_call(cb, 0, m++)) 117 goto err; 118 119 if (use_random_seed) { 120 if (RAND_bytes(seed, qsize) <= 0) 121 goto err; 122 } else { 123 /* If we come back through, use random seed next time. */ 124 seed_in = NULL; 125 } 126 memcpy(buf, seed, qsize); 127 memcpy(buf2, seed, qsize); 128 /* precompute "SEED + 1" for step 7: */ 129 for (i = qsize - 1; i >= 0; i--) { 130 buf[i]++; 131 if (buf[i] != 0) 132 break; 133 } 134 135 /* step 2 */ 136 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) 137 goto err; 138 if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) 139 goto err; 140 for (i = 0; i < qsize; i++) 141 md[i] ^= buf2[i]; 142 143 /* step 3 */ 144 md[0] |= 0x80; 145 md[qsize - 1] |= 0x01; 146 if (!BN_bin2bn(md, qsize, q)) 147 goto err; 148 149 /* step 4 */ 150 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, 151 use_random_seed, cb); 152 if (r > 0) 153 break; 154 if (r != 0) 155 goto err; 156 157 /* do a callback call */ 158 /* step 5 */ 159 } 160 161 if (!BN_GENCB_call(cb, 2, 0)) 162 goto err; 163 if (!BN_GENCB_call(cb, 3, 0)) 164 goto err; 165 166 /* step 6 */ 167 counter = 0; 168 /* "offset = 2" */ 169 170 n = (bits - 1) / 160; 171 172 for (;;) { 173 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) 174 goto err; 175 176 /* step 7 */ 177 BN_zero(W); 178 /* now 'buf' contains "SEED + offset - 1" */ 179 for (k = 0; k <= n; k++) { 180 /* 181 * obtain "SEED + offset + k" by incrementing: 182 */ 183 for (i = qsize - 1; i >= 0; i--) { 184 buf[i]++; 185 if (buf[i] != 0) 186 break; 187 } 188 189 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) 190 goto err; 191 192 /* step 8 */ 193 if (!BN_bin2bn(md, qsize, r0)) 194 goto err; 195 if (!BN_lshift(r0, r0, (qsize << 3) * k)) 196 goto err; 197 if (!BN_add(W, W, r0)) 198 goto err; 199 } 200 201 /* more of step 8 */ 202 if (!BN_mask_bits(W, bits - 1)) 203 goto err; 204 if (!BN_copy(X, W)) 205 goto err; 206 if (!BN_add(X, X, test)) 207 goto err; 208 209 /* step 9 */ 210 if (!BN_lshift1(r0, q)) 211 goto err; 212 if (!BN_mod(c, X, r0, ctx)) 213 goto err; 214 if (!BN_sub(r0, c, BN_value_one())) 215 goto err; 216 if (!BN_sub(p, X, r0)) 217 goto err; 218 219 /* step 10 */ 220 if (BN_cmp(p, test) >= 0) { 221 /* step 11 */ 222 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 223 if (r > 0) 224 goto end; /* found it */ 225 if (r != 0) 226 goto err; 227 } 228 229 /* step 13 */ 230 counter++; 231 /* "offset = offset + n + 1" */ 232 233 /* step 14 */ 234 if (counter >= 4096) 235 break; 236 } 237 } 238 end: 239 if (!BN_GENCB_call(cb, 2, 1)) 240 goto err; 241 242 /* We now need to generate g */ 243 /* Set r0=(p-1)/q */ 244 if (!BN_sub(test, p, BN_value_one())) 245 goto err; 246 if (!BN_div(r0, NULL, test, q, ctx)) 247 goto err; 248 249 if (!BN_set_word(test, h)) 250 goto err; 251 if (!BN_MONT_CTX_set(mont, p, ctx)) 252 goto err; 253 254 for (;;) { 255 /* g=test^r0%p */ 256 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) 257 goto err; 258 if (!BN_is_one(g)) 259 break; 260 if (!BN_add(test, test, BN_value_one())) 261 goto err; 262 h++; 263 } 264 265 if (!BN_GENCB_call(cb, 3, 1)) 266 goto err; 267 268 ok = 1; 269 err: 270 if (ok) { 271 BN_free(ret->p); 272 BN_free(ret->q); 273 BN_free(ret->g); 274 ret->p = BN_dup(p); 275 ret->q = BN_dup(q); 276 ret->g = BN_dup(g); 277 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 278 ok = 0; 279 goto err; 280 } 281 if (counter_ret != NULL) 282 *counter_ret = counter; 283 if (h_ret != NULL) 284 *h_ret = h; 285 if (seed_out) 286 memcpy(seed_out, seed, qsize); 287 } 288 if (ctx) 289 BN_CTX_end(ctx); 290 BN_CTX_free(ctx); 291 BN_MONT_CTX_free(mont); 292 return ok; 293 } 294 295 /* 296 * This is a parameter generation algorithm for the DSA2 algorithm as 297 * described in FIPS 186-3. 298 */ 299 300 int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, 301 const EVP_MD *evpmd, const unsigned char *seed_in, 302 size_t seed_len, int idx, unsigned char *seed_out, 303 int *counter_ret, unsigned long *h_ret, 304 BN_GENCB *cb) 305 { 306 int ok = -1; 307 unsigned char *seed = NULL, *seed_tmp = NULL; 308 unsigned char md[EVP_MAX_MD_SIZE]; 309 int mdsize; 310 BIGNUM *r0, *W, *X, *c, *test; 311 BIGNUM *g = NULL, *q = NULL, *p = NULL; 312 BN_MONT_CTX *mont = NULL; 313 int i, k, n = 0, m = 0, qsize = N >> 3; 314 int counter = 0; 315 int r = 0; 316 BN_CTX *ctx = NULL; 317 EVP_MD_CTX *mctx = EVP_MD_CTX_new(); 318 unsigned int h = 2; 319 320 if (mctx == NULL) 321 goto err; 322 323 if (evpmd == NULL) { 324 if (N == 160) 325 evpmd = EVP_sha1(); 326 else if (N == 224) 327 evpmd = EVP_sha224(); 328 else 329 evpmd = EVP_sha256(); 330 } 331 332 mdsize = EVP_MD_size(evpmd); 333 /* If unverifiable g generation only don't need seed */ 334 if (!ret->p || !ret->q || idx >= 0) { 335 if (seed_len == 0) 336 seed_len = mdsize; 337 338 seed = OPENSSL_malloc(seed_len); 339 340 if (seed_out) 341 seed_tmp = seed_out; 342 else 343 seed_tmp = OPENSSL_malloc(seed_len); 344 345 if (seed == NULL || seed_tmp == NULL) 346 goto err; 347 348 if (seed_in) 349 memcpy(seed, seed_in, seed_len); 350 351 } 352 353 if ((ctx = BN_CTX_new()) == NULL) 354 goto err; 355 356 if ((mont = BN_MONT_CTX_new()) == NULL) 357 goto err; 358 359 BN_CTX_start(ctx); 360 r0 = BN_CTX_get(ctx); 361 g = BN_CTX_get(ctx); 362 W = BN_CTX_get(ctx); 363 X = BN_CTX_get(ctx); 364 c = BN_CTX_get(ctx); 365 test = BN_CTX_get(ctx); 366 if (test == NULL) 367 goto err; 368 369 /* if p, q already supplied generate g only */ 370 if (ret->p && ret->q) { 371 p = ret->p; 372 q = ret->q; 373 if (idx >= 0) 374 memcpy(seed_tmp, seed, seed_len); 375 goto g_only; 376 } else { 377 p = BN_CTX_get(ctx); 378 q = BN_CTX_get(ctx); 379 if (q == NULL) 380 goto err; 381 } 382 383 if (!BN_lshift(test, BN_value_one(), L - 1)) 384 goto err; 385 for (;;) { 386 for (;;) { /* find q */ 387 unsigned char *pmd; 388 /* step 1 */ 389 if (!BN_GENCB_call(cb, 0, m++)) 390 goto err; 391 392 if (!seed_in) { 393 if (RAND_bytes(seed, seed_len) <= 0) 394 goto err; 395 } 396 /* step 2 */ 397 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) 398 goto err; 399 /* Take least significant bits of md */ 400 if (mdsize > qsize) 401 pmd = md + mdsize - qsize; 402 else 403 pmd = md; 404 405 if (mdsize < qsize) 406 memset(md + mdsize, 0, qsize - mdsize); 407 408 /* step 3 */ 409 pmd[0] |= 0x80; 410 pmd[qsize - 1] |= 0x01; 411 if (!BN_bin2bn(pmd, qsize, q)) 412 goto err; 413 414 /* step 4 */ 415 r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, 416 seed_in ? 1 : 0, cb); 417 if (r > 0) 418 break; 419 if (r != 0) 420 goto err; 421 /* Provided seed didn't produce a prime: error */ 422 if (seed_in) { 423 ok = 0; 424 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME); 425 goto err; 426 } 427 428 /* do a callback call */ 429 /* step 5 */ 430 } 431 /* Copy seed to seed_out before we mess with it */ 432 if (seed_out) 433 memcpy(seed_out, seed, seed_len); 434 435 if (!BN_GENCB_call(cb, 2, 0)) 436 goto err; 437 if (!BN_GENCB_call(cb, 3, 0)) 438 goto err; 439 440 /* step 6 */ 441 counter = 0; 442 /* "offset = 1" */ 443 444 n = (L - 1) / (mdsize << 3); 445 446 for (;;) { 447 if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) 448 goto err; 449 450 /* step 7 */ 451 BN_zero(W); 452 /* now 'buf' contains "SEED + offset - 1" */ 453 for (k = 0; k <= n; k++) { 454 /* 455 * obtain "SEED + offset + k" by incrementing: 456 */ 457 for (i = seed_len - 1; i >= 0; i--) { 458 seed[i]++; 459 if (seed[i] != 0) 460 break; 461 } 462 463 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) 464 goto err; 465 466 /* step 8 */ 467 if (!BN_bin2bn(md, mdsize, r0)) 468 goto err; 469 if (!BN_lshift(r0, r0, (mdsize << 3) * k)) 470 goto err; 471 if (!BN_add(W, W, r0)) 472 goto err; 473 } 474 475 /* more of step 8 */ 476 if (!BN_mask_bits(W, L - 1)) 477 goto err; 478 if (!BN_copy(X, W)) 479 goto err; 480 if (!BN_add(X, X, test)) 481 goto err; 482 483 /* step 9 */ 484 if (!BN_lshift1(r0, q)) 485 goto err; 486 if (!BN_mod(c, X, r0, ctx)) 487 goto err; 488 if (!BN_sub(r0, c, BN_value_one())) 489 goto err; 490 if (!BN_sub(p, X, r0)) 491 goto err; 492 493 /* step 10 */ 494 if (BN_cmp(p, test) >= 0) { 495 /* step 11 */ 496 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 497 if (r > 0) 498 goto end; /* found it */ 499 if (r != 0) 500 goto err; 501 } 502 503 /* step 13 */ 504 counter++; 505 /* "offset = offset + n + 1" */ 506 507 /* step 14 */ 508 if (counter >= (int)(4 * L)) 509 break; 510 } 511 if (seed_in) { 512 ok = 0; 513 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); 514 goto err; 515 } 516 } 517 end: 518 if (!BN_GENCB_call(cb, 2, 1)) 519 goto err; 520 521 g_only: 522 523 /* We now need to generate g */ 524 /* Set r0=(p-1)/q */ 525 if (!BN_sub(test, p, BN_value_one())) 526 goto err; 527 if (!BN_div(r0, NULL, test, q, ctx)) 528 goto err; 529 530 if (idx < 0) { 531 if (!BN_set_word(test, h)) 532 goto err; 533 } else 534 h = 1; 535 if (!BN_MONT_CTX_set(mont, p, ctx)) 536 goto err; 537 538 for (;;) { 539 static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e }; 540 if (idx >= 0) { 541 md[0] = idx & 0xff; 542 md[1] = (h >> 8) & 0xff; 543 md[2] = h & 0xff; 544 if (!EVP_DigestInit_ex(mctx, evpmd, NULL)) 545 goto err; 546 if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len)) 547 goto err; 548 if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen))) 549 goto err; 550 if (!EVP_DigestUpdate(mctx, md, 3)) 551 goto err; 552 if (!EVP_DigestFinal_ex(mctx, md, NULL)) 553 goto err; 554 if (!BN_bin2bn(md, mdsize, test)) 555 goto err; 556 } 557 /* g=test^r0%p */ 558 if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) 559 goto err; 560 if (!BN_is_one(g)) 561 break; 562 if (idx < 0 && !BN_add(test, test, BN_value_one())) 563 goto err; 564 h++; 565 if (idx >= 0 && h > 0xffff) 566 goto err; 567 } 568 569 if (!BN_GENCB_call(cb, 3, 1)) 570 goto err; 571 572 ok = 1; 573 err: 574 if (ok == 1) { 575 if (p != ret->p) { 576 BN_free(ret->p); 577 ret->p = BN_dup(p); 578 } 579 if (q != ret->q) { 580 BN_free(ret->q); 581 ret->q = BN_dup(q); 582 } 583 BN_free(ret->g); 584 ret->g = BN_dup(g); 585 if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 586 ok = -1; 587 goto err; 588 } 589 if (counter_ret != NULL) 590 *counter_ret = counter; 591 if (h_ret != NULL) 592 *h_ret = h; 593 } 594 OPENSSL_free(seed); 595 if (seed_out != seed_tmp) 596 OPENSSL_free(seed_tmp); 597 if (ctx) 598 BN_CTX_end(ctx); 599 BN_CTX_free(ctx); 600 BN_MONT_CTX_free(mont); 601 EVP_MD_CTX_free(mctx); 602 return ok; 603 } 604