ffc_params_generate.c 32 KB

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