[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.26 2003/12/16 15:51:54 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"

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;

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