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