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