crypto/ffc/ffc_params_generate.c

   1 /*
   2  * Copyright 2019-2020 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         DHerr(0, 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         DSAerr(0, 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         DHerr(0, DH_R_BAD_FFC_PARAMETERS);
  78 # endif
  79     } else if (type == FFC_PARAM_TYPE_DSA) {
  80         if (L == 1024 && N == 160)
  81             return 80;
  82         if (L == 2048 && (N == 224 || N == 256))
  83             return 112;
  84         if (L == 3072 && N == 256)
  85             return 128;
  86 # ifndef OPENSSL_NO_DSA
  87         DSAerr(0, 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_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_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_size(evpmd);
 322     unsigned char *pmd;
 323     OPENSSL_CTX *libctx = bn_get_lib_ctx(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, (int)seedlen) < 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     OPENSSL_CTX *libctx = bn_get_lib_ctx(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, (int)qsize) <= 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_ALL
 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(OPENSSL_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_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_ALL) == 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(OPENSSL_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_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_ALL) == 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(OPENSSL_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(OPENSSL_CTX *libctx, FFC_PARAMS *params,
1047                                        int type, size_t L, size_t N,
1048                                        int *res, BN_GENCB *cb)
1049 {
1050     return ossl_ffc_params_FIPS186_2_gen_verify(libctx, params,
1051                                                 FFC_PARAM_MODE_GENERATE,
1052                                                 type, L, N, res, cb);
1053 }