legacy-libs/grpc-cloned/deps/grpc/third_party/boringssl/crypto/dh/dh.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.] */
  56
  57 #include <openssl/dh.h>
  58
  59 #include <string.h>
  60
  61 #include <openssl/bn.h>
  62 #include <openssl/buf.h>
  63 #include <openssl/err.h>
  64 #include <openssl/ex_data.h>
  65 #include <openssl/mem.h>
  66 #include <openssl/thread.h>
  67
  68 #include "../internal.h"
  69
  70
  71 #define OPENSSL_DH_MAX_MODULUS_BITS 10000
  72
  73 static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT;
  74
  75 DH *DH_new(void) {
  76   DH *dh = OPENSSL_malloc(sizeof(DH));
  77   if (dh == NULL) {
  78     OPENSSL_PUT_ERROR(DH, ERR_R_MALLOC_FAILURE);
  79     return NULL;
  80   }
  81
  82   OPENSSL_memset(dh, 0, sizeof(DH));
  83
  84   CRYPTO_MUTEX_init(&dh->method_mont_p_lock);
  85
  86   dh->references = 1;
  87   CRYPTO_new_ex_data(&dh->ex_data);
  88
  89   return dh;
  90 }
  91
  92 void DH_free(DH *dh) {
  93   if (dh == NULL) {
  94     return;
  95   }
  96
  97   if (!CRYPTO_refcount_dec_and_test_zero(&dh->references)) {
  98     return;
  99   }
 100
 101   CRYPTO_free_ex_data(&g_ex_data_class, dh, &dh->ex_data);
 102
 103   BN_MONT_CTX_free(dh->method_mont_p);
 104   BN_clear_free(dh->p);
 105   BN_clear_free(dh->g);
 106   BN_clear_free(dh->q);
 107   BN_clear_free(dh->j);
 108   OPENSSL_free(dh->seed);
 109   BN_clear_free(dh->counter);
 110   BN_clear_free(dh->pub_key);
 111   BN_clear_free(dh->priv_key);
 112   CRYPTO_MUTEX_cleanup(&dh->method_mont_p_lock);
 113
 114   OPENSSL_free(dh);
 115 }
 116
 117 void DH_get0_key(const DH *dh, const BIGNUM **out_pub_key,
 118                  const BIGNUM **out_priv_key) {
 119   if (out_pub_key != NULL) {
 120     *out_pub_key = dh->pub_key;
 121   }
 122   if (out_priv_key != NULL) {
 123     *out_priv_key = dh->priv_key;
 124   }
 125 }
 126
 127 int DH_set0_key(DH *dh, BIGNUM *pub_key, BIGNUM *priv_key) {
 128   if (pub_key != NULL) {
 129     BN_free(dh->pub_key);
 130     dh->pub_key = pub_key;
 131   }
 132
 133   if (priv_key != NULL) {
 134     BN_free(dh->priv_key);
 135     dh->priv_key = priv_key;
 136   }
 137
 138   return 1;
 139 }
 140
 141 void DH_get0_pqg(const DH *dh, const BIGNUM **out_p, const BIGNUM **out_q,
 142                  const BIGNUM **out_g) {
 143   if (out_p != NULL) {
 144     *out_p = dh->p;
 145   }
 146   if (out_q != NULL) {
 147     *out_q = dh->q;
 148   }
 149   if (out_g != NULL) {
 150     *out_g = dh->g;
 151   }
 152 }
 153
 154 int DH_set0_pqg(DH *dh, BIGNUM *p, BIGNUM *q, BIGNUM *g) {
 155   if ((dh->p == NULL && p == NULL) ||
 156       (dh->g == NULL && g == NULL)) {
 157     return 0;
 158   }
 159
 160   if (p != NULL) {
 161     BN_free(dh->p);
 162     dh->p = p;
 163   }
 164
 165   if (q != NULL) {
 166     BN_free(dh->q);
 167     dh->q = q;
 168   }
 169
 170   if (g != NULL) {
 171     BN_free(dh->g);
 172     dh->g = g;
 173   }
 174
 175   return 1;
 176 }
 177
 178 int DH_generate_parameters_ex(DH *dh, int prime_bits, int generator, BN_GENCB *cb) {
 179   // We generate DH parameters as follows
 180   // find a prime q which is prime_bits/2 bits long.
 181   // p=(2*q)+1 or (p-1)/2 = q
 182   // For this case, g is a generator if
 183   // g^((p-1)/q) mod p != 1 for values of q which are the factors of p-1.
 184   // Since the factors of p-1 are q and 2, we just need to check
 185   // g^2 mod p != 1 and g^q mod p != 1.
 186   //
 187   // Having said all that,
 188   // there is another special case method for the generators 2, 3 and 5.
 189   // for 2, p mod 24 == 11
 190   // for 3, p mod 12 == 5  <<<<< does not work for safe primes.
 191   // for 5, p mod 10 == 3 or 7
 192   //
 193   // Thanks to Phil Karn <karn@qualcomm.com> for the pointers about the
 194   // special generators and for answering some of my questions.
 195   //
 196   // I've implemented the second simple method :-).
 197   // Since DH should be using a safe prime (both p and q are prime),
 198   // this generator function can take a very very long time to run.
 199
 200   // Actually there is no reason to insist that 'generator' be a generator.
 201   // It's just as OK (and in some sense better) to use a generator of the
 202   // order-q subgroup.
 203
 204   BIGNUM *t1, *t2;
 205   int g, ok = 0;
 206   BN_CTX *ctx = NULL;
 207
 208   ctx = BN_CTX_new();
 209   if (ctx == NULL) {
 210     goto err;
 211   }
 212   BN_CTX_start(ctx);
 213   t1 = BN_CTX_get(ctx);
 214   t2 = BN_CTX_get(ctx);
 215   if (t1 == NULL || t2 == NULL) {
 216     goto err;
 217   }
 218
 219   // Make sure |dh| has the necessary elements
 220   if (dh->p == NULL) {
 221     dh->p = BN_new();
 222     if (dh->p == NULL) {
 223       goto err;
 224     }
 225   }
 226   if (dh->g == NULL) {
 227     dh->g = BN_new();
 228     if (dh->g == NULL) {
 229       goto err;
 230     }
 231   }
 232
 233   if (generator <= 1) {
 234     OPENSSL_PUT_ERROR(DH, DH_R_BAD_GENERATOR);
 235     goto err;
 236   }
 237   if (generator == DH_GENERATOR_2) {
 238     if (!BN_set_word(t1, 24)) {
 239       goto err;
 240     }
 241     if (!BN_set_word(t2, 11)) {
 242       goto err;
 243     }
 244     g = 2;
 245   } else if (generator == DH_GENERATOR_5) {
 246     if (!BN_set_word(t1, 10)) {
 247       goto err;
 248     }
 249     if (!BN_set_word(t2, 3)) {
 250       goto err;
 251     }
 252     // BN_set_word(t3,7); just have to miss
 253     // out on these ones :-(
 254     g = 5;
 255   } else {
 256     // in the general case, don't worry if 'generator' is a
 257     // generator or not: since we are using safe primes,
 258     // it will generate either an order-q or an order-2q group,
 259     // which both is OK
 260     if (!BN_set_word(t1, 2)) {
 261       goto err;
 262     }
 263     if (!BN_set_word(t2, 1)) {
 264       goto err;
 265     }
 266     g = generator;
 267   }
 268
 269   if (!BN_generate_prime_ex(dh->p, prime_bits, 1, t1, t2, cb)) {
 270     goto err;
 271   }
 272   if (!BN_GENCB_call(cb, 3, 0)) {
 273     goto err;
 274   }
 275   if (!BN_set_word(dh->g, g)) {
 276     goto err;
 277   }
 278   ok = 1;
 279
 280 err:
 281   if (!ok) {
 282     OPENSSL_PUT_ERROR(DH, ERR_R_BN_LIB);
 283   }
 284
 285   if (ctx != NULL) {
 286     BN_CTX_end(ctx);
 287     BN_CTX_free(ctx);
 288   }
 289   return ok;
 290 }
 291
 292 int DH_generate_key(DH *dh) {
 293   int ok = 0;
 294   int generate_new_key = 0;
 295   BN_CTX *ctx = NULL;
 296   BIGNUM *pub_key = NULL, *priv_key = NULL;
 297
 298   if (BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS) {
 299     OPENSSL_PUT_ERROR(DH, DH_R_MODULUS_TOO_LARGE);
 300     goto err;
 301   }
 302
 303   ctx = BN_CTX_new();
 304   if (ctx == NULL) {
 305     goto err;
 306   }
 307
 308   if (dh->priv_key == NULL) {
 309     priv_key = BN_new();
 310     if (priv_key == NULL) {
 311       goto err;
 312     }
 313     generate_new_key = 1;
 314   } else {
 315     priv_key = dh->priv_key;
 316   }
 317
 318   if (dh->pub_key == NULL) {
 319     pub_key = BN_new();
 320     if (pub_key == NULL) {
 321       goto err;
 322     }
 323   } else {
 324     pub_key = dh->pub_key;
 325   }
 326
 327   if (!BN_MONT_CTX_set_locked(&dh->method_mont_p, &dh->method_mont_p_lock,
 328                               dh->p, ctx)) {
 329     goto err;
 330   }
 331
 332   if (generate_new_key) {
 333     if (dh->q) {
 334       if (!BN_rand_range_ex(priv_key, 2, dh->q)) {
 335         goto err;
 336       }
 337     } else {
 338       // secret exponent length
 339       unsigned priv_bits = dh->priv_length;
 340       if (priv_bits == 0) {
 341         const unsigned p_bits = BN_num_bits(dh->p);
 342         if (p_bits == 0) {
 343           goto err;
 344         }
 345
 346         priv_bits = p_bits - 1;
 347       }
 348
 349       if (!BN_rand(priv_key, priv_bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)) {
 350         goto err;
 351       }
 352     }
 353   }
 354
 355   if (!BN_mod_exp_mont_consttime(pub_key, dh->g, priv_key, dh->p, ctx,
 356                                  dh->method_mont_p)) {
 357     goto err;
 358   }
 359
 360   dh->pub_key = pub_key;
 361   dh->priv_key = priv_key;
 362   ok = 1;
 363
 364 err:
 365   if (ok != 1) {
 366     OPENSSL_PUT_ERROR(DH, ERR_R_BN_LIB);
 367   }
 368
 369   if (dh->pub_key == NULL) {
 370     BN_free(pub_key);
 371   }
 372   if (dh->priv_key == NULL) {
 373     BN_free(priv_key);
 374   }
 375   BN_CTX_free(ctx);
 376   return ok;
 377 }
 378
 379 int DH_compute_key(unsigned char *out, const BIGNUM *peers_key, DH *dh) {
 380   BN_CTX *ctx = NULL;
 381   BIGNUM *shared_key;
 382   int ret = -1;
 383   int check_result;
 384
 385   if (BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS) {
 386     OPENSSL_PUT_ERROR(DH, DH_R_MODULUS_TOO_LARGE);
 387     goto err;
 388   }
 389
 390   ctx = BN_CTX_new();
 391   if (ctx == NULL) {
 392     goto err;
 393   }
 394   BN_CTX_start(ctx);
 395   shared_key = BN_CTX_get(ctx);
 396   if (shared_key == NULL) {
 397     goto err;
 398   }
 399
 400   if (dh->priv_key == NULL) {
 401     OPENSSL_PUT_ERROR(DH, DH_R_NO_PRIVATE_VALUE);
 402     goto err;
 403   }
 404
 405   if (!BN_MONT_CTX_set_locked(&dh->method_mont_p, &dh->method_mont_p_lock,
 406                               dh->p, ctx)) {
 407     goto err;
 408   }
 409
 410   if (!DH_check_pub_key(dh, peers_key, &check_result) || check_result) {
 411     OPENSSL_PUT_ERROR(DH, DH_R_INVALID_PUBKEY);
 412     goto err;
 413   }
 414
 415   if (!BN_mod_exp_mont_consttime(shared_key, peers_key, dh->priv_key, dh->p,
 416                                  ctx, dh->method_mont_p)) {
 417     OPENSSL_PUT_ERROR(DH, ERR_R_BN_LIB);
 418     goto err;
 419   }
 420
 421   ret = BN_bn2bin(shared_key, out);
 422
 423 err:
 424   if (ctx != NULL) {
 425     BN_CTX_end(ctx);
 426     BN_CTX_free(ctx);
 427   }
 428
 429   return ret;
 430 }
 431
 432 int DH_size(const DH *dh) { return BN_num_bytes(dh->p); }
 433
 434 unsigned DH_num_bits(const DH *dh) { return BN_num_bits(dh->p); }
 435
 436 int DH_up_ref(DH *dh) {
 437   CRYPTO_refcount_inc(&dh->references);
 438   return 1;
 439 }
 440
 441 static int int_dh_bn_cpy(BIGNUM **dst, const BIGNUM *src) {
 442   BIGNUM *a = NULL;
 443
 444   if (src) {
 445     a = BN_dup(src);
 446     if (!a) {
 447       return 0;
 448     }
 449   }
 450
 451   BN_free(*dst);
 452   *dst = a;
 453   return 1;
 454 }
 455
 456 static int int_dh_param_copy(DH *to, const DH *from, int is_x942) {
 457   if (is_x942 == -1) {
 458     is_x942 = !!from->q;
 459   }
 460   if (!int_dh_bn_cpy(&to->p, from->p) ||
 461       !int_dh_bn_cpy(&to->g, from->g)) {
 462     return 0;
 463   }
 464
 465   if (!is_x942) {
 466     return 1;
 467   }
 468
 469   if (!int_dh_bn_cpy(&to->q, from->q) ||
 470       !int_dh_bn_cpy(&to->j, from->j)) {
 471     return 0;
 472   }
 473
 474   OPENSSL_free(to->seed);
 475   to->seed = NULL;
 476   to->seedlen = 0;
 477
 478   if (from->seed) {
 479     to->seed = BUF_memdup(from->seed, from->seedlen);
 480     if (!to->seed) {
 481       return 0;
 482     }
 483     to->seedlen = from->seedlen;
 484   }
 485
 486   return 1;
 487 }
 488
 489 DH *DHparams_dup(const DH *dh) {
 490   DH *ret = DH_new();
 491   if (!ret) {
 492     return NULL;
 493   }
 494
 495   if (!int_dh_param_copy(ret, dh, -1)) {
 496     DH_free(ret);
 497     return NULL;
 498   }
 499
 500   return ret;
 501 }
 502
 503 int DH_get_ex_new_index(long argl, void *argp, CRYPTO_EX_unused *unused,
 504                         CRYPTO_EX_dup *dup_unused, CRYPTO_EX_free *free_func) {
 505   int index;
 506   if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp,
 507                                free_func)) {
 508     return -1;
 509   }
 510   return index;
 511 }
 512
 513 int DH_set_ex_data(DH *d, int idx, void *arg) {
 514   return CRYPTO_set_ex_data(&d->ex_data, idx, arg);
 515 }
 516
 517 void *DH_get_ex_data(DH *d, int idx) {
 518   return CRYPTO_get_ex_data(&d->ex_data, idx);
 519 }