dh.c 9.28 KB
Newer Older
1
/* $OpenBSD: dh.c,v 1.53 2013/11/21 00:45:44 djm Exp $ */
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
/*
 * 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"

28 29
#include <sys/param.h>

30 31 32
#include <openssl/bn.h>
#include <openssl/dh.h>

33
#include <stdarg.h>
34
#include <stdio.h>
35
#include <stdlib.h>
36 37
#include <string.h>

38
#include "dh.h"
39 40 41
#include "pathnames.h"
#include "log.h"
#include "misc.h"
42

43
static int
44 45 46 47
parse_prime(int linenum, char *line, struct dhgroup *dhg)
{
	char *cp, *arg;
	char *strsize, *gen, *prime;
48
	const char *errstr = NULL;
49
	long long n;
50

51
	dhg->p = dhg->g = NULL;
52
	cp = line;
53 54
	if ((arg = strdelim(&cp)) == NULL)
		return 0;
55 56 57
	/* Ignore leading whitespace */
	if (*arg == '\0')
		arg = strdelim(&cp);
58
	if (!arg || !*arg || *arg == '#')
59 60 61 62
		return 0;

	/* time */
	if (cp == NULL || *arg == '\0')
63
		goto truncated;
64 65
	arg = strsep(&cp, " "); /* type */
	if (cp == NULL || *arg == '\0')
66
		goto truncated;
67 68
	/* Ensure this is a safe prime */
	n = strtonum(arg, 0, 5, &errstr);
69 70
	if (errstr != NULL || n != MODULI_TYPE_SAFE) {
		error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
71
		goto fail;
72
	}
73 74
	arg = strsep(&cp, " "); /* tests */
	if (cp == NULL || *arg == '\0')
75
		goto truncated;
76 77 78
	/* Ensure prime has been tested and is not composite */
	n = strtonum(arg, 0, 0x1f, &errstr);
	if (errstr != NULL ||
79 80
	    (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
		error("moduli:%d: invalid moduli tests flag", linenum);
81
		goto fail;
82
	}
83 84
	arg = strsep(&cp, " "); /* tries */
	if (cp == NULL || *arg == '\0')
85
		goto truncated;
86
	n = strtonum(arg, 0, 1<<30, &errstr);
87 88
	if (errstr != NULL || n == 0) {
		error("moduli:%d: invalid primality trial count", linenum);
89
		goto fail;
90
	}
91 92
	strsize = strsep(&cp, " "); /* size */
	if (cp == NULL || *strsize == '\0' ||
93
	    (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
94 95
	    errstr) {
		error("moduli:%d: invalid prime length", linenum);
96
		goto fail;
97
	}
98 99
	/* The whole group is one bit larger */
	dhg->size++;
100 101
	gen = strsep(&cp, " "); /* gen */
	if (cp == NULL || *gen == '\0')
102
		goto truncated;
103
	prime = strsep(&cp, " "); /* prime */
104 105 106
	if (cp != NULL || *prime == '\0') {
 truncated:
		error("moduli:%d: truncated", linenum);
107
		goto fail;
108
	}
109

110 111 112 113
	if ((dhg->g = BN_new()) == NULL)
		fatal("parse_prime: BN_new failed");
	if ((dhg->p = BN_new()) == NULL)
		fatal("parse_prime: BN_new failed");
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
	if (BN_hex2bn(&dhg->g, gen) == 0) {
		error("moduli:%d: could not parse generator value", linenum);
		goto fail;
	}
	if (BN_hex2bn(&dhg->p, prime) == 0) {
		error("moduli:%d: could not parse prime value", linenum);
		goto fail;
	}
	if (BN_num_bits(dhg->p) != dhg->size) {
		error("moduli:%d: prime has wrong size: actual %d listed %d",
		    linenum, BN_num_bits(dhg->p), dhg->size - 1);
		goto fail;
	}
	if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
		error("moduli:%d: generator is invalid", linenum);
		goto fail;
	}
131

132
	return 1;
Damien Miller's avatar
Damien Miller committed
133

134
 fail:
135 136 137 138 139
	if (dhg->g != NULL)
		BN_clear_free(dhg->g);
	if (dhg->p != NULL)
		BN_clear_free(dhg->p);
	dhg->g = dhg->p = NULL;
140
	error("Bad prime description in line %d", linenum);
141
	return 0;
142 143 144
}

DH *
145
choose_dh(int min, int wantbits, int max)
146 147
{
	FILE *f;
148
	char line[4096];
149 150 151 152
	int best, bestcount, which;
	int linenum;
	struct dhgroup dhg;

153 154
	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
	    (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
155 156 157
		logit("WARNING: %s does not exist, using fixed modulus",
		    _PATH_DH_MODULI);
		return (dh_new_group14());
158 159 160 161 162 163 164 165
	}

	linenum = 0;
	best = bestcount = 0;
	while (fgets(line, sizeof(line), f)) {
		linenum++;
		if (!parse_prime(linenum, line, &dhg))
			continue;
166 167
		BN_clear_free(dhg.g);
		BN_clear_free(dhg.p);
168

169 170 171 172 173
		if (dhg.size > max || dhg.size < min)
			continue;

		if ((dhg.size > wantbits && dhg.size < best) ||
		    (dhg.size > best && best < wantbits)) {
174 175 176 177 178 179
			best = dhg.size;
			bestcount = 0;
		}
		if (dhg.size == best)
			bestcount++;
	}
180
	rewind(f);
181 182

	if (bestcount == 0) {
183
		fclose(f);
184
		logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
185
		return (dh_new_group14());
186 187 188
	}

	linenum = 0;
189
	which = arc4random_uniform(bestcount);
190 191 192
	while (fgets(line, sizeof(line), f)) {
		if (!parse_prime(linenum, line, &dhg))
			continue;
193 194 195
		if ((dhg.size > max || dhg.size < min) ||
		    dhg.size != best ||
		    linenum++ != which) {
196 197
			BN_clear_free(dhg.g);
			BN_clear_free(dhg.p);
198 199 200 201 202
			continue;
		}
		break;
	}
	fclose(f);
203 204 205
	if (linenum != which+1)
		fatal("WARNING: line %d disappeared in %s, giving up",
		    which, _PATH_DH_PRIMES);
206 207 208

	return (dh_new_group(dhg.g, dhg.p));
}
Damien Miller's avatar
Damien Miller committed
209

210
/* diffie-hellman-groupN-sha1 */
Damien Miller's avatar
Damien Miller committed
211 212 213 214 215 216 217

int
dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
{
	int i;
	int n = BN_num_bits(dh_pub);
	int bits_set = 0;
218
	BIGNUM *tmp;
Damien Miller's avatar
Damien Miller committed
219 220

	if (dh_pub->neg) {
221
		logit("invalid public DH value: negative");
Damien Miller's avatar
Damien Miller committed
222 223
		return 0;
	}
224 225 226 227 228
	if (BN_cmp(dh_pub, BN_value_one()) != 1) {	/* pub_exp <= 1 */
		logit("invalid public DH value: <= 1");
		return 0;
	}

229 230 231 232
	if ((tmp = BN_new()) == NULL) {
		error("%s: BN_new failed", __func__);
		return 0;
	}
233 234 235 236 237 238 239 240
	if (!BN_sub(tmp, dh->p, BN_value_one()) ||
	    BN_cmp(dh_pub, tmp) != -1) {		/* pub_exp > p-2 */
		BN_clear_free(tmp);
		logit("invalid public DH value: >= p-1");
		return 0;
	}
	BN_clear_free(tmp);

Damien Miller's avatar
Damien Miller committed
241 242 243
	for (i = 0; i <= n; i++)
		if (BN_is_bit_set(dh_pub, i))
			bits_set++;
244
	debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
Damien Miller's avatar
Damien Miller committed
245 246

	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
247
	if (bits_set > 1)
Damien Miller's avatar
Damien Miller committed
248
		return 1;
249

250
	logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
Damien Miller's avatar
Damien Miller committed
251 252 253 254 255 256
	return 0;
}

void
dh_gen_key(DH *dh, int need)
{
257
	int pbits;
Damien Miller's avatar
Damien Miller committed
258

259 260
	if (need <= 0)
		fatal("%s: need <= 0", __func__);
Damien Miller's avatar
Damien Miller committed
261
	if (dh->p == NULL)
262 263 264 265 266 267 268 269
		fatal("%s: dh->p == NULL", __func__);
	if ((pbits = BN_num_bits(dh->p)) <= 0)
		fatal("%s: bits(p) <= 0", __func__);
	dh->length = MIN(need * 2, pbits - 1);
	if (DH_generate_key(dh) == 0)
		fatal("%s: key generation failed", __func__);
	if (!dh_pub_is_valid(dh, dh->pub_key))
		fatal("%s: generated invalid key", __func__);
Damien Miller's avatar
Damien Miller committed
270 271 272 273 274 275 276
}

DH *
dh_new_group_asc(const char *gen, const char *modulus)
{
	DH *dh;

277 278
	if ((dh = DH_new()) == NULL)
		fatal("dh_new_group_asc: DH_new");
Damien Miller's avatar
Damien Miller committed
279

280
	if (BN_hex2bn(&dh->p, modulus) == 0)
Damien Miller's avatar
Damien Miller committed
281
		fatal("BN_hex2bn p");
282
	if (BN_hex2bn(&dh->g, gen) == 0)
Damien Miller's avatar
Damien Miller committed
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297
		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;

298 299
	if ((dh = DH_new()) == NULL)
		fatal("dh_new_group: DH_new");
Damien Miller's avatar
Damien Miller committed
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
	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));
}
319

320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338
DH *
dh_new_group14(void)
{
	static char *gen = "2", *group14 =
	    "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" "ECE45B3D"
	    "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
	    "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
	    "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
	    "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
	    "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
	    "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";

	return (dh_new_group_asc(gen, group14));
}

339 340
/*
 * Estimates the group order for a Diffie-Hellman group that has an
341 342 343 344
 * attack complexity approximately the same as O(2**bits).
 * Values from NIST Special Publication 800-57: Recommendation for Key
 * Management Part 1 (rev 3) limited by the recommended maximum value
 * from RFC4419 section 3.
345 346 347 348 349
 */

int
dh_estimate(int bits)
{
350 351
	if (bits <= 112)
		return 2048;
352
	if (bits <= 128)
353
		return 3072;
354
	if (bits <= 192)
355 356
		return 7680;
	return 8192;
357
}