1/*	$NetBSD: dh.c,v 1.4 2011/07/25 03:03:10 christos Exp $	*/
2/* $OpenBSD: dh.c,v 1.48 2009/10/01 11:37:33 grunk Exp $ */
3/*
4 * Copyright (c) 2000 Niels Provos.  All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "includes.h"
28__RCSID("$NetBSD: dh.c,v 1.4 2011/07/25 03:03:10 christos Exp $");
29#include <sys/param.h>
30
31#include <openssl/bn.h>
32#include <openssl/dh.h>
33
34#include <stdio.h>
35#include <stdlib.h>
36#include <string.h>
37#include <time.h>
38
39#include "dh.h"
40#include "pathnames.h"
41#include "log.h"
42#include "misc.h"
43#include "random.h"
44
45static int
46parse_prime(int linenum, char *line, struct dhgroup *dhg)
47{
48	char *cp, *arg;
49	char *strsize, *gen, *prime;
50	const char *errstr = NULL;
51	long long n;
52
53	cp = line;
54	if ((arg = strdelim(&cp)) == NULL)
55		return 0;
56	/* Ignore leading whitespace */
57	if (*arg == '\0')
58		arg = strdelim(&cp);
59	if (!arg || !*arg || *arg == '#')
60		return 0;
61
62	/* time */
63	if (cp == NULL || *arg == '\0')
64		goto fail;
65	arg = strsep(&cp, " "); /* type */
66	if (cp == NULL || *arg == '\0')
67		goto fail;
68	/* Ensure this is a safe prime */
69	n = strtonum(arg, 0, 5, &errstr);
70	if (errstr != NULL || n != MODULI_TYPE_SAFE)
71		goto fail;
72	arg = strsep(&cp, " "); /* tests */
73	if (cp == NULL || *arg == '\0')
74		goto fail;
75	/* Ensure prime has been tested and is not composite */
76	n = strtonum(arg, 0, 0x1f, &errstr);
77	if (errstr != NULL ||
78	    (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
79		goto fail;
80	arg = strsep(&cp, " "); /* tries */
81	if (cp == NULL || *arg == '\0')
82		goto fail;
83	n = strtonum(arg, 0, 1<<30, &errstr);
84	if (errstr != NULL || n == 0)
85		goto fail;
86	strsize = strsep(&cp, " "); /* size */
87	if (cp == NULL || *strsize == '\0' ||
88	    (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
89	    errstr)
90		goto fail;
91	/* The whole group is one bit larger */
92	dhg->size++;
93	gen = strsep(&cp, " "); /* gen */
94	if (cp == NULL || *gen == '\0')
95		goto fail;
96	prime = strsep(&cp, " "); /* prime */
97	if (cp != NULL || *prime == '\0')
98		goto fail;
99
100	if ((dhg->g = BN_new()) == NULL)
101		fatal("parse_prime: BN_new failed");
102	if ((dhg->p = BN_new()) == NULL)
103		fatal("parse_prime: BN_new failed");
104	if (BN_hex2bn(&dhg->g, gen) == 0)
105		goto failclean;
106
107	if (BN_hex2bn(&dhg->p, prime) == 0)
108		goto failclean;
109
110	if (BN_num_bits(dhg->p) != dhg->size)
111		goto failclean;
112
113	if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
114		goto failclean;
115
116	return (1);
117
118 failclean:
119	BN_clear_free(dhg->g);
120	BN_clear_free(dhg->p);
121 fail:
122	error("Bad prime description in line %d", linenum);
123	return (0);
124}
125
126DH *
127choose_dh(int min, int wantbits, int max)
128{
129	FILE *f;
130	char line[4096];
131	int best, bestcount, which;
132	int linenum;
133	struct dhgroup dhg;
134
135	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
136	    (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
137		logit("WARNING: %s does not exist, using fixed modulus",
138		    _PATH_DH_MODULI);
139		return (dh_new_group14());
140	}
141
142	linenum = 0;
143	best = bestcount = 0;
144	while (fgets(line, sizeof(line), f)) {
145		linenum++;
146		if (!parse_prime(linenum, line, &dhg))
147			continue;
148		BN_clear_free(dhg.g);
149		BN_clear_free(dhg.p);
150
151		if (dhg.size > max || dhg.size < min)
152			continue;
153
154		if ((dhg.size > wantbits && dhg.size < best) ||
155		    (dhg.size > best && best < wantbits)) {
156			best = dhg.size;
157			bestcount = 0;
158		}
159		if (dhg.size == best)
160			bestcount++;
161	}
162	rewind(f);
163
164	if (bestcount == 0) {
165		fclose(f);
166		logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
167		return (dh_new_group14());
168	}
169
170	linenum = 0;
171	which = arc4random_uniform(bestcount);
172	while (fgets(line, sizeof(line), f)) {
173		if (!parse_prime(linenum, line, &dhg))
174			continue;
175		if ((dhg.size > max || dhg.size < min) ||
176		    dhg.size != best ||
177		    linenum++ != which) {
178			BN_clear_free(dhg.g);
179			BN_clear_free(dhg.p);
180			continue;
181		}
182		break;
183	}
184	fclose(f);
185	if (linenum != which+1)
186		fatal("WARNING: line %d disappeared in %s, giving up",
187		    which, _PATH_DH_PRIMES);
188
189	return (dh_new_group(dhg.g, dhg.p));
190}
191
192/* diffie-hellman-groupN-sha1 */
193
194int
195dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
196{
197	int i;
198	int n = BN_num_bits(dh_pub);
199	int bits_set = 0;
200	BIGNUM *tmp;
201
202	if (dh_pub->neg) {
203		logit("invalid public DH value: negative");
204		return 0;
205	}
206	if (BN_cmp(dh_pub, BN_value_one()) != 1) {	/* pub_exp <= 1 */
207		logit("invalid public DH value: <= 1");
208		return 0;
209	}
210
211	if ((tmp = BN_new()) == NULL) {
212		error("%s: BN_new failed", __func__);
213		return 0;
214	}
215	if (!BN_sub(tmp, dh->p, BN_value_one()) ||
216	    BN_cmp(dh_pub, tmp) != -1) {		/* pub_exp > p-2 */
217		BN_clear_free(tmp);
218		logit("invalid public DH value: >= p-1");
219		return 0;
220	}
221	BN_clear_free(tmp);
222
223	for (i = 0; i <= n; i++)
224		if (BN_is_bit_set(dh_pub, i))
225			bits_set++;
226	debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
227
228	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
229	if (bits_set > 1)
230		return 1;
231
232	logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
233	return 0;
234}
235
236void
237dh_gen_key(DH *dh, int need)
238{
239	int i, bits_set, tries = 0;
240
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 const 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 const 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