1 /* $OpenBSD: dh.c,v 1.63 2018/02/07 02:06:50 jsing Exp $ */
3 * Copyright (c) 2000 Niels Provos. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
30 #include <openssl/bn.h>
31 #include <openssl/dh.h>
41 #include "pathnames.h"
47 parse_prime(int linenum, char *line, struct dhgroup *dhg)
50 char *strsize, *gen, *prime;
51 const char *errstr = NULL;
54 dhg->p = dhg->g = NULL;
56 if ((arg = strdelim(&cp)) == NULL)
58 /* Ignore leading whitespace */
61 if (!arg || !*arg || *arg == '#')
65 if (cp == NULL || *arg == '\0')
67 arg = strsep(&cp, " "); /* type */
68 if (cp == NULL || *arg == '\0')
70 /* Ensure this is a safe prime */
71 n = strtonum(arg, 0, 5, &errstr);
72 if (errstr != NULL || n != MODULI_TYPE_SAFE) {
73 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
76 arg = strsep(&cp, " "); /* tests */
77 if (cp == NULL || *arg == '\0')
79 /* Ensure prime has been tested and is not composite */
80 n = strtonum(arg, 0, 0x1f, &errstr);
82 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
83 error("moduli:%d: invalid moduli tests flag", linenum);
86 arg = strsep(&cp, " "); /* tries */
87 if (cp == NULL || *arg == '\0')
89 n = strtonum(arg, 0, 1<<30, &errstr);
90 if (errstr != NULL || n == 0) {
91 error("moduli:%d: invalid primality trial count", linenum);
94 strsize = strsep(&cp, " "); /* size */
95 if (cp == NULL || *strsize == '\0' ||
96 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
98 error("moduli:%d: invalid prime length", linenum);
101 /* The whole group is one bit larger */
103 gen = strsep(&cp, " "); /* gen */
104 if (cp == NULL || *gen == '\0')
106 prime = strsep(&cp, " "); /* prime */
107 if (cp != NULL || *prime == '\0') {
109 error("moduli:%d: truncated", linenum);
113 if ((dhg->g = BN_new()) == NULL ||
114 (dhg->p = BN_new()) == NULL) {
115 error("parse_prime: BN_new failed");
118 if (BN_hex2bn(&dhg->g, gen) == 0) {
119 error("moduli:%d: could not parse generator value", linenum);
122 if (BN_hex2bn(&dhg->p, prime) == 0) {
123 error("moduli:%d: could not parse prime value", linenum);
126 if (BN_num_bits(dhg->p) != dhg->size) {
127 error("moduli:%d: prime has wrong size: actual %d listed %d",
128 linenum, BN_num_bits(dhg->p), dhg->size - 1);
131 if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
132 error("moduli:%d: generator is invalid", linenum);
138 BN_clear_free(dhg->g);
139 BN_clear_free(dhg->p);
140 dhg->g = dhg->p = NULL;
145 choose_dh(int min, int wantbits, int max)
149 int best, bestcount, which;
153 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL) {
154 logit("WARNING: could not open %s (%s), using fixed modulus",
155 _PATH_DH_MODULI, strerror(errno));
156 return (dh_new_group_fallback(max));
160 best = bestcount = 0;
161 while (fgets(line, sizeof(line), f)) {
163 if (!parse_prime(linenum, line, &dhg))
165 BN_clear_free(dhg.g);
166 BN_clear_free(dhg.p);
168 if (dhg.size > max || dhg.size < min)
171 if ((dhg.size > wantbits && dhg.size < best) ||
172 (dhg.size > best && best < wantbits)) {
176 if (dhg.size == best)
181 if (bestcount == 0) {
183 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI);
184 return (dh_new_group_fallback(max));
188 which = arc4random_uniform(bestcount);
189 while (fgets(line, sizeof(line), f)) {
190 if (!parse_prime(linenum, line, &dhg))
192 if ((dhg.size > max || dhg.size < min) ||
194 linenum++ != which) {
195 BN_clear_free(dhg.g);
196 BN_clear_free(dhg.p);
202 if (linenum != which+1) {
203 logit("WARNING: line %d disappeared in %s, giving up",
204 which, _PATH_DH_MODULI);
205 return (dh_new_group_fallback(max));
208 return (dh_new_group(dhg.g, dhg.p));
211 /* diffie-hellman-groupN-sha1 */
214 dh_pub_is_valid(const DH *dh, const BIGNUM *dh_pub)
217 int n = BN_num_bits(dh_pub);
222 if (BN_is_negative(dh_pub)) {
223 logit("invalid public DH value: negative");
226 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
227 logit("invalid public DH value: <= 1");
231 if ((tmp = BN_new()) == NULL) {
232 error("%s: BN_new failed", __func__);
235 DH_get0_pqg(dh, &p, NULL, NULL);
236 if (!BN_sub(tmp, p, BN_value_one()) ||
237 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
239 logit("invalid public DH value: >= p-1");
244 for (i = 0; i <= n; i++)
245 if (BN_is_bit_set(dh_pub, i))
247 debug2("bits set: %d/%d", bits_set, BN_num_bits(p));
250 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
253 logit("invalid public DH value (%d/%d)",
254 bits_set, BN_num_bits(p));
261 dh_gen_key(DH *dh, int need)
264 const BIGNUM *p, *pub_key;
267 DH_get0_pqg(dh, &p, NULL, NULL);
269 if (need < 0 || p == NULL ||
270 (pbits = BN_num_bits(p)) <= 0 ||
271 need > INT_MAX / 2 || 2 * need > pbits)
272 return SSH_ERR_INVALID_ARGUMENT;
276 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
277 * so double requested need here.
279 DH_set_length(dh, MIN(need * 2, pbits - 1));
280 if (DH_generate_key(dh) == 0) {
281 return SSH_ERR_LIBCRYPTO_ERROR;
283 DH_get0_key(dh, &pub_key, &priv_key);
284 if (!dh_pub_is_valid(dh, pub_key)) {
286 return SSH_ERR_LIBCRYPTO_ERROR;
292 dh_new_group_asc(const char *gen, const char *modulus)
295 BIGNUM *p=NULL, *g=NULL;
297 if ((dh = DH_new()) == NULL ||
298 (p = BN_new()) == NULL ||
299 (g = BN_new()) == NULL)
301 if (BN_hex2bn(&p, modulus) == 0 ||
302 BN_hex2bn(&g, gen) == 0) {
305 if (DH_set0_pqg(dh, p, NULL, g) == 0) {
318 * This just returns the group, we still need to generate the exchange
323 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
327 if ((dh = DH_new()) == NULL)
329 if (DH_set0_pqg(dh, modulus, NULL, gen) == 0)
335 /* rfc2409 "Second Oakley Group" (1024 bits) */
339 static char *gen = "2", *group1 =
340 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
341 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
342 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
343 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
344 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
345 "FFFFFFFF" "FFFFFFFF";
347 return (dh_new_group_asc(gen, group1));
350 /* rfc3526 group 14 "2048-bit MODP Group" */
354 static char *gen = "2", *group14 =
355 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
356 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
357 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
358 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
359 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
360 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
361 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
362 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
363 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
364 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
365 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
367 return (dh_new_group_asc(gen, group14));
370 /* rfc3526 group 16 "4096-bit MODP Group" */
374 static char *gen = "2", *group16 =
375 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
376 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
377 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
378 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
379 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
380 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
381 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
382 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
383 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
384 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
385 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
386 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
387 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
388 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
389 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
390 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
391 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
392 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
393 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
394 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
395 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
396 "FFFFFFFF" "FFFFFFFF";
398 return (dh_new_group_asc(gen, group16));
401 /* rfc3526 group 18 "8192-bit MODP Group" */
405 static char *gen = "2", *group16 =
406 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
407 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
408 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
409 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
410 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
411 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
412 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
413 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
414 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
415 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
416 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
417 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
418 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
419 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
420 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
421 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
422 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
423 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
424 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
425 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
426 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
427 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
428 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
429 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
430 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
431 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
432 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
433 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
434 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
435 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
436 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
437 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
438 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
439 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
440 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
441 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
442 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
443 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
444 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
445 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
446 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
447 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
448 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
450 return (dh_new_group_asc(gen, group16));
453 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
455 dh_new_group_fallback(int max)
457 debug3("%s: requested max size %d", __func__, max);
459 debug3("using 2k bit group 14");
460 return dh_new_group14();
461 } else if (max < 6144) {
462 debug3("using 4k bit group 16");
463 return dh_new_group16();
465 debug3("using 8k bit group 18");
466 return dh_new_group18();
470 * Estimates the group order for a Diffie-Hellman group that has an
471 * attack complexity approximately the same as O(2**bits).
472 * Values from NIST Special Publication 800-57: Recommendation for Key
473 * Management Part 1 (rev 3) limited by the recommended maximum value
474 * from RFC4419 section 3.
477 dh_estimate(int bits)
488 #endif /* WITH_OPENSSL */