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