1 /* 2 * Copyright 2019-2024 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 if (mdsize <= 0) 326 goto err; 327 328 /* find q */ 329 for (;;) { 330 if (!BN_GENCB_call(cb, 0, m++)) 331 goto err; 332 333 /* A.1.1.2 Step (5) : generate seed with size seed_len */ 334 if (generate_seed 335 && RAND_bytes_ex(libctx, seed, seedlen, 0) <= 0) 336 goto err; 337 /* 338 * A.1.1.2 Step (6) AND 339 * A.1.1.3 Step (7) 340 * U = Hash(seed) % (2^(N-1)) 341 */ 342 if (!EVP_Digest(seed, seedlen, md, NULL, evpmd, NULL)) 343 goto err; 344 /* Take least significant bits of md */ 345 if (mdsize > qsize) 346 pmd = md + mdsize - qsize; 347 else 348 pmd = md; 349 if (mdsize < qsize) 350 memset(md + mdsize, 0, qsize - mdsize); 351 352 /* 353 * A.1.1.2 Step (7) AND 354 * A.1.1.3 Step (8) 355 * q = U + 2^(N-1) + (1 - U %2) (This sets top and bottom bits) 356 */ 357 pmd[0] |= 0x80; 358 pmd[qsize-1] |= 0x01; 359 if (!BN_bin2bn(pmd, qsize, q)) 360 goto err; 361 362 /* 363 * A.1.1.2 Step (8) AND 364 * A.1.1.3 Step (9) 365 * Test if q is prime 366 */ 367 r = BN_check_prime(q, ctx, cb); 368 if (r > 0) { 369 ret = 1; 370 goto err; 371 } 372 /* 373 * A.1.1.3 Step (9) : If the provided seed didn't produce a prime q 374 * return an error. 375 */ 376 if (!generate_seed) { 377 *res |= FFC_CHECK_Q_NOT_PRIME; 378 goto err; 379 } 380 if (r != 0) 381 goto err; 382 /* A.1.1.2 Step (9) : if q is not prime, try another q */ 383 } 384 err: 385 *retm = m; 386 return ret; 387 } 388 389 static int generate_q_fips186_2(BN_CTX *ctx, BIGNUM *q, const EVP_MD *evpmd, 390 unsigned char *buf, unsigned char *seed, 391 size_t qsize, int generate_seed, int *retm, 392 int *res, BN_GENCB *cb) 393 { 394 unsigned char buf2[EVP_MAX_MD_SIZE]; 395 unsigned char md[EVP_MAX_MD_SIZE]; 396 int i, r, ret = 0, m = *retm; 397 OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx); 398 399 /* find q */ 400 for (;;) { 401 /* step 1 */ 402 if (!BN_GENCB_call(cb, 0, m++)) 403 goto err; 404 405 if (generate_seed && RAND_bytes_ex(libctx, seed, qsize, 0) <= 0) 406 goto err; 407 408 memcpy(buf, seed, qsize); 409 memcpy(buf2, seed, qsize); 410 411 /* precompute "SEED + 1" for step 7: */ 412 for (i = (int)qsize - 1; i >= 0; i--) { 413 buf[i]++; 414 if (buf[i] != 0) 415 break; 416 } 417 418 /* step 2 */ 419 if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) 420 goto err; 421 if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) 422 goto err; 423 for (i = 0; i < (int)qsize; i++) 424 md[i] ^= buf2[i]; 425 426 /* step 3 */ 427 md[0] |= 0x80; 428 md[qsize - 1] |= 0x01; 429 if (!BN_bin2bn(md, (int)qsize, q)) 430 goto err; 431 432 /* step 4 */ 433 r = BN_check_prime(q, ctx, cb); 434 if (r > 0) { 435 /* Found a prime */ 436 ret = 1; 437 goto err; 438 } 439 if (r != 0) 440 goto err; /* Exit if error */ 441 /* Try another iteration if it wasn't prime - was in old code.. */ 442 generate_seed = 1; 443 } 444 err: 445 *retm = m; 446 return ret; 447 } 448 449 static const char *default_mdname(size_t N) 450 { 451 if (N == 160) 452 return "SHA1"; 453 else if (N == 224) 454 return "SHA-224"; 455 else if (N == 256) 456 return "SHA-256"; 457 return NULL; 458 } 459 460 /* 461 * FIPS 186-4 FFC parameter generation (as defined in Appendix A). 462 * The same code is used for validation (when validate_flags != 0) 463 * 464 * The primes p & q are generated/validated using: 465 * A.1.1.2 Generation of probable primes p & q using approved hash. 466 * A.1.1.3 Validation of generated probable primes 467 * 468 * Generator 'g' has 2 types in FIPS 186-4: 469 * (1) A.2.1 unverifiable generation of generator g. 470 * A.2.2 Assurance of the validity of unverifiable generator g. 471 * (2) A.2.3 Verifiable Canonical Generation of the generator g. 472 * A.2.4 Validation for Canonical Generation of the generator g. 473 * 474 * Notes: 475 * (1) is only a partial validation of g, The validation of (2) requires 476 * the seed and index used during generation as input. 477 * 478 * params: used to pass in values for generation and validation. 479 * params->md: is the digest to use, If this value is NULL, then the digest is 480 * chosen using the value of N. 481 * params->flags: 482 * For validation one of: 483 * -FFC_PARAM_FLAG_VALIDATE_PQ 484 * -FFC_PARAM_FLAG_VALIDATE_G 485 * -FFC_PARAM_FLAG_VALIDATE_PQG 486 * For generation of p & q: 487 * - This is skipped if p & q are passed in. 488 * - If the seed is passed in then generation of p & q uses this seed (and if 489 * this fails an error will occur). 490 * - Otherwise the seed is generated, and values of p & q are generated and 491 * the value of seed and counter are optionally returned. 492 * For the generation of g (after the generation of p, q): 493 * - If the seed has been generated or passed in and a valid gindex is passed 494 * in then canonical generation of g is used otherwise unverifiable 495 * generation of g is chosen. 496 * For validation of p & q: 497 * - p, q, and the seed and counter used for generation must be passed in. 498 * For validation of g: 499 * - For a partial validation : p, q and g are required. 500 * - For a canonical validation : the gindex and seed used for generation are 501 * also required. 502 * mode: The mode - either FFC_PARAM_MODE_GENERATE or FFC_PARAM_MODE_VERIFY. 503 * type: The key type - FFC_PARAM_TYPE_DSA or FFC_PARAM_TYPE_DH. 504 * L: is the size of the prime p in bits (e.g 2048) 505 * N: is the size of the prime q in bits (e.g 256) 506 * res: A returned failure reason (One of FFC_CHECK_XXXX), 507 * or 0 for general failures. 508 * cb: A callback (can be NULL) that is called during different phases 509 * 510 * Returns: 511 * - FFC_PARAM_RET_STATUS_FAILED: if there was an error, or validation failed. 512 * - FFC_PARAM_RET_STATUS_SUCCESS if the generation or validation succeeded. 513 * - FFC_PARAM_RET_STATUS_UNVERIFIABLE_G if the validation of G succeeded, 514 * but G is unverifiable. 515 */ 516 int ossl_ffc_params_FIPS186_4_gen_verify(OSSL_LIB_CTX *libctx, 517 FFC_PARAMS *params, int mode, int type, 518 size_t L, size_t N, int *res, 519 BN_GENCB *cb) 520 { 521 int ok = FFC_PARAM_RET_STATUS_FAILED; 522 unsigned char *seed = NULL, *seed_tmp = NULL; 523 int mdsize, counter = 0, pcounter = 0, r = 0; 524 size_t seedlen = 0; 525 BIGNUM *tmp, *pm1, *e, *test; 526 BIGNUM *g = NULL, *q = NULL, *p = NULL; 527 BN_MONT_CTX *mont = NULL; 528 int n = 0, m = 0, qsize; 529 int canonical_g = 0, hret = 0; 530 BN_CTX *ctx = NULL; 531 EVP_MD_CTX *mctx = NULL; 532 EVP_MD *md = NULL; 533 int verify = (mode == FFC_PARAM_MODE_VERIFY); 534 unsigned int flags = verify ? params->flags : 0; 535 const char *def_name; 536 537 *res = 0; 538 539 if (params->mdname != NULL) { 540 md = EVP_MD_fetch(libctx, params->mdname, params->mdprops); 541 } else { 542 if (N == 0) 543 N = (L >= 2048 ? SHA256_DIGEST_LENGTH : SHA_DIGEST_LENGTH) * 8; 544 def_name = default_mdname(N); 545 if (def_name == NULL) { 546 *res = FFC_CHECK_INVALID_Q_VALUE; 547 goto err; 548 } 549 md = EVP_MD_fetch(libctx, def_name, params->mdprops); 550 } 551 if (md == NULL) 552 goto err; 553 mdsize = EVP_MD_get_size(md); 554 if (mdsize <= 0) 555 goto err; 556 557 if (N == 0) 558 N = mdsize * 8; 559 qsize = N >> 3; 560 561 /* 562 * A.1.1.2 Step (1) AND 563 * A.1.1.3 Step (3) 564 * Check that the L,N pair is an acceptable pair. 565 */ 566 if (L <= N || !ffc_validate_LN(L, N, type, verify)) { 567 *res = FFC_CHECK_BAD_LN_PAIR; 568 goto err; 569 } 570 571 mctx = EVP_MD_CTX_new(); 572 if (mctx == NULL) 573 goto err; 574 575 if ((ctx = BN_CTX_new_ex(libctx)) == NULL) 576 goto err; 577 578 BN_CTX_start(ctx); 579 g = BN_CTX_get(ctx); 580 pm1 = BN_CTX_get(ctx); 581 e = BN_CTX_get(ctx); 582 test = BN_CTX_get(ctx); 583 tmp = BN_CTX_get(ctx); 584 if (tmp == NULL) 585 goto err; 586 587 seedlen = params->seedlen; 588 if (seedlen == 0) 589 seedlen = (size_t)mdsize; 590 /* If the seed was passed in - use this value as the seed */ 591 if (params->seed != NULL) 592 seed = params->seed; 593 594 if (!verify) { 595 /* For generation: p & q must both be NULL or NON-NULL */ 596 if ((params->p == NULL) != (params->q == NULL)) { 597 *res = FFC_CHECK_INVALID_PQ; 598 goto err; 599 } 600 } else { 601 /* Validation of p,q requires seed and counter to be valid */ 602 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) != 0) { 603 if (seed == NULL || params->pcounter < 0) { 604 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER; 605 goto err; 606 } 607 } 608 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) { 609 /* validation of g also requires g to be set */ 610 if (params->g == NULL) { 611 *res = FFC_CHECK_INVALID_G; 612 goto err; 613 } 614 } 615 } 616 617 /* 618 * If p & q are passed in and 619 * validate_flags = 0 then skip the generation of PQ. 620 * validate_flags = VALIDATE_G then also skip the validation of PQ. 621 */ 622 if (params->p != NULL && ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) == 0)) { 623 /* p and q already exists so only generate g */ 624 p = params->p; 625 q = params->q; 626 goto g_only; 627 /* otherwise fall through to validate p & q */ 628 } 629 630 /* p & q will be used for generation and validation */ 631 p = BN_CTX_get(ctx); 632 q = BN_CTX_get(ctx); 633 if (q == NULL) 634 goto err; 635 636 /* 637 * A.1.1.2 Step (2) AND 638 * A.1.1.3 Step (6) 639 * Return invalid if seedlen < N 640 */ 641 if ((seedlen * 8) < N) { 642 *res = FFC_CHECK_INVALID_SEED_SIZE; 643 goto err; 644 } 645 646 seed_tmp = OPENSSL_malloc(seedlen); 647 if (seed_tmp == NULL) 648 goto err; 649 650 if (seed == NULL) { 651 /* Validation requires the seed to be supplied */ 652 if (verify) { 653 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER; 654 goto err; 655 } 656 /* if the seed is not supplied then alloc a seed buffer */ 657 seed = OPENSSL_malloc(seedlen); 658 if (seed == NULL) 659 goto err; 660 } 661 662 /* A.1.1.2 Step (11): max loop count = 4L - 1 */ 663 counter = 4 * L - 1; 664 /* Validation requires the counter to be supplied */ 665 if (verify) { 666 /* A.1.1.3 Step (4) : if (counter > (4L -1)) return INVALID */ 667 if (params->pcounter > counter) { 668 *res = FFC_CHECK_INVALID_COUNTER; 669 goto err; 670 } 671 counter = params->pcounter; 672 } 673 674 /* 675 * A.1.1.2 Step (3) AND 676 * A.1.1.3 Step (10) 677 * n = floor(L / hash_outlen) - 1 678 */ 679 n = (L - 1) / (mdsize << 3); 680 681 /* Calculate 2^(L-1): Used in step A.1.1.2 Step (11.3) */ 682 if (!BN_lshift(test, BN_value_one(), L - 1)) 683 goto err; 684 685 for (;;) { 686 if (!generate_q_fips186_4(ctx, q, md, qsize, seed, seedlen, 687 seed != params->seed, &m, res, cb)) 688 goto err; 689 /* A.1.1.3 Step (9): Verify that q matches the expected value */ 690 if (verify && (BN_cmp(q, params->q) != 0)) { 691 *res = FFC_CHECK_Q_MISMATCH; 692 goto err; 693 } 694 if (!BN_GENCB_call(cb, 2, 0)) 695 goto err; 696 if (!BN_GENCB_call(cb, 3, 0)) 697 goto err; 698 699 memcpy(seed_tmp, seed, seedlen); 700 r = generate_p(ctx, md, counter, n, seed_tmp, seedlen, q, p, L, 701 cb, &pcounter, res); 702 if (r > 0) 703 break; /* found p */ 704 if (r < 0) 705 goto err; 706 /* 707 * A.1.1.3 Step (14): 708 * If we get here we failed to get a p for the given seed. If the 709 * seed is not random then it needs to fail (as it will always fail). 710 */ 711 if (seed == params->seed) { 712 *res = FFC_CHECK_P_NOT_PRIME; 713 goto err; 714 } 715 } 716 if(!BN_GENCB_call(cb, 2, 1)) 717 goto err; 718 /* 719 * Gets here if we found p. 720 * A.1.1.3 Step (14): return error if i != counter OR computed_p != known_p. 721 */ 722 if (verify && (pcounter != counter || (BN_cmp(p, params->p) != 0))) 723 goto err; 724 725 /* If validating p & q only then skip the g validation test */ 726 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQG) == FFC_PARAM_FLAG_VALIDATE_PQ) 727 goto pass; 728 g_only: 729 if ((mont = BN_MONT_CTX_new()) == NULL) 730 goto err; 731 if (!BN_MONT_CTX_set(mont, p, ctx)) 732 goto err; 733 734 if (((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) 735 && !ossl_ffc_params_validate_unverifiable_g(ctx, mont, p, q, params->g, 736 tmp, res)) 737 goto err; 738 739 /* 740 * A.2.1 Step (1) AND 741 * A.2.3 Step (3) AND 742 * A.2.4 Step (5) 743 * e = (p - 1) / q (i.e- Cofactor 'e' is given by p = q * e + 1) 744 */ 745 if (!(BN_sub(pm1, p, BN_value_one()) && BN_div(e, NULL, pm1, q, ctx))) 746 goto err; 747 748 /* Canonical g requires a seed and index to be set */ 749 if ((seed != NULL) && (params->gindex != FFC_UNVERIFIABLE_GINDEX)) { 750 canonical_g = 1; 751 if (!generate_canonical_g(ctx, mont, md, g, tmp, p, e, 752 params->gindex, seed, seedlen)) { 753 *res = FFC_CHECK_INVALID_G; 754 goto err; 755 } 756 /* A.2.4 Step (13): Return valid if computed_g == g */ 757 if (verify && BN_cmp(g, params->g) != 0) { 758 *res = FFC_CHECK_G_MISMATCH; 759 goto err; 760 } 761 } else if (!verify) { 762 if (!generate_unverifiable_g(ctx, mont, g, tmp, p, e, pm1, &hret)) 763 goto err; 764 } 765 766 if (!BN_GENCB_call(cb, 3, 1)) 767 goto err; 768 769 if (!verify) { 770 if (p != params->p) { 771 BN_free(params->p); 772 params->p = BN_dup(p); 773 } 774 if (q != params->q) { 775 BN_free(params->q); 776 params->q = BN_dup(q); 777 } 778 if (g != params->g) { 779 BN_free(params->g); 780 params->g = BN_dup(g); 781 } 782 if (params->p == NULL || params->q == NULL || params->g == NULL) 783 goto err; 784 if (!ossl_ffc_params_set_validate_params(params, seed, seedlen, 785 pcounter)) 786 goto err; 787 params->h = hret; 788 } 789 pass: 790 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0 && (canonical_g == 0)) 791 /* Return for the case where g is partially valid */ 792 ok = FFC_PARAM_RET_STATUS_UNVERIFIABLE_G; 793 else 794 ok = FFC_PARAM_RET_STATUS_SUCCESS; 795 err: 796 if (seed != params->seed) 797 OPENSSL_free(seed); 798 OPENSSL_free(seed_tmp); 799 if (ctx != NULL) 800 BN_CTX_end(ctx); 801 BN_CTX_free(ctx); 802 BN_MONT_CTX_free(mont); 803 EVP_MD_CTX_free(mctx); 804 EVP_MD_free(md); 805 return ok; 806 } 807 808 /* Note this function is only used for verification in fips mode */ 809 int ossl_ffc_params_FIPS186_2_gen_verify(OSSL_LIB_CTX *libctx, 810 FFC_PARAMS *params, int mode, int type, 811 size_t L, size_t N, int *res, 812 BN_GENCB *cb) 813 { 814 int ok = FFC_PARAM_RET_STATUS_FAILED; 815 unsigned char seed[SHA256_DIGEST_LENGTH]; 816 unsigned char buf[SHA256_DIGEST_LENGTH]; 817 BIGNUM *r0, *test, *tmp, *g = NULL, *q = NULL, *p = NULL; 818 BN_MONT_CTX *mont = NULL; 819 EVP_MD *md = NULL; 820 int md_size; 821 size_t qsize; 822 int n = 0, m = 0; 823 int counter = 0, pcounter = 0, use_random_seed; 824 int rv; 825 BN_CTX *ctx = NULL; 826 int hret = -1; 827 unsigned char *seed_in = params->seed; 828 size_t seed_len = params->seedlen; 829 int verify = (mode == FFC_PARAM_MODE_VERIFY); 830 unsigned int flags = verify ? params->flags : 0; 831 const char *def_name; 832 833 *res = 0; 834 835 if (params->mdname != NULL) { 836 md = EVP_MD_fetch(libctx, params->mdname, params->mdprops); 837 } else { 838 if (N == 0) 839 N = (L >= 2048 ? SHA256_DIGEST_LENGTH : SHA_DIGEST_LENGTH) * 8; 840 def_name = default_mdname(N); 841 if (def_name == NULL) { 842 *res = FFC_CHECK_INVALID_Q_VALUE; 843 goto err; 844 } 845 md = EVP_MD_fetch(libctx, def_name, params->mdprops); 846 } 847 if (md == NULL) 848 goto err; 849 md_size = EVP_MD_get_size(md); 850 if (md_size <= 0) 851 goto err; 852 if (N == 0) 853 N = md_size * 8; 854 qsize = N >> 3; 855 856 /* 857 * The original spec allowed L = 512 + 64*j (j = 0.. 8) 858 * https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf 859 * says that 512 can be used for legacy verification. 860 */ 861 if (L < 512) { 862 *res = FFC_CHECK_BAD_LN_PAIR; 863 goto err; 864 } 865 if (qsize != SHA_DIGEST_LENGTH 866 && qsize != SHA224_DIGEST_LENGTH 867 && qsize != SHA256_DIGEST_LENGTH) { 868 /* invalid q size */ 869 *res = FFC_CHECK_INVALID_Q_VALUE; 870 goto err; 871 } 872 873 L = (L + 63) / 64 * 64; 874 875 if (seed_in != NULL) { 876 if (seed_len < qsize) { 877 *res = FFC_CHECK_INVALID_SEED_SIZE; 878 goto err; 879 } 880 /* Only consume as much seed as is expected. */ 881 if (seed_len > qsize) 882 seed_len = qsize; 883 memcpy(seed, seed_in, seed_len); 884 } 885 886 ctx = BN_CTX_new_ex(libctx); 887 if (ctx == NULL) 888 goto err; 889 890 BN_CTX_start(ctx); 891 892 r0 = BN_CTX_get(ctx); 893 g = BN_CTX_get(ctx); 894 q = BN_CTX_get(ctx); 895 p = BN_CTX_get(ctx); 896 tmp = BN_CTX_get(ctx); 897 test = BN_CTX_get(ctx); 898 if (test == NULL) 899 goto err; 900 901 if (!BN_lshift(test, BN_value_one(), L - 1)) 902 goto err; 903 904 if (!verify) { 905 /* For generation: p & q must both be NULL or NON-NULL */ 906 if ((params->p != NULL) != (params->q != NULL)) { 907 *res = FFC_CHECK_INVALID_PQ; 908 goto err; 909 } 910 } else { 911 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) != 0) { 912 /* Validation of p,q requires seed and counter to be valid */ 913 if (seed_in == NULL || params->pcounter < 0) { 914 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER; 915 goto err; 916 } 917 } 918 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) { 919 /* validation of g also requires g to be set */ 920 if (params->g == NULL) { 921 *res = FFC_CHECK_INVALID_G; 922 goto err; 923 } 924 } 925 } 926 927 if (params->p != NULL && ((flags & FFC_PARAM_FLAG_VALIDATE_PQ) == 0)) { 928 /* p and q already exists so only generate g */ 929 p = params->p; 930 q = params->q; 931 goto g_only; 932 /* otherwise fall through to validate p and q */ 933 } 934 935 use_random_seed = (seed_in == NULL); 936 for (;;) { 937 if (!generate_q_fips186_2(ctx, q, md, buf, seed, qsize, 938 use_random_seed, &m, res, cb)) 939 goto err; 940 941 if (!BN_GENCB_call(cb, 2, 0)) 942 goto err; 943 if (!BN_GENCB_call(cb, 3, 0)) 944 goto err; 945 946 /* step 6 */ 947 n = (L - 1) / 160; 948 counter = 4 * L - 1; /* Was 4096 */ 949 /* Validation requires the counter to be supplied */ 950 if (verify) { 951 if (params->pcounter > counter) { 952 *res = FFC_CHECK_INVALID_COUNTER; 953 goto err; 954 } 955 counter = params->pcounter; 956 } 957 958 rv = generate_p(ctx, md, counter, n, buf, qsize, q, p, L, cb, 959 &pcounter, res); 960 if (rv > 0) 961 break; /* found it */ 962 if (rv == -1) 963 goto err; 964 /* This is what the old code did - probably not a good idea! */ 965 use_random_seed = 1; 966 } 967 968 if (!BN_GENCB_call(cb, 2, 1)) 969 goto err; 970 971 if (verify) { 972 if (pcounter != counter) { 973 *res = FFC_CHECK_COUNTER_MISMATCH; 974 goto err; 975 } 976 if (BN_cmp(p, params->p) != 0) { 977 *res = FFC_CHECK_P_MISMATCH; 978 goto err; 979 } 980 } 981 /* If validating p & q only then skip the g validation test */ 982 if ((flags & FFC_PARAM_FLAG_VALIDATE_PQG) == FFC_PARAM_FLAG_VALIDATE_PQ) 983 goto pass; 984 g_only: 985 if ((mont = BN_MONT_CTX_new()) == NULL) 986 goto err; 987 if (!BN_MONT_CTX_set(mont, p, ctx)) 988 goto err; 989 990 if (!verify) { 991 /* We now need to generate g */ 992 /* set test = p - 1 */ 993 if (!BN_sub(test, p, BN_value_one())) 994 goto err; 995 /* Set r0 = (p - 1) / q */ 996 if (!BN_div(r0, NULL, test, q, ctx)) 997 goto err; 998 if (!generate_unverifiable_g(ctx, mont, g, tmp, p, r0, test, &hret)) 999 goto err; 1000 } else if (((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) 1001 && !ossl_ffc_params_validate_unverifiable_g(ctx, mont, p, q, 1002 params->g, tmp, 1003 res)) { 1004 goto err; 1005 } 1006 1007 if (!BN_GENCB_call(cb, 3, 1)) 1008 goto err; 1009 1010 if (!verify) { 1011 if (p != params->p) { 1012 BN_free(params->p); 1013 params->p = BN_dup(p); 1014 } 1015 if (q != params->q) { 1016 BN_free(params->q); 1017 params->q = BN_dup(q); 1018 } 1019 if (g != params->g) { 1020 BN_free(params->g); 1021 params->g = BN_dup(g); 1022 } 1023 if (params->p == NULL || params->q == NULL || params->g == NULL) 1024 goto err; 1025 if (!ossl_ffc_params_set_validate_params(params, seed, qsize, pcounter)) 1026 goto err; 1027 params->h = hret; 1028 } 1029 pass: 1030 if ((flags & FFC_PARAM_FLAG_VALIDATE_G) != 0) 1031 ok = FFC_PARAM_RET_STATUS_UNVERIFIABLE_G; 1032 else 1033 ok = FFC_PARAM_RET_STATUS_SUCCESS; 1034 err: 1035 if (ctx != NULL) 1036 BN_CTX_end(ctx); 1037 BN_CTX_free(ctx); 1038 BN_MONT_CTX_free(mont); 1039 EVP_MD_free(md); 1040 return ok; 1041 } 1042 1043 int ossl_ffc_params_FIPS186_4_generate(OSSL_LIB_CTX *libctx, FFC_PARAMS *params, 1044 int type, size_t L, size_t N, 1045 int *res, BN_GENCB *cb) 1046 { 1047 return ossl_ffc_params_FIPS186_4_gen_verify(libctx, params, 1048 FFC_PARAM_MODE_GENERATE, 1049 type, L, N, res, cb); 1050 } 1051 1052 /* This should no longer be used in FIPS mode */ 1053 int ossl_ffc_params_FIPS186_2_generate(OSSL_LIB_CTX *libctx, FFC_PARAMS *params, 1054 int type, size_t L, size_t N, 1055 int *res, BN_GENCB *cb) 1056 { 1057 if (!ossl_ffc_params_FIPS186_2_gen_verify(libctx, params, 1058 FFC_PARAM_MODE_GENERATE, 1059 type, L, N, res, cb)) 1060 return 0; 1061 1062 ossl_ffc_params_enable_flags(params, FFC_PARAM_FLAG_VALIDATE_LEGACY, 1); 1063 return 1; 1064 } 1065