Generate error queue entry on FFC_CHECK_BAD_LN_PAIR for DH and DSA
[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 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 EVP_MD *fetch_default_md(OPENSSL_CTX *libctx, size_t N)
417 {
418     char *name = NULL;
419
420     if (N == 160)
421         name = "SHA1";
422     else if (N == 224)
423         name = "SHA-224";
424     else if (N == 256)
425         name = "SHA-256";
426
427     return name !=  NULL ?  EVP_MD_fetch(libctx, name, "") : NULL;
428 }
429
430 /*
431  * FIPS 186-4 FFC parameter generation (as defined in Appendix A).
432  * The same code is used for validation (when validate_flags != 0)
433  *
434  * The primes p & q are generated/validated using:
435  *   A.1.1.2 Generation of probable primes p & q using approved hash.
436  *   A.1.1.3 Validation of generated probable primes
437  *
438  * Generator 'g' has 2 types in FIPS 186-4:
439  *   (1) A.2.1 unverifiable generation of generator g.
440  *       A.2.2 Assurance of the validity of unverifiable generator g.
441  *   (2) A.2.3 Verifiable Canonical Generation of the generator g.
442  *       A.2.4 Validation for Canonical Generation of the generator g.
443  *
444  * Notes:
445  * (1) is only a partial validation of g, The validation of (2) requires
446  * the seed and index used during generation as input.
447  *
448  * params: used to pass in values for generation and validation.
449  *  For generation of p & q:
450  *   - This is skipped if p & q are passed in.
451  *   - If the seed is passed in then generation of p & q uses this seed (and if
452  *     this fails an error will occur).
453  *   - Otherwise the seed is generated, and values of p & q are generated and
454  *     the value of seed and counter are optionally returned.
455  *  For the generation of g (after the generation of p, q):
456  *   - If the seed has been generated or passed in and a valid gindex is passed
457  *     in then canonical generation of g is used otherwise unverifiable
458  *     generation of g is chosen.
459  *  For validation of p & q:
460  *   - p, q, and the seed and counter used for generation must be passed in.
461  *  For validation of g:
462  *   - For a partial validation : p, q and g are required.
463  *   - For a canonical validation : the gindex and seed used for generation are
464  *     also required.
465  * type: The key type - FFC_PARAM_TYPE_DSA or FFC_PARAM_TYPE_DH.
466  * L: is the size of the prime p in bits (e.g 2048)
467  * N: is the size of the prime q in bits (e.g 256)
468  * evpmd: is the digest to use, If this value is NULL, then the digest is chosen
469  *        using the value of N.
470  * validate_flags:
471  *  or generation: FFC_PARAMS_GENERATE.
472  *  For validation one of:
473  *   -FFC_PARAMS_VALIDATE_PQ
474  *   -FFC_PARAMS_VALIDATE_G
475  *   -FFC_PARAMS_VALIDATE_ALL
476  * res: A returned failure reason (One of FFC_CHECK_XXXX),
477  *      or 0 for general failures.
478  * cb: A callback (can be NULL) that is called during different phases
479  *
480  * Returns:
481  *   - FFC_PARAMS_RET_STATUS_FAILED: if there was an error, or validation failed.
482  *   - FFC_PARAMS_RET_STATUS_SUCCESS if the generation or validation succeeded.
483  *   - FFC_PARAMS_RET_STATUS_UNVERIFIABLE_G if the validation of G succeeded,
484  *     but G is unverifiable.
485  */
486 int ffc_params_FIPS186_4_gen_verify(OPENSSL_CTX *libctx, FFC_PARAMS *params,
487                                     int type, size_t L, size_t N,
488                                     const EVP_MD *evpmd, int validate_flags,
489                                     int *res, BN_GENCB *cb)
490 {
491     int ok = FFC_PARAMS_RET_STATUS_FAILED;
492     unsigned char *seed = NULL, *seed_tmp = NULL;
493     int mdsize, counter = 0, pcounter = 0, r = 0;
494     size_t seedlen = 0;
495     BIGNUM *tmp, *pm1, *e, *test;
496     BIGNUM *g = NULL, *q = NULL, *p = NULL;
497     BN_MONT_CTX *mont = NULL;
498     int n = 0, m = 0, qsize = N >> 3;
499     int canonical_g = 0, hret = 0;
500     BN_CTX *ctx = NULL;
501     EVP_MD_CTX *mctx = NULL;
502     int generate = (validate_flags == 0);
503     EVP_MD *evpmd_fetch = NULL;
504
505     *res = 0;
506
507     /*
508      * A.1.1.2 Step (1) AND
509      * A.1.1.3 Step (3)
510      * Check that the L,N pair is an acceptable pair.
511      */
512     if (L <= N || !ffc_validate_LN(L, N, type)) {
513         *res = FFC_CHECK_BAD_LN_PAIR;
514         goto err;
515     }
516
517     mctx = EVP_MD_CTX_new();
518     if (mctx == NULL)
519         goto err;
520
521     if (evpmd == NULL) {
522         evpmd_fetch = fetch_default_md(libctx, N);
523         evpmd = evpmd_fetch;
524     }
525
526     mdsize = EVP_MD_size(evpmd);
527     if (mdsize <= 0)
528         goto err;
529
530     if ((ctx = BN_CTX_new_ex(libctx)) == NULL)
531         goto err;
532
533     BN_CTX_start(ctx);
534     g = BN_CTX_get(ctx);
535     pm1 = BN_CTX_get(ctx);
536     e = BN_CTX_get(ctx);
537     test = BN_CTX_get(ctx);
538     tmp = BN_CTX_get(ctx);
539     if (tmp == NULL)
540         goto err;
541
542     seedlen = params->seedlen;
543     if (seedlen == 0)
544         seedlen = (size_t)mdsize;
545     /* If the seed was passed in - use this value as the seed */
546     if (params->seed != NULL)
547         seed = params->seed;
548
549     if (generate) {
550         /* For generation: p & q must both be NULL or NON-NULL */
551         if ((params->p == NULL) != (params->q == NULL)) {
552             *res = FFC_CHECK_INVALID_PQ;
553             goto err;
554         }
555     } else {
556         /* Validation of p,q requires seed and counter to be valid */
557         if ((validate_flags & FFC_PARAMS_VALIDATE_PQ) != 0) {
558             if (seed == NULL || params->pcounter < 0) {
559                 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER;
560                 goto err;
561             }
562         }
563         if ((validate_flags & FFC_PARAMS_VALIDATE_G) != 0) {
564             /* validation of g also requires g to be set */
565             if (params->g == NULL) {
566                 *res = FFC_CHECK_INVALID_G;
567                 goto err;
568             }
569         }
570     }
571
572     /*
573      * If p & q are passed in and
574      *   validate_flags = 0 then skip the generation of PQ.
575      *   validate_flags = VALIDATE_G then also skip the validation of PQ.
576      */
577     if (params->p != NULL && ((validate_flags & FFC_PARAMS_VALIDATE_PQ) == 0)) {
578         /* p and q already exists so only generate g */
579         p = params->p;
580         q = params->q;
581         goto g_only;
582         /* otherwise fall thru to validate p & q */
583     }
584
585     /* p & q will be used for generation and validation */
586     p = BN_CTX_get(ctx);
587     q = BN_CTX_get(ctx);
588     if (q == NULL)
589         goto err;
590
591     /*
592      * A.1.1.2 Step (2) AND
593      * A.1.1.3 Step (6)
594      * Return invalid if seedlen  < N
595      */
596     if ((seedlen * 8) < N) {
597         *res = FFC_CHECK_INVALID_SEED_SIZE;
598         goto err;
599     }
600
601     seed_tmp = OPENSSL_malloc(seedlen);
602     if (seed_tmp == NULL)
603         goto err;
604
605     if (seed == NULL) {
606         /* Validation requires the seed to be supplied */
607         if (validate_flags) {
608             *res = FFC_CHECK_MISSING_SEED_OR_COUNTER;
609             goto err;
610         }
611         /* if the seed is not supplied then alloc a seed buffer */
612         seed = OPENSSL_malloc(seedlen);
613         if (seed == NULL)
614             goto err;
615     }
616
617     /* A.1.1.2 Step (11): max loop count = 4L - 1 */
618     counter = 4 * L - 1;
619     /* Validation requires the counter to be supplied */
620     if (validate_flags) {
621         /* A.1.1.3 Step (4) : if (counter > (4L -1)) return INVALID */
622         if (params->pcounter > counter) {
623             *res = FFC_CHECK_INVALID_COUNTER;
624             goto err;
625         }
626         counter = params->pcounter;
627     }
628
629     /*
630      * A.1.1.2 Step (3) AND
631      * A.1.1.3 Step (10)
632      * n = floor(L / hash_outlen) - 1
633      */
634     n = (L - 1 ) / (mdsize << 3);
635
636     /* Calculate 2^(L-1): Used in step A.1.1.2 Step (11.3) */
637     if (!BN_lshift(test, BN_value_one(), L - 1))
638         goto err;
639
640     for (;;) {
641         if (!generate_q_fips186_4(ctx, q, evpmd, qsize, seed, seedlen,
642                                   seed != params->seed, &m, res, cb))
643             goto err;
644         /* A.1.1.3 Step (9): Verify that q matches the expected value */
645         if (validate_flags && (BN_cmp(q, params->q) != 0)) {
646             *res = FFC_CHECK_Q_MISMATCH;
647             goto err;
648         }
649         if(!BN_GENCB_call(cb, 2, 0))
650             goto err;
651         if(!BN_GENCB_call(cb, 3, 0))
652             goto err;
653
654         memcpy(seed_tmp, seed, seedlen);
655         r = generate_p(ctx, evpmd, counter, n, seed_tmp, seedlen, q, p, L, cb,
656                        &pcounter, res);
657         if (r > 0)
658             break; /* found p */
659         if (r < 0)
660             goto err;
661         /*
662          * A.1.1.3 Step (14):
663          * If we get here we failed to get a p for the given seed. If the
664          * seed is not random then it needs to fail (as it will always fail).
665          */
666         if (seed == params->seed) {
667             *res = FFC_CHECK_P_NOT_PRIME;
668             goto err;
669         }
670     }
671     if(!BN_GENCB_call(cb, 2, 1))
672         goto err;
673     /*
674      * Gets here if we found p.
675      * A.1.1.3 Step (14): return error if i != counter OR computed_p != known_p.
676      */
677     if (validate_flags && (pcounter != counter || (BN_cmp(p, params->p) != 0)))
678         goto err;
679
680     /* If validating p & q only then skip the g validation test */
681     if ((validate_flags & FFC_PARAMS_VALIDATE_ALL) == FFC_PARAMS_VALIDATE_PQ)
682         goto pass;
683 g_only:
684     if ((mont = BN_MONT_CTX_new()) == NULL)
685         goto err;
686     if (!BN_MONT_CTX_set(mont, p, ctx))
687         goto err;
688
689     if (((validate_flags & FFC_PARAMS_VALIDATE_G) != 0)
690         && !ffc_params_validate_unverifiable_g(ctx, mont, p, q, params->g,
691                                                tmp, res))
692         goto err;
693
694     /*
695      * A.2.1 Step (1) AND
696      * A.2.3 Step (3) AND
697      * A.2.4 Step (5)
698      * e = (p - 1) / q (i.e- Cofactor 'e' is given by p = q * e + 1)
699      */
700     if (!(BN_sub(pm1, p, BN_value_one()) && BN_div(e, NULL, pm1, q, ctx)))
701         goto err;
702
703     /* Canonical g requires a seed and index to be set */
704     if ((seed != NULL) && (params->gindex != FFC_UNVERIFIABLE_GINDEX)) {
705         canonical_g = 1;
706         if (!generate_canonical_g(ctx, mont, evpmd, g, tmp, p, e,
707                                   params->gindex, seed, seedlen)) {
708             *res = FFC_CHECK_INVALID_G;
709             goto err;
710         }
711         /* A.2.4 Step (13): Return valid if computed_g == g */
712         if (validate_flags && BN_cmp(g, params->g) != 0) {
713             *res = FFC_CHECK_G_MISMATCH;
714             goto err;
715         }
716     } else if (generate) {
717         if (!generate_unverifiable_g(ctx, mont, g, tmp, p, e, pm1, &hret))
718             goto err;
719     }
720
721     if (!BN_GENCB_call(cb, 3, 1))
722         goto err;
723
724     if (generate) {
725         if (p != params->p) {
726             BN_free(params->p);
727             params->p = BN_dup(p);
728         }
729         if (q != params->q) {
730             BN_free(params->q);
731             params->q = BN_dup(q);
732         }
733         if (g != params->g) {
734             BN_free(params->g);
735             params->g = BN_dup(g);
736         }
737         if (params->p == NULL || params->q == NULL || params->g == NULL)
738             goto err;
739         if (!ffc_params_set_validate_params(params, seed, seedlen, pcounter))
740             goto err;
741         params->h = hret;
742     }
743 pass:
744     if ((validate_flags & FFC_PARAMS_VALIDATE_G) != 0 && (canonical_g == 0))
745         /* Return for the case where g is partially valid */
746         ok = FFC_PARAMS_RET_STATUS_UNVERIFIABLE_G;
747     else
748         ok = FFC_PARAMS_RET_STATUS_SUCCESS;
749 err:
750     if (seed != params->seed)
751         OPENSSL_free(seed);
752     OPENSSL_free(seed_tmp);
753     if (ctx != NULL)
754         BN_CTX_end(ctx);
755     BN_CTX_free(ctx);
756     BN_MONT_CTX_free(mont);
757     EVP_MD_free(evpmd_fetch);
758     EVP_MD_CTX_free(mctx);
759     return ok;
760 }
761
762 int ffc_params_FIPS186_2_gen_verify(OPENSSL_CTX *libctx, FFC_PARAMS *params,
763                                     int type, size_t L, size_t N,
764                                     const EVP_MD *evpmd, int validate_flags,
765                                     int *res, BN_GENCB *cb)
766 {
767     int ok = FFC_PARAMS_RET_STATUS_FAILED;
768     unsigned char seed[SHA256_DIGEST_LENGTH];
769     unsigned char buf[SHA256_DIGEST_LENGTH];
770     BIGNUM *r0, *test, *tmp, *g = NULL, *q = NULL, *p = NULL;
771     BN_MONT_CTX *mont = NULL;
772     size_t qsize = N >> 3;
773     int n = 0, m = 0;
774     int counter = 0, pcounter = 0, use_random_seed;
775     int rv;
776     BN_CTX *ctx = NULL;
777     int hret = -1;
778     int generate = (validate_flags == 0);
779     unsigned char *seed_in = params->seed;
780     size_t seed_len = params->seedlen;
781     EVP_MD *evpmd_fetch = NULL;
782
783     *res = 0;
784 #ifdef FIPS_MODULE
785     /*
786      * FIPS 186-4 states that validation can only be done for this pair.
787      * (Even though the original spec allowed L = 512 + 64*j (j = 0.. 8))
788      */
789     if (L != 1024 || N != 160) {
790         *res = FFC_CHECK_BAD_LN_PAIR;
791         return FFC_PARAMS_RET_STATUS_FAILED;
792     }
793 #endif
794     if (qsize != SHA_DIGEST_LENGTH
795         && qsize != SHA224_DIGEST_LENGTH
796         && qsize != SHA256_DIGEST_LENGTH) {
797         /* invalid q size */
798         *res = FFC_CHECK_INVALID_Q_VALUE;
799         return FFC_PARAMS_RET_STATUS_FAILED;
800     }
801
802     if (evpmd == NULL) {
803         evpmd_fetch = fetch_default_md(libctx, qsize * 8);
804         evpmd = evpmd_fetch;
805     } else {
806         rv = EVP_MD_size(evpmd);
807         if (rv <= 0)
808             return 0;
809         qsize = (size_t)rv;
810     }
811
812     if (L < 512)
813         L = 512;
814
815     L = (L + 63) / 64 * 64;
816
817     if (seed_in != NULL) {
818         if (seed_len < qsize) {
819             *res = FFC_CHECK_INVALID_SEED_SIZE;
820             return 0;
821         }
822         if (seed_len > qsize) {
823             /* Only consume as much seed as is expected. */
824             seed_len = qsize;
825         }
826         memcpy(seed, seed_in, seed_len);
827     }
828
829     ctx = BN_CTX_new_ex(libctx);
830     if (ctx == NULL)
831         goto err;
832
833     BN_CTX_start(ctx);
834
835     r0 = BN_CTX_get(ctx);
836     g = BN_CTX_get(ctx);
837     q = BN_CTX_get(ctx);
838     p = BN_CTX_get(ctx);
839     tmp = BN_CTX_get(ctx);
840     test = BN_CTX_get(ctx);
841     if (test == NULL)
842         goto err;
843
844     if (!BN_lshift(test, BN_value_one(), L - 1))
845         goto err;
846
847     if (generate) {
848         /* For generation: p & q must both be NULL or NON-NULL */
849         if ((params->p != NULL) != (params->q != NULL)) {
850             *res = FFC_CHECK_INVALID_PQ;
851             goto err;
852         }
853     } else {
854         if ((validate_flags & FFC_PARAMS_VALIDATE_PQ) != 0) {
855             /* Validation of p,q requires seed and counter to be valid */
856             if (seed_in == NULL || params->pcounter < 0) {
857                 *res = FFC_CHECK_MISSING_SEED_OR_COUNTER;
858                 goto err;
859             }
860         }
861         if ((validate_flags & FFC_PARAMS_VALIDATE_G) != 0) {
862             /* validation of g also requires g to be set */
863             if (params->g == NULL) {
864                 *res = FFC_CHECK_INVALID_G;
865                 goto err;
866             }
867         }
868     }
869
870     if (params->p != NULL && ((validate_flags & FFC_PARAMS_VALIDATE_PQ) == 0)) {
871         /* p and q already exists so only generate g */
872         p = params->p;
873         q = params->q;
874         goto g_only;
875         /* otherwise fall thru to validate p and q */
876     }
877
878     use_random_seed = (seed_in == NULL);
879     for (;;) {
880         if (!generate_q_fips186_2(ctx, q, evpmd, buf, seed, qsize,
881                                   use_random_seed, &m, res, cb))
882             goto err;
883
884         if (!BN_GENCB_call(cb, 2, 0))
885             goto err;
886         if (!BN_GENCB_call(cb, 3, 0))
887             goto err;
888
889         /* step 6 */
890         n = (L - 1) / 160;
891         counter = 4 * L - 1; /* Was 4096 */
892         /* Validation requires the counter to be supplied */
893         if (validate_flags) {
894             if (params->pcounter > counter) {
895                 *res = FFC_CHECK_INVALID_COUNTER;
896                 goto err;
897             }
898             counter = params->pcounter;
899         }
900
901         rv = generate_p(ctx, evpmd, counter, n, buf, qsize, q, p, L, cb,
902                         &pcounter, res);
903         if (rv > 0)
904             break; /* found it */
905         if (rv == -1)
906             goto err;
907         /* This is what the old code did - probably not a good idea! */
908         use_random_seed = 1;
909     }
910
911     if (!BN_GENCB_call(cb, 2, 1))
912         goto err;
913
914     if (validate_flags) {
915         if (pcounter != counter) {
916             *res = FFC_CHECK_COUNTER_MISMATCH;
917             goto err;
918         }
919         if (BN_cmp(p, params->p) != 0) {
920             *res = FFC_CHECK_P_MISMATCH;
921             goto err;
922         }
923     }
924     /* If validating p & q only then skip the g validation test */
925     if ((validate_flags & FFC_PARAMS_VALIDATE_ALL) == FFC_PARAMS_VALIDATE_PQ)
926         goto pass;
927 g_only:
928     if ((mont = BN_MONT_CTX_new()) == NULL)
929         goto err;
930     if (!BN_MONT_CTX_set(mont, p, ctx))
931         goto err;
932
933     if (generate) {
934         /* We now need to generate g */
935         /* set test = p - 1 */
936         if (!BN_sub(test, p, BN_value_one()))
937             goto err;
938         /* Set r0 = (p - 1) / q */
939         if (!BN_div(r0, NULL, test, q, ctx))
940             goto err;
941         if (!generate_unverifiable_g(ctx, mont, g, tmp, p, r0, test, &hret))
942             goto err;
943     } else if (((validate_flags & FFC_PARAMS_VALIDATE_G) != 0)
944                && !ffc_params_validate_unverifiable_g(ctx, mont, p, q,
945                                                       params->g, tmp, res)) {
946         goto err;
947     }
948
949     if (!BN_GENCB_call(cb, 3, 1))
950         goto err;
951
952     if (generate) {
953         if (p != params->p) {
954             BN_free(params->p);
955             params->p = BN_dup(p);
956         }
957         if (q != params->q) {
958             BN_free(params->q);
959             params->q = BN_dup(q);
960         }
961         if (g != params->g) {
962             BN_free(params->g);
963             params->g = BN_dup(g);
964         }
965         if (params->p == NULL || params->q == NULL || params->g == NULL)
966             goto err;
967         if (!ffc_params_set_validate_params(params, seed, qsize, pcounter))
968             goto err;
969         params->h = hret;
970     }
971 pass:
972     if ((validate_flags & FFC_PARAMS_VALIDATE_G) != 0)
973         ok = FFC_PARAMS_RET_STATUS_UNVERIFIABLE_G;
974     else
975         ok = FFC_PARAMS_RET_STATUS_SUCCESS;
976 err:
977     if (ctx != NULL)
978         BN_CTX_end(ctx);
979     BN_CTX_free(ctx);
980     EVP_MD_free(evpmd_fetch);
981     BN_MONT_CTX_free(mont);
982     return ok;
983 }
984
985 int ffc_params_FIPS186_4_generate(OPENSSL_CTX *libctx, FFC_PARAMS *params,
986                                   int type, size_t L, size_t N,
987                                   const EVP_MD *evpmd, int *res, BN_GENCB *cb)
988 {
989     return ffc_params_FIPS186_4_gen_verify(libctx, params, type, L, N, evpmd, 0,
990                                            res, cb);
991 }
992
993 /* This should no longer be used in FIPS mode */
994 int ffc_params_FIPS186_2_generate(OPENSSL_CTX *libctx, FFC_PARAMS *params,
995                                   int type, size_t L, size_t N,
996                                   const EVP_MD *evpmd, int *res, BN_GENCB *cb)
997 {
998     return ffc_params_FIPS186_2_gen_verify(libctx, params, type, L, N, evpmd,
999                                            0, res, cb);
1000 }