1 /* $NetBSD: dh.c,v 1.11 2016/12/25 00:07:47 christos Exp $ */ 2 /* $OpenBSD: dh.c,v 1.62 2016/12/15 21:20:41 dtucker Exp $ */ 3 4 /* 5 * Copyright (c) 2000 Niels Provos. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 */ 27 28 #include "includes.h" 29 __RCSID("$NetBSD: dh.c,v 1.11 2016/12/25 00:07:47 christos Exp $"); 30 31 #include <sys/param.h> /* MIN */ 32 #include <openssl/bn.h> 33 #include <openssl/dh.h> 34 35 #include <errno.h> 36 #include <stdio.h> 37 #include <stdlib.h> 38 #include <string.h> 39 #include <time.h> 40 #include <limits.h> 41 42 #include "dh.h" 43 #include "pathnames.h" 44 #include "log.h" 45 #include "misc.h" 46 #include "random.h" 47 #include "ssherr.h" 48 49 static int 50 parse_prime(int linenum, char *line, struct dhgroup *dhg) 51 { 52 char *cp, *arg; 53 char *strsize, *gen, *prime; 54 const char *errstr = NULL; 55 long long n; 56 57 dhg->p = dhg->g = NULL; 58 cp = line; 59 if ((arg = strdelim(&cp)) == NULL) 60 return 0; 61 /* Ignore leading whitespace */ 62 if (*arg == '\0') 63 arg = strdelim(&cp); 64 if (!arg || !*arg || *arg == '#') 65 return 0; 66 67 /* time */ 68 if (cp == NULL || *arg == '\0') 69 goto truncated; 70 arg = strsep(&cp, " "); /* type */ 71 if (cp == NULL || *arg == '\0') 72 goto truncated; 73 /* Ensure this is a safe prime */ 74 n = strtonum(arg, 0, 5, &errstr); 75 if (errstr != NULL || n != MODULI_TYPE_SAFE) { 76 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE); 77 goto fail; 78 } 79 arg = strsep(&cp, " "); /* tests */ 80 if (cp == NULL || *arg == '\0') 81 goto truncated; 82 /* Ensure prime has been tested and is not composite */ 83 n = strtonum(arg, 0, 0x1f, &errstr); 84 if (errstr != NULL || 85 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 86 error("moduli:%d: invalid moduli tests flag", linenum); 87 goto fail; 88 } 89 arg = strsep(&cp, " "); /* tries */ 90 if (cp == NULL || *arg == '\0') 91 goto truncated; 92 n = strtonum(arg, 0, 1<<30, &errstr); 93 if (errstr != NULL || n == 0) { 94 error("moduli:%d: invalid primality trial count", linenum); 95 goto fail; 96 } 97 strsize = strsep(&cp, " "); /* size */ 98 if (cp == NULL || *strsize == '\0' || 99 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 100 errstr) { 101 error("moduli:%d: invalid prime length", linenum); 102 goto fail; 103 } 104 /* The whole group is one bit larger */ 105 dhg->size++; 106 gen = strsep(&cp, " "); /* gen */ 107 if (cp == NULL || *gen == '\0') 108 goto truncated; 109 prime = strsep(&cp, " "); /* prime */ 110 if (cp != NULL || *prime == '\0') { 111 truncated: 112 error("moduli:%d: truncated", linenum); 113 goto fail; 114 } 115 116 if ((dhg->g = BN_new()) == NULL || 117 (dhg->p = BN_new()) == NULL) { 118 error("parse_prime: BN_new failed"); 119 goto fail; 120 } 121 if (BN_hex2bn(&dhg->g, gen) == 0) { 122 error("moduli:%d: could not parse generator value", linenum); 123 goto fail; 124 } 125 if (BN_hex2bn(&dhg->p, prime) == 0) { 126 error("moduli:%d: could not parse prime value", linenum); 127 goto fail; 128 } 129 if (BN_num_bits(dhg->p) != dhg->size) { 130 error("moduli:%d: prime has wrong size: actual %d listed %d", 131 linenum, BN_num_bits(dhg->p), dhg->size - 1); 132 goto fail; 133 } 134 if (BN_cmp(dhg->g, BN_value_one()) <= 0) { 135 error("moduli:%d: generator is invalid", linenum); 136 goto fail; 137 } 138 return 1; 139 140 fail: 141 if (dhg->g != NULL) 142 BN_clear_free(dhg->g); 143 if (dhg->p != NULL) 144 BN_clear_free(dhg->p); 145 dhg->g = dhg->p = NULL; 146 return 0; 147 } 148 149 DH * 150 choose_dh(int min, int wantbits, int max) 151 { 152 FILE *f; 153 char line[4096]; 154 int best, bestcount, which; 155 int linenum; 156 struct dhgroup dhg; 157 158 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL) { 159 logit("WARNING: could not open %s (%s), using fixed modulus", 160 _PATH_DH_MODULI, strerror(errno)); 161 return (dh_new_group_fallback(max)); 162 } 163 164 linenum = 0; 165 best = bestcount = 0; 166 while (fgets(line, sizeof(line), f)) { 167 linenum++; 168 if (!parse_prime(linenum, line, &dhg)) 169 continue; 170 BN_clear_free(dhg.g); 171 BN_clear_free(dhg.p); 172 173 if (dhg.size > max || dhg.size < min) 174 continue; 175 176 if ((dhg.size > wantbits && dhg.size < best) || 177 (dhg.size > best && best < wantbits)) { 178 best = dhg.size; 179 bestcount = 0; 180 } 181 if (dhg.size == best) 182 bestcount++; 183 } 184 rewind(f); 185 186 if (bestcount == 0) { 187 fclose(f); 188 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI); 189 return (dh_new_group_fallback(max)); 190 } 191 192 linenum = 0; 193 which = arc4random_uniform(bestcount); 194 while (fgets(line, sizeof(line), f)) { 195 if (!parse_prime(linenum, line, &dhg)) 196 continue; 197 if ((dhg.size > max || dhg.size < min) || 198 dhg.size != best || 199 linenum++ != which) { 200 BN_clear_free(dhg.g); 201 BN_clear_free(dhg.p); 202 continue; 203 } 204 break; 205 } 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 return SSH_ERR_LIBCRYPTO_ERROR; 283 } 284 return 0; 285 } 286 287 DH * 288 dh_new_group_asc(const char *gen, const char *modulus) 289 { 290 DH *dh; 291 292 if ((dh = DH_new()) == NULL) 293 return NULL; 294 if (BN_hex2bn(&dh->p, modulus) == 0 || 295 BN_hex2bn(&dh->g, gen) == 0) { 296 DH_free(dh); 297 return NULL; 298 } 299 return (dh); 300 } 301 302 /* 303 * This just returns the group, we still need to generate the exchange 304 * value. 305 */ 306 307 DH * 308 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 309 { 310 DH *dh; 311 312 if ((dh = DH_new()) == NULL) 313 return NULL; 314 dh->p = modulus; 315 dh->g = gen; 316 317 return (dh); 318 } 319 320 /* rfc2409 "Second Oakley Group" (1024 bits) */ 321 DH * 322 dh_new_group1(void) 323 { 324 static const char *gen = "2", *group1 = 325 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 326 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 327 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 328 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 329 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 330 "FFFFFFFF" "FFFFFFFF"; 331 332 return (dh_new_group_asc(gen, group1)); 333 } 334 335 /* rfc3526 group 14 "2048-bit MODP Group" */ 336 DH * 337 dh_new_group14(void) 338 { 339 static const char *gen = "2", *group14 = 340 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 341 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 342 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 343 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 344 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 345 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 346 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 347 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 348 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 349 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 350 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 351 352 return (dh_new_group_asc(gen, group14)); 353 } 354 355 /* rfc3526 group 16 "4096-bit MODP Group" */ 356 DH * 357 dh_new_group16(void) 358 { 359 static const char *gen = "2", *group16 = 360 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 361 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 362 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 363 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 364 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 365 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 366 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 367 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 368 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 369 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 370 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 371 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 372 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 373 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 374 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 375 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 376 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 377 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 378 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 379 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 380 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199" 381 "FFFFFFFF" "FFFFFFFF"; 382 383 return (dh_new_group_asc(gen, group16)); 384 } 385 386 /* rfc3526 group 18 "8192-bit MODP Group" */ 387 DH * 388 dh_new_group18(void) 389 { 390 static const char *gen = "2", *group16 = 391 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 392 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 393 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 394 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 395 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 396 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 397 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 398 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 399 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 400 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 401 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 402 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 403 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 404 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 405 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 406 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 407 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 408 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 409 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 410 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 411 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492" 412 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD" 413 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831" 414 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B" 415 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF" 416 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6" 417 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3" 418 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA" 419 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328" 420 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C" 421 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE" 422 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4" 423 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300" 424 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568" 425 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9" 426 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B" 427 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A" 428 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36" 429 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1" 430 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92" 431 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47" 432 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71" 433 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF"; 434 435 return (dh_new_group_asc(gen, group16)); 436 } 437 438 /* Select fallback group used by DH-GEX if moduli file cannot be read. */ 439 DH * 440 dh_new_group_fallback(int max) 441 { 442 debug3("%s: requested max size %d", __func__, max); 443 if (max < 3072) { 444 debug3("using 2k bit group 14"); 445 return dh_new_group14(); 446 } else if (max < 6144) { 447 debug3("using 4k bit group 16"); 448 return dh_new_group16(); 449 } 450 debug3("using 8k bit group 18"); 451 return dh_new_group18(); 452 } 453 454 /* 455 * Estimates the group order for a Diffie-Hellman group that has an 456 * attack complexity approximately the same as O(2**bits). 457 * Values from NIST Special Publication 800-57: Recommendation for Key 458 * Management Part 1 (rev 3) limited by the recommended maximum value 459 * from RFC4419 section 3. 460 */ 461 u_int 462 dh_estimate(int bits) 463 { 464 if (bits <= 112) 465 return 2048; 466 if (bits <= 128) 467 return 3072; 468 if (bits <= 192) 469 return 7680; 470 return 8192; 471 } 472