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 }