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