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