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