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