[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.13 2001/04/04 23:09:17 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) ||
		    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;
	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"
a7ca6275	26	RCSID("$OpenBSD: dh.c,v 1.13 2001/04/04 23:09:17 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;
a7ca6275	154	if ((dhg.size > max \|\| dhg.size < min) \|\|
	155	dhg.size != best \|\|
	156	linenum++ != which) {
94ec8c6b	157	BN_free(dhg.g);
	158	BN_free(dhg.p);
	159	continue;
	160	}
	161	break;
	162	}
	163	fclose(f);
a7ca6275	164	if (linenum != which+1)
	165	fatal("WARNING: line %d disappeared in %s, giving up",
	166	which, _PATH_DH_PRIMES);
94ec8c6b	167
	168	return (dh_new_group(dhg.g, dhg.p));
	169	}
03b8f8be	170
	171	/* diffie-hellman-group1-sha1 */
	172
	173	int
	174	dh_pub_is_valid(DH dh, BIGNUM dh_pub)
	175	{
	176	int i;
	177	int n = BN_num_bits(dh_pub);
	178	int bits_set = 0;
	179
	180	if (dh_pub->neg) {
	181	log("invalid public DH value: negativ");
	182	return 0;
	183	}
	184	for (i = 0; i <= n; i++)
	185	if (BN_is_bit_set(dh_pub, i))
	186	bits_set++;
	187	debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
	188
	189	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
	190	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
	191	return 1;
	192	log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
	193	return 0;
	194	}
	195
	196	void
	197	dh_gen_key(DH *dh, int need)
	198	{
	199	int i, bits_set = 0, tries = 0;
	200
	201	if (dh->p == NULL)
	202	fatal("dh_gen_key: dh->p == NULL");
	203	if (2*need >= BN_num_bits(dh->p))
	204	fatal("dh_gen_key: group too small: %d (2*need %d)",
	205	BN_num_bits(dh->p), 2*need);
	206	do {
	207	if (dh->priv_key != NULL)
	208	BN_free(dh->priv_key);
	209	dh->priv_key = BN_new();
	210	if (dh->priv_key == NULL)
	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");
	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++;
	220	debug("dh_gen_key: priv key bits set: %d/%d",
	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	int ret;
	232
	233	dh = DH_new();
234	if (dh == NULL)
235	fatal("DH_new");
236
237	if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
238	fatal("BN_hex2bn p");
239	if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
240	fatal("BN_hex2bn g");
241
242	return (dh);
243	}
244
245	/*
246	* This just returns the group, we still need to generate the exchange
247	* value.
248	*/
249
250	DH *
251	dh_new_group(BIGNUM gen, BIGNUM modulus)
252	{
253	DH *dh;
254
255	dh = DH_new();
256	if (dh == NULL)
257	fatal("DH_new");
258	dh->p = modulus;
259	dh->g = gen;
260
261	return (dh);
262	}
263
264	DH *
265	dh_new_group1(void)
266	{
267	static char gen = "2", group1 =
268	"FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
269	"29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
270	"EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
271	"E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
272	"EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
273	"FFFFFFFF" "FFFFFFFF";
274
275	return (dh_new_group_asc(gen, group1));
276	}
a5c9ffdb	277
	278	/*
	279	* Estimates the group order for a Diffie-Hellman group that has an
	280	* attack complexity approximately the same as O(2**bits). Estimate
	281	* with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
	282	*/
	283
	284	int
	285	dh_estimate(int bits)
	286	{
	287
	288	if (bits < 64)
	289	return (512); /* O(2*63) /
	290	if (bits < 128)
	291	return (1024); /* O(2*86) /
	292	if (bits < 192)
	293	return (2048); /* O(2*116) /
	294	return (4096); /* O(2*156) /
	295	}