[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.12 2001/04/03 19:53:29 markus 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[1024];
	int best, bestcount, which;
	int linenum;
	struct dhgroup dhg;

	f = fopen(_PATH_DH_PRIMES, "r");
	if (!f) {
		log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES);
		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++;
	}
	fclose (f);

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

	f = fopen(_PATH_DH_PRIMES, "r");
	if (!f) {
		fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES);
	}

	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)
			continue;
		if (dhg.size != best)
			continue;
		if (linenum++ != which) {
			BN_free(dhg.g);
			BN_free(dhg.p);
			continue;
		}
		break;
	}
	fclose(f);

	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;
	int ret;

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

	if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
		fatal("BN_hex2bn p");
	if ((ret = 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"
a5c9ffdb	26	RCSID("$OpenBSD: dh.c,v 1.12 2001/04/03 19:53:29 markus 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();
c8682232	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;
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	{
	105	FILE *f;
	106	char line[1024];
	107	int best, bestcount, which;
	108	int linenum;
	109	struct dhgroup dhg;
	110
42f11eb2	111	f = fopen(_PATH_DH_PRIMES, "r");
94ec8c6b	112	if (!f) {
42f11eb2	113	log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES);
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	}
	137	fclose (f);
	138
	139	if (bestcount == 0) {
db1cd2f3	140	log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
db1cd2f3	141	return (NULL);
94ec8c6b	142	}
94ec8c6b	143
42f11eb2	144	f = fopen(_PATH_DH_PRIMES, "r");
94ec8c6b	145	if (!f) {
0b2190ee	146	fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES);
94ec8c6b	147	}
	148
	149	linenum = 0;
	150	which = arc4random() % bestcount;
	151	while (fgets(line, sizeof(line), f)) {
	152	if (!parse_prime(linenum, line, &dhg))
	153	continue;
db1cd2f3	154	if (dhg.size > max \|\| dhg.size < min)
db1cd2f3	155	continue;
94ec8c6b	156	if (dhg.size != best)
	157	continue;
	158	if (linenum++ != which) {
	159	BN_free(dhg.g);
	160	BN_free(dhg.p);
	161	continue;
	162	}
	163	break;
	164	}
	165	fclose(f);
	166
	167	return (dh_new_group(dhg.g, dhg.p));
	168	}
03b8f8be	169
	170	/* diffie-hellman-group1-sha1 */
	171
	172	int
	173	dh_pub_is_valid(DH dh, BIGNUM dh_pub)
	174	{
	175	int i;
	176	int n = BN_num_bits(dh_pub);
	177	int bits_set = 0;
	178
	179	if (dh_pub->neg) {
	180	log("invalid public DH value: negativ");
	181	return 0;
	182	}
	183	for (i = 0; i <= n; i++)
	184	if (BN_is_bit_set(dh_pub, i))
	185	bits_set++;
	186	debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
	187
	188	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
	189	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
	190	return 1;
	191	log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
	192	return 0;
	193	}
	194
	195	void
	196	dh_gen_key(DH *dh, int need)
	197	{
	198	int i, bits_set = 0, tries = 0;
	199
	200	if (dh->p == NULL)
	201	fatal("dh_gen_key: dh->p == NULL");
	202	if (2*need >= BN_num_bits(dh->p))
	203	fatal("dh_gen_key: group too small: %d (2*need %d)",
	204	BN_num_bits(dh->p), 2*need);
	205	do {
	206	if (dh->priv_key != NULL)
	207	BN_free(dh->priv_key);
	208	dh->priv_key = BN_new();
	209	if (dh->priv_key == NULL)
	210	fatal("dh_gen_key: BN_new failed");
	211	/* generate a 2need bits random private exponent /
	212	if (!BN_rand(dh->priv_key, 2*need, 0, 0))
	213	fatal("dh_gen_key: BN_rand failed");
	214	if (DH_generate_key(dh) == 0)
	215	fatal("DH_generate_key");
	216	for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
	217	if (BN_is_bit_set(dh->priv_key, i))
	218	bits_set++;
	219	debug("dh_gen_key: priv key bits set: %d/%d",
	220	bits_set, BN_num_bits(dh->priv_key));
	221	if (tries++ > 10)
	222	fatal("dh_gen_key: too many bad keys: giving up");
	223	} while (!dh_pub_is_valid(dh, dh->pub_key));
	224	}
	225
	226	DH *
	227	dh_new_group_asc(const char gen, const char modulus)
	228	{
	229	DH *dh;
	230	int ret;
	231
	232	dh = DH_new();
233	if (dh == NULL)
234	fatal("DH_new");
235
236	if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
237	fatal("BN_hex2bn p");
238	if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
239	fatal("BN_hex2bn g");
240
241	return (dh);
242	}
243
244	/*
245	* This just returns the group, we still need to generate the exchange
246	* value.
247	*/
248
249	DH *
250	dh_new_group(BIGNUM gen, BIGNUM modulus)
251	{
252	DH *dh;
253
254	dh = DH_new();
255	if (dh == NULL)
256	fatal("DH_new");
257	dh->p = modulus;
258	dh->g = gen;
259
260	return (dh);
261	}
262
263	DH *
264	dh_new_group1(void)
265	{
266	static char gen = "2", group1 =
267	"FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
268	"29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
269	"EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
270	"E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
271	"EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
272	"FFFFFFFF" "FFFFFFFF";
273
274	return (dh_new_group_asc(gen, group1));
275	}
a5c9ffdb	276
	277	/*
	278	* Estimates the group order for a Diffie-Hellman group that has an
	279	* attack complexity approximately the same as O(2**bits). Estimate
	280	* with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
	281	*/
	282
	283	int
	284	dh_estimate(int bits)
	285	{
	286
	287	if (bits < 64)
	288	return (512); /* O(2*63) /
	289	if (bits < 128)
	290	return (1024); /* O(2*86) /
	291	if (bits < 192)
	292	return (2048); /* O(2*116) /
	293	return (4096); /* O(2*156) /
	294	}