dh.c revision 240075
1/* $OpenBSD: dh.c,v 1.49 2011/12/07 05:44:38 djm 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
43static int
44parse_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
124DH *
125choose_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
192int
193dh_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
234void
235dh_gen_key(DH *dh, int need)
236{
237	int i, bits_set, tries = 0;
238
239	if (need < 0)
240		fatal("dh_gen_key: need < 0");
241	if (dh->p == NULL)
242		fatal("dh_gen_key: dh->p == NULL");
243	if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
244		fatal("dh_gen_key: group too small: %d (2*need %d)",
245		    BN_num_bits(dh->p), 2*need);
246	do {
247		if (dh->priv_key != NULL)
248			BN_clear_free(dh->priv_key);
249		if ((dh->priv_key = BN_new()) == NULL)
250			fatal("dh_gen_key: BN_new failed");
251		/* generate a 2*need bits random private exponent */
252		if (!BN_rand(dh->priv_key, 2*need, 0, 0))
253			fatal("dh_gen_key: BN_rand failed");
254		if (DH_generate_key(dh) == 0)
255			fatal("DH_generate_key");
256		for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
257			if (BN_is_bit_set(dh->priv_key, i))
258				bits_set++;
259		debug2("dh_gen_key: priv key bits set: %d/%d",
260		    bits_set, BN_num_bits(dh->priv_key));
261		if (tries++ > 10)
262			fatal("dh_gen_key: too many bad keys: giving up");
263	} while (!dh_pub_is_valid(dh, dh->pub_key));
264}
265
266DH *
267dh_new_group_asc(const char *gen, const char *modulus)
268{
269	DH *dh;
270
271	if ((dh = DH_new()) == NULL)
272		fatal("dh_new_group_asc: DH_new");
273
274	if (BN_hex2bn(&dh->p, modulus) == 0)
275		fatal("BN_hex2bn p");
276	if (BN_hex2bn(&dh->g, gen) == 0)
277		fatal("BN_hex2bn g");
278
279	return (dh);
280}
281
282/*
283 * This just returns the group, we still need to generate the exchange
284 * value.
285 */
286
287DH *
288dh_new_group(BIGNUM *gen, BIGNUM *modulus)
289{
290	DH *dh;
291
292	if ((dh = DH_new()) == NULL)
293		fatal("dh_new_group: DH_new");
294	dh->p = modulus;
295	dh->g = gen;
296
297	return (dh);
298}
299
300DH *
301dh_new_group1(void)
302{
303	static char *gen = "2", *group1 =
304	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
305	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
306	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
307	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
308	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
309	    "FFFFFFFF" "FFFFFFFF";
310
311	return (dh_new_group_asc(gen, group1));
312}
313
314DH *
315dh_new_group14(void)
316{
317	static char *gen = "2", *group14 =
318	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
319	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
320	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
321	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
322	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
323	    "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
324	    "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
325	    "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
326	    "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
327	    "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
328	    "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
329
330	return (dh_new_group_asc(gen, group14));
331}
332
333/*
334 * Estimates the group order for a Diffie-Hellman group that has an
335 * attack complexity approximately the same as O(2**bits).  Estimate
336 * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
337 */
338
339int
340dh_estimate(int bits)
341{
342
343	if (bits <= 128)
344		return (1024);	/* O(2**86) */
345	if (bits <= 192)
346		return (2048);	/* O(2**116) */
347	return (4096);		/* O(2**156) */
348}
349