[openssh.git] / 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.28 2004/02/27 22:44:56 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 = 0, 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; 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
94ec8c6b	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"
cd744742	26	RCSID("$OpenBSD: dh.c,v 1.28 2004/02/27 22:44:56 dtucker Exp $");
94ec8c6b	27
	28	#include "xmalloc.h"
	29
	30	#include <openssl/bn.h>
	31	#include <openssl/dh.h>
	32	#include <openssl/evp.h>
	33
94ec8c6b	34	#include "buffer.h"
42f11eb2	35	#include "cipher.h"
94ec8c6b	36	#include "kex.h"
94ec8c6b	37	#include "dh.h"
42f11eb2	38	#include "pathnames.h"
	39	#include "log.h"
	40	#include "misc.h"
94ec8c6b	41
396c147e	42	static int
94ec8c6b	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);
f11fe301	53	if (!arg \|\| !arg \|\| arg == '#')
94ec8c6b	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;
db1cd2f3	72	/* The whole group is one bit larger */
db1cd2f3	73	dhg->size++;
94ec8c6b	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
b775c6f2	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");
ec1f12d3	85	if (BN_hex2bn(&dhg->g, gen) == 0)
c8682232	86	goto failclean;
c8682232	87
ec1f12d3	88	if (BN_hex2bn(&dhg->p, prime) == 0)
c8682232	89	goto failclean;
	90
	91	if (BN_num_bits(dhg->p) != dhg->size)
	92	goto failclean;
94ec8c6b	93
8b0a55ac	94	if (BN_is_zero(dhg->g) \|\| BN_is_one(dhg->g))
	95	goto failclean;
	96
94ec8c6b	97	return (1);
c8682232	98
c8682232	99	failclean:
108d362e	100	BN_clear_free(dhg->g);
108d362e	101	BN_clear_free(dhg->p);
94ec8c6b	102	fail:
54b974dc	103	error("Bad prime description in line %d", linenum);
94ec8c6b	104	return (0);
	105	}
	106
	107	DH *
db1cd2f3	108	choose_dh(int min, int wantbits, int max)
94ec8c6b	109	{
94ec8c6b	110	FILE *f;
cd744742	111	char line[4096];
94ec8c6b	112	int best, bestcount, which;
	113	int linenum;
	114	struct dhgroup dhg;
	115
e2854364	116	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
e2854364	117	(f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
bbe88b6d	118	logit("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
94ec8c6b	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;
108d362e	128	BN_clear_free(dhg.g);
108d362e	129	BN_clear_free(dhg.p);
94ec8c6b	130
db1cd2f3	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)) {
94ec8c6b	136	best = dhg.size;
	137	bestcount = 0;
	138	}
	139	if (dhg.size == best)
	140	bestcount++;
	141	}
826676b3	142	rewind(f);
94ec8c6b	143
94ec8c6b	144	if (bestcount == 0) {
826676b3	145	fclose(f);
bbe88b6d	146	logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
db1cd2f3	147	return (NULL);
94ec8c6b	148	}
94ec8c6b	149
94ec8c6b	150	linenum = 0;
	151	which = arc4random() % bestcount;
	152	while (fgets(line, sizeof(line), f)) {
	153	if (!parse_prime(linenum, line, &dhg))
	154	continue;
a7ca6275	155	if ((dhg.size > max \|\| dhg.size < min) \|\|
	156	dhg.size != best \|\|
	157	linenum++ != which) {
108d362e	158	BN_clear_free(dhg.g);
108d362e	159	BN_clear_free(dhg.p);
94ec8c6b	160	continue;
	161	}
	162	break;
	163	}
	164	fclose(f);
a7ca6275	165	if (linenum != which+1)
	166	fatal("WARNING: line %d disappeared in %s, giving up",
	167	which, _PATH_DH_PRIMES);
94ec8c6b	168
	169	return (dh_new_group(dhg.g, dhg.p));
	170	}
03b8f8be	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) {
bbe88b6d	182	logit("invalid public DH value: negativ");
03b8f8be	183	return 0;
	184	}
	185	for (i = 0; i <= n; i++)
	186	if (BN_is_bit_set(dh_pub, i))
	187	bits_set++;
35efb24c	188	debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
03b8f8be	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;
bbe88b6d	193	logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
03b8f8be	194	return 0;
	195	}
	196
	197	void
	198	dh_gen_key(DH *dh, int need)
	199	{
	200	int i, bits_set = 0, tries = 0;
	201
	202	if (dh->p == NULL)
	203	fatal("dh_gen_key: dh->p == NULL");
bb92e5cc	204	if (need > INT_MAX / 2 \|\| 2 * need >= BN_num_bits(dh->p))
03b8f8be	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)
108d362e	209	BN_clear_free(dh->priv_key);
b775c6f2	210	if ((dh->priv_key = BN_new()) == NULL)
03b8f8be	211	fatal("dh_gen_key: BN_new failed");
03b8f8be	212	/* generate a 2need bits random private exponent /
83a9aa63	213	if (!BN_rand(dh->priv_key, 2*need, 0, 0))
83a9aa63	214	fatal("dh_gen_key: BN_rand failed");
03b8f8be	215	if (DH_generate_key(dh) == 0)
	216	fatal("DH_generate_key");
	217	for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
	218	if (BN_is_bit_set(dh->priv_key, i))
	219	bits_set++;
35efb24c	220	debug2("dh_gen_key: priv key bits set: %d/%d",
03b8f8be	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;
03b8f8be	231
b775c6f2	232	if ((dh = DH_new()) == NULL)
b775c6f2	233	fatal("dh_new_group_asc: DH_new");
03b8f8be	234
ec1f12d3	235	if (BN_hex2bn(&dh->p, modulus) == 0)
03b8f8be	236	fatal("BN_hex2bn p");
ec1f12d3	237	if (BN_hex2bn(&dh->g, gen) == 0)
03b8f8be	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
b775c6f2	253	if ((dh = DH_new()) == NULL)
b775c6f2	254	fatal("dh_new_group: DH_new");
03b8f8be	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	}
a5c9ffdb	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
b3c35b71	285	if (bits <= 128)
a5c9ffdb	286	return (1024); /* O(2*86) /
b3c35b71	287	if (bits <= 192)
a5c9ffdb	288	return (2048); /* O(2*116) /
	289	return (4096); /* O(2*156) /
	290	}