1 /* $OpenBSD: dh.c,v 1.66 2018/08/04 00:55:06 djm 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));
193 which = arc4random_uniform(bestcount);
194 while (getline(&line, &linesize, f) != -1) {
195 if (!parse_prime(linenum, line, &dhg))
197 if ((dhg.size > max || dhg.size < min) ||
199 linenum++ != which) {
200 BN_clear_free(dhg.g);
201 BN_clear_free(dhg.p);
209 if (linenum != which+1) {
210 logit("WARNING: line %d disappeared in %s, giving up",
211 which, _PATH_DH_MODULI);
212 return (dh_new_group_fallback(max));
215 return (dh_new_group(dhg.g, dhg.p));
218 /* diffie-hellman-groupN-sha1 */
221 dh_pub_is_valid(const DH *dh, const BIGNUM *dh_pub)
224 int n = BN_num_bits(dh_pub);
229 DH_get0_pqg(dh, &dh_p, NULL, NULL);
231 if (BN_is_negative(dh_pub)) {
232 logit("invalid public DH value: negative");
235 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
236 logit("invalid public DH value: <= 1");
240 if ((tmp = BN_new()) == NULL) {
241 error("%s: BN_new failed", __func__);
244 if (!BN_sub(tmp, dh_p, BN_value_one()) ||
245 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
247 logit("invalid public DH value: >= p-1");
252 for (i = 0; i <= n; i++)
253 if (BN_is_bit_set(dh_pub, i))
255 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh_p));
258 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
261 logit("invalid public DH value (%d/%d)",
262 bits_set, BN_num_bits(dh_p));
269 dh_gen_key(DH *dh, int need)
272 const BIGNUM *dh_p, *pub_key;
274 DH_get0_pqg(dh, &dh_p, NULL, NULL);
276 if (need < 0 || dh_p == NULL ||
277 (pbits = BN_num_bits(dh_p)) <= 0 ||
278 need > INT_MAX / 2 || 2 * need > pbits)
279 return SSH_ERR_INVALID_ARGUMENT;
283 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
284 * so double requested need here.
286 if (!DH_set_length(dh, MINIMUM(need * 2, pbits - 1)))
287 return SSH_ERR_LIBCRYPTO_ERROR;
289 if (DH_generate_key(dh) == 0)
290 return SSH_ERR_LIBCRYPTO_ERROR;
291 DH_get0_key(dh, &pub_key, NULL);
292 if (!dh_pub_is_valid(dh, pub_key))
293 return SSH_ERR_INVALID_FORMAT;
298 dh_new_group_asc(const char *gen, const char *modulus)
301 BIGNUM *dh_p = NULL, *dh_g = NULL;
303 if ((dh = DH_new()) == NULL)
305 if (BN_hex2bn(&dh_p, modulus) == 0 ||
306 BN_hex2bn(&dh_g, gen) == 0)
308 if (!DH_set0_pqg(dh, dh_p, NULL, dh_g))
319 * 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)) {
337 /* rfc2409 "Second Oakley Group" (1024 bits) */
341 static char *gen = "2", *group1 =
342 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
343 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
344 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
345 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
346 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
347 "FFFFFFFF" "FFFFFFFF";
349 return (dh_new_group_asc(gen, group1));
352 /* rfc3526 group 14 "2048-bit MODP Group" */
356 static char *gen = "2", *group14 =
357 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
358 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
359 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
360 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
361 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
362 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
363 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
364 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
365 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
366 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
367 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
369 return (dh_new_group_asc(gen, group14));
372 /* rfc3526 group 16 "4096-bit MODP Group" */
376 static char *gen = "2", *group16 =
377 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
378 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
379 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
380 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
381 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
382 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
383 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
384 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
385 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
386 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
387 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
388 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
389 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
390 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
391 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
392 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
393 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
394 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
395 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
396 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
397 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
398 "FFFFFFFF" "FFFFFFFF";
400 return (dh_new_group_asc(gen, group16));
403 /* rfc3526 group 18 "8192-bit MODP Group" */
407 static char *gen = "2", *group16 =
408 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
409 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
410 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
411 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
412 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
413 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
414 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
415 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
416 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
417 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
418 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
419 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
420 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
421 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
422 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
423 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
424 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
425 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
426 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
427 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
428 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
429 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
430 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
431 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
432 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
433 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
434 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
435 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
436 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
437 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
438 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
439 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
440 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
441 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
442 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
443 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
444 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
445 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
446 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
447 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
448 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
449 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
450 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
452 return (dh_new_group_asc(gen, group16));
455 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
457 dh_new_group_fallback(int max)
459 debug3("%s: requested max size %d", __func__, max);
461 debug3("using 2k bit group 14");
462 return dh_new_group14();
463 } else if (max < 6144) {
464 debug3("using 4k bit group 16");
465 return dh_new_group16();
467 debug3("using 8k bit group 18");
468 return dh_new_group18();
472 * Estimates the group order for a Diffie-Hellman group that has an
473 * attack complexity approximately the same as O(2**bits).
474 * Values from NIST Special Publication 800-57: Recommendation for Key
475 * Management Part 1 (rev 3) limited by the recommended maximum value
476 * from RFC4419 section 3.
479 dh_estimate(int bits)
490 #endif /* WITH_OPENSSL */