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