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 <openssl/bn.h>
60 #include <openssl/err.h>
61 #include <openssl/thread.h>
62 
63 #include "internal.h"
64 
65 
66 #define OPENSSL_DH_MAX_MODULUS_BITS 10000
67 
generate_parameters(DH * ret,int prime_bits,int generator,BN_GENCB * cb)68 static int generate_parameters(DH *ret, int prime_bits, int generator, BN_GENCB *cb) {
69   /* We generate DH parameters as follows
70    * find a prime q which is prime_bits/2 bits long.
71    * p=(2*q)+1 or (p-1)/2 = q
72    * For this case, g is a generator if
73    * g^((p-1)/q) mod p != 1 for values of q which are the factors of p-1.
74    * Since the factors of p-1 are q and 2, we just need to check
75    * g^2 mod p != 1 and g^q mod p != 1.
76    *
77    * Having said all that,
78    * there is another special case method for the generators 2, 3 and 5.
79    * for 2, p mod 24 == 11
80    * for 3, p mod 12 == 5  <<<<< does not work for safe primes.
81    * for 5, p mod 10 == 3 or 7
82    *
83    * Thanks to Phil Karn <karn@qualcomm.com> for the pointers about the
84    * special generators and for answering some of my questions.
85    *
86    * I've implemented the second simple method :-).
87    * Since DH should be using a safe prime (both p and q are prime),
88    * this generator function can take a very very long time to run.
89    */
90 
91   /* Actually there is no reason to insist that 'generator' be a generator.
92    * It's just as OK (and in some sense better) to use a generator of the
93    * order-q subgroup.
94    */
95 
96   BIGNUM *t1, *t2;
97   int g, ok = 0;
98   BN_CTX *ctx = NULL;
99 
100   ctx = BN_CTX_new();
101   if (ctx == NULL) {
102     goto err;
103   }
104   BN_CTX_start(ctx);
105   t1 = BN_CTX_get(ctx);
106   t2 = BN_CTX_get(ctx);
107   if (t1 == NULL || t2 == NULL) {
108     goto err;
109   }
110 
111   /* Make sure 'ret' has the necessary elements */
112   if (!ret->p && ((ret->p = BN_new()) == NULL)) {
113     goto err;
114   }
115   if (!ret->g && ((ret->g = BN_new()) == NULL)) {
116     goto err;
117   }
118 
119   if (generator <= 1) {
120     OPENSSL_PUT_ERROR(DH, generate_parameters, DH_R_BAD_GENERATOR);
121     goto err;
122   }
123   if (generator == DH_GENERATOR_2) {
124     if (!BN_set_word(t1, 24)) {
125       goto err;
126     }
127     if (!BN_set_word(t2, 11)) {
128       goto err;
129     }
130     g = 2;
131   } else if (generator == DH_GENERATOR_5) {
132     if (!BN_set_word(t1, 10)) {
133       goto err;
134     }
135     if (!BN_set_word(t2, 3)) {
136       goto err;
137     }
138     /* BN_set_word(t3,7); just have to miss
139      * out on these ones :-( */
140     g = 5;
141   } else {
142     /* in the general case, don't worry if 'generator' is a
143      * generator or not: since we are using safe primes,
144      * it will generate either an order-q or an order-2q group,
145      * which both is OK */
146     if (!BN_set_word(t1, 2)) {
147       goto err;
148     }
149     if (!BN_set_word(t2, 1)) {
150       goto err;
151     }
152     g = generator;
153   }
154 
155   if (!BN_generate_prime_ex(ret->p, prime_bits, 1, t1, t2, cb)) {
156     goto err;
157   }
158   if (!BN_GENCB_call(cb, 3, 0)) {
159     goto err;
160   }
161   if (!BN_set_word(ret->g, g)) {
162     goto err;
163   }
164   ok = 1;
165 
166 err:
167   if (!ok) {
168     OPENSSL_PUT_ERROR(DH, generate_parameters, ERR_R_BN_LIB);
169   }
170 
171   if (ctx != NULL) {
172     BN_CTX_end(ctx);
173     BN_CTX_free(ctx);
174   }
175   return ok;
176 }
177 
generate_key(DH * dh)178 static int generate_key(DH *dh) {
179   int ok = 0;
180   int generate_new_key = 0;
181   unsigned l;
182   BN_CTX *ctx;
183   BN_MONT_CTX *mont = NULL;
184   BIGNUM *pub_key = NULL, *priv_key = NULL;
185   BIGNUM local_priv;
186 
187   ctx = BN_CTX_new();
188   if (ctx == NULL) {
189     goto err;
190   }
191 
192   if (dh->priv_key == NULL) {
193     priv_key = BN_new();
194     if (priv_key == NULL) {
195       goto err;
196     }
197     generate_new_key = 1;
198   } else {
199     priv_key = dh->priv_key;
200   }
201 
202   if (dh->pub_key == NULL) {
203     pub_key = BN_new();
204     if (pub_key == NULL) {
205       goto err;
206     }
207   } else {
208     pub_key = dh->pub_key;
209   }
210 
211   mont = BN_MONT_CTX_set_locked(&dh->method_mont_p, &dh->method_mont_p_lock,
212                                 dh->p, ctx);
213   if (!mont) {
214     goto err;
215   }
216 
217   if (generate_new_key) {
218     if (dh->q) {
219       do {
220         if (!BN_rand_range(priv_key, dh->q)) {
221           goto err;
222         }
223       } while (BN_is_zero(priv_key) || BN_is_one(priv_key));
224     } else {
225       /* secret exponent length */
226       DH_check_standard_parameters(dh);
227       l = dh->priv_length ? dh->priv_length : BN_num_bits(dh->p) - 1;
228       if (!BN_rand(priv_key, l, 0, 0)) {
229         goto err;
230       }
231     }
232   }
233 
234   BN_with_flags(&local_priv, priv_key, BN_FLG_CONSTTIME);
235   if (!BN_mod_exp_mont(pub_key, dh->g, &local_priv, dh->p, ctx, mont)) {
236     goto err;
237   }
238 
239   dh->pub_key = pub_key;
240   dh->priv_key = priv_key;
241   ok = 1;
242 
243 err:
244   if (ok != 1) {
245     OPENSSL_PUT_ERROR(DH, generate_key, ERR_R_BN_LIB);
246   }
247 
248   if (dh->pub_key == NULL) {
249     BN_free(pub_key);
250   }
251   if (dh->priv_key == NULL) {
252     BN_free(priv_key);
253   }
254   BN_CTX_free(ctx);
255   return ok;
256 }
257 
compute_key(DH * dh,unsigned char * out,const BIGNUM * pub_key)258 static int compute_key(DH *dh, unsigned char *out, const BIGNUM *pub_key) {
259   BN_CTX *ctx = NULL;
260   BN_MONT_CTX *mont = NULL;
261   BIGNUM *shared_key;
262   int ret = -1;
263   int check_result;
264   BIGNUM local_priv;
265 
266   if (BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS) {
267     OPENSSL_PUT_ERROR(DH, compute_key, DH_R_MODULUS_TOO_LARGE);
268     goto err;
269   }
270 
271   ctx = BN_CTX_new();
272   if (ctx == NULL) {
273     goto err;
274   }
275   BN_CTX_start(ctx);
276   shared_key = BN_CTX_get(ctx);
277   if (shared_key == NULL) {
278     goto err;
279   }
280 
281   if (dh->priv_key == NULL) {
282     OPENSSL_PUT_ERROR(DH, compute_key, DH_R_NO_PRIVATE_VALUE);
283     goto err;
284   }
285 
286   mont = BN_MONT_CTX_set_locked(&dh->method_mont_p, &dh->method_mont_p_lock,
287                                 dh->p, ctx);
288   if (!mont) {
289     goto err;
290   }
291 
292   if (!DH_check_pub_key(dh, pub_key, &check_result) || check_result) {
293     OPENSSL_PUT_ERROR(DH, compute_key, DH_R_INVALID_PUBKEY);
294     goto err;
295   }
296 
297   BN_with_flags(&local_priv, dh->priv_key, BN_FLG_CONSTTIME);
298   if (!BN_mod_exp_mont(shared_key, pub_key, &local_priv, dh->p, ctx,
299                        mont)) {
300     OPENSSL_PUT_ERROR(DH, compute_key, ERR_R_BN_LIB);
301     goto err;
302   }
303 
304   ret = BN_bn2bin(shared_key, out);
305 
306 err:
307   if (ctx != NULL) {
308     BN_CTX_end(ctx);
309     BN_CTX_free(ctx);
310   }
311 
312   return ret;
313 }
314 
315 const struct dh_method DH_default_method = {
316   {
317     0 /* references */,
318     1 /* is_static */,
319   },
320   NULL /* app_data */,
321   NULL /* init */,
322   NULL /* finish */,
323   generate_parameters,
324   generate_key,
325   compute_key,
326 };
327