[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.16 2001/06/22 21:57:59 provos 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"

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
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"
826676b3	26	RCSID("$OpenBSD: dh.c,v 1.16 2001/06/22 21:57:59 provos 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
	42	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;
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
	81	dhg->g = BN_new();
94ec8c6b	82	dhg->p = BN_new();
ec1f12d3	83	if (BN_hex2bn(&dhg->g, gen) == 0)
c8682232	84	goto failclean;
c8682232	85
ec1f12d3	86	if (BN_hex2bn(&dhg->p, prime) == 0)
c8682232	87	goto failclean;
	88
	89	if (BN_num_bits(dhg->p) != dhg->size)
	90	goto failclean;
94ec8c6b	91
94ec8c6b	92	return (1);
c8682232	93
	94	failclean:
	95	BN_free(dhg->g);
	96	BN_free(dhg->p);
94ec8c6b	97	fail:
54b974dc	98	error("Bad prime description in line %d", linenum);
94ec8c6b	99	return (0);
	100	}
	101
	102	DH *
db1cd2f3	103	choose_dh(int min, int wantbits, int max)
94ec8c6b	104	{
94ec8c6b	105	FILE *f;
826676b3	106	char line[2048];
94ec8c6b	107	int best, bestcount, which;
	108	int linenum;
	109	struct dhgroup dhg;
	110
e2854364	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);
94ec8c6b	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
db1cd2f3	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)) {
94ec8c6b	131	best = dhg.size;
	132	bestcount = 0;
	133	}
	134	if (dhg.size == best)
	135	bestcount++;
	136	}
826676b3	137	rewind(f);
94ec8c6b	138
94ec8c6b	139	if (bestcount == 0) {
826676b3	140	fclose(f);
db1cd2f3	141	log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
db1cd2f3	142	return (NULL);
94ec8c6b	143	}
94ec8c6b	144
94ec8c6b	145	linenum = 0;
	146	which = arc4random() % bestcount;
	147	while (fgets(line, sizeof(line), f)) {
	148	if (!parse_prime(linenum, line, &dhg))
	149	continue;
a7ca6275	150	if ((dhg.size > max \|\| dhg.size < min) \|\|
	151	dhg.size != best \|\|
	152	linenum++ != which) {
94ec8c6b	153	BN_free(dhg.g);
	154	BN_free(dhg.p);
	155	continue;
	156	}
	157	break;
	158	}
	159	fclose(f);
a7ca6275	160	if (linenum != which+1)
	161	fatal("WARNING: line %d disappeared in %s, giving up",
	162	which, _PATH_DH_PRIMES);
94ec8c6b	163
	164	return (dh_new_group(dhg.g, dhg.p));
	165	}
03b8f8be	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;
03b8f8be	227
	228	dh = DH_new();
	229	if (dh == NULL)
	230	fatal("DH_new");
	231
ec1f12d3	232	if (BN_hex2bn(&dh->p, modulus) == 0)
03b8f8be	233	fatal("BN_hex2bn p");
ec1f12d3	234	if (BN_hex2bn(&dh->g, gen) == 0)
03b8f8be	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	}
a5c9ffdb	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	}