| 1 |
/* Copyright (C) 1995-1998 Eric Young ([email protected]) |
| 2 |
* All rights reserved. |
| 3 |
* |
| 4 |
* This package is an SSL implementation written |
| 5 |
* by Eric Young ([email protected]). |
| 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 ([email protected]). |
| 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 ([email protected])" |
| 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 ([email protected])" |
| 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 |
#include "../internal.h" |
| 70 |
|
| 71 |
|
| 72 |
#define OPENSSL_DH_MAX_MODULUS_BITS 10000 |
| 73 |
|
| 74 |
static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT; |
| 75 |
|
| 76 |
DH *DH_new(void) { |
| 77 |
DH *dh = OPENSSL_malloc(sizeof(DH)); |
| 78 |
if (dh == NULL) { |
| 79 |
OPENSSL_PUT_ERROR(DH, ERR_R_MALLOC_FAILURE); |
| 80 |
return NULL; |
| 81 |
} |
| 82 |
|
| 83 |
memset(dh, 0, sizeof(DH)); |
| 84 |
|
| 85 |
CRYPTO_MUTEX_init(&dh->method_mont_p_lock); |
| 86 |
|
| 87 |
dh->references = 1; |
| 88 |
CRYPTO_new_ex_data(&dh->ex_data); |
| 89 |
|
| 90 |
return dh; |
| 91 |
} |
| 92 |
|
| 93 |
void DH_free(DH *dh) { |
| 94 |
if (dh == NULL) { |
| 95 |
return; |
| 96 |
} |
| 97 |
|
| 98 |
if (!CRYPTO_refcount_dec_and_test_zero(&dh->references)) { |
| 99 |
return; |
| 100 |
} |
| 101 |
|
| 102 |
CRYPTO_free_ex_data(&g_ex_data_class, dh, &dh->ex_data); |
| 103 |
|
| 104 |
BN_MONT_CTX_free(dh->method_mont_p); |
| 105 |
BN_clear_free(dh->p); |
| 106 |
BN_clear_free(dh->g); |
| 107 |
BN_clear_free(dh->q); |
| 108 |
BN_clear_free(dh->j); |
| 109 |
OPENSSL_free(dh->seed); |
| 110 |
BN_clear_free(dh->counter); |
| 111 |
BN_clear_free(dh->pub_key); |
| 112 |
BN_clear_free(dh->priv_key); |
| 113 |
CRYPTO_MUTEX_cleanup(&dh->method_mont_p_lock); |
| 114 |
|
| 115 |
OPENSSL_free(dh); |
| 116 |
} |
| 117 |
|
| 118 |
int DH_generate_parameters_ex(DH *dh, int prime_bits, int generator, BN_GENCB *cb) { |
| 119 |
/* We generate DH parameters as follows |
| 120 |
* find a prime q which is prime_bits/2 bits long. |
| 121 |
* p=(2*q)+1 or (p-1)/2 = q |
| 122 |
* For this case, g is a generator if |
| 123 |
* g^((p-1)/q) mod p != 1 for values of q which are the factors of p-1. |
| 124 |
* Since the factors of p-1 are q and 2, we just need to check |
| 125 |
* g^2 mod p != 1 and g^q mod p != 1. |
| 126 |
* |
| 127 |
* Having said all that, |
| 128 |
* there is another special case method for the generators 2, 3 and 5. |
| 129 |
* for 2, p mod 24 == 11 |
| 130 |
* for 3, p mod 12 == 5 <<<<< does not work for safe primes. |
| 131 |
* for 5, p mod 10 == 3 or 7 |
| 132 |
* |
| 133 |
* Thanks to Phil Karn <[email protected]> for the pointers about the |
| 134 |
* special generators and for answering some of my questions. |
| 135 |
* |
| 136 |
* I've implemented the second simple method :-). |
| 137 |
* Since DH should be using a safe prime (both p and q are prime), |
| 138 |
* this generator function can take a very very long time to run. |
| 139 |
*/ |
| 140 |
|
| 141 |
/* Actually there is no reason to insist that 'generator' be a generator. |
| 142 |
* It's just as OK (and in some sense better) to use a generator of the |
| 143 |
* order-q subgroup. |
| 144 |
*/ |
| 145 |
|
| 146 |
BIGNUM *t1, *t2; |
| 147 |
int g, ok = 0; |
| 148 |
BN_CTX *ctx = NULL; |
| 149 |
|
| 150 |
ctx = BN_CTX_new(); |
| 151 |
if (ctx == NULL) { |
| 152 |
goto err; |
| 153 |
} |
| 154 |
BN_CTX_start(ctx); |
| 155 |
t1 = BN_CTX_get(ctx); |
| 156 |
t2 = BN_CTX_get(ctx); |
| 157 |
if (t1 == NULL || t2 == NULL) { |
| 158 |
goto err; |
| 159 |
} |
| 160 |
|
| 161 |
/* Make sure |dh| has the necessary elements */ |
| 162 |
if (dh->p == NULL) { |
| 163 |
dh->p = BN_new(); |
| 164 |
if (dh->p == NULL) { |
| 165 |
goto err; |
| 166 |
} |
| 167 |
} |
| 168 |
if (dh->g == NULL) { |
| 169 |
dh->g = BN_new(); |
| 170 |
if (dh->g == NULL) { |
| 171 |
goto err; |
| 172 |
} |
| 173 |
} |
| 174 |
|
| 175 |
if (generator <= 1) { |
| 176 |
OPENSSL_PUT_ERROR(DH, DH_R_BAD_GENERATOR); |
| 177 |
goto err; |
| 178 |
} |
| 179 |
if (generator == DH_GENERATOR_2) { |
| 180 |
if (!BN_set_word(t1, 24)) { |
| 181 |
goto err; |
| 182 |
} |
| 183 |
if (!BN_set_word(t2, 11)) { |
| 184 |
goto err; |
| 185 |
} |
| 186 |
g = 2; |
| 187 |
} else if (generator == DH_GENERATOR_5) { |
| 188 |
if (!BN_set_word(t1, 10)) { |
| 189 |
goto err; |
| 190 |
} |
| 191 |
if (!BN_set_word(t2, 3)) { |
| 192 |
goto err; |
| 193 |
} |
| 194 |
/* BN_set_word(t3,7); just have to miss |
| 195 |
* out on these ones :-( */ |
| 196 |
g = 5; |
| 197 |
} else { |
| 198 |
/* in the general case, don't worry if 'generator' is a |
| 199 |
* generator or not: since we are using safe primes, |
| 200 |
* it will generate either an order-q or an order-2q group, |
| 201 |
* which both is OK */ |
| 202 |
if (!BN_set_word(t1, 2)) { |
| 203 |
goto err; |
| 204 |
} |
| 205 |
if (!BN_set_word(t2, 1)) { |
| 206 |
goto err; |
| 207 |
} |
| 208 |
g = generator; |
| 209 |
} |
| 210 |
|
| 211 |
if (!BN_generate_prime_ex(dh->p, prime_bits, 1, t1, t2, cb)) { |
| 212 |
goto err; |
| 213 |
} |
| 214 |
if (!BN_GENCB_call(cb, 3, 0)) { |
| 215 |
goto err; |
| 216 |
} |
| 217 |
if (!BN_set_word(dh->g, g)) { |
| 218 |
goto err; |
| 219 |
} |
| 220 |
ok = 1; |
| 221 |
|
| 222 |
err: |
| 223 |
if (!ok) { |
| 224 |
OPENSSL_PUT_ERROR(DH, ERR_R_BN_LIB); |
| 225 |
} |
| 226 |
|
| 227 |
if (ctx != NULL) { |
| 228 |
BN_CTX_end(ctx); |
| 229 |
BN_CTX_free(ctx); |
| 230 |
} |
| 231 |
return ok; |
| 232 |
} |
| 233 |
|
| 234 |
int DH_generate_key(DH *dh) { |
| 235 |
int ok = 0; |
| 236 |
int generate_new_key = 0; |
| 237 |
unsigned l; |
| 238 |
BN_CTX *ctx = NULL; |
| 239 |
BIGNUM *pub_key = NULL, *priv_key = NULL; |
| 240 |
BIGNUM local_priv; |
| 241 |
|
| 242 |
if (BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS) { |
| 243 |
OPENSSL_PUT_ERROR(DH, DH_R_MODULUS_TOO_LARGE); |
| 244 |
goto err; |
| 245 |
} |
| 246 |
|
| 247 |
ctx = BN_CTX_new(); |
| 248 |
if (ctx == NULL) { |
| 249 |
goto err; |
| 250 |
} |
| 251 |
|
| 252 |
if (dh->priv_key == NULL) { |
| 253 |
priv_key = BN_new(); |
| 254 |
if (priv_key == NULL) { |
| 255 |
goto err; |
| 256 |
} |
| 257 |
generate_new_key = 1; |
| 258 |
} else { |
| 259 |
priv_key = dh->priv_key; |
| 260 |
} |
| 261 |
|
| 262 |
if (dh->pub_key == NULL) { |
| 263 |
pub_key = BN_new(); |
| 264 |
if (pub_key == NULL) { |
| 265 |
goto err; |
| 266 |
} |
| 267 |
} else { |
| 268 |
pub_key = dh->pub_key; |
| 269 |
} |
| 270 |
|
| 271 |
if (!BN_MONT_CTX_set_locked(&dh->method_mont_p, &dh->method_mont_p_lock, |
| 272 |
dh->p, ctx)) { |
| 273 |
goto err; |
| 274 |
} |
| 275 |
|
| 276 |
if (generate_new_key) { |
| 277 |
if (dh->q) { |
| 278 |
do { |
| 279 |
if (!BN_rand_range(priv_key, dh->q)) { |
| 280 |
goto err; |
| 281 |
} |
| 282 |
} while (BN_is_zero(priv_key) || BN_is_one(priv_key)); |
| 283 |
} else { |
| 284 |
/* secret exponent length */ |
| 285 |
DH_check_standard_parameters(dh); |
| 286 |
l = dh->priv_length ? dh->priv_length : BN_num_bits(dh->p) - 1; |
| 287 |
if (!BN_rand(priv_key, l, 0, 0)) { |
| 288 |
goto err; |
| 289 |
} |
| 290 |
} |
| 291 |
} |
| 292 |
|
| 293 |
BN_with_flags(&local_priv, priv_key, BN_FLG_CONSTTIME); |
| 294 |
if (!BN_mod_exp_mont_consttime(pub_key, dh->g, &local_priv, dh->p, ctx, |
| 295 |
dh->method_mont_p)) { |
| 296 |
goto err; |
| 297 |
} |
| 298 |
|
| 299 |
dh->pub_key = pub_key; |
| 300 |
dh->priv_key = priv_key; |
| 301 |
ok = 1; |
| 302 |
|
| 303 |
err: |
| 304 |
if (ok != 1) { |
| 305 |
OPENSSL_PUT_ERROR(DH, ERR_R_BN_LIB); |
| 306 |
} |
| 307 |
|
| 308 |
if (dh->pub_key == NULL) { |
| 309 |
BN_free(pub_key); |
| 310 |
} |
| 311 |
if (dh->priv_key == NULL) { |
| 312 |
BN_free(priv_key); |
| 313 |
} |
| 314 |
BN_CTX_free(ctx); |
| 315 |
return ok; |
| 316 |
} |
| 317 |
|
| 318 |
int DH_compute_key(unsigned char *out, const BIGNUM *peers_key, DH *dh) { |
| 319 |
BN_CTX *ctx = NULL; |
| 320 |
BIGNUM *shared_key; |
| 321 |
int ret = -1; |
| 322 |
int check_result; |
| 323 |
BIGNUM local_priv; |
| 324 |
|
| 325 |
if (BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS) { |
| 326 |
OPENSSL_PUT_ERROR(DH, DH_R_MODULUS_TOO_LARGE); |
| 327 |
goto err; |
| 328 |
} |
| 329 |
|
| 330 |
ctx = BN_CTX_new(); |
| 331 |
if (ctx == NULL) { |
| 332 |
goto err; |
| 333 |
} |
| 334 |
BN_CTX_start(ctx); |
| 335 |
shared_key = BN_CTX_get(ctx); |
| 336 |
if (shared_key == NULL) { |
| 337 |
goto err; |
| 338 |
} |
| 339 |
|
| 340 |
if (dh->priv_key == NULL) { |
| 341 |
OPENSSL_PUT_ERROR(DH, DH_R_NO_PRIVATE_VALUE); |
| 342 |
goto err; |
| 343 |
} |
| 344 |
|
| 345 |
if (!BN_MONT_CTX_set_locked(&dh->method_mont_p, &dh->method_mont_p_lock, |
| 346 |
dh->p, ctx)) { |
| 347 |
goto err; |
| 348 |
} |
| 349 |
|
| 350 |
if (!DH_check_pub_key(dh, peers_key, &check_result) || check_result) { |
| 351 |
OPENSSL_PUT_ERROR(DH, DH_R_INVALID_PUBKEY); |
| 352 |
goto err; |
| 353 |
} |
| 354 |
|
| 355 |
BN_with_flags(&local_priv, dh->priv_key, BN_FLG_CONSTTIME); |
| 356 |
if (!BN_mod_exp_mont_consttime(shared_key, peers_key, &local_priv, dh->p, ctx, |
| 357 |
dh->method_mont_p)) { |
| 358 |
OPENSSL_PUT_ERROR(DH, ERR_R_BN_LIB); |
| 359 |
goto err; |
| 360 |
} |
| 361 |
|
| 362 |
ret = BN_bn2bin(shared_key, out); |
| 363 |
|
| 364 |
err: |
| 365 |
if (ctx != NULL) { |
| 366 |
BN_CTX_end(ctx); |
| 367 |
BN_CTX_free(ctx); |
| 368 |
} |
| 369 |
|
| 370 |
return ret; |
| 371 |
} |
| 372 |
|
| 373 |
int DH_size(const DH *dh) { return BN_num_bytes(dh->p); } |
| 374 |
|
| 375 |
unsigned DH_num_bits(const DH *dh) { return BN_num_bits(dh->p); } |
| 376 |
|
| 377 |
int DH_up_ref(DH *dh) { |
| 378 |
CRYPTO_refcount_inc(&dh->references); |
| 379 |
return 1; |
| 380 |
} |
| 381 |
|
| 382 |
static int int_dh_bn_cpy(BIGNUM **dst, const BIGNUM *src) { |
| 383 |
BIGNUM *a = NULL; |
| 384 |
|
| 385 |
if (src) { |
| 386 |
a = BN_dup(src); |
| 387 |
if (!a) { |
| 388 |
return 0; |
| 389 |
} |
| 390 |
} |
| 391 |
|
| 392 |
BN_free(*dst); |
| 393 |
*dst = a; |
| 394 |
return 1; |
| 395 |
} |
| 396 |
|
| 397 |
static int int_dh_param_copy(DH *to, const DH *from, int is_x942) { |
| 398 |
if (is_x942 == -1) { |
| 399 |
is_x942 = !!from->q; |
| 400 |
} |
| 401 |
if (!int_dh_bn_cpy(&to->p, from->p) || |
| 402 |
!int_dh_bn_cpy(&to->g, from->g)) { |
| 403 |
return 0; |
| 404 |
} |
| 405 |
|
| 406 |
if (!is_x942) { |
| 407 |
return 1; |
| 408 |
} |
| 409 |
|
| 410 |
if (!int_dh_bn_cpy(&to->q, from->q) || |
| 411 |
!int_dh_bn_cpy(&to->j, from->j)) { |
| 412 |
return 0; |
| 413 |
} |
| 414 |
|
| 415 |
OPENSSL_free(to->seed); |
| 416 |
to->seed = NULL; |
| 417 |
to->seedlen = 0; |
| 418 |
|
| 419 |
if (from->seed) { |
| 420 |
to->seed = BUF_memdup(from->seed, from->seedlen); |
| 421 |
if (!to->seed) { |
| 422 |
return 0; |
| 423 |
} |
| 424 |
to->seedlen = from->seedlen; |
| 425 |
} |
| 426 |
|
| 427 |
return 1; |
| 428 |
} |
| 429 |
|
| 430 |
DH *DHparams_dup(const DH *dh) { |
| 431 |
DH *ret = DH_new(); |
| 432 |
if (!ret) { |
| 433 |
return NULL; |
| 434 |
} |
| 435 |
|
| 436 |
if (!int_dh_param_copy(ret, dh, -1)) { |
| 437 |
DH_free(ret); |
| 438 |
return NULL; |
| 439 |
} |
| 440 |
|
| 441 |
return ret; |
| 442 |
} |
| 443 |
|
| 444 |
int DH_get_ex_new_index(long argl, void *argp, CRYPTO_EX_unused *unused, |
| 445 |
CRYPTO_EX_dup *dup_func, CRYPTO_EX_free *free_func) { |
| 446 |
int index; |
| 447 |
if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp, dup_func, |
| 448 |
free_func)) { |
| 449 |
return -1; |
| 450 |
} |
| 451 |
return index; |
| 452 |
} |
| 453 |
|
| 454 |
int DH_set_ex_data(DH *d, int idx, void *arg) { |
| 455 |
return CRYPTO_set_ex_data(&d->ex_data, idx, arg); |
| 456 |
} |
| 457 |
|
| 458 |
void *DH_get_ex_data(DH *d, int idx) { |
| 459 |
return CRYPTO_get_ex_data(&d->ex_data, idx); |
| 460 |
} |