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