dh.c revision 323134 
1/* $OpenBSD: dh.c,v 1.62 2016/12/15 21:20:41 dtucker Exp $ */
2/*
3 * Copyright (c) 2000 Niels Provos.  All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "includes.h"
27
28
29#include <openssl/bn.h>
30#include <openssl/dh.h>
31
32#include <errno.h>
33#include <stdarg.h>
34#include <stdio.h>
35#include <stdlib.h>
36#include <string.h>
37#include <limits.h>
38
39#include "dh.h"
40#include "pathnames.h"
41#include "log.h"
42#include "misc.h"
43#include "ssherr.h"
44
45static int
46parse_prime(int linenum, char *line, struct dhgroup *dhg)
47{
48	char *cp, *arg;
49	char *strsize, *gen, *prime;
50	const char *errstr = NULL;
51	long long n;
52
53	dhg->p = dhg->g = NULL;
54	cp = line;
55	if ((arg = strdelim(&cp)) == NULL)
56		return 0;
57	/* Ignore leading whitespace */
58	if (*arg == '\0')
59		arg = strdelim(&cp);
60	if (!arg || !*arg || *arg == '#')
61		return 0;
62
63	/* time */
64	if (cp == NULL || *arg == '\0')
65		goto truncated;
66	arg = strsep(&cp, " "); /* type */
67	if (cp == NULL || *arg == '\0')
68		goto truncated;
69	/* Ensure this is a safe prime */
70	n = strtonum(arg, 0, 5, &errstr);
71	if (errstr != NULL || n != MODULI_TYPE_SAFE) {
72		error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
73		goto fail;
74	}
75	arg = strsep(&cp, " "); /* tests */
76	if (cp == NULL || *arg == '\0')
77		goto truncated;
78	/* Ensure prime has been tested and is not composite */
79	n = strtonum(arg, 0, 0x1f, &errstr);
80	if (errstr != NULL ||
81	    (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
82		error("moduli:%d: invalid moduli tests flag", linenum);
83		goto fail;
84	}
85	arg = strsep(&cp, " "); /* tries */
86	if (cp == NULL || *arg == '\0')
87		goto truncated;
88	n = strtonum(arg, 0, 1<<30, &errstr);
89	if (errstr != NULL || n == 0) {
90		error("moduli:%d: invalid primality trial count", linenum);
91		goto fail;
92	}
93	strsize = strsep(&cp, " "); /* size */
94	if (cp == NULL || *strsize == '\0' ||
95	    (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
96	    errstr) {
97		error("moduli:%d: invalid prime length", linenum);
98		goto fail;
99	}
100	/* The whole group is one bit larger */
101	dhg->size++;
102	gen = strsep(&cp, " "); /* gen */
103	if (cp == NULL || *gen == '\0')
104		goto truncated;
105	prime = strsep(&cp, " "); /* prime */
106	if (cp != NULL || *prime == '\0') {
107 truncated:
108		error("moduli:%d: truncated", linenum);
109		goto fail;
110	}
111
112	if ((dhg->g = BN_new()) == NULL ||
113	    (dhg->p = BN_new()) == NULL) {
114		error("parse_prime: BN_new failed");
115		goto fail;
116	}
117	if (BN_hex2bn(&dhg->g, gen) == 0) {
118		error("moduli:%d: could not parse generator value", linenum);
119		goto fail;
120	}
121	if (BN_hex2bn(&dhg->p, prime) == 0) {
122		error("moduli:%d: could not parse prime value", linenum);
123		goto fail;
124	}
125	if (BN_num_bits(dhg->p) != dhg->size) {
126		error("moduli:%d: prime has wrong size: actual %d listed %d",
127		    linenum, BN_num_bits(dhg->p), dhg->size - 1);
128		goto fail;
129	}
130	if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
131		error("moduli:%d: generator is invalid", linenum);
132		goto fail;
133	}
134	return 1;
135
136 fail:
137	if (dhg->g != NULL)
138		BN_clear_free(dhg->g);
139	if (dhg->p != NULL)
140		BN_clear_free(dhg->p);
141	dhg->g = dhg->p = NULL;
142	return 0;
143}
144
145DH *
146choose_dh(int min, int wantbits, int max)
147{
148	FILE *f;
149	char line[4096];
150	int best, bestcount, which;
151	int linenum;
152	struct dhgroup dhg;
153
154	if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL) {
155		logit("WARNING: could not open %s (%s), using fixed modulus",
156		    _PATH_DH_MODULI, strerror(errno));
157		return (dh_new_group_fallback(max));
158	}
159
160	linenum = 0;
161	best = bestcount = 0;
162	while (fgets(line, sizeof(line), f)) {
163		linenum++;
164		if (!parse_prime(linenum, line, &dhg))
165			continue;
166		BN_clear_free(dhg.g);
167		BN_clear_free(dhg.p);
168
169		if (dhg.size > max || dhg.size < min)
170			continue;
171
172		if ((dhg.size > wantbits && dhg.size < best) ||
173		    (dhg.size > best && best < wantbits)) {
174			best = dhg.size;
175			bestcount = 0;
176		}
177		if (dhg.size == best)
178			bestcount++;
179	}
180	rewind(f);
181
182	if (bestcount == 0) {
183		fclose(f);
184		logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI);
185		return (dh_new_group_fallback(max));
186	}
187
188	linenum = 0;
189	which = arc4random_uniform(bestcount);
190	while (fgets(line, sizeof(line), f)) {
191		if (!parse_prime(linenum, line, &dhg))
192			continue;
193		if ((dhg.size > max || dhg.size < min) ||
194		    dhg.size != best ||
195		    linenum++ != which) {
196			BN_clear_free(dhg.g);
197			BN_clear_free(dhg.p);
198			continue;
199		}
200		break;
201	}
202	fclose(f);
203	if (linenum != which+1) {
204		logit("WARNING: line %d disappeared in %s, giving up",
205		    which, _PATH_DH_MODULI);
206		return (dh_new_group_fallback(max));
207	}
208
209	return (dh_new_group(dhg.g, dhg.p));
210}
211
212/* diffie-hellman-groupN-sha1 */
213
214int
215dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
216{
217	int i;
218	int n = BN_num_bits(dh_pub);
219	int bits_set = 0;
220	BIGNUM *tmp;
221
222	if (dh_pub->neg) {
223		logit("invalid public DH value: negative");
224		return 0;
225	}
226	if (BN_cmp(dh_pub, BN_value_one()) != 1) {	/* pub_exp <= 1 */
227		logit("invalid public DH value: <= 1");
228		return 0;
229	}
230
231	if ((tmp = BN_new()) == NULL) {
232		error("%s: BN_new failed", __func__);
233		return 0;
234	}
235	if (!BN_sub(tmp, dh->p, BN_value_one()) ||
236	    BN_cmp(dh_pub, tmp) != -1) {		/* pub_exp > p-2 */
237		BN_clear_free(tmp);
238		logit("invalid public DH value: >= p-1");
239		return 0;
240	}
241	BN_clear_free(tmp);
242
243	for (i = 0; i <= n; i++)
244		if (BN_is_bit_set(dh_pub, i))
245			bits_set++;
246	debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
247
248	/*
249	 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
250	 */
251	if (bits_set < 4) {
252		logit("invalid public DH value (%d/%d)",
253		   bits_set, BN_num_bits(dh->p));
254		return 0;
255	}
256	return 1;
257}
258
259int
260dh_gen_key(DH *dh, int need)
261{
262	int pbits;
263
264	if (need < 0 || dh->p == NULL ||
265	    (pbits = BN_num_bits(dh->p)) <= 0 ||
266	    need > INT_MAX / 2 || 2 * need > pbits)
267		return SSH_ERR_INVALID_ARGUMENT;
268	if (need < 256)
269		need = 256;
270	/*
271	 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
272	 * so double requested need here.
273	 */
274	dh->length = MINIMUM(need * 2, pbits - 1);
275	if (DH_generate_key(dh) == 0 ||
276	    !dh_pub_is_valid(dh, dh->pub_key)) {
277		BN_clear_free(dh->priv_key);
278		return SSH_ERR_LIBCRYPTO_ERROR;
279	}
280	return 0;
281}
282
283DH *
284dh_new_group_asc(const char *gen, const char *modulus)
285{
286	DH *dh;
287
288	if ((dh = DH_new()) == NULL)
289		return NULL;
290	if (BN_hex2bn(&dh->p, modulus) == 0 ||
291	    BN_hex2bn(&dh->g, gen) == 0) {
292		DH_free(dh);
293		return NULL;
294	}
295	return (dh);
296}
297
298/*
299 * This just returns the group, we still need to generate the exchange
300 * value.
301 */
302
303DH *
304dh_new_group(BIGNUM *gen, BIGNUM *modulus)
305{
306	DH *dh;
307
308	if ((dh = DH_new()) == NULL)
309		return NULL;
310	dh->p = modulus;
311	dh->g = gen;
312
313	return (dh);
314}
315
316/* rfc2409 "Second Oakley Group" (1024 bits) */
317DH *
318dh_new_group1(void)
319{
320	static char *gen = "2", *group1 =
321	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
322	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
323	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
324	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
325	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
326	    "FFFFFFFF" "FFFFFFFF";
327
328	return (dh_new_group_asc(gen, group1));
329}
330
331/* rfc3526 group 14 "2048-bit MODP Group" */
332DH *
333dh_new_group14(void)
334{
335	static char *gen = "2", *group14 =
336	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
337	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
338	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
339	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
340	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
341	    "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
342	    "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
343	    "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
344	    "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
345	    "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
346	    "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
347
348	return (dh_new_group_asc(gen, group14));
349}
350
351/* rfc3526 group 16 "4096-bit MODP Group" */
352DH *
353dh_new_group16(void)
354{
355	static char *gen = "2", *group16 =
356	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
357	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
358	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
359	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
360	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
361	    "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
362	    "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
363	    "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
364	    "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
365	    "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
366	    "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
367	    "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
368	    "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
369	    "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
370	    "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
371	    "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
372	    "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
373	    "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
374	    "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
375	    "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
376	    "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
377	    "FFFFFFFF" "FFFFFFFF";
378
379	return (dh_new_group_asc(gen, group16));
380}
381
382/* rfc3526 group 18 "8192-bit MODP Group" */
383DH *
384dh_new_group18(void)
385{
386	static char *gen = "2", *group16 =
387	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
388	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
389	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
390	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
391	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
392	    "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
393	    "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
394	    "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
395	    "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
396	    "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
397	    "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
398	    "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
399	    "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
400	    "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
401	    "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
402	    "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
403	    "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
404	    "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
405	    "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
406	    "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
407	    "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
408	    "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
409	    "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
410	    "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
411	    "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
412	    "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
413	    "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
414	    "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
415	    "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
416	    "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
417	    "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
418	    "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
419	    "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
420	    "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
421	    "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
422	    "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
423	    "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
424	    "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
425	    "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
426	    "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
427	    "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
428	    "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
429	    "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
430
431	return (dh_new_group_asc(gen, group16));
432}
433
434/* Select fallback group used by DH-GEX if moduli file cannot be read. */
435DH *
436dh_new_group_fallback(int max)
437{
438	debug3("%s: requested max size %d", __func__, max);
439	if (max < 3072) {
440		debug3("using 2k bit group 14");
441		return dh_new_group14();
442	} else if (max < 6144) {
443		debug3("using 4k bit group 16");
444		return dh_new_group16();
445	}
446	debug3("using 8k bit group 18");
447	return dh_new_group18();
448}
449
450/*
451 * Estimates the group order for a Diffie-Hellman group that has an
452 * attack complexity approximately the same as O(2**bits).
453 * Values from NIST Special Publication 800-57: Recommendation for Key
454 * Management Part 1 (rev 3) limited by the recommended maximum value
455 * from RFC4419 section 3.
456 */
457u_int
458dh_estimate(int bits)
459{
460	if (bits <= 112)
461		return 2048;
462	if (bits <= 128)
463		return 3072;
464	if (bits <= 192)
465		return 7680;
466	return 8192;
467}
468