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