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