crypto/dsa/dsa_gen.c

   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_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         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_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
 158                                         use_random_seed, cb);
 159             if (r > 0)
 160                 break;
 161             if (r != 0)
 162                 goto err;
 163
 164             /* do a callback call */
 165             /* step 5 */
 166         }
 167
 168         if (!BN_GENCB_call(cb, 2, 0))
 169             goto err;
 170         if (!BN_GENCB_call(cb, 3, 0))
 171             goto err;
 172
 173         /* step 6 */
 174         counter = 0;
 175         /* "offset = 2" */
 176
 177         n = (bits - 1) / 160;
 178
 179         for (;;) {
 180             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
 181                 goto err;
 182
 183             /* step 7 */
 184             BN_zero(W);
 185             /* now 'buf' contains "SEED + offset - 1" */
 186             for (k = 0; k <= n; k++) {
 187                 /*
 188                  * obtain "SEED + offset + k" by incrementing:
 189                  */
 190                 for (i = qsize - 1; i >= 0; i--) {
 191                     buf[i]++;
 192                     if (buf[i] != 0)
 193                         break;
 194                 }
 195
 196                 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
 197                     goto err;
 198
 199                 /* step 8 */
 200                 if (!BN_bin2bn(md, qsize, r0))
 201                     goto err;
 202                 if (!BN_lshift(r0, r0, (qsize << 3) * k))
 203                     goto err;
 204                 if (!BN_add(W, W, r0))
 205                     goto err;
 206             }
 207
 208             /* more of step 8 */
 209             if (!BN_mask_bits(W, bits - 1))
 210                 goto err;
 211             if (!BN_copy(X, W))
 212                 goto err;
 213             if (!BN_add(X, X, test))
 214                 goto err;
 215
 216             /* step 9 */
 217             if (!BN_lshift1(r0, q))
 218                 goto err;
 219             if (!BN_mod(c, X, r0, ctx))
 220                 goto err;
 221             if (!BN_sub(r0, c, BN_value_one()))
 222                 goto err;
 223             if (!BN_sub(p, X, r0))
 224                 goto err;
 225
 226             /* step 10 */
 227             if (BN_cmp(p, test) >= 0) {
 228                 /* step 11 */
 229                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 230                 if (r > 0)
 231                     goto end;   /* found it */
 232                 if (r != 0)
 233                     goto err;
 234             }
 235
 236             /* step 13 */
 237             counter++;
 238             /* "offset = offset + n + 1" */
 239
 240             /* step 14 */
 241             if (counter >= 4096)
 242                 break;
 243         }
 244     }
 245  end:
 246     if (!BN_GENCB_call(cb, 2, 1))
 247         goto err;
 248
 249     /* We now need to generate g */
 250     /* Set r0=(p-1)/q */
 251     if (!BN_sub(test, p, BN_value_one()))
 252         goto err;
 253     if (!BN_div(r0, NULL, test, q, ctx))
 254         goto err;
 255
 256     if (!BN_set_word(test, h))
 257         goto err;
 258     if (!BN_MONT_CTX_set(mont, p, ctx))
 259         goto err;
 260
 261     for (;;) {
 262         /* g=test^r0%p */
 263         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
 264             goto err;
 265         if (!BN_is_one(g))
 266             break;
 267         if (!BN_add(test, test, BN_value_one()))
 268             goto err;
 269         h++;
 270     }
 271
 272     if (!BN_GENCB_call(cb, 3, 1))
 273         goto err;
 274
 275     ok = 1;
 276  err:
 277     if (ok) {
 278         BN_free(ret->p);
 279         BN_free(ret->q);
 280         BN_free(ret->g);
 281         ret->p = BN_dup(p);
 282         ret->q = BN_dup(q);
 283         ret->g = BN_dup(g);
 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     if (ctx)
 296         BN_CTX_end(ctx);
 297     BN_CTX_free(ctx);
 298     BN_MONT_CTX_free(mont);
 299     return ok;
 300 }
 301
 302 /*
 303  * This is a parameter generation algorithm for the DSA2 algorithm as
 304  * described in FIPS 186-3.
 305  */
 306
 307 int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
 308                           const EVP_MD *evpmd, const unsigned char *seed_in,
 309                           size_t seed_len, int idx, unsigned char *seed_out,
 310                           int *counter_ret, unsigned long *h_ret,
 311                           BN_GENCB *cb)
 312 {
 313     int ok = -1;
 314     unsigned char *seed = NULL, *seed_tmp = NULL;
 315     unsigned char md[EVP_MAX_MD_SIZE];
 316     int mdsize;
 317     BIGNUM *r0, *W, *X, *c, *test;
 318     BIGNUM *g = NULL, *q = NULL, *p = NULL;
 319     BN_MONT_CTX *mont = NULL;
 320     int i, k, n = 0, m = 0, qsize = N >> 3;
 321     int counter = 0;
 322     int r = 0;
 323     BN_CTX *ctx = NULL;
 324     EVP_MD_CTX *mctx = EVP_MD_CTX_new();
 325     unsigned int h = 2;
 326
 327     if (mctx == NULL)
 328         goto err;
 329
 330     /* make sure L > N, otherwise we'll get trapped in an infinite loop */
 331     if (L <= N) {
 332         DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
 333         goto err;
 334     }
 335
 336     if (evpmd == NULL) {
 337         if (N == 160)
 338             evpmd = EVP_sha1();
 339         else if (N == 224)
 340             evpmd = EVP_sha224();
 341         else
 342             evpmd = EVP_sha256();
 343     }
 344
 345     mdsize = EVP_MD_size(evpmd);
 346     /* If unverifiable g generation only don't need seed */
 347     if (!ret->p || !ret->q || idx >= 0) {
 348         if (seed_len == 0)
 349             seed_len = mdsize;
 350
 351         seed = OPENSSL_malloc(seed_len);
 352
 353         if (seed_out)
 354             seed_tmp = seed_out;
 355         else
 356             seed_tmp = OPENSSL_malloc(seed_len);
 357
 358         if (seed == NULL || seed_tmp == NULL)
 359             goto err;
 360
 361         if (seed_in)
 362             memcpy(seed, seed_in, seed_len);
 363
 364     }
 365
 366     if ((ctx = BN_CTX_new()) == NULL)
 367         goto err;
 368
 369     if ((mont = BN_MONT_CTX_new()) == NULL)
 370         goto err;
 371
 372     BN_CTX_start(ctx);
 373     r0 = BN_CTX_get(ctx);
 374     g = BN_CTX_get(ctx);
 375     W = BN_CTX_get(ctx);
 376     X = BN_CTX_get(ctx);
 377     c = BN_CTX_get(ctx);
 378     test = BN_CTX_get(ctx);
 379     if (test == NULL)
 380         goto err;
 381
 382     /* if p, q already supplied generate g only */
 383     if (ret->p && ret->q) {
 384         p = ret->p;
 385         q = ret->q;
 386         if (idx >= 0)
 387             memcpy(seed_tmp, seed, seed_len);
 388         goto g_only;
 389     } else {
 390         p = BN_CTX_get(ctx);
 391         q = BN_CTX_get(ctx);
 392         if (q == NULL)
 393             goto err;
 394     }
 395
 396     if (!BN_lshift(test, BN_value_one(), L - 1))
 397         goto err;
 398     for (;;) {
 399         for (;;) {              /* find q */
 400             unsigned char *pmd;
 401             /* step 1 */
 402             if (!BN_GENCB_call(cb, 0, m++))
 403                 goto err;
 404
 405             if (!seed_in) {
 406                 if (RAND_bytes(seed, seed_len) <= 0)
 407                     goto err;
 408             }
 409             /* step 2 */
 410             if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
 411                 goto err;
 412             /* Take least significant bits of md */
 413             if (mdsize > qsize)
 414                 pmd = md + mdsize - qsize;
 415             else
 416                 pmd = md;
 417
 418             if (mdsize < qsize)
 419                 memset(md + mdsize, 0, qsize - mdsize);
 420
 421             /* step 3 */
 422             pmd[0] |= 0x80;
 423             pmd[qsize - 1] |= 0x01;
 424             if (!BN_bin2bn(pmd, qsize, q))
 425                 goto err;
 426
 427             /* step 4 */
 428             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
 429                                         seed_in ? 1 : 0, cb);
 430             if (r > 0)
 431                 break;
 432             if (r != 0)
 433                 goto err;
 434             /* Provided seed didn't produce a prime: error */
 435             if (seed_in) {
 436                 ok = 0;
 437                 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
 438                 goto err;
 439             }
 440
 441             /* do a callback call */
 442             /* step 5 */
 443         }
 444         /* Copy seed to seed_out before we mess with it */
 445         if (seed_out)
 446             memcpy(seed_out, seed, seed_len);
 447
 448         if (!BN_GENCB_call(cb, 2, 0))
 449             goto err;
 450         if (!BN_GENCB_call(cb, 3, 0))
 451             goto err;
 452
 453         /* step 6 */
 454         counter = 0;
 455         /* "offset = 1" */
 456
 457         n = (L - 1) / (mdsize << 3);
 458
 459         for (;;) {
 460             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
 461                 goto err;
 462
 463             /* step 7 */
 464             BN_zero(W);
 465             /* now 'buf' contains "SEED + offset - 1" */
 466             for (k = 0; k <= n; k++) {
 467                 /*
 468                  * obtain "SEED + offset + k" by incrementing:
 469                  */
 470                 for (i = seed_len - 1; i >= 0; i--) {
 471                     seed[i]++;
 472                     if (seed[i] != 0)
 473                         break;
 474                 }
 475
 476                 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
 477                     goto err;
 478
 479                 /* step 8 */
 480                 if (!BN_bin2bn(md, mdsize, r0))
 481                     goto err;
 482                 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
 483                     goto err;
 484                 if (!BN_add(W, W, r0))
 485                     goto err;
 486             }
 487
 488             /* more of step 8 */
 489             if (!BN_mask_bits(W, L - 1))
 490                 goto err;
 491             if (!BN_copy(X, W))
 492                 goto err;
 493             if (!BN_add(X, X, test))
 494                 goto err;
 495
 496             /* step 9 */
 497             if (!BN_lshift1(r0, q))
 498                 goto err;
 499             if (!BN_mod(c, X, r0, ctx))
 500                 goto err;
 501             if (!BN_sub(r0, c, BN_value_one()))
 502                 goto err;
 503             if (!BN_sub(p, X, r0))
 504                 goto err;
 505
 506             /* step 10 */
 507             if (BN_cmp(p, test) >= 0) {
 508                 /* step 11 */
 509                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 510                 if (r > 0)
 511                     goto end;   /* found it */
 512                 if (r != 0)
 513                     goto err;
 514             }
 515
 516             /* step 13 */
 517             counter++;
 518             /* "offset = offset + n + 1" */
 519
 520             /* step 14 */
 521             if (counter >= (int)(4 * L))
 522                 break;
 523         }
 524         if (seed_in) {
 525             ok = 0;
 526             DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
 527             goto err;
 528         }
 529     }
 530  end:
 531     if (!BN_GENCB_call(cb, 2, 1))
 532         goto err;
 533
 534  g_only:
 535
 536     /* We now need to generate g */
 537     /* Set r0=(p-1)/q */
 538     if (!BN_sub(test, p, BN_value_one()))
 539         goto err;
 540     if (!BN_div(r0, NULL, test, q, ctx))
 541         goto err;
 542
 543     if (idx < 0) {
 544         if (!BN_set_word(test, h))
 545             goto err;
 546     } else
 547         h = 1;
 548     if (!BN_MONT_CTX_set(mont, p, ctx))
 549         goto err;
 550
 551     for (;;) {
 552         static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
 553         if (idx >= 0) {
 554             md[0] = idx & 0xff;
 555             md[1] = (h >> 8) & 0xff;
 556             md[2] = h & 0xff;
 557             if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
 558                 goto err;
 559             if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
 560                 goto err;
 561             if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
 562                 goto err;
 563             if (!EVP_DigestUpdate(mctx, md, 3))
 564                 goto err;
 565             if (!EVP_DigestFinal_ex(mctx, md, NULL))
 566                 goto err;
 567             if (!BN_bin2bn(md, mdsize, test))
 568                 goto err;
 569         }
 570         /* g=test^r0%p */
 571         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
 572             goto err;
 573         if (!BN_is_one(g))
 574             break;
 575         if (idx < 0 && !BN_add(test, test, BN_value_one()))
 576             goto err;
 577         h++;
 578         if (idx >= 0 && h > 0xffff)
 579             goto err;
 580     }
 581
 582     if (!BN_GENCB_call(cb, 3, 1))
 583         goto err;
 584
 585     ok = 1;
 586  err:
 587     if (ok == 1) {
 588         if (p != ret->p) {
 589             BN_free(ret->p);
 590             ret->p = BN_dup(p);
 591         }
 592         if (q != ret->q) {
 593             BN_free(ret->q);
 594             ret->q = BN_dup(q);
 595         }
 596         BN_free(ret->g);
 597         ret->g = BN_dup(g);
 598         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
 599             ok = -1;
 600             goto err;
 601         }
 602         if (counter_ret != NULL)
 603             *counter_ret = counter;
 604         if (h_ret != NULL)
 605             *h_ret = h;
 606     }
 607     OPENSSL_free(seed);
 608     if (seed_out != seed_tmp)
 609         OPENSSL_free(seed_tmp);
 610     if (ctx)
 611         BN_CTX_end(ctx);
 612     BN_CTX_free(ctx);
 613     BN_MONT_CTX_free(mont);
 614     EVP_MD_CTX_free(mctx);
 615     return ok;
 616 }