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