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
45 static int
parse_prime(int linenum,char * line,struct dhgroup * dhg)46 parse_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
145 DH *
choose_dh(int min,int wantbits,int max)146 choose_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
214 int
dh_pub_is_valid(DH * dh,BIGNUM * dh_pub)215 dh_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
259 int
dh_gen_key(DH * dh,int need)260 dh_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 #if !defined(ANDROID) || !defined(OPENSSL_IS_BORINGSSL)
275 /* BoringSSL renamed |length| to |priv_length| to better reflect its
276 * actual use. Also, BoringSSL recognises common groups and chooses the
277 * length of the private exponent accoringly. */
278 dh->length = MINIMUM(need * 2, pbits - 1);
279 #endif
280 if (DH_generate_key(dh) == 0 ||
281 !dh_pub_is_valid(dh, dh->pub_key)) {
282 BN_clear_free(dh->priv_key);
283 return SSH_ERR_LIBCRYPTO_ERROR;
284 }
285 return 0;
286 }
287
288 DH *
dh_new_group_asc(const char * gen,const char * modulus)289 dh_new_group_asc(const char *gen, const char *modulus)
290 {
291 DH *dh;
292
293 if ((dh = DH_new()) == NULL)
294 return NULL;
295 if (BN_hex2bn(&dh->p, modulus) == 0 ||
296 BN_hex2bn(&dh->g, gen) == 0) {
297 DH_free(dh);
298 return NULL;
299 }
300 return (dh);
301 }
302
303 /*
304 * This just returns the group, we still need to generate the exchange
305 * value.
306 */
307
308 DH *
dh_new_group(BIGNUM * gen,BIGNUM * modulus)309 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
310 {
311 DH *dh;
312
313 if ((dh = DH_new()) == NULL)
314 return NULL;
315 dh->p = modulus;
316 dh->g = gen;
317
318 return (dh);
319 }
320
321 /* rfc2409 "Second Oakley Group" (1024 bits) */
322 DH *
dh_new_group1(void)323 dh_new_group1(void)
324 {
325 static char *gen = "2", *group1 =
326 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
327 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
328 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
329 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
330 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
331 "FFFFFFFF" "FFFFFFFF";
332
333 return (dh_new_group_asc(gen, group1));
334 }
335
336 /* rfc3526 group 14 "2048-bit MODP Group" */
337 DH *
dh_new_group14(void)338 dh_new_group14(void)
339 {
340 static char *gen = "2", *group14 =
341 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
342 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
343 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
344 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
345 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
346 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
347 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
348 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
349 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
350 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
351 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
352
353 return (dh_new_group_asc(gen, group14));
354 }
355
356 /* rfc3526 group 16 "4096-bit MODP Group" */
357 DH *
dh_new_group16(void)358 dh_new_group16(void)
359 {
360 static char *gen = "2", *group16 =
361 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
362 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
363 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
364 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
365 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
366 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
367 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
368 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
369 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
370 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
371 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
372 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
373 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
374 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
375 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
376 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
377 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
378 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
379 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
380 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
381 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
382 "FFFFFFFF" "FFFFFFFF";
383
384 return (dh_new_group_asc(gen, group16));
385 }
386
387 /* rfc3526 group 18 "8192-bit MODP Group" */
388 DH *
dh_new_group18(void)389 dh_new_group18(void)
390 {
391 static char *gen = "2", *group16 =
392 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
393 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
394 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
395 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
396 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
397 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
398 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
399 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
400 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
401 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
402 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
403 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
404 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
405 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
406 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
407 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
408 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
409 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
410 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
411 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
412 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
413 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
414 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
415 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
416 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
417 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
418 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
419 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
420 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
421 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
422 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
423 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
424 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
425 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
426 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
427 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
428 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
429 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
430 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
431 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
432 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
433 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
434 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
435
436 return (dh_new_group_asc(gen, group16));
437 }
438
439 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
440 DH *
dh_new_group_fallback(int max)441 dh_new_group_fallback(int max)
442 {
443 debug3("%s: requested max size %d", __func__, max);
444 if (max < 3072) {
445 debug3("using 2k bit group 14");
446 return dh_new_group14();
447 } else if (max < 6144) {
448 debug3("using 4k bit group 16");
449 return dh_new_group16();
450 }
451 debug3("using 8k bit group 18");
452 return dh_new_group18();
453 }
454
455 /*
456 * Estimates the group order for a Diffie-Hellman group that has an
457 * attack complexity approximately the same as O(2**bits).
458 * Values from NIST Special Publication 800-57: Recommendation for Key
459 * Management Part 1 (rev 3) limited by the recommended maximum value
460 * from RFC4419 section 3.
461 */
462 u_int
dh_estimate(int bits)463 dh_estimate(int bits)
464 {
465 if (bits <= 112)
466 return 2048;
467 if (bits <= 128)
468 return 3072;
469 if (bits <= 192)
470 return 7680;
471 return 8192;
472 }
473