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