[gssapi-openssh.git] / openssh / dh.c

/*
 * Copyright (c) 2000 Niels Provos.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "includes.h"
RCSID("$OpenBSD: dh.c,v 1.17 2001/06/23 15:12:18 itojun Exp $");

#include "xmalloc.h"

#include <openssl/bn.h>
#include <openssl/dh.h>
#include <openssl/evp.h>

#include "buffer.h"
#include "cipher.h"
#include "kex.h"
#include "dh.h"
#include "pathnames.h"
#include "log.h"
#include "misc.h"

static int
parse_prime(int linenum, char *line, struct dhgroup *dhg)
{
	char *cp, *arg;
	char *strsize, *gen, *prime;

	cp = line;
	arg = strdelim(&cp);
	/* Ignore leading whitespace */
	if (*arg == '\0')
		arg = strdelim(&cp);
	if (!*arg || *arg == '#')
		return 0;

	/* time */
	if (cp == NULL || *arg == '\0')
		goto fail;
	arg = strsep(&cp, " "); /* type */
	if (cp == NULL || *arg == '\0')
		goto fail;
	arg = strsep(&cp, " "); /* tests */
	if (cp == NULL || *arg == '\0')
		goto fail;
	arg = strsep(&cp, " "); /* tries */
	if (cp == NULL || *arg == '\0')
		goto fail;
	strsize = strsep(&cp, " "); /* size */
	if (cp == NULL || *strsize == '\0' ||
	    (dhg->size = atoi(strsize)) == 0)
		goto fail;
	/* The whole group is one bit larger */
	dhg->size++;
	gen = strsep(&cp, " "); /* gen */
	if (cp == NULL || *gen == '\0')
		goto fail;
	prime = strsep(&cp, " "); /* prime */
	if (cp != NULL || *prime == '\0')
		goto fail;

	dhg->g = BN_new();
	dhg->p = BN_new();
	if (BN_hex2bn(&dhg->g, gen) == 0)
		goto failclean;

	if (BN_hex2bn(&dhg->p, prime) == 0)
		goto failclean;

	if (BN_num_bits(dhg->p) != dhg->size)
		goto failclean;

	return (1);

 failclean:
	BN_free(dhg->g);
	BN_free(dhg->p);
 fail:
	error("Bad prime description in line %d", linenum);
	return (0);
}

DH *
choose_dh(int min, int wantbits, int max)
{
	FILE *f;
	char line[2048];
	int best, bestcount, which;
	int linenum;
	struct dhgroup dhg;

	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
	    (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
		log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
		return (dh_new_group1());
	}

	linenum = 0;
	best = bestcount = 0;
	while (fgets(line, sizeof(line), f)) {
		linenum++;
		if (!parse_prime(linenum, line, &dhg))
			continue;
		BN_free(dhg.g);
		BN_free(dhg.p);

		if (dhg.size > max || dhg.size < min)
			continue;

		if ((dhg.size > wantbits && dhg.size < best) ||
		    (dhg.size > best && best < wantbits)) {
			best = dhg.size;
			bestcount = 0;
		}
		if (dhg.size == best)
			bestcount++;
	}
	rewind(f);

	if (bestcount == 0) {
		fclose(f);
		log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
		return (NULL);
	}

	linenum = 0;
	which = arc4random() % bestcount;
	while (fgets(line, sizeof(line), f)) {
		if (!parse_prime(linenum, line, &dhg))
			continue;
		if ((dhg.size > max || dhg.size < min) ||
		    dhg.size != best ||
		    linenum++ != which) {
			BN_free(dhg.g);
			BN_free(dhg.p);
			continue;
		}
		break;
	}
	fclose(f);
	if (linenum != which+1)
		fatal("WARNING: line %d disappeared in %s, giving up",
		    which, _PATH_DH_PRIMES);

	return (dh_new_group(dhg.g, dhg.p));
}

/* diffie-hellman-group1-sha1 */

int
dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
{
	int i;
	int n = BN_num_bits(dh_pub);
	int bits_set = 0;

	if (dh_pub->neg) {
		log("invalid public DH value: negativ");
		return 0;
	}
	for (i = 0; i <= n; i++)
		if (BN_is_bit_set(dh_pub, i))
			bits_set++;
	debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));

	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
		return 1;
	log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
	return 0;
}

void
dh_gen_key(DH *dh, int need)
{
	int i, bits_set = 0, tries = 0;

	if (dh->p == NULL)
		fatal("dh_gen_key: dh->p == NULL");
	if (2*need >= BN_num_bits(dh->p))
		fatal("dh_gen_key: group too small: %d (2*need %d)",
		    BN_num_bits(dh->p), 2*need);
	do {
		if (dh->priv_key != NULL)
			BN_free(dh->priv_key);
		dh->priv_key = BN_new();
		if (dh->priv_key == NULL)
			fatal("dh_gen_key: BN_new failed");
		/* generate a 2*need bits random private exponent */
		if (!BN_rand(dh->priv_key, 2*need, 0, 0))
			fatal("dh_gen_key: BN_rand failed");
		if (DH_generate_key(dh) == 0)
			fatal("DH_generate_key");
		for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
			if (BN_is_bit_set(dh->priv_key, i))
				bits_set++;
		debug("dh_gen_key: priv key bits set: %d/%d",
		    bits_set, BN_num_bits(dh->priv_key));
		if (tries++ > 10)
			fatal("dh_gen_key: too many bad keys: giving up");
	} while (!dh_pub_is_valid(dh, dh->pub_key));
}

DH *
dh_new_group_asc(const char *gen, const char *modulus)
{
	DH *dh;

	dh = DH_new();
	if (dh == NULL)
		fatal("DH_new");

	if (BN_hex2bn(&dh->p, modulus) == 0)
		fatal("BN_hex2bn p");
	if (BN_hex2bn(&dh->g, gen) == 0)
		fatal("BN_hex2bn g");

	return (dh);
}

/*
 * This just returns the group, we still need to generate the exchange
 * value.
 */

DH *
dh_new_group(BIGNUM *gen, BIGNUM *modulus)
{
	DH *dh;

	dh = DH_new();
	if (dh == NULL)
		fatal("DH_new");
	dh->p = modulus;
	dh->g = gen;

	return (dh);
}

DH *
dh_new_group1(void)
{
	static char *gen = "2", *group1 =
	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
	    "FFFFFFFF" "FFFFFFFF";

	return (dh_new_group_asc(gen, group1));
}

/*
 * Estimates the group order for a Diffie-Hellman group that has an
 * attack complexity approximately the same as O(2**bits).  Estimate
 * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 */

int
dh_estimate(int bits)
{

	if (bits < 64)
		return (512);	/* O(2**63) */
	if (bits < 128)
		return (1024);	/* O(2**86) */
	if (bits < 192)
		return (2048);	/* O(2**116) */
	return (4096);		/* O(2**156) */
}
Commit	Line	Data
3c0ef626	1	/*
	2	* Copyright (c) 2000 Niels Provos. All rights reserved.
	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted provided that the following conditions
	6	* are met:
	7	* 1. Redistributions of source code must retain the above copyright
	8	* notice, this list of conditions and the following disclaimer.
	9	* 2. Redistributions in binary form must reproduce the above copyright
	10	* notice, this list of conditions and the following disclaimer in the
	11	* documentation and/or other materials provided with the distribution.
	12	*
	13	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	14	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	15	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	16	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	17	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	18	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	19	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	20	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	21	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	22	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	23	*/
	24
	25	#include "includes.h"
	26	RCSID("$OpenBSD: dh.c,v 1.17 2001/06/23 15:12:18 itojun Exp $");
	27
	28	#include "xmalloc.h"
	29
	30	#include <openssl/bn.h>
	31	#include <openssl/dh.h>
	32	#include <openssl/evp.h>
	33
	34	#include "buffer.h"
	35	#include "cipher.h"
	36	#include "kex.h"
	37	#include "dh.h"
	38	#include "pathnames.h"
	39	#include "log.h"
	40	#include "misc.h"
	41
	42	static int
	43	parse_prime(int linenum, char line, struct dhgroup dhg)
	44	{
	45	char cp, arg;
	46	char strsize, gen, *prime;
	47
	48	cp = line;
	49	arg = strdelim(&cp);
	50	/* Ignore leading whitespace */
	51	if (*arg == '\0')
	52	arg = strdelim(&cp);
	53	if (!arg \|\| arg == '#')
	54	return 0;
	55
	56	/* time */
	57	if (cp == NULL \|\| *arg == '\0')
	58	goto fail;
	59	arg = strsep(&cp, " "); /* type */
	60	if (cp == NULL \|\| *arg == '\0')
	61	goto fail;
	62	arg = strsep(&cp, " "); /* tests */
	63	if (cp == NULL \|\| *arg == '\0')
	64	goto fail;
65	arg = strsep(&cp, " "); /* tries */
66	if (cp == NULL \|\| *arg == '\0')
67	goto fail;
68	strsize = strsep(&cp, " "); /* size */
69	if (cp == NULL \|\| *strsize == '\0' \|\|
70	(dhg->size = atoi(strsize)) == 0)
71	goto fail;
72	/* The whole group is one bit larger */
73	dhg->size++;
74	gen = strsep(&cp, " "); /* gen */
75	if (cp == NULL \|\| *gen == '\0')
76	goto fail;
77	prime = strsep(&cp, " "); /* prime */
78	if (cp != NULL \|\| *prime == '\0')
79	goto fail;
80
81	dhg->g = BN_new();
82	dhg->p = BN_new();
83	if (BN_hex2bn(&dhg->g, gen) == 0)
84	goto failclean;
85
86	if (BN_hex2bn(&dhg->p, prime) == 0)
87	goto failclean;
88
89	if (BN_num_bits(dhg->p) != dhg->size)
90	goto failclean;
91
92	return (1);
93
94	failclean:
95	BN_free(dhg->g);
96	BN_free(dhg->p);
97	fail:
98	error("Bad prime description in line %d", linenum);
99	return (0);
100	}
101
102	DH *
103	choose_dh(int min, int wantbits, int max)
104	{
105	FILE *f;
106	char line[2048];
107	int best, bestcount, which;
108	int linenum;
109	struct dhgroup dhg;
110
111	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
112	(f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
113	log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
114	return (dh_new_group1());
115	}
116
117	linenum = 0;
118	best = bestcount = 0;
119	while (fgets(line, sizeof(line), f)) {
120	linenum++;
121	if (!parse_prime(linenum, line, &dhg))
122	continue;
123	BN_free(dhg.g);
124	BN_free(dhg.p);
125
126	if (dhg.size > max \|\| dhg.size < min)
127	continue;
128
129	if ((dhg.size > wantbits && dhg.size < best) \|\|
130	(dhg.size > best && best < wantbits)) {
131	best = dhg.size;
132	bestcount = 0;
133	}
134	if (dhg.size == best)
135	bestcount++;
136	}
137	rewind(f);
138
139	if (bestcount == 0) {
140	fclose(f);
141	log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
142	return (NULL);
143	}
144
145	linenum = 0;
146	which = arc4random() % bestcount;
147	while (fgets(line, sizeof(line), f)) {
148	if (!parse_prime(linenum, line, &dhg))
149	continue;
150	if ((dhg.size > max \|\| dhg.size < min) \|\|
151	dhg.size != best \|\|
152	linenum++ != which) {
153	BN_free(dhg.g);
154	BN_free(dhg.p);
155	continue;
156	}
157	break;
158	}
159	fclose(f);
160	if (linenum != which+1)
161	fatal("WARNING: line %d disappeared in %s, giving up",
162	which, _PATH_DH_PRIMES);
163
164	return (dh_new_group(dhg.g, dhg.p));
165	}
166
167	/* diffie-hellman-group1-sha1 */
168
169	int
170	dh_pub_is_valid(DH dh, BIGNUM dh_pub)
171	{
172	int i;
173	int n = BN_num_bits(dh_pub);
174	int bits_set = 0;
175
176	if (dh_pub->neg) {
177	log("invalid public DH value: negativ");
178	return 0;
179	}
180	for (i = 0; i <= n; i++)
181	if (BN_is_bit_set(dh_pub, i))
182	bits_set++;
183	debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
184
185	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
186	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
187	return 1;
188	log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
189	return 0;
190	}
191
192	void
193	dh_gen_key(DH *dh, int need)
194	{
195	int i, bits_set = 0, tries = 0;
196
197	if (dh->p == NULL)
198	fatal("dh_gen_key: dh->p == NULL");
199	if (2*need >= BN_num_bits(dh->p))
200	fatal("dh_gen_key: group too small: %d (2*need %d)",
201	BN_num_bits(dh->p), 2*need);
202	do {
203	if (dh->priv_key != NULL)
204	BN_free(dh->priv_key);
205	dh->priv_key = BN_new();
206	if (dh->priv_key == NULL)
207	fatal("dh_gen_key: BN_new failed");
208	/* generate a 2need bits random private exponent /
209	if (!BN_rand(dh->priv_key, 2*need, 0, 0))
210	fatal("dh_gen_key: BN_rand failed");
211	if (DH_generate_key(dh) == 0)
212	fatal("DH_generate_key");
213	for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
214	if (BN_is_bit_set(dh->priv_key, i))
215	bits_set++;
216	debug("dh_gen_key: priv key bits set: %d/%d",
217	bits_set, BN_num_bits(dh->priv_key));
218	if (tries++ > 10)
219	fatal("dh_gen_key: too many bad keys: giving up");
220	} while (!dh_pub_is_valid(dh, dh->pub_key));
221	}
222
223	DH *
224	dh_new_group_asc(const char gen, const char modulus)
225	{
226	DH *dh;
227
228	dh = DH_new();
229	if (dh == NULL)
230	fatal("DH_new");
231
232	if (BN_hex2bn(&dh->p, modulus) == 0)
233	fatal("BN_hex2bn p");
234	if (BN_hex2bn(&dh->g, gen) == 0)
235	fatal("BN_hex2bn g");
236
237	return (dh);
238	}
239
240	/*
241	* This just returns the group, we still need to generate the exchange
242	* value.
243	*/
244
245	DH *
246	dh_new_group(BIGNUM gen, BIGNUM modulus)
247	{
248	DH *dh;
249
250	dh = DH_new();
251	if (dh == NULL)
252	fatal("DH_new");
253	dh->p = modulus;
254	dh->g = gen;
255
256	return (dh);
257	}
258
259	DH *
260	dh_new_group1(void)
261	{
262	static char gen = "2", group1 =
263	"FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
264	"29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
265	"EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
266	"E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
267	"EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
268	"FFFFFFFF" "FFFFFFFF";
269
270	return (dh_new_group_asc(gen, group1));
271	}
272
273	/*
274	* Estimates the group order for a Diffie-Hellman group that has an
275	* attack complexity approximately the same as O(2**bits). Estimate
276	* with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
277	*/
278
279	int
280	dh_estimate(int bits)
281	{
282
283	if (bits < 64)
284	return (512); /* O(2*63) /
285	if (bits < 128)
286	return (1024); /* O(2*86) /
287	if (bits < 192)
288	return (2048); /* O(2*116) /
289	return (4096); /* O(2*156) /
290	}