1 | /* |
2 | * Copyright 1995-2018 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 | * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186, |
12 | * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB |
13 | * 180-1) |
14 | */ |
15 | #define xxxHASH EVP_sha1() |
16 | |
17 | #include <openssl/opensslconf.h> |
18 | #include <stdio.h> |
19 | #include "internal/cryptlib.h" |
20 | #include <openssl/evp.h> |
21 | #include <openssl/bn.h> |
22 | #include <openssl/rand.h> |
23 | #include <openssl/sha.h> |
24 | #include "dsa_local.h" |
25 | |
26 | int DSA_generate_parameters_ex(DSA *ret, int bits, |
27 | const unsigned char *seed_in, int seed_len, |
28 | int *counter_ret, unsigned long *h_ret, |
29 | BN_GENCB *cb) |
30 | { |
31 | if (ret->meth->dsa_paramgen) |
32 | return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len, |
33 | counter_ret, h_ret, cb); |
34 | else { |
35 | const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1(); |
36 | size_t qbits = EVP_MD_size(evpmd) * 8; |
37 | |
38 | return dsa_builtin_paramgen(ret, bits, qbits, evpmd, |
39 | seed_in, seed_len, NULL, counter_ret, |
40 | h_ret, cb); |
41 | } |
42 | } |
43 | |
44 | int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, |
45 | const EVP_MD *evpmd, const unsigned char *seed_in, |
46 | size_t seed_len, unsigned char *seed_out, |
47 | int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) |
48 | { |
49 | int ok = 0; |
50 | unsigned char seed[SHA256_DIGEST_LENGTH]; |
51 | unsigned char md[SHA256_DIGEST_LENGTH]; |
52 | unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; |
53 | BIGNUM *r0, *W, *X, *c, *test; |
54 | BIGNUM *g = NULL, *q = NULL, *p = NULL; |
55 | BN_MONT_CTX *mont = NULL; |
56 | int i, k, n = 0, m = 0, qsize = qbits >> 3; |
57 | int counter = 0; |
58 | int r = 0; |
59 | BN_CTX *ctx = NULL; |
60 | unsigned int h = 2; |
61 | |
62 | if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH && |
63 | qsize != SHA256_DIGEST_LENGTH) |
64 | /* invalid q size */ |
65 | return 0; |
66 | |
67 | if (evpmd == NULL) { |
68 | if (qsize == SHA_DIGEST_LENGTH) |
69 | evpmd = EVP_sha1(); |
70 | else if (qsize == SHA224_DIGEST_LENGTH) |
71 | evpmd = EVP_sha224(); |
72 | else |
73 | evpmd = EVP_sha256(); |
74 | } else { |
75 | qsize = EVP_MD_size(evpmd); |
76 | } |
77 | |
78 | if (bits < 512) |
79 | bits = 512; |
80 | |
81 | bits = (bits + 63) / 64 * 64; |
82 | |
83 | if (seed_in != NULL) { |
84 | if (seed_len < (size_t)qsize) { |
85 | DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN, DSA_R_SEED_LEN_SMALL); |
86 | return 0; |
87 | } |
88 | if (seed_len > (size_t)qsize) { |
89 | /* Only consume as much seed as is expected. */ |
90 | seed_len = qsize; |
91 | } |
92 | memcpy(seed, seed_in, seed_len); |
93 | } |
94 | |
95 | if ((mont = BN_MONT_CTX_new()) == NULL) |
96 | goto err; |
97 | |
98 | if ((ctx = BN_CTX_new()) == NULL) |
99 | goto err; |
100 | |
101 | BN_CTX_start(ctx); |
102 | |
103 | r0 = BN_CTX_get(ctx); |
104 | g = BN_CTX_get(ctx); |
105 | W = BN_CTX_get(ctx); |
106 | q = BN_CTX_get(ctx); |
107 | X = BN_CTX_get(ctx); |
108 | c = BN_CTX_get(ctx); |
109 | p = BN_CTX_get(ctx); |
110 | test = BN_CTX_get(ctx); |
111 | |
112 | if (test == NULL) |
113 | goto err; |
114 | |
115 | if (!BN_lshift(test, BN_value_one(), bits - 1)) |
116 | goto err; |
117 | |
118 | for (;;) { |
119 | for (;;) { /* find q */ |
120 | int use_random_seed = (seed_in == NULL); |
121 | |
122 | /* step 1 */ |
123 | if (!BN_GENCB_call(cb, 0, m++)) |
124 | goto err; |
125 | |
126 | if (use_random_seed) { |
127 | if (RAND_bytes(seed, qsize) <= 0) |
128 | goto err; |
129 | } else { |
130 | /* If we come back through, use random seed next time. */ |
131 | seed_in = NULL; |
132 | } |
133 | memcpy(buf, seed, qsize); |
134 | memcpy(buf2, seed, qsize); |
135 | /* precompute "SEED + 1" for step 7: */ |
136 | for (i = qsize - 1; i >= 0; i--) { |
137 | buf[i]++; |
138 | if (buf[i] != 0) |
139 | break; |
140 | } |
141 | |
142 | /* step 2 */ |
143 | if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) |
144 | goto err; |
145 | if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) |
146 | goto err; |
147 | for (i = 0; i < qsize; i++) |
148 | md[i] ^= buf2[i]; |
149 | |
150 | /* step 3 */ |
151 | md[0] |= 0x80; |
152 | md[qsize - 1] |= 0x01; |
153 | if (!BN_bin2bn(md, qsize, q)) |
154 | goto err; |
155 | |
156 | /* step 4 */ |
157 | r = BN_check_prime(q, ctx, cb); |
158 | if (r > 0) |
159 | break; |
160 | if (r != 0) |
161 | goto err; |
162 | |
163 | /* do a callback call */ |
164 | /* step 5 */ |
165 | } |
166 | |
167 | if (!BN_GENCB_call(cb, 2, 0)) |
168 | goto err; |
169 | if (!BN_GENCB_call(cb, 3, 0)) |
170 | goto err; |
171 | |
172 | /* step 6 */ |
173 | counter = 0; |
174 | /* "offset = 2" */ |
175 | |
176 | n = (bits - 1) / 160; |
177 | |
178 | for (;;) { |
179 | if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) |
180 | goto err; |
181 | |
182 | /* step 7 */ |
183 | BN_zero(W); |
184 | /* now 'buf' contains "SEED + offset - 1" */ |
185 | for (k = 0; k <= n; k++) { |
186 | /* |
187 | * obtain "SEED + offset + k" by incrementing: |
188 | */ |
189 | for (i = qsize - 1; i >= 0; i--) { |
190 | buf[i]++; |
191 | if (buf[i] != 0) |
192 | break; |
193 | } |
194 | |
195 | if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) |
196 | goto err; |
197 | |
198 | /* step 8 */ |
199 | if (!BN_bin2bn(md, qsize, r0)) |
200 | goto err; |
201 | if (!BN_lshift(r0, r0, (qsize << 3) * k)) |
202 | goto err; |
203 | if (!BN_add(W, W, r0)) |
204 | goto err; |
205 | } |
206 | |
207 | /* more of step 8 */ |
208 | if (!BN_mask_bits(W, bits - 1)) |
209 | goto err; |
210 | if (!BN_copy(X, W)) |
211 | goto err; |
212 | if (!BN_add(X, X, test)) |
213 | goto err; |
214 | |
215 | /* step 9 */ |
216 | if (!BN_lshift1(r0, q)) |
217 | goto err; |
218 | if (!BN_mod(c, X, r0, ctx)) |
219 | goto err; |
220 | if (!BN_sub(r0, c, BN_value_one())) |
221 | goto err; |
222 | if (!BN_sub(p, X, r0)) |
223 | goto err; |
224 | |
225 | /* step 10 */ |
226 | if (BN_cmp(p, test) >= 0) { |
227 | /* step 11 */ |
228 | r = BN_check_prime(p, ctx, cb); |
229 | if (r > 0) |
230 | goto end; /* found it */ |
231 | if (r != 0) |
232 | goto err; |
233 | } |
234 | |
235 | /* step 13 */ |
236 | counter++; |
237 | /* "offset = offset + n + 1" */ |
238 | |
239 | /* step 14 */ |
240 | if (counter >= 4096) |
241 | break; |
242 | } |
243 | } |
244 | end: |
245 | if (!BN_GENCB_call(cb, 2, 1)) |
246 | goto err; |
247 | |
248 | /* We now need to generate g */ |
249 | /* Set r0=(p-1)/q */ |
250 | if (!BN_sub(test, p, BN_value_one())) |
251 | goto err; |
252 | if (!BN_div(r0, NULL, test, q, ctx)) |
253 | goto err; |
254 | |
255 | if (!BN_set_word(test, h)) |
256 | goto err; |
257 | if (!BN_MONT_CTX_set(mont, p, ctx)) |
258 | goto err; |
259 | |
260 | for (;;) { |
261 | /* g=test^r0%p */ |
262 | if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) |
263 | goto err; |
264 | if (!BN_is_one(g)) |
265 | break; |
266 | if (!BN_add(test, test, BN_value_one())) |
267 | goto err; |
268 | h++; |
269 | } |
270 | |
271 | if (!BN_GENCB_call(cb, 3, 1)) |
272 | goto err; |
273 | |
274 | ok = 1; |
275 | err: |
276 | if (ok) { |
277 | BN_free(ret->p); |
278 | BN_free(ret->q); |
279 | BN_free(ret->g); |
280 | ret->p = BN_dup(p); |
281 | ret->q = BN_dup(q); |
282 | ret->g = BN_dup(g); |
283 | ret->dirty_cnt++; |
284 | if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { |
285 | ok = 0; |
286 | goto err; |
287 | } |
288 | if (counter_ret != NULL) |
289 | *counter_ret = counter; |
290 | if (h_ret != NULL) |
291 | *h_ret = h; |
292 | if (seed_out) |
293 | memcpy(seed_out, seed, qsize); |
294 | } |
295 | BN_CTX_end(ctx); |
296 | BN_CTX_free(ctx); |
297 | BN_MONT_CTX_free(mont); |
298 | return ok; |
299 | } |
300 | |
301 | /* |
302 | * This is a parameter generation algorithm for the DSA2 algorithm as |
303 | * described in FIPS 186-3. |
304 | */ |
305 | |
306 | int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, |
307 | const EVP_MD *evpmd, const unsigned char *seed_in, |
308 | size_t seed_len, int idx, unsigned char *seed_out, |
309 | int *counter_ret, unsigned long *h_ret, |
310 | BN_GENCB *cb) |
311 | { |
312 | int ok = -1; |
313 | unsigned char *seed = NULL, *seed_tmp = NULL; |
314 | unsigned char md[EVP_MAX_MD_SIZE]; |
315 | int mdsize; |
316 | BIGNUM *r0, *W, *X, *c, *test; |
317 | BIGNUM *g = NULL, *q = NULL, *p = NULL; |
318 | BN_MONT_CTX *mont = NULL; |
319 | int i, k, n = 0, m = 0, qsize = N >> 3; |
320 | int counter = 0; |
321 | int r = 0; |
322 | BN_CTX *ctx = NULL; |
323 | EVP_MD_CTX *mctx = EVP_MD_CTX_new(); |
324 | unsigned int h = 2; |
325 | |
326 | if (mctx == NULL) |
327 | goto err; |
328 | |
329 | /* make sure L > N, otherwise we'll get trapped in an infinite loop */ |
330 | if (L <= N) { |
331 | DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); |
332 | goto err; |
333 | } |
334 | |
335 | if (evpmd == NULL) { |
336 | if (N == 160) |
337 | evpmd = EVP_sha1(); |
338 | else if (N == 224) |
339 | evpmd = EVP_sha224(); |
340 | else |
341 | evpmd = EVP_sha256(); |
342 | } |
343 | |
344 | mdsize = EVP_MD_size(evpmd); |
345 | /* If unverifiable g generation only don't need seed */ |
346 | if (!ret->p || !ret->q || idx >= 0) { |
347 | if (seed_len == 0) |
348 | seed_len = mdsize; |
349 | |
350 | seed = OPENSSL_malloc(seed_len); |
351 | |
352 | if (seed_out) |
353 | seed_tmp = seed_out; |
354 | else |
355 | seed_tmp = OPENSSL_malloc(seed_len); |
356 | |
357 | if (seed == NULL || seed_tmp == NULL) |
358 | goto err; |
359 | |
360 | if (seed_in) |
361 | memcpy(seed, seed_in, seed_len); |
362 | |
363 | } |
364 | |
365 | if ((ctx = BN_CTX_new()) == NULL) |
366 | goto err; |
367 | |
368 | if ((mont = BN_MONT_CTX_new()) == NULL) |
369 | goto err; |
370 | |
371 | BN_CTX_start(ctx); |
372 | r0 = BN_CTX_get(ctx); |
373 | g = BN_CTX_get(ctx); |
374 | W = BN_CTX_get(ctx); |
375 | X = BN_CTX_get(ctx); |
376 | c = BN_CTX_get(ctx); |
377 | test = BN_CTX_get(ctx); |
378 | if (test == NULL) |
379 | goto err; |
380 | |
381 | /* if p, q already supplied generate g only */ |
382 | if (ret->p && ret->q) { |
383 | p = ret->p; |
384 | q = ret->q; |
385 | if (idx >= 0) |
386 | memcpy(seed_tmp, seed, seed_len); |
387 | goto g_only; |
388 | } else { |
389 | p = BN_CTX_get(ctx); |
390 | q = BN_CTX_get(ctx); |
391 | if (q == NULL) |
392 | goto err; |
393 | } |
394 | |
395 | if (!BN_lshift(test, BN_value_one(), L - 1)) |
396 | goto err; |
397 | for (;;) { |
398 | for (;;) { /* find q */ |
399 | unsigned char *pmd; |
400 | /* step 1 */ |
401 | if (!BN_GENCB_call(cb, 0, m++)) |
402 | goto err; |
403 | |
404 | if (!seed_in) { |
405 | if (RAND_bytes(seed, seed_len) <= 0) |
406 | goto err; |
407 | } |
408 | /* step 2 */ |
409 | if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) |
410 | goto err; |
411 | /* Take least significant bits of md */ |
412 | if (mdsize > qsize) |
413 | pmd = md + mdsize - qsize; |
414 | else |
415 | pmd = md; |
416 | |
417 | if (mdsize < qsize) |
418 | memset(md + mdsize, 0, qsize - mdsize); |
419 | |
420 | /* step 3 */ |
421 | pmd[0] |= 0x80; |
422 | pmd[qsize - 1] |= 0x01; |
423 | if (!BN_bin2bn(pmd, qsize, q)) |
424 | goto err; |
425 | |
426 | /* step 4 */ |
427 | r = BN_check_prime(q, ctx, cb); |
428 | if (r > 0) |
429 | break; |
430 | if (r != 0) |
431 | goto err; |
432 | /* Provided seed didn't produce a prime: error */ |
433 | if (seed_in) { |
434 | ok = 0; |
435 | DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME); |
436 | goto err; |
437 | } |
438 | |
439 | /* do a callback call */ |
440 | /* step 5 */ |
441 | } |
442 | /* Copy seed to seed_out before we mess with it */ |
443 | if (seed_out) |
444 | memcpy(seed_out, seed, seed_len); |
445 | |
446 | if (!BN_GENCB_call(cb, 2, 0)) |
447 | goto err; |
448 | if (!BN_GENCB_call(cb, 3, 0)) |
449 | goto err; |
450 | |
451 | /* step 6 */ |
452 | counter = 0; |
453 | /* "offset = 1" */ |
454 | |
455 | n = (L - 1) / (mdsize << 3); |
456 | |
457 | for (;;) { |
458 | if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) |
459 | goto err; |
460 | |
461 | /* step 7 */ |
462 | BN_zero(W); |
463 | /* now 'buf' contains "SEED + offset - 1" */ |
464 | for (k = 0; k <= n; k++) { |
465 | /* |
466 | * obtain "SEED + offset + k" by incrementing: |
467 | */ |
468 | for (i = seed_len - 1; i >= 0; i--) { |
469 | seed[i]++; |
470 | if (seed[i] != 0) |
471 | break; |
472 | } |
473 | |
474 | if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) |
475 | goto err; |
476 | |
477 | /* step 8 */ |
478 | if (!BN_bin2bn(md, mdsize, r0)) |
479 | goto err; |
480 | if (!BN_lshift(r0, r0, (mdsize << 3) * k)) |
481 | goto err; |
482 | if (!BN_add(W, W, r0)) |
483 | goto err; |
484 | } |
485 | |
486 | /* more of step 8 */ |
487 | if (!BN_mask_bits(W, L - 1)) |
488 | goto err; |
489 | if (!BN_copy(X, W)) |
490 | goto err; |
491 | if (!BN_add(X, X, test)) |
492 | goto err; |
493 | |
494 | /* step 9 */ |
495 | if (!BN_lshift1(r0, q)) |
496 | goto err; |
497 | if (!BN_mod(c, X, r0, ctx)) |
498 | goto err; |
499 | if (!BN_sub(r0, c, BN_value_one())) |
500 | goto err; |
501 | if (!BN_sub(p, X, r0)) |
502 | goto err; |
503 | |
504 | /* step 10 */ |
505 | if (BN_cmp(p, test) >= 0) { |
506 | /* step 11 */ |
507 | r = BN_check_prime(p, ctx, cb); |
508 | if (r > 0) |
509 | goto end; /* found it */ |
510 | if (r != 0) |
511 | goto err; |
512 | } |
513 | |
514 | /* step 13 */ |
515 | counter++; |
516 | /* "offset = offset + n + 1" */ |
517 | |
518 | /* step 14 */ |
519 | if (counter >= (int)(4 * L)) |
520 | break; |
521 | } |
522 | if (seed_in) { |
523 | ok = 0; |
524 | DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); |
525 | goto err; |
526 | } |
527 | } |
528 | end: |
529 | if (!BN_GENCB_call(cb, 2, 1)) |
530 | goto err; |
531 | |
532 | g_only: |
533 | |
534 | /* We now need to generate g */ |
535 | /* Set r0=(p-1)/q */ |
536 | if (!BN_sub(test, p, BN_value_one())) |
537 | goto err; |
538 | if (!BN_div(r0, NULL, test, q, ctx)) |
539 | goto err; |
540 | |
541 | if (idx < 0) { |
542 | if (!BN_set_word(test, h)) |
543 | goto err; |
544 | } else |
545 | h = 1; |
546 | if (!BN_MONT_CTX_set(mont, p, ctx)) |
547 | goto err; |
548 | |
549 | for (;;) { |
550 | static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e }; |
551 | if (idx >= 0) { |
552 | md[0] = idx & 0xff; |
553 | md[1] = (h >> 8) & 0xff; |
554 | md[2] = h & 0xff; |
555 | if (!EVP_DigestInit_ex(mctx, evpmd, NULL)) |
556 | goto err; |
557 | if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len)) |
558 | goto err; |
559 | if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen))) |
560 | goto err; |
561 | if (!EVP_DigestUpdate(mctx, md, 3)) |
562 | goto err; |
563 | if (!EVP_DigestFinal_ex(mctx, md, NULL)) |
564 | goto err; |
565 | if (!BN_bin2bn(md, mdsize, test)) |
566 | goto err; |
567 | } |
568 | /* g=test^r0%p */ |
569 | if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) |
570 | goto err; |
571 | if (!BN_is_one(g)) |
572 | break; |
573 | if (idx < 0 && !BN_add(test, test, BN_value_one())) |
574 | goto err; |
575 | h++; |
576 | if (idx >= 0 && h > 0xffff) |
577 | goto err; |
578 | } |
579 | |
580 | if (!BN_GENCB_call(cb, 3, 1)) |
581 | goto err; |
582 | |
583 | ok = 1; |
584 | err: |
585 | if (ok == 1) { |
586 | if (p != ret->p) { |
587 | BN_free(ret->p); |
588 | ret->p = BN_dup(p); |
589 | } |
590 | if (q != ret->q) { |
591 | BN_free(ret->q); |
592 | ret->q = BN_dup(q); |
593 | } |
594 | BN_free(ret->g); |
595 | ret->g = BN_dup(g); |
596 | if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { |
597 | ok = -1; |
598 | goto err; |
599 | } |
600 | ret->dirty_cnt++; |
601 | if (counter_ret != NULL) |
602 | *counter_ret = counter; |
603 | if (h_ret != NULL) |
604 | *h_ret = h; |
605 | } |
606 | OPENSSL_free(seed); |
607 | if (seed_out != seed_tmp) |
608 | OPENSSL_free(seed_tmp); |
609 | BN_CTX_end(ctx); |
610 | BN_CTX_free(ctx); |
611 | BN_MONT_CTX_free(mont); |
612 | EVP_MD_CTX_free(mctx); |
613 | return ok; |
614 | } |
615 | |