1 /* $OpenBSD: dh.c,v 1.48 2009/10/01 11:37:33 grunk Exp $ */
2 /*
3 * Copyright (c) 2000 Niels Provos. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 #include "includes.h"
27
28 #include <sys/param.h>
29
30 #include <openssl/bn.h>
31 #include <openssl/dh.h>
32
33 #include <stdarg.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37
38 #include "dh.h"
39 #include "pathnames.h"
40 #include "log.h"
41 #include "misc.h"
42
43 static int
parse_prime(int linenum,char * line,struct dhgroup * dhg)44 parse_prime(int linenum, char *line, struct dhgroup *dhg)
45 {
46 char *cp, *arg;
47 char *strsize, *gen, *prime;
48 const char *errstr = NULL;
49 long long n;
50
51 cp = line;
52 if ((arg = strdelim(&cp)) == NULL)
53 return 0;
54 /* Ignore leading whitespace */
55 if (*arg == '\0')
56 arg = strdelim(&cp);
57 if (!arg || !*arg || *arg == '#')
58 return 0;
59
60 /* time */
61 if (cp == NULL || *arg == '\0')
62 goto fail;
63 arg = strsep(&cp, " "); /* type */
64 if (cp == NULL || *arg == '\0')
65 goto fail;
66 /* Ensure this is a safe prime */
67 n = strtonum(arg, 0, 5, &errstr);
68 if (errstr != NULL || n != MODULI_TYPE_SAFE)
69 goto fail;
70 arg = strsep(&cp, " "); /* tests */
71 if (cp == NULL || *arg == '\0')
72 goto fail;
73 /* Ensure prime has been tested and is not composite */
74 n = strtonum(arg, 0, 0x1f, &errstr);
75 if (errstr != NULL ||
76 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
77 goto fail;
78 arg = strsep(&cp, " "); /* tries */
79 if (cp == NULL || *arg == '\0')
80 goto fail;
81 n = strtonum(arg, 0, 1<<30, &errstr);
82 if (errstr != NULL || n == 0)
83 goto fail;
84 strsize = strsep(&cp, " "); /* size */
85 if (cp == NULL || *strsize == '\0' ||
86 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
87 errstr)
88 goto fail;
89 /* The whole group is one bit larger */
90 dhg->size++;
91 gen = strsep(&cp, " "); /* gen */
92 if (cp == NULL || *gen == '\0')
93 goto fail;
94 prime = strsep(&cp, " "); /* prime */
95 if (cp != NULL || *prime == '\0')
96 goto fail;
97
98 if ((dhg->g = BN_new()) == NULL)
99 fatal("parse_prime: BN_new failed");
100 if ((dhg->p = BN_new()) == NULL)
101 fatal("parse_prime: BN_new failed");
102 if (BN_hex2bn(&dhg->g, gen) == 0)
103 goto failclean;
104
105 if (BN_hex2bn(&dhg->p, prime) == 0)
106 goto failclean;
107
108 if (BN_num_bits(dhg->p) != dhg->size)
109 goto failclean;
110
111 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
112 goto failclean;
113
114 return (1);
115
116 failclean:
117 BN_clear_free(dhg->g);
118 BN_clear_free(dhg->p);
119 fail:
120 error("Bad prime description in line %d", linenum);
121 return (0);
122 }
123
124 DH *
choose_dh(int min,int wantbits,int max)125 choose_dh(int min, int wantbits, int max)
126 {
127 FILE *f;
128 char line[4096];
129 int best, bestcount, which;
130 int linenum;
131 struct dhgroup dhg;
132
133 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
134 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
135 logit("WARNING: %s does not exist, using fixed modulus",
136 _PATH_DH_MODULI);
137 return (dh_new_group14());
138 }
139
140 linenum = 0;
141 best = bestcount = 0;
142 while (fgets(line, sizeof(line), f)) {
143 linenum++;
144 if (!parse_prime(linenum, line, &dhg))
145 continue;
146 BN_clear_free(dhg.g);
147 BN_clear_free(dhg.p);
148
149 if (dhg.size > max || dhg.size < min)
150 continue;
151
152 if ((dhg.size > wantbits && dhg.size < best) ||
153 (dhg.size > best && best < wantbits)) {
154 best = dhg.size;
155 bestcount = 0;
156 }
157 if (dhg.size == best)
158 bestcount++;
159 }
160 rewind(f);
161
162 if (bestcount == 0) {
163 fclose(f);
164 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
165 return (dh_new_group14());
166 }
167
168 linenum = 0;
169 which = arc4random_uniform(bestcount);
170 while (fgets(line, sizeof(line), f)) {
171 if (!parse_prime(linenum, line, &dhg))
172 continue;
173 if ((dhg.size > max || dhg.size < min) ||
174 dhg.size != best ||
175 linenum++ != which) {
176 BN_clear_free(dhg.g);
177 BN_clear_free(dhg.p);
178 continue;
179 }
180 break;
181 }
182 fclose(f);
183 if (linenum != which+1)
184 fatal("WARNING: line %d disappeared in %s, giving up",
185 which, _PATH_DH_PRIMES);
186
187 return (dh_new_group(dhg.g, dhg.p));
188 }
189
190 /* diffie-hellman-groupN-sha1 */
191
192 int
dh_pub_is_valid(DH * dh,BIGNUM * dh_pub)193 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
194 {
195 int i;
196 int n = BN_num_bits(dh_pub);
197 int bits_set = 0;
198 BIGNUM *tmp;
199
200 if (dh_pub->neg) {
201 logit("invalid public DH value: negative");
202 return 0;
203 }
204 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
205 logit("invalid public DH value: <= 1");
206 return 0;
207 }
208
209 if ((tmp = BN_new()) == NULL) {
210 error("%s: BN_new failed", __func__);
211 return 0;
212 }
213 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
214 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
215 BN_clear_free(tmp);
216 logit("invalid public DH value: >= p-1");
217 return 0;
218 }
219 BN_clear_free(tmp);
220
221 for (i = 0; i <= n; i++)
222 if (BN_is_bit_set(dh_pub, i))
223 bits_set++;
224 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
225
226 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
227 if (bits_set > 1)
228 return 1;
229
230 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
231 return 0;
232 }
233
234 void
dh_gen_key(DH * dh,int need)235 dh_gen_key(DH *dh, int need)
236 {
237 int i, bits_set, tries = 0;
238
239 if (dh->p == NULL)
240 fatal("dh_gen_key: dh->p == NULL");
241 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
242 fatal("dh_gen_key: group too small: %d (2*need %d)",
243 BN_num_bits(dh->p), 2*need);
244 do {
245 if (dh->priv_key != NULL)
246 BN_clear_free(dh->priv_key);
247 if ((dh->priv_key = BN_new()) == NULL)
248 fatal("dh_gen_key: BN_new failed");
249 /* generate a 2*need bits random private exponent */
250 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
251 fatal("dh_gen_key: BN_rand failed");
252 if (DH_generate_key(dh) == 0)
253 fatal("DH_generate_key");
254 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
255 if (BN_is_bit_set(dh->priv_key, i))
256 bits_set++;
257 debug2("dh_gen_key: priv key bits set: %d/%d",
258 bits_set, BN_num_bits(dh->priv_key));
259 if (tries++ > 10)
260 fatal("dh_gen_key: too many bad keys: giving up");
261 } while (!dh_pub_is_valid(dh, dh->pub_key));
262 }
263
264 DH *
dh_new_group_asc(const char * gen,const char * modulus)265 dh_new_group_asc(const char *gen, const char *modulus)
266 {
267 DH *dh;
268
269 if ((dh = DH_new()) == NULL)
270 fatal("dh_new_group_asc: DH_new");
271
272 if (BN_hex2bn(&dh->p, modulus) == 0)
273 fatal("BN_hex2bn p");
274 if (BN_hex2bn(&dh->g, gen) == 0)
275 fatal("BN_hex2bn g");
276
277 return (dh);
278 }
279
280 /*
281 * This just returns the group, we still need to generate the exchange
282 * value.
283 */
284
285 DH *
dh_new_group(BIGNUM * gen,BIGNUM * modulus)286 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
287 {
288 DH *dh;
289
290 if ((dh = DH_new()) == NULL)
291 fatal("dh_new_group: DH_new");
292 dh->p = modulus;
293 dh->g = gen;
294
295 return (dh);
296 }
297
298 DH *
dh_new_group1(void)299 dh_new_group1(void)
300 {
301 static char *gen = "2", *group1 =
302 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
303 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
304 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
305 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
306 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
307 "FFFFFFFF" "FFFFFFFF";
308
309 return (dh_new_group_asc(gen, group1));
310 }
311
312 DH *
dh_new_group14(void)313 dh_new_group14(void)
314 {
315 static char *gen = "2", *group14 =
316 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
317 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
318 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
319 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
320 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
321 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
322 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
323 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
324 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
325 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
326 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
327
328 return (dh_new_group_asc(gen, group14));
329 }
330
331 /*
332 * Estimates the group order for a Diffie-Hellman group that has an
333 * attack complexity approximately the same as O(2**bits). Estimate
334 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
335 */
336
337 int
dh_estimate(int bits)338 dh_estimate(int bits)
339 {
340
341 if (bits <= 128)
342 return (1024); /* O(2**86) */
343 if (bits <= 192)
344 return (2048); /* O(2**116) */
345 return (4096); /* O(2**156) */
346 }
347