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