1 /* $OpenBSD: dh.c,v 1.63 2018/02/07 02:06:50 jsing 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[4096]; 149 int best, bestcount, which; 150 int 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 (fgets(line, sizeof(line), f)) { 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 rewind(f); 180 181 if (bestcount == 0) { 182 fclose(f); 183 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI); 184 return (dh_new_group_fallback(max)); 185 } 186 187 linenum = 0; 188 which = arc4random_uniform(bestcount); 189 while (fgets(line, sizeof(line), f)) { 190 if (!parse_prime(linenum, line, &dhg)) 191 continue; 192 if ((dhg.size > max || dhg.size < min) || 193 dhg.size != best || 194 linenum++ != which) { 195 BN_clear_free(dhg.g); 196 BN_clear_free(dhg.p); 197 continue; 198 } 199 break; 200 } 201 fclose(f); 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)); 206 } 207 208 return (dh_new_group(dhg.g, dhg.p)); 209 } 210 211 /* diffie-hellman-groupN-sha1 */ 212 213 int 214 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 215 { 216 int i; 217 int n = BN_num_bits(dh_pub); 218 int bits_set = 0; 219 BIGNUM *tmp; 220 221 if (dh_pub->neg) { 222 logit("invalid public DH value: negative"); 223 return 0; 224 } 225 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 226 logit("invalid public DH value: <= 1"); 227 return 0; 228 } 229 230 if ((tmp = BN_new()) == NULL) { 231 error("%s: BN_new failed", __func__); 232 return 0; 233 } 234 if (!BN_sub(tmp, dh->p, BN_value_one()) || 235 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 236 BN_clear_free(tmp); 237 logit("invalid public DH value: >= p-1"); 238 return 0; 239 } 240 BN_clear_free(tmp); 241 242 for (i = 0; i <= n; i++) 243 if (BN_is_bit_set(dh_pub, i)) 244 bits_set++; 245 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 246 247 /* 248 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial 249 */ 250 if (bits_set < 4) { 251 logit("invalid public DH value (%d/%d)", 252 bits_set, BN_num_bits(dh->p)); 253 return 0; 254 } 255 return 1; 256 } 257 258 int 259 dh_gen_key(DH *dh, int need) 260 { 261 int pbits; 262 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; 267 if (need < 256) 268 need = 256; 269 /* 270 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)), 271 * so double requested need here. 272 */ 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; 278 } 279 return 0; 280 } 281 282 DH * 283 dh_new_group_asc(const char *gen, const char *modulus) 284 { 285 DH *dh; 286 287 if ((dh = DH_new()) == NULL) 288 return NULL; 289 if (BN_hex2bn(&dh->p, modulus) == 0 || 290 BN_hex2bn(&dh->g, gen) == 0) { 291 DH_free(dh); 292 return NULL; 293 } 294 return (dh); 295 } 296 297 /* 298 * This just returns the group, we still need to generate the exchange 299 * value. 300 */ 301 302 DH * 303 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 304 { 305 DH *dh; 306 307 if ((dh = DH_new()) == NULL) 308 return NULL; 309 dh->p = modulus; 310 dh->g = gen; 311 312 return (dh); 313 } 314 315 /* rfc2409 "Second Oakley Group" (1024 bits) */ 316 DH * 317 dh_new_group1(void) 318 { 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"; 326 327 return (dh_new_group_asc(gen, group1)); 328 } 329 330 /* rfc3526 group 14 "2048-bit MODP Group" */ 331 DH * 332 dh_new_group14(void) 333 { 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"; 346 347 return (dh_new_group_asc(gen, group14)); 348 } 349 350 /* rfc3526 group 16 "4096-bit MODP Group" */ 351 DH * 352 dh_new_group16(void) 353 { 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"; 377 378 return (dh_new_group_asc(gen, group16)); 379 } 380 381 /* rfc3526 group 18 "8192-bit MODP Group" */ 382 DH * 383 dh_new_group18(void) 384 { 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"; 429 430 return (dh_new_group_asc(gen, group16)); 431 } 432 433 /* Select fallback group used by DH-GEX if moduli file cannot be read. */ 434 DH * 435 dh_new_group_fallback(int max) 436 { 437 debug3("%s: requested max size %d", __func__, max); 438 if (max < 3072) { 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(); 444 } 445 debug3("using 8k bit group 18"); 446 return dh_new_group18(); 447 } 448 449 /* 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. 455 */ 456 u_int 457 dh_estimate(int bits) 458 { 459 if (bits <= 112) 460 return 2048; 461 if (bits <= 128) 462 return 3072; 463 if (bits <= 192) 464 return 7680; 465 return 8192; 466 } 467 468 #endif /* WITH_OPENSSL */ 469