dh.c revision 262566 
1/* $OpenBSD: dh.c,v 1.53 2013/11/21 00:45:44 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	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 pbits;
258
259	if (need <= 0)
260		fatal("%s: need <= 0", __func__);
261	if (dh->p == NULL)
262		fatal("%s: dh->p == NULL", __func__);
263	if ((pbits = BN_num_bits(dh->p)) <= 0)
264		fatal("%s: bits(p) <= 0", __func__);
265	dh->length = MIN(need * 2, pbits - 1);
266	if (DH_generate_key(dh) == 0)
267		fatal("%s: key generation failed", __func__);
268	if (!dh_pub_is_valid(dh, dh->pub_key))
269		fatal("%s: generated invalid key", __func__);
270}
271
272DH *
273dh_new_group_asc(const char *gen, const char *modulus)
274{
275	DH *dh;
276
277	if ((dh = DH_new()) == NULL)
278		fatal("dh_new_group_asc: DH_new");
279
280	if (BN_hex2bn(&dh->p, modulus) == 0)
281		fatal("BN_hex2bn p");
282	if (BN_hex2bn(&dh->g, gen) == 0)
283		fatal("BN_hex2bn g");
284
285	return (dh);
286}
287
288/*
289 * This just returns the group, we still need to generate the exchange
290 * value.
291 */
292
293DH *
294dh_new_group(BIGNUM *gen, BIGNUM *modulus)
295{
296	DH *dh;
297
298	if ((dh = DH_new()) == NULL)
299		fatal("dh_new_group: DH_new");
300	dh->p = modulus;
301	dh->g = gen;
302
303	return (dh);
304}
305
306DH *
307dh_new_group1(void)
308{
309	static char *gen = "2", *group1 =
310	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
311	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
312	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
313	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
314	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
315	    "FFFFFFFF" "FFFFFFFF";
316
317	return (dh_new_group_asc(gen, group1));
318}
319
320DH *
321dh_new_group14(void)
322{
323	static char *gen = "2", *group14 =
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" "ECE45B3D"
329	    "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
330	    "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
331	    "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
332	    "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
333	    "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
334	    "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
335
336	return (dh_new_group_asc(gen, group14));
337}
338
339/*
340 * Estimates the group order for a Diffie-Hellman group that has an
341 * attack complexity approximately the same as O(2**bits).
342 * Values from NIST Special Publication 800-57: Recommendation for Key
343 * Management Part 1 (rev 3) limited by the recommended maximum value
344 * from RFC4419 section 3.
345 */
346
347int
348dh_estimate(int bits)
349{
350	if (bits <= 112)
351		return 2048;
352	if (bits <= 128)
353		return 3072;
354	if (bits <= 192)
355		return 7680;
356	return 8192;
357}
358