1 /* 2 * Copyright 2019-2023 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (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 * For the prime check.. 12 * FIPS 186-4 Section C.3 Table C.1 13 * Returns the minimum number of Miller Rabin iterations for a L,N pair 14 * (where L = len(p), N = len(q)) 15 * L N Min 16 * 1024 160 40 17 * 2048 224 56 18 * 2048 256 56 19 * 3072 256 64 20 * 21 * BN_check_prime() uses: 22 * 64 iterations for L <= 2048 OR 23 * 128 iterations for L > 2048 24 * So this satisfies the requirement. 25 */ 26 27 #include <string.h> /* memset */ 28 #include <openssl/sha.h> /* SHA_DIGEST_LENGTH */ 29 #include <openssl/rand.h> 30 #include <openssl/err.h> 31 #include <openssl/dherr.h> 32 #include <openssl/dsaerr.h> 33 #include "crypto/bn.h" 34 #include "internal/ffc.h" 35 36 /* 37 * Verify that the passed in L, N pair for DH or DSA is valid. 38 * Returns 0 if invalid, otherwise it returns the security strength. 39 */ 40 41 #ifdef FIPS_MODULE 42 static int ffc_validate_LN(size_t L, size_t N, int type, int verify) 43 { 44 if (type == FFC_PARAM_TYPE_DH) { 45 /* Valid DH L,N parameters from SP800-56Ar3 5.5.1 Table 1 */ 46 if (L == 2048 && (N == 224 || N == 256)) 47 return 112; 48 # ifndef OPENSSL_NO_DH 49 ERR_raise(ERR_LIB_DH, DH_R_BAD_FFC_PARAMETERS); 50 # endif 51 } else if (type == FFC_PARAM_TYPE_DSA) { 52 /* Valid DSA L,N parameters from FIPS 186-4 Section 4.2 */ 53 /* In fips mode 1024/160 can only be used for verification */ 54 if (verify && L == 1024 && N == 160) 55 return 80; 56 if (L == 2048 && (N == 224 || N == 256)) 57 return 112; 58 if (L == 3072 && N == 256) 59 return 128; 60 # ifndef OPENSSL_NO_DSA 61 ERR_raise(ERR_LIB_DSA, DSA_R_BAD_FFC_PARAMETERS); 62 # endif 63 } 64 return 0; 65 } 66 #else 67 static int ffc_validate_LN(size_t L, size_t N, int type, int verify) 68 { 69 if (type == FFC_PARAM_TYPE_DH) { 70 /* Allow legacy 1024/160 in non fips mode */ 71 if (L == 1024 && N == 160) 72 return 80; 73 /* Valid DH L,N parameters from SP800-56Ar3 5.5.1 Table 1 */ 74 if (L == 2048 && (N == 224 || N == 256)) 75 return 112; 76 # ifndef OPENSSL_NO_DH 77 ERR_raise(ERR_LIB_DH, DH_R_BAD_FFC_PARAMETERS); 78 # endif 79 } else if (type == FFC_PARAM_TYPE_DSA) { 80 if (L >= 3072 && N >= 256) 81 return 128; 82 if (L >= 2048 && N >= 224) 83 return 112; 84 if (L >= 1024 && N >= 160) 85 return 80; 86 # ifndef OPENSSL_NO_DSA 87 ERR_raise(ERR_LIB_DSA, DSA_R_BAD_FFC_PARAMETERS); 88 # endif 89 } 90 return 0; 91 } 92 #endif /* FIPS_MODULE */ 93 94 /* FIPS186-4 A.2.1 Unverifiable Generation of Generator g */ 95 static int generate_unverifiable_g(BN_CTX *ctx, BN_MONT_CTX *mont, BIGNUM *g, 96 BIGNUM *hbn, const BIGNUM *p, 97 const BIGNUM *e,const BIGNUM *pm1, 98 int *hret) 99 { 100 int h = 2; 101 102 /* Step (2): choose h (where 1 < h)*/ 103 if (!BN_set_word(hbn, h)) 104 return 0; 105 106 for (;;) { 107 /* Step (3): g = h^e % p */ 108 if (!BN_mod_exp_mont(g, hbn, e, p, ctx, mont)) 109 return 0; 110 /* Step (4): Finish if g > 1 */ 111 if (BN_cmp(g, BN_value_one()) > 0) 112 break; 113 114 /* Step (2) Choose any h in the range 1 < h < (p-1) */ 115 if (!BN_add_word(hbn, 1) || BN_cmp(hbn, pm1) >= 0) 116 return 0; 117 ++h; 118 } 119 *hret = h; 120 return 1; 121 } 122 123 /* 124 * FIPS186-4 A.2 Generation of canonical generator g. 125 * 126 * It requires the following values as input: 127 * 'evpmd' digest, 'p' prime, 'e' cofactor, gindex and seed. 128 * tmp is a passed in temporary BIGNUM. 129 * mont is used in a BN_mod_exp_mont() with a modulus of p. 130 * Returns a value in g. 131 */ 132 static int generate_canonical_g(BN_CTX *ctx, BN_MONT_CTX *mont, 133 const EVP_MD *evpmd, BIGNUM *g, BIGNUM *tmp, 134 const BIGNUM *p, const BIGNUM *e, 135 int gindex, unsigned char *seed, size_t seedlen) 136 { 137 int ret = 0; 138 int counter = 1; 139 unsigned char md[EVP_MAX_MD_SIZE]; 140 EVP_MD_CTX *mctx = NULL; 141 int mdsize; 142 143 mdsize = EVP_MD_get_size(evpmd); 144 if (mdsize <= 0) 145 return 0; 146 147 mctx = EVP_MD_CTX_new(); 148 if (mctx == NULL) 149 return 0; 150 151 /* 152 * A.2.3 Step (4) & (5) 153 * A.2.4 Step (6) & (7) 154 * counter = 0; counter += 1 155 */ 156 for (counter = 1; counter <= 0xFFFF; ++counter) { 157 /* 158 * A.2.3 Step (7) & (8) & (9) 159 * A.2.4 Step (9) & (10) & (11) 160 * W = Hash(seed || "ggen" || index || counter) 161 * g = W^e % p 162 */ 163 static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e }; 164 165 md[0] = (unsigned char)(gindex & 0xff); 166 md[1] = (unsigned char)((counter >> 8) & 0xff); 167 md[2] = (unsigned char)(counter & 0xff); 168 if (!EVP_DigestInit_ex(mctx, evpmd, NULL) 169 || !EVP_DigestUpdate(mctx, seed, seedlen) 170 || !EVP_DigestUpdate(mctx, ggen, sizeof(ggen)) 171 || !EVP_DigestUpdate(mctx, md, 3) 172 || !EVP_DigestFinal_ex(mctx, md, NULL) 173 || (BN_bin2bn(md, mdsize, tmp) == NULL) 174 || !BN_mod_exp_mont(g, tmp, e, p, ctx, mont)) 175 break; /* exit on failure */ 176 /* 177 * A.2.3 Step (10) 178 * A.2.4 Step (12) 179 * Found a value for g if (g >= 2) 180 */ 181 if (BN_cmp(g, BN_value_one()) > 0) { 182 ret = 1; 183 break; /* found g */ 184 } 185 } 186 EVP_MD_CTX_free(mctx); 187 return ret; 188 } 189 190 /* Generation of p is the same for FIPS 186-4 & FIPS 186-2 */ 191 static int generate_p(BN_CTX *ctx, const EVP_MD *evpmd, int max_counter, int n, 192 unsigned char *buf, size_t buf_len, const BIGNUM *q, 193 BIGNUM *p, int L, BN_GENCB *cb, int *counter, 194 int *res) 195 { 196 int ret = -1; 197 int i, j, k, r; 198 unsigned char md[EVP_MAX_MD_SIZE]; 199 int mdsize; 200 BIGNUM *W, *X, *tmp, *c, *test; 201 202 BN_CTX_start(ctx); 203 W = BN_CTX_get(ctx); 204 X = BN_CTX_get(ctx); 205 c = BN_CTX_get(ctx); 206 test = BN_CTX_get(ctx); 207 tmp = BN_CTX_get(ctx); 208 if (tmp == NULL) 209 goto err; 210 211 if (!BN_lshift(test, BN_value_one(), L - 1)) 212 goto err; 213 214 mdsize = EVP_MD_get_size(evpmd); 215 if (mdsize <= 0) 216 goto err; 217 218 /* A.1.1.2 Step (10) AND 219 * A.1.1.2 Step (12) 220 * offset = 1 (this is handled below) 221 */ 222 /* 223 * A.1.1.2 Step (11) AND 224 * A.1.1.3 Step (13) 225 */ 226 for (i = 0; i <= max_counter; i++) { 227 if ((i != 0) && !BN_GENCB_call(cb, 0, i)) 228 goto err; 229 230 BN_zero(W); 231 /* seed_tmp buffer contains "seed + offset - 1" */ 232 for (j = 0; j <= n; j++) { 233 /* obtain "seed + offset + j" by incrementing by 1: */ 234 for (k = (int)buf_len - 1; k >= 0; k--) { 235 buf[k]++; 236 if (buf[k] != 0) 237 break; 238 } 239 /* 240 * A.1.1.2 Step (11.1) AND 241 * A.1.1.3 Step (13.1) 242 * tmp = V(j) = Hash((seed + offset + j) % 2^seedlen) 243 */ 244 if (!EVP_Digest(buf, buf_len, md, NULL, evpmd, NULL) 245 || (BN_bin2bn(md, mdsize, tmp) == NULL) 246 /* 247 * A.1.1.2 Step (11.2) 248 * A.1.1.3 Step (13.2) 249 * W += V(j) * 2^(outlen * j) 250 */ 251 || !BN_lshift(tmp, tmp, (mdsize << 3) * j) 252 || !BN_add(W, W, tmp)) 253 goto err; 254 } 255 256 /* 257 * A.1.1.2 Step (11.3) AND 258 * A.1.1.3 Step (13.3) 259 * X = W + 2^(L-1) where W < 2^(L-1) 260 */ 261 if (!BN_mask_bits(W, L - 1) 262 || !BN_copy(X, W) 263 || !BN_add(X, X, test) 264 /* 265 * A.1.1.2 Step (11.4) AND 266 * A.1.1.3 Step (13.4) 267 * c = X mod 2q 268 */ 269 || !BN_lshift1(tmp, q) 270 || !BN_mod(c, X, tmp, ctx) 271 /* 272 * A.1.1.2 Step (11.5) AND 273 * A.1.1.3 Step (13.5) 274 * p = X - (c - 1) 275 */ 276 || !BN_sub(tmp, c, BN_value_one()) 277 || !BN_sub(p, X, tmp)) 278 goto err; 279 280 /* 281 * A.1.1.2 Step (11.6) AND 282 * A.1.1.3 Step (13.6) 283 * if (p < 2 ^ (L-1)) continue 284 * This makes sure the top bit is set. 285 */ 286 if (BN_cmp(p, test) >= 0) { 287 /* 288 * A.1.1.2 Step (11.7) AND 289 * A.1.1.3 Step (13.7) 290 * Test if p is prime 291 * (This also makes sure the bottom bit is set) 292 */ 293 r = BN_check_prime(p, ctx, cb); 294 /* A.1.1.2 Step (11.8) : Return if p is prime */ 295 if (r > 0) { 296 *counter = i; 297 ret = 1; /* return success */ 298 goto err; 299 } 300 if (r != 0) 301 goto err; 302 } 303 /* Step (11.9) : offset = offset + n + 1 is done auto-magically */ 304 } 305 /* No prime P found */ 306 ret = 0; 307 *res |= FFC_CHECK_P_NOT_PRIME; 308 err: 309 BN_CTX_end(ctx); 310 return ret; 311 } 312 313 static int generate_q_fips186_4(BN_CTX *ctx, BIGNUM *q, const EVP_MD *evpmd, 314 int qsize, unsigned char *seed, size_t seedlen, 315 int generate_seed, int *retm, int *res, 316 BN_GENCB *cb) 317 { 318 int ret = 0, r; 319 int m = *retm; 320 unsigned char md[EVP_MAX_MD_SIZE]; 321 int mdsize = EVP_MD_get_size(evpmd); 322 unsigned char *pmd; 323 OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); 324 325 /* find q */ 326 for (;;) { 327 if(!BN_GENCB_call(cb, 0, m++)) 328 goto err; 329 330 /* A.1.1.2 Step (5) : generate seed with size seed_len */ 331 if (generate_seed 332 && RAND_bytes_ex(libctx, seed, seedlen, 0) <= 0) 333 goto err; 334 /* 335 * A.1.1.2 Step (6) AND 336 * A.1.1.3 Step (7) 337 * U = Hash(seed) % (2^(N-1)) 338 */ 339 if (!EVP_Digest(seed, seedlen, md, NULL, evpmd, NULL)) 340 goto err; 341 /* Take least significant bits of md */ 342 if (mdsize > qsize) 343 pmd = md + mdsize - qsize; 344 else 345 pmd = md; 346 if (mdsize < qsize) 347 memset(md + mdsize, 0, qsize - mdsize); 348 349 /* 350 * A.1.1.2 Step (7) AND 351 * A.1.1.3 Step (8) 352 * q = U + 2^(N-1) + (1 - U %2) (This sets top and bottom bits) 353 */ 354 pmd[0] |= 0x80; 355 pmd[qsize-1] |= 0x01; 356 if (!BN_bin2bn(pmd, qsize, q)) 357 goto err; 358 359 /* 360 * A.1.1.2 Step (8) AND 361 * A.1.1.3 Step (9) 362 * Test if q is prime 363 */ 364 r = BN_check_prime(q, ctx, cb); 365 if (r > 0) { 366 ret = 1; 367 goto err; 368 } 369 /* 370 * A.1.1.3 Step (9) : If the provided seed didn't produce a prime q 371 * return an error. 372 */ 373 if (!generate_seed) { 374 *res |= FFC_CHECK_Q_NOT_PRIME; 375 goto err; 376 } 377 if (r != 0) 378 goto err; 379 /* A.1.1.2 Step (9) : if q is not prime, try another q */ 380 } 381 err: 382 *retm = m; 383 return ret; 384 } 385 386 static int generate_q_fips186_2(BN_CTX *ctx, BIGNUM *q, const EVP_MD *evpmd, 387 unsigned char *buf, unsigned char *seed, 388 size_t qsize, int generate_seed, int *retm, 389 int *res, BN_GENCB *cb) 390 { 391 unsigned char buf2[EVP_MAX_MD_SIZE]; 392 unsigned char md[EVP_MAX_MD_SIZE]; 393 int i, r, ret = 0, m = *retm; 394 OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); 395 396 /* find q */ 397 for (;;) { 398 /* step 1 */ 399 if (!BN_GENCB_call(cb, 0, m++)) 400 goto err; 401 402 if (generate_seed && RAND_bytes_ex(libctx, seed, qsize, 0) <= 0) 403 goto err; 404 405 memcpy(buf, seed, qsize); 406 memcpy(buf2, seed, qsize); 407 408 /* precompute "SEED + 1" for step 7: */ 409 for (i = (int)qsize - 1; i >= 0; i--) { 410 buf[i]++; 411 if (buf[i] != 0) 412 break; 413 } 414 415 /* step 2 */ 416 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) 417 goto err; 418 if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) 419 goto err; 420 for (i = 0; i < (int)qsize; i++) 421 md[i] ^= buf2[i]; 422 423 /* step 3 */ 424 md[0] |= 0x80; 425 md[qsize - 1] |= 0x01; 426 if (!BN_bin2bn(md, (int)qsize, q)) 427 goto err; 428 429 /* step 4 */ 430 r = BN_check_prime(q, ctx, cb); 431 if (r > 0) { 432 /* Found a prime */ 433 ret = 1; 434 goto err; 435 } 436 if (r != 0) 437 goto err; /* Exit if error */ 438 /* Try another iteration if it wasnt prime - was in old code.. */ 439 generate_seed = 1; 440 } 441 err: 442 *retm = m; 443 return ret; 444 } 445 446 static const char *default_mdname(size_t N) 447 { 448 if (N == 160) 449 return "SHA1"; 450 else if (N == 224) 451 return "SHA-224"; 452 else if (N == 256) 453 return "SHA-256"; 454 return NULL; 455 } 456 457 /* 458 * FIPS 186-4 FFC parameter generation (as defined in Appendix A). 459 * The same code is used for validation (when validate_flags != 0) 460 * 461 * The primes p & q are generated/validated using: 462 * A.1.1.2 Generation of probable primes p & q using approved hash. 463 * A.1.1.3 Validation of generated probable primes 464 * 465 * Generator 'g' has 2 types in FIPS 186-4: 466 * (1) A.2.1 unverifiable generation of generator g. 467 * A.2.2 Assurance of the validity of unverifiable generator g. 468 * (2) A.2.3 Verifiable Canonical Generation of the generator g. 469 * A.2.4 Validation for Canonical Generation of the generator g. 470 * 471 * Notes: 472 * (1) is only a partial validation of g, The validation of (2) requires 473 * the seed and index used during generation as input. 474 * 475 * params: used to pass in values for generation and validation. 476 * params->md: is the digest to use, If this value is NULL, then the digest is 477 * chosen using the value of N. 478 * params->flags: 479 * For validation one of: 480 * -FFC_PARAM_FLAG_VALIDATE_PQ 481 * -FFC_PARAM_FLAG_VALIDATE_G 482 * -FFC_PARAM_FLAG_VALIDATE_PQG 483 * For generation of p & q: 484 * - This is skipped if p & q are passed in. 485 * - If the seed is passed in then generation of p & q uses this seed (and if 486 * this fails an error will occur). 487 * - Otherwise the seed is generated, and values of p & q are generated and 488 * the value of seed and counter are optionally returned. 489 * For the generation of g (after the generation of p, q): 490 * - If the seed has been generated or passed in and a valid gindex is passed 491 * in then canonical generation of g is used otherwise unverifiable 492 * generation of g is chosen. 493 * For validation of p & q: 494 * - p, q, and the seed and counter used for generation must be passed in. 495 * For validation of g: 496 * - For a partial validation : p, q and g are required. 497 * - For a canonical validation : the gindex and seed used for generation are 498 * also required. 499 * mode: The mode - either FFC_PARAM_MODE_GENERATE or FFC_PARAM_MODE_VERIFY. 500 * type: The key type - FFC_PARAM_TYPE_DSA or FFC_PARAM_TYPE_DH. 501 * L: is the size of the prime p in bits (e.g 2048) 502 * N: is the size of the prime q in bits (e.g 256) 503 * res: A returned failure reason (One of FFC_CHECK_XXXX), 504 * or 0 for general failures. 505 * cb: A callback (can be NULL) that is called during different phases 506 * 507 * Returns: 508 * - FFC_PARAM_RET_STATUS_FAILED: if there was an error, or validation failed. 509 * - FFC_PARAM_RET_STATUS_SUCCESS if the generation or validation succeeded. 510 * - FFC_PARAM_RET_STATUS_UNVERIFIABLE_G if the validation of G succeeded, 511 * but G is unverifiable. 512 */ 513 int ossl_ffc_params_FIPS186_4_gen_verify(OSSL_LIB_CTX *libctx, 514 FFC_PARAMS *params, int mode, int type, 515 size_t L, size_t N, int *res, 516 BN_GENCB *cb) 517 { 518 int ok = FFC_PARAM_RET_STATUS_FAILED; 519 unsigned char *seed = NULL, *seed_tmp = NULL; 520 int mdsize, counter = 0, pcounter = 0, r = 0; 521 size_t seedlen = 0; 522 BIGNUM *tmp, *pm1, *e, *test; 523 BIGNUM *g = NULL, *q = NULL, *p = NULL; 524 BN_MONT_CTX *mont = NULL; 525 int n = 0, m = 0, qsize; 526 int canonical_g = 0, hret = 0; 527 BN_CTX *ctx = NULL; 528 EVP_MD_CTX *mctx = NULL; 529 EVP_MD *md = NULL; 530 int verify = (mode == FFC_PARAM_MODE_VERIFY); 531 unsigned int flags = verify ? params->flags : 0; 532 const char *def_name; 533 534 *res = 0; 535 536 if (params->mdname != NULL) { 537 md = EVP_MD_fetch(libctx, params->mdname, params->mdprops); 538 } else { 539 if (N == 0) 540 N = (L >= 2048 ? SHA256_DIGEST_LENGTH : SHA_DIGEST_LENGTH) * 8; 541 def_name = default_mdname(N); 542 if (def_name == NULL) { 543 *res = FFC_CHECK_INVALID_Q_VALUE; 544 goto err; 545 } 546 md = EVP_MD_fetch(libctx, def_name, params->mdprops); 547 } 548 if (md == NULL) 549 goto err; 550 mdsize = EVP_MD_get_size(md); 551 if (mdsize <= 0) 552 goto err; 553 554 if (N == 0) 555 N = mdsize * 8; 556 qsize = N >> 3; 557 558 /* 559 * A.1.1.2 Step (1) AND 560 * A.1.1.3 Step (3) 561 * Check that the L,N pair is an acceptable pair. 562 */ 563 if (L <= N || !ffc_validate_LN(L, N, type, verify)) { 564 *res = FFC_CHECK_BAD_LN_PAIR; 565 goto err; 566 } 567 568 mctx = EVP_MD_CTX_new(); 569 if (mctx == NULL) 570 goto err; 571 572 if ((ctx = BN_CTX_new_ex(libctx)) == NULL) 573 goto err; 574 575 BN_CTX_start(ctx); 576 g = BN_CTX_get(ctx); 577 pm1 = BN_CTX_get(ctx); 578 e = BN_CTX_get(ctx); 579 test = BN_CTX_get(ctx); 580 tmp = BN_CTX_get(ctx); 581 if (tmp == NULL) 582 goto err; 583 584 seedlen = params->seedlen; 585 if (seedlen == 0) 586 seedlen = (size_t)mdsize; 587 /* If the seed was passed in - use this value as the seed */ 588 if (params->seed != NULL) 589 seed = params->seed; 590 591 if (!verify) { 592 /* For generation: p & q must both be NULL or NON-NULL */ 593 if ((params->p == NULL) != (params->q == NULL)) { 594 *res = FFC_CHECK_INVALID_PQ; 595 goto err; 596 } 597 } else { 598 /* Validation of p,q requires seed and counter to be valid */ 599 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) != 0) { 600 if (seed == NULL || params->pcounter < 0) { 601 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER; 602 goto err; 603 } 604 } 605 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) { 606 /* validation of g also requires g to be set */ 607 if (params->g == NULL) { 608 *res = FFC_CHECK_INVALID_G; 609 goto err; 610 } 611 } 612 } 613 614 /* 615 * If p & q are passed in and 616 * validate_flags = 0 then skip the generation of PQ. 617 * validate_flags = VALIDATE_G then also skip the validation of PQ. 618 */ 619 if (params->p != NULL && ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) == 0)) { 620 /* p and q already exists so only generate g */ 621 p = params->p; 622 q = params->q; 623 goto g_only; 624 /* otherwise fall thru to validate p & q */ 625 } 626 627 /* p & q will be used for generation and validation */ 628 p = BN_CTX_get(ctx); 629 q = BN_CTX_get(ctx); 630 if (q == NULL) 631 goto err; 632 633 /* 634 * A.1.1.2 Step (2) AND 635 * A.1.1.3 Step (6) 636 * Return invalid if seedlen < N 637 */ 638 if ((seedlen * 8) < N) { 639 *res = FFC_CHECK_INVALID_SEED_SIZE; 640 goto err; 641 } 642 643 seed_tmp = OPENSSL_malloc(seedlen); 644 if (seed_tmp == NULL) 645 goto err; 646 647 if (seed == NULL) { 648 /* Validation requires the seed to be supplied */ 649 if (verify) { 650 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER; 651 goto err; 652 } 653 /* if the seed is not supplied then alloc a seed buffer */ 654 seed = OPENSSL_malloc(seedlen); 655 if (seed == NULL) 656 goto err; 657 } 658 659 /* A.1.1.2 Step (11): max loop count = 4L - 1 */ 660 counter = 4 * L - 1; 661 /* Validation requires the counter to be supplied */ 662 if (verify) { 663 /* A.1.1.3 Step (4) : if (counter > (4L -1)) return INVALID */ 664 if (params->pcounter > counter) { 665 *res = FFC_CHECK_INVALID_COUNTER; 666 goto err; 667 } 668 counter = params->pcounter; 669 } 670 671 /* 672 * A.1.1.2 Step (3) AND 673 * A.1.1.3 Step (10) 674 * n = floor(L / hash_outlen) - 1 675 */ 676 n = (L - 1 ) / (mdsize << 3); 677 678 /* Calculate 2^(L-1): Used in step A.1.1.2 Step (11.3) */ 679 if (!BN_lshift(test, BN_value_one(), L - 1)) 680 goto err; 681 682 for (;;) { 683 if (!generate_q_fips186_4(ctx, q, md, qsize, seed, seedlen, 684 seed != params->seed, &m, res, cb)) 685 goto err; 686 /* A.1.1.3 Step (9): Verify that q matches the expected value */ 687 if (verify && (BN_cmp(q, params->q) != 0)) { 688 *res = FFC_CHECK_Q_MISMATCH; 689 goto err; 690 } 691 if(!BN_GENCB_call(cb, 2, 0)) 692 goto err; 693 if(!BN_GENCB_call(cb, 3, 0)) 694 goto err; 695 696 memcpy(seed_tmp, seed, seedlen); 697 r = generate_p(ctx, md, counter, n, seed_tmp, seedlen, q, p, L, 698 cb, &pcounter, res); 699 if (r > 0) 700 break; /* found p */ 701 if (r < 0) 702 goto err; 703 /* 704 * A.1.1.3 Step (14): 705 * If we get here we failed to get a p for the given seed. If the 706 * seed is not random then it needs to fail (as it will always fail). 707 */ 708 if (seed == params->seed) { 709 *res = FFC_CHECK_P_NOT_PRIME; 710 goto err; 711 } 712 } 713 if(!BN_GENCB_call(cb, 2, 1)) 714 goto err; 715 /* 716 * Gets here if we found p. 717 * A.1.1.3 Step (14): return error if i != counter OR computed_p != known_p. 718 */ 719 if (verify && (pcounter != counter || (BN_cmp(p, params->p) != 0))) 720 goto err; 721 722 /* If validating p & q only then skip the g validation test */ 723 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQG) == FFC_PARAM_FLAG_VALIDATE_PQ) 724 goto pass; 725 g_only: 726 if ((mont = BN_MONT_CTX_new()) == NULL) 727 goto err; 728 if (!BN_MONT_CTX_set(mont, p, ctx)) 729 goto err; 730 731 if (((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) 732 && !ossl_ffc_params_validate_unverifiable_g(ctx, mont, p, q, params->g, 733 tmp, res)) 734 goto err; 735 736 /* 737 * A.2.1 Step (1) AND 738 * A.2.3 Step (3) AND 739 * A.2.4 Step (5) 740 * e = (p - 1) / q (i.e- Cofactor 'e' is given by p = q * e + 1) 741 */ 742 if (!(BN_sub(pm1, p, BN_value_one()) && BN_div(e, NULL, pm1, q, ctx))) 743 goto err; 744 745 /* Canonical g requires a seed and index to be set */ 746 if ((seed != NULL) && (params->gindex != FFC_UNVERIFIABLE_GINDEX)) { 747 canonical_g = 1; 748 if (!generate_canonical_g(ctx, mont, md, g, tmp, p, e, 749 params->gindex, seed, seedlen)) { 750 *res = FFC_CHECK_INVALID_G; 751 goto err; 752 } 753 /* A.2.4 Step (13): Return valid if computed_g == g */ 754 if (verify && BN_cmp(g, params->g) != 0) { 755 *res = FFC_CHECK_G_MISMATCH; 756 goto err; 757 } 758 } else if (!verify) { 759 if (!generate_unverifiable_g(ctx, mont, g, tmp, p, e, pm1, &hret)) 760 goto err; 761 } 762 763 if (!BN_GENCB_call(cb, 3, 1)) 764 goto err; 765 766 if (!verify) { 767 if (p != params->p) { 768 BN_free(params->p); 769 params->p = BN_dup(p); 770 } 771 if (q != params->q) { 772 BN_free(params->q); 773 params->q = BN_dup(q); 774 } 775 if (g != params->g) { 776 BN_free(params->g); 777 params->g = BN_dup(g); 778 } 779 if (params->p == NULL || params->q == NULL || params->g == NULL) 780 goto err; 781 if (!ossl_ffc_params_set_validate_params(params, seed, seedlen, 782 pcounter)) 783 goto err; 784 params->h = hret; 785 } 786 pass: 787 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0 && (canonical_g == 0)) 788 /* Return for the case where g is partially valid */ 789 ok = FFC_PARAM_RET_STATUS_UNVERIFIABLE_G; 790 else 791 ok = FFC_PARAM_RET_STATUS_SUCCESS; 792 err: 793 if (seed != params->seed) 794 OPENSSL_free(seed); 795 OPENSSL_free(seed_tmp); 796 if (ctx != NULL) 797 BN_CTX_end(ctx); 798 BN_CTX_free(ctx); 799 BN_MONT_CTX_free(mont); 800 EVP_MD_CTX_free(mctx); 801 EVP_MD_free(md); 802 return ok; 803 } 804 805 /* Note this function is only used for verification in fips mode */ 806 int ossl_ffc_params_FIPS186_2_gen_verify(OSSL_LIB_CTX *libctx, 807 FFC_PARAMS *params, int mode, int type, 808 size_t L, size_t N, int *res, 809 BN_GENCB *cb) 810 { 811 int ok = FFC_PARAM_RET_STATUS_FAILED; 812 unsigned char seed[SHA256_DIGEST_LENGTH]; 813 unsigned char buf[SHA256_DIGEST_LENGTH]; 814 BIGNUM *r0, *test, *tmp, *g = NULL, *q = NULL, *p = NULL; 815 BN_MONT_CTX *mont = NULL; 816 EVP_MD *md = NULL; 817 size_t qsize; 818 int n = 0, m = 0; 819 int counter = 0, pcounter = 0, use_random_seed; 820 int rv; 821 BN_CTX *ctx = NULL; 822 int hret = -1; 823 unsigned char *seed_in = params->seed; 824 size_t seed_len = params->seedlen; 825 int verify = (mode == FFC_PARAM_MODE_VERIFY); 826 unsigned int flags = verify ? params->flags : 0; 827 const char *def_name; 828 829 *res = 0; 830 831 if (params->mdname != NULL) { 832 md = EVP_MD_fetch(libctx, params->mdname, params->mdprops); 833 } else { 834 if (N == 0) 835 N = (L >= 2048 ? SHA256_DIGEST_LENGTH : SHA_DIGEST_LENGTH) * 8; 836 def_name = default_mdname(N); 837 if (def_name == NULL) { 838 *res = FFC_CHECK_INVALID_Q_VALUE; 839 goto err; 840 } 841 md = EVP_MD_fetch(libctx, def_name, params->mdprops); 842 } 843 if (md == NULL) 844 goto err; 845 if (N == 0) 846 N = EVP_MD_get_size(md) * 8; 847 qsize = N >> 3; 848 849 /* 850 * The original spec allowed L = 512 + 64*j (j = 0.. 8) 851 * https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf 852 * says that 512 can be used for legacy verification. 853 */ 854 if (L < 512) { 855 *res = FFC_CHECK_BAD_LN_PAIR; 856 goto err; 857 } 858 if (qsize != SHA_DIGEST_LENGTH 859 && qsize != SHA224_DIGEST_LENGTH 860 && qsize != SHA256_DIGEST_LENGTH) { 861 /* invalid q size */ 862 *res = FFC_CHECK_INVALID_Q_VALUE; 863 goto err; 864 } 865 866 L = (L + 63) / 64 * 64; 867 868 if (seed_in != NULL) { 869 if (seed_len < qsize) { 870 *res = FFC_CHECK_INVALID_SEED_SIZE; 871 goto err; 872 } 873 /* Only consume as much seed as is expected. */ 874 if (seed_len > qsize) 875 seed_len = qsize; 876 memcpy(seed, seed_in, seed_len); 877 } 878 879 ctx = BN_CTX_new_ex(libctx); 880 if (ctx == NULL) 881 goto err; 882 883 BN_CTX_start(ctx); 884 885 r0 = BN_CTX_get(ctx); 886 g = BN_CTX_get(ctx); 887 q = BN_CTX_get(ctx); 888 p = BN_CTX_get(ctx); 889 tmp = BN_CTX_get(ctx); 890 test = BN_CTX_get(ctx); 891 if (test == NULL) 892 goto err; 893 894 if (!BN_lshift(test, BN_value_one(), L - 1)) 895 goto err; 896 897 if (!verify) { 898 /* For generation: p & q must both be NULL or NON-NULL */ 899 if ((params->p != NULL) != (params->q != NULL)) { 900 *res = FFC_CHECK_INVALID_PQ; 901 goto err; 902 } 903 } else { 904 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) != 0) { 905 /* Validation of p,q requires seed and counter to be valid */ 906 if (seed_in == NULL || params->pcounter < 0) { 907 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER; 908 goto err; 909 } 910 } 911 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) { 912 /* validation of g also requires g to be set */ 913 if (params->g == NULL) { 914 *res = FFC_CHECK_INVALID_G; 915 goto err; 916 } 917 } 918 } 919 920 if (params->p != NULL && ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) == 0)) { 921 /* p and q already exists so only generate g */ 922 p = params->p; 923 q = params->q; 924 goto g_only; 925 /* otherwise fall thru to validate p and q */ 926 } 927 928 use_random_seed = (seed_in == NULL); 929 for (;;) { 930 if (!generate_q_fips186_2(ctx, q, md, buf, seed, qsize, 931 use_random_seed, &m, res, cb)) 932 goto err; 933 934 if (!BN_GENCB_call(cb, 2, 0)) 935 goto err; 936 if (!BN_GENCB_call(cb, 3, 0)) 937 goto err; 938 939 /* step 6 */ 940 n = (L - 1) / 160; 941 counter = 4 * L - 1; /* Was 4096 */ 942 /* Validation requires the counter to be supplied */ 943 if (verify) { 944 if (params->pcounter > counter) { 945 *res = FFC_CHECK_INVALID_COUNTER; 946 goto err; 947 } 948 counter = params->pcounter; 949 } 950 951 rv = generate_p(ctx, md, counter, n, buf, qsize, q, p, L, cb, 952 &pcounter, res); 953 if (rv > 0) 954 break; /* found it */ 955 if (rv == -1) 956 goto err; 957 /* This is what the old code did - probably not a good idea! */ 958 use_random_seed = 1; 959 } 960 961 if (!BN_GENCB_call(cb, 2, 1)) 962 goto err; 963 964 if (verify) { 965 if (pcounter != counter) { 966 *res = FFC_CHECK_COUNTER_MISMATCH; 967 goto err; 968 } 969 if (BN_cmp(p, params->p) != 0) { 970 *res = FFC_CHECK_P_MISMATCH; 971 goto err; 972 } 973 } 974 /* If validating p & q only then skip the g validation test */ 975 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQG) == FFC_PARAM_FLAG_VALIDATE_PQ) 976 goto pass; 977 g_only: 978 if ((mont = BN_MONT_CTX_new()) == NULL) 979 goto err; 980 if (!BN_MONT_CTX_set(mont, p, ctx)) 981 goto err; 982 983 if (!verify) { 984 /* We now need to generate g */ 985 /* set test = p - 1 */ 986 if (!BN_sub(test, p, BN_value_one())) 987 goto err; 988 /* Set r0 = (p - 1) / q */ 989 if (!BN_div(r0, NULL, test, q, ctx)) 990 goto err; 991 if (!generate_unverifiable_g(ctx, mont, g, tmp, p, r0, test, &hret)) 992 goto err; 993 } else if (((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) 994 && !ossl_ffc_params_validate_unverifiable_g(ctx, mont, p, q, 995 params->g, tmp, 996 res)) { 997 goto err; 998 } 999 1000 if (!BN_GENCB_call(cb, 3, 1)) 1001 goto err; 1002 1003 if (!verify) { 1004 if (p != params->p) { 1005 BN_free(params->p); 1006 params->p = BN_dup(p); 1007 } 1008 if (q != params->q) { 1009 BN_free(params->q); 1010 params->q = BN_dup(q); 1011 } 1012 if (g != params->g) { 1013 BN_free(params->g); 1014 params->g = BN_dup(g); 1015 } 1016 if (params->p == NULL || params->q == NULL || params->g == NULL) 1017 goto err; 1018 if (!ossl_ffc_params_set_validate_params(params, seed, qsize, pcounter)) 1019 goto err; 1020 params->h = hret; 1021 } 1022 pass: 1023 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) 1024 ok = FFC_PARAM_RET_STATUS_UNVERIFIABLE_G; 1025 else 1026 ok = FFC_PARAM_RET_STATUS_SUCCESS; 1027 err: 1028 if (ctx != NULL) 1029 BN_CTX_end(ctx); 1030 BN_CTX_free(ctx); 1031 BN_MONT_CTX_free(mont); 1032 EVP_MD_free(md); 1033 return ok; 1034 } 1035 1036 int ossl_ffc_params_FIPS186_4_generate(OSSL_LIB_CTX *libctx, FFC_PARAMS *params, 1037 int type, size_t L, size_t N, 1038 int *res, BN_GENCB *cb) 1039 { 1040 return ossl_ffc_params_FIPS186_4_gen_verify(libctx, params, 1041 FFC_PARAM_MODE_GENERATE, 1042 type, L, N, res, cb); 1043 } 1044 1045 /* This should no longer be used in FIPS mode */ 1046 int ossl_ffc_params_FIPS186_2_generate(OSSL_LIB_CTX *libctx, FFC_PARAMS *params, 1047 int type, size_t L, size_t N, 1048 int *res, BN_GENCB *cb) 1049 { 1050 if (!ossl_ffc_params_FIPS186_2_gen_verify(libctx, params, 1051 FFC_PARAM_MODE_GENERATE, 1052 type, L, N, res, cb)) 1053 return 0; 1054 1055 ossl_ffc_params_enable_flags(params, FFC_PARAM_FLAG_VALIDATE_LEGACY, 1); 1056 return 1; 1057 } 1058