[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.29 2004/02/27 22:49:27 dtucker 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 || *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;

	if ((dhg->g = BN_new()) == NULL)
		fatal("parse_prime: BN_new failed");
	if ((dhg->p = BN_new()) == NULL)
		fatal("parse_prime: BN_new failed");
	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;

	if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
		goto failclean;

	return (1);

 failclean:
	BN_clear_free(dhg->g);
	BN_clear_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[4096];
	int best, bestcount, which;
	int linenum;
	struct dhgroup dhg;

	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
	    (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
		logit("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_clear_free(dhg.g);
		BN_clear_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);
		logit("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_clear_free(dhg.g);
			BN_clear_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) {
		logit("invalid public DH value: negativ");
		return 0;
	}
	for (i = 0; i <= n; i++)
		if (BN_is_bit_set(dh_pub, i))
			bits_set++;
	debug2("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;
	logit("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, tries = 0;

	if (dh->p == NULL)
		fatal("dh_gen_key: dh->p == NULL");
	if (need > INT_MAX / 2 || 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_clear_free(dh->priv_key);
		if ((dh->priv_key = BN_new()) == 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, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
			if (BN_is_bit_set(dh->priv_key, i))
				bits_set++;
		debug2("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;

	if ((dh = DH_new()) == NULL)
		fatal("dh_new_group_asc: 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;

	if ((dh = DH_new()) == NULL)
		fatal("dh_new_group: 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 <= 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"
99be0775	26	RCSID("$OpenBSD: dh.c,v 1.29 2004/02/27 22:49:27 dtucker Exp $");
3c0ef626	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);
41b2f314	53	if (!arg \|\| !arg \|\| arg == '#')
3c0ef626	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
e9a17296	81	if ((dhg->g = BN_new()) == NULL)
	82	fatal("parse_prime: BN_new failed");
	83	if ((dhg->p = BN_new()) == NULL)
	84	fatal("parse_prime: BN_new failed");
3c0ef626	85	if (BN_hex2bn(&dhg->g, gen) == 0)
	86	goto failclean;
	87
	88	if (BN_hex2bn(&dhg->p, prime) == 0)
	89	goto failclean;
	90
	91	if (BN_num_bits(dhg->p) != dhg->size)
	92	goto failclean;
	93
99be0775	94	if (BN_is_zero(dhg->g) \|\| BN_is_one(dhg->g))
	95	goto failclean;
	96
3c0ef626	97	return (1);
	98
	99	failclean:
e9a17296	100	BN_clear_free(dhg->g);
e9a17296	101	BN_clear_free(dhg->p);
3c0ef626	102	fail:
	103	error("Bad prime description in line %d", linenum);
	104	return (0);
	105	}
	106
	107	DH *
	108	choose_dh(int min, int wantbits, int max)
	109	{
	110	FILE *f;
99be0775	111	char line[4096];
3c0ef626	112	int best, bestcount, which;
	113	int linenum;
	114	struct dhgroup dhg;
	115
	116	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
	117	(f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
0fff78ff	118	logit("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
3c0ef626	119	return (dh_new_group1());
	120	}
	121
	122	linenum = 0;
	123	best = bestcount = 0;
	124	while (fgets(line, sizeof(line), f)) {
	125	linenum++;
	126	if (!parse_prime(linenum, line, &dhg))
	127	continue;
e9a17296	128	BN_clear_free(dhg.g);
e9a17296	129	BN_clear_free(dhg.p);
3c0ef626	130
	131	if (dhg.size > max \|\| dhg.size < min)
	132	continue;
	133
	134	if ((dhg.size > wantbits && dhg.size < best) \|\|
	135	(dhg.size > best && best < wantbits)) {
	136	best = dhg.size;
	137	bestcount = 0;
	138	}
	139	if (dhg.size == best)
	140	bestcount++;
	141	}
	142	rewind(f);
	143
	144	if (bestcount == 0) {
	145	fclose(f);
0fff78ff	146	logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
3c0ef626	147	return (NULL);
	148	}
	149
	150	linenum = 0;
	151	which = arc4random() % bestcount;
	152	while (fgets(line, sizeof(line), f)) {
	153	if (!parse_prime(linenum, line, &dhg))
	154	continue;
	155	if ((dhg.size > max \|\| dhg.size < min) \|\|
	156	dhg.size != best \|\|
	157	linenum++ != which) {
e9a17296	158	BN_clear_free(dhg.g);
e9a17296	159	BN_clear_free(dhg.p);
3c0ef626	160	continue;
	161	}
	162	break;
	163	}
	164	fclose(f);
	165	if (linenum != which+1)
	166	fatal("WARNING: line %d disappeared in %s, giving up",
	167	which, _PATH_DH_PRIMES);
	168
	169	return (dh_new_group(dhg.g, dhg.p));
	170	}
	171
	172	/* diffie-hellman-group1-sha1 */
	173
	174	int
	175	dh_pub_is_valid(DH dh, BIGNUM dh_pub)
	176	{
	177	int i;
	178	int n = BN_num_bits(dh_pub);
	179	int bits_set = 0;
	180
	181	if (dh_pub->neg) {
0fff78ff	182	logit("invalid public DH value: negativ");
3c0ef626	183	return 0;
	184	}
	185	for (i = 0; i <= n; i++)
	186	if (BN_is_bit_set(dh_pub, i))
	187	bits_set++;
6a9b3198	188	debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
3c0ef626	189
	190	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
	191	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
	192	return 1;
0fff78ff	193	logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
3c0ef626	194	return 0;
	195	}
	196
	197	void
	198	dh_gen_key(DH *dh, int need)
	199	{
99be0775	200	int i, bits_set, tries = 0;
3c0ef626	201
	202	if (dh->p == NULL)
	203	fatal("dh_gen_key: dh->p == NULL");
cdd66111	204	if (need > INT_MAX / 2 \|\| 2 * need >= BN_num_bits(dh->p))
3c0ef626	205	fatal("dh_gen_key: group too small: %d (2*need %d)",
	206	BN_num_bits(dh->p), 2*need);
	207	do {
	208	if (dh->priv_key != NULL)
e9a17296	209	BN_clear_free(dh->priv_key);
e9a17296	210	if ((dh->priv_key = BN_new()) == NULL)
3c0ef626	211	fatal("dh_gen_key: BN_new failed");
	212	/* generate a 2need bits random private exponent /
	213	if (!BN_rand(dh->priv_key, 2*need, 0, 0))
	214	fatal("dh_gen_key: BN_rand failed");
	215	if (DH_generate_key(dh) == 0)
	216	fatal("DH_generate_key");
99be0775	217	for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
3c0ef626	218	if (BN_is_bit_set(dh->priv_key, i))
3c0ef626	219	bits_set++;
6a9b3198	220	debug2("dh_gen_key: priv key bits set: %d/%d",
3c0ef626	221	bits_set, BN_num_bits(dh->priv_key));
	222	if (tries++ > 10)
	223	fatal("dh_gen_key: too many bad keys: giving up");
	224	} while (!dh_pub_is_valid(dh, dh->pub_key));
	225	}
	226
	227	DH *
	228	dh_new_group_asc(const char gen, const char modulus)
	229	{
	230	DH *dh;
	231
e9a17296	232	if ((dh = DH_new()) == NULL)
e9a17296	233	fatal("dh_new_group_asc: DH_new");
3c0ef626	234
	235	if (BN_hex2bn(&dh->p, modulus) == 0)
	236	fatal("BN_hex2bn p");
	237	if (BN_hex2bn(&dh->g, gen) == 0)
	238	fatal("BN_hex2bn g");
	239
	240	return (dh);
	241	}
	242
	243	/*
	244	* This just returns the group, we still need to generate the exchange
	245	* value.
	246	*/
	247
	248	DH *
	249	dh_new_group(BIGNUM gen, BIGNUM modulus)
	250	{
	251	DH *dh;
	252
e9a17296	253	if ((dh = DH_new()) == NULL)
e9a17296	254	fatal("dh_new_group: DH_new");
3c0ef626	255	dh->p = modulus;
	256	dh->g = gen;
	257
	258	return (dh);
	259	}
	260
	261	DH *
	262	dh_new_group1(void)
	263	{
	264	static char gen = "2", group1 =
	265	"FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
	266	"29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
	267	"EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
	268	"E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
	269	"EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
	270	"FFFFFFFF" "FFFFFFFF";
	271
	272	return (dh_new_group_asc(gen, group1));
	273	}
	274
	275	/*
	276	* Estimates the group order for a Diffie-Hellman group that has an
	277	* attack complexity approximately the same as O(2**bits). Estimate
	278	* with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
	279	*/
	280
	281	int
	282	dh_estimate(int bits)
	283	{
	284
cdd66111	285	if (bits <= 128)
3c0ef626	286	return (1024); /* O(2*86) /
cdd66111	287	if (bits <= 192)
3c0ef626	288	return (2048); /* O(2*116) /
	289	return (4096); /* O(2*156) /
	290	}