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