GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/ssh/lib/../dh.c Lines: 0 175 0.0 %
Date: 2017-11-13 Branches: 0 150 0.0 %

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