1 /* $OpenBSD: dh.c,v 1.66 2018/08/04 00:55:06 djm 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 #ifdef WITH_OPENSSL 29 30 #include <openssl/bn.h> 31 #include <openssl/dh.h> 32 33 #include <errno.h> 34 #include <stdarg.h> 35 #include <stdio.h> 36 #include <stdlib.h> 37 #include <string.h> 38 #include <limits.h> 39 40 #include "dh.h" 41 #include "pathnames.h" 42 #include "log.h" 43 #include "misc.h" 44 #include "ssherr.h" 45 46 static int 47 parse_prime(int linenum, char *line, struct dhgroup *dhg) 48 { 49 char *cp, *arg; 50 char *strsize, *gen, *prime; 51 const char *errstr = NULL; 52 long long n; 53 54 dhg->p = dhg->g = NULL; 55 cp = line; 56 if ((arg = strdelim(&cp)) == NULL) 57 return 0; 58 /* Ignore leading whitespace */ 59 if (*arg == '\0') 60 arg = strdelim(&cp); 61 if (!arg || !*arg || *arg == '#') 62 return 0; 63 64 /* time */ 65 if (cp == NULL || *arg == '\0') 66 goto truncated; 67 arg = strsep(&cp, " "); /* type */ 68 if (cp == NULL || *arg == '\0') 69 goto truncated; 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); 74 goto fail; 75 } 76 arg = strsep(&cp, " "); /* tests */ 77 if (cp == NULL || *arg == '\0') 78 goto truncated; 79 /* Ensure prime has been tested and is not composite */ 80 n = strtonum(arg, 0, 0x1f, &errstr); 81 if (errstr != NULL || 82 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 83 error("moduli:%d: invalid moduli tests flag", linenum); 84 goto fail; 85 } 86 arg = strsep(&cp, " "); /* tries */ 87 if (cp == NULL || *arg == '\0') 88 goto truncated; 89 n = strtonum(arg, 0, 1<<30, &errstr); 90 if (errstr != NULL || n == 0) { 91 error("moduli:%d: invalid primality trial count", linenum); 92 goto fail; 93 } 94 strsize = strsep(&cp, " "); /* size */ 95 if (cp == NULL || *strsize == '\0' || 96 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 97 errstr) { 98 error("moduli:%d: invalid prime length", linenum); 99 goto fail; 100 } 101 /* The whole group is one bit larger */ 102 dhg->size++; 103 gen = strsep(&cp, " "); /* gen */ 104 if (cp == NULL || *gen == '\0') 105 goto truncated; 106 prime = strsep(&cp, " "); /* prime */ 107 if (cp != NULL || *prime == '\0') { 108 truncated: 109 error("moduli:%d: truncated", linenum); 110 goto fail; 111 } 112 113 if ((dhg->g = BN_new()) == NULL || 114 (dhg->p = BN_new()) == NULL) { 115 error("parse_prime: BN_new failed"); 116 goto fail; 117 } 118 if (BN_hex2bn(&dhg->g, gen) == 0) { 119 error("moduli:%d: could not parse generator value", linenum); 120 goto fail; 121 } 122 if (BN_hex2bn(&dhg->p, prime) == 0) { 123 error("moduli:%d: could not parse prime value", linenum); 124 goto fail; 125 } 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); 129 goto fail; 130 } 131 if (BN_cmp(dhg->g, BN_value_one()) <= 0) { 132 error("moduli:%d: generator is invalid", linenum); 133 goto fail; 134 } 135 return 1; 136 137 fail: 138 BN_clear_free(dhg->g); 139 BN_clear_free(dhg->p); 140 dhg->g = dhg->p = NULL; 141 return 0; 142 } 143 144 DH * 145 choose_dh(int min, int wantbits, int max) 146 { 147 FILE *f; 148 char *line = NULL; 149 size_t linesize = 0; 150 int best, bestcount, which, linenum; 151 struct dhgroup dhg; 152 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)); 157 } 158 159 linenum = 0; 160 best = bestcount = 0; 161 while (getline(&line, &linesize, f) != -1) { 162 linenum++; 163 if (!parse_prime(linenum, line, &dhg)) 164 continue; 165 BN_clear_free(dhg.g); 166 BN_clear_free(dhg.p); 167 168 if (dhg.size > max || dhg.size < min) 169 continue; 170 171 if ((dhg.size > wantbits && dhg.size < best) || 172 (dhg.size > best && best < wantbits)) { 173 best = dhg.size; 174 bestcount = 0; 175 } 176 if (dhg.size == best) 177 bestcount++; 178 } 179 free(line); 180 line = NULL; 181 linesize = 0; 182 rewind(f); 183 184 if (bestcount == 0) { 185 fclose(f); 186 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI); 187 return (dh_new_group_fallback(max)); 188 } 189 190 linenum = 0; 191 which = arc4random_uniform(bestcount); 192 while (getline(&line, &linesize, f) != -1) { 193 if (!parse_prime(linenum, line, &dhg)) 194 continue; 195 if ((dhg.size > max || dhg.size < min) || 196 dhg.size != best || 197 linenum++ != which) { 198 BN_clear_free(dhg.g); 199 BN_clear_free(dhg.p); 200 continue; 201 } 202 break; 203 } 204 free(line); 205 line = NULL; 206 fclose(f); 207 if (linenum != which+1) { 208 logit("WARNING: line %d disappeared in %s, giving up", 209 which, _PATH_DH_MODULI); 210 return (dh_new_group_fallback(max)); 211 } 212 213 return (dh_new_group(dhg.g, dhg.p)); 214 } 215 216 /* diffie-hellman-groupN-sha1 */ 217 218 int 219 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 220 { 221 int i; 222 int n = BN_num_bits(dh_pub); 223 int bits_set = 0; 224 BIGNUM *tmp; 225 226 if (dh_pub->neg) { 227 logit("invalid public DH value: negative"); 228 return 0; 229 } 230 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 231 logit("invalid public DH value: <= 1"); 232 return 0; 233 } 234 235 if ((tmp = BN_new()) == NULL) { 236 error("%s: BN_new failed", __func__); 237 return 0; 238 } 239 if (!BN_sub(tmp, dh->p, BN_value_one()) || 240 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 241 BN_clear_free(tmp); 242 logit("invalid public DH value: >= p-1"); 243 return 0; 244 } 245 BN_clear_free(tmp); 246 247 for (i = 0; i <= n; i++) 248 if (BN_is_bit_set(dh_pub, i)) 249 bits_set++; 250 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 251 252 /* 253 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial 254 */ 255 if (bits_set < 4) { 256 logit("invalid public DH value (%d/%d)", 257 bits_set, BN_num_bits(dh->p)); 258 return 0; 259 } 260 return 1; 261 } 262 263 int 264 dh_gen_key(DH *dh, int need) 265 { 266 int pbits; 267 268 if (need < 0 || dh->p == NULL || 269 (pbits = BN_num_bits(dh->p)) <= 0 || 270 need > INT_MAX / 2 || 2 * need > pbits) 271 return SSH_ERR_INVALID_ARGUMENT; 272 if (need < 256) 273 need = 256; 274 /* 275 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)), 276 * so double requested need here. 277 */ 278 dh->length = MINIMUM(need * 2, pbits - 1); 279 if (DH_generate_key(dh) == 0 || 280 !dh_pub_is_valid(dh, dh->pub_key)) { 281 BN_clear_free(dh->priv_key); 282 dh->priv_key = NULL; 283 return SSH_ERR_LIBCRYPTO_ERROR; 284 } 285 return 0; 286 } 287 288 DH * 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 * 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 * 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 * 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 * 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 * 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 * 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 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 474 #endif /* WITH_OPENSSL */ 475