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(DH *dh, BIGNUM *dh_pub)
217 int n = BN_num_bits(dh_pub);
222 logit("invalid public DH value: negative");
225 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
226 logit("invalid public DH value: <= 1");
230 if ((tmp = BN_new()) == NULL) {
231 error("%s: BN_new failed", __func__);
234 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
235 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
237 logit("invalid public DH value: >= p-1");
242 for (i = 0; i <= n; i++)
243 if (BN_is_bit_set(dh_pub, i))
245 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
248 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
251 logit("invalid public DH value (%d/%d)",
252 bits_set, BN_num_bits(dh->p));
259 dh_gen_key(DH *dh, int need)
263 if (need < 0 || dh->p == NULL ||
264 (pbits = BN_num_bits(dh->p)) <= 0 ||
265 need > INT_MAX / 2 || 2 * need > pbits)
266 return SSH_ERR_INVALID_ARGUMENT;
270 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
271 * so double requested need here.
273 dh->length = MINIMUM(need * 2, pbits - 1);
274 if (DH_generate_key(dh) == 0 ||
275 !dh_pub_is_valid(dh, dh->pub_key)) {
276 BN_clear_free(dh->priv_key);
277 return SSH_ERR_LIBCRYPTO_ERROR;
283 dh_new_group_asc(const char *gen, const char *modulus)
287 if ((dh = DH_new()) == NULL)
289 if (BN_hex2bn(&dh->p, modulus) == 0 ||
290 BN_hex2bn(&dh->g, gen) == 0) {
298 * This just returns the group, we still need to generate the exchange
303 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
307 if ((dh = DH_new()) == NULL)
315 /* rfc2409 "Second Oakley Group" (1024 bits) */
319 static char *gen = "2", *group1 =
320 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
321 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
322 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
323 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
324 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
325 "FFFFFFFF" "FFFFFFFF";
327 return (dh_new_group_asc(gen, group1));
330 /* rfc3526 group 14 "2048-bit MODP Group" */
334 static char *gen = "2", *group14 =
335 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
336 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
337 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
338 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
339 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
340 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
341 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
342 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
343 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
344 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
345 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
347 return (dh_new_group_asc(gen, group14));
350 /* rfc3526 group 16 "4096-bit MODP Group" */
354 static char *gen = "2", *group16 =
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" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
366 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
367 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
368 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
369 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
370 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
371 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
372 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
373 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
374 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
375 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
376 "FFFFFFFF" "FFFFFFFF";
378 return (dh_new_group_asc(gen, group16));
381 /* rfc3526 group 18 "8192-bit MODP Group" */
385 static char *gen = "2", *group16 =
386 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
387 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
388 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
389 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
390 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
391 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
392 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
393 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
394 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
395 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
396 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
397 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
398 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
399 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
400 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
401 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
402 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
403 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
404 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
405 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
406 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
407 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
408 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
409 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
410 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
411 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
412 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
413 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
414 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
415 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
416 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
417 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
418 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
419 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
420 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
421 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
422 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
423 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
424 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
425 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
426 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
427 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
428 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
430 return (dh_new_group_asc(gen, group16));
433 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
435 dh_new_group_fallback(int max)
437 debug3("%s: requested max size %d", __func__, max);
439 debug3("using 2k bit group 14");
440 return dh_new_group14();
441 } else if (max < 6144) {
442 debug3("using 4k bit group 16");
443 return dh_new_group16();
445 debug3("using 8k bit group 18");
446 return dh_new_group18();
450 * Estimates the group order for a Diffie-Hellman group that has an
451 * attack complexity approximately the same as O(2**bits).
452 * Values from NIST Special Publication 800-57: Recommendation for Key
453 * Management Part 1 (rev 3) limited by the recommended maximum value
454 * from RFC4419 section 3.
457 dh_estimate(int bits)
468 #endif /* WITH_OPENSSL */