1 /* $OpenBSD: dh.c,v 1.68 2018/09/17 15:40:14 millert 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"
46 #include "openbsd-compat/openssl-compat.h"
49 parse_prime(int linenum, char *line, struct dhgroup *dhg)
52 char *strsize, *gen, *prime;
53 const char *errstr = NULL;
56 dhg->p = dhg->g = NULL;
58 if ((arg = strdelim(&cp)) == NULL)
60 /* Ignore leading whitespace */
63 if (!arg || !*arg || *arg == '#')
67 if (cp == NULL || *arg == '\0')
69 arg = strsep(&cp, " "); /* type */
70 if (cp == NULL || *arg == '\0')
72 /* Ensure this is a safe prime */
73 n = strtonum(arg, 0, 5, &errstr);
74 if (errstr != NULL || n != MODULI_TYPE_SAFE) {
75 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
78 arg = strsep(&cp, " "); /* tests */
79 if (cp == NULL || *arg == '\0')
81 /* Ensure prime has been tested and is not composite */
82 n = strtonum(arg, 0, 0x1f, &errstr);
84 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
85 error("moduli:%d: invalid moduli tests flag", linenum);
88 arg = strsep(&cp, " "); /* tries */
89 if (cp == NULL || *arg == '\0')
91 n = strtonum(arg, 0, 1<<30, &errstr);
92 if (errstr != NULL || n == 0) {
93 error("moduli:%d: invalid primality trial count", linenum);
96 strsize = strsep(&cp, " "); /* size */
97 if (cp == NULL || *strsize == '\0' ||
98 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
100 error("moduli:%d: invalid prime length", linenum);
103 /* The whole group is one bit larger */
105 gen = strsep(&cp, " "); /* gen */
106 if (cp == NULL || *gen == '\0')
108 prime = strsep(&cp, " "); /* prime */
109 if (cp != NULL || *prime == '\0') {
111 error("moduli:%d: truncated", linenum);
115 if ((dhg->g = BN_new()) == NULL ||
116 (dhg->p = BN_new()) == NULL) {
117 error("parse_prime: BN_new failed");
120 if (BN_hex2bn(&dhg->g, gen) == 0) {
121 error("moduli:%d: could not parse generator value", linenum);
124 if (BN_hex2bn(&dhg->p, prime) == 0) {
125 error("moduli:%d: could not parse prime value", linenum);
128 if (BN_num_bits(dhg->p) != dhg->size) {
129 error("moduli:%d: prime has wrong size: actual %d listed %d",
130 linenum, BN_num_bits(dhg->p), dhg->size - 1);
133 if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
134 error("moduli:%d: generator is invalid", linenum);
140 BN_clear_free(dhg->g);
141 BN_clear_free(dhg->p);
142 dhg->g = dhg->p = NULL;
147 choose_dh(int min, int wantbits, int max)
152 int best, bestcount, which, linenum;
155 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL) {
156 logit("WARNING: could not open %s (%s), using fixed modulus",
157 _PATH_DH_MODULI, strerror(errno));
158 return (dh_new_group_fallback(max));
162 best = bestcount = 0;
163 while (getline(&line, &linesize, f) != -1) {
165 if (!parse_prime(linenum, line, &dhg))
167 BN_clear_free(dhg.g);
168 BN_clear_free(dhg.p);
170 if (dhg.size > max || dhg.size < min)
173 if ((dhg.size > wantbits && dhg.size < best) ||
174 (dhg.size > best && best < wantbits)) {
178 if (dhg.size == best)
186 if (bestcount == 0) {
188 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI);
189 return (dh_new_group_fallback(max));
191 which = arc4random_uniform(bestcount);
195 while (getline(&line, &linesize, f) != -1) {
197 if (!parse_prime(linenum, line, &dhg))
199 if ((dhg.size > max || dhg.size < min) ||
201 bestcount++ != which) {
202 BN_clear_free(dhg.g);
203 BN_clear_free(dhg.p);
211 if (bestcount != which + 1) {
212 logit("WARNING: selected prime disappeared in %s, giving up",
214 return (dh_new_group_fallback(max));
217 return (dh_new_group(dhg.g, dhg.p));
220 /* diffie-hellman-groupN-sha1 */
223 dh_pub_is_valid(const DH *dh, const BIGNUM *dh_pub)
226 int n = BN_num_bits(dh_pub);
231 DH_get0_pqg(dh, &dh_p, NULL, NULL);
233 if (BN_is_negative(dh_pub)) {
234 logit("invalid public DH value: negative");
237 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
238 logit("invalid public DH value: <= 1");
242 if ((tmp = BN_new()) == NULL) {
243 error("%s: BN_new failed", __func__);
246 if (!BN_sub(tmp, dh_p, BN_value_one()) ||
247 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
249 logit("invalid public DH value: >= p-1");
254 for (i = 0; i <= n; i++)
255 if (BN_is_bit_set(dh_pub, i))
257 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh_p));
260 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
263 logit("invalid public DH value (%d/%d)",
264 bits_set, BN_num_bits(dh_p));
271 dh_gen_key(DH *dh, int need)
274 const BIGNUM *dh_p, *pub_key;
276 DH_get0_pqg(dh, &dh_p, NULL, NULL);
278 if (need < 0 || dh_p == NULL ||
279 (pbits = BN_num_bits(dh_p)) <= 0 ||
280 need > INT_MAX / 2 || 2 * need > pbits)
281 return SSH_ERR_INVALID_ARGUMENT;
285 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
286 * so double requested need here.
288 if (!DH_set_length(dh, MINIMUM(need * 2, pbits - 1)))
289 return SSH_ERR_LIBCRYPTO_ERROR;
291 if (DH_generate_key(dh) == 0)
292 return SSH_ERR_LIBCRYPTO_ERROR;
293 DH_get0_key(dh, &pub_key, NULL);
294 if (!dh_pub_is_valid(dh, pub_key))
295 return SSH_ERR_INVALID_FORMAT;
300 dh_new_group_asc(const char *gen, const char *modulus)
303 BIGNUM *dh_p = NULL, *dh_g = NULL;
305 if ((dh = DH_new()) == NULL)
307 if (BN_hex2bn(&dh_p, modulus) == 0 ||
308 BN_hex2bn(&dh_g, gen) == 0)
310 if (!DH_set0_pqg(dh, dh_p, NULL, dh_g))
321 * This just returns the group, we still need to generate the exchange
325 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
329 if ((dh = DH_new()) == NULL)
331 if (!DH_set0_pqg(dh, modulus, NULL, gen)) {
339 /* rfc2409 "Second Oakley Group" (1024 bits) */
343 static char *gen = "2", *group1 =
344 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
345 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
346 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
347 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
348 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
349 "FFFFFFFF" "FFFFFFFF";
351 return (dh_new_group_asc(gen, group1));
354 /* rfc3526 group 14 "2048-bit MODP Group" */
358 static char *gen = "2", *group14 =
359 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
360 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
361 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
362 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
363 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
364 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
365 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
366 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
367 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
368 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
369 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
371 return (dh_new_group_asc(gen, group14));
374 /* rfc3526 group 16 "4096-bit MODP Group" */
378 static char *gen = "2", *group16 =
379 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
380 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
381 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
382 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
383 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
384 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
385 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
386 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
387 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
388 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
389 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
390 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
391 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
392 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
393 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
394 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
395 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
396 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
397 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
398 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
399 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
400 "FFFFFFFF" "FFFFFFFF";
402 return (dh_new_group_asc(gen, group16));
405 /* rfc3526 group 18 "8192-bit MODP Group" */
409 static char *gen = "2", *group16 =
410 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
411 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
412 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
413 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
414 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
415 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
416 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
417 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
418 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
419 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
420 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
421 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
422 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
423 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
424 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
425 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
426 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
427 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
428 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
429 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
430 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
431 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
432 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
433 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
434 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
435 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
436 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
437 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
438 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
439 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
440 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
441 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
442 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
443 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
444 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
445 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
446 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
447 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
448 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
449 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
450 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
451 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
452 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
454 return (dh_new_group_asc(gen, group16));
457 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
459 dh_new_group_fallback(int max)
461 debug3("%s: requested max size %d", __func__, max);
463 debug3("using 2k bit group 14");
464 return dh_new_group14();
465 } else if (max < 6144) {
466 debug3("using 4k bit group 16");
467 return dh_new_group16();
469 debug3("using 8k bit group 18");
470 return dh_new_group18();
474 * Estimates the group order for a Diffie-Hellman group that has an
475 * attack complexity approximately the same as O(2**bits).
476 * Values from NIST Special Publication 800-57: Recommendation for Key
477 * Management Part 1 (rev 3) limited by the recommended maximum value
478 * from RFC4419 section 3.
481 dh_estimate(int bits)
492 #endif /* WITH_OPENSSL */