1 /* $OpenBSD: dh.c,v 1.62 2016/12/15 21:20:41 dtucker 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 27 #include <openssl/bn.h> 28 #include <openssl/dh.h> 29 30 #include <errno.h> 31 #include <stdio.h> 32 #include <stdlib.h> 33 #include <string.h> 34 #include <limits.h> 35 36 #include "dh.h" 37 #include "pathnames.h" 38 #include "log.h" 39 #include "misc.h" 40 #include "ssherr.h" 41 42 static int 43 parse_prime(int linenum, char *line, struct dhgroup *dhg) 44 { 45 char *cp, *arg; 46 char *strsize, *gen, *prime; 47 const char *errstr = NULL; 48 long long n; 49 50 dhg->p = dhg->g = NULL; 51 cp = line; 52 if ((arg = strdelim(&cp)) == NULL) 53 return 0; 54 /* Ignore leading whitespace */ 55 if (*arg == '\0') 56 arg = strdelim(&cp); 57 if (!arg || !*arg || *arg == '#') 58 return 0; 59 60 /* time */ 61 if (cp == NULL || *arg == '\0') 62 goto truncated; 63 arg = strsep(&cp, " "); /* type */ 64 if (cp == NULL || *arg == '\0') 65 goto truncated; 66 /* Ensure this is a safe prime */ 67 n = strtonum(arg, 0, 5, &errstr); 68 if (errstr != NULL || n != MODULI_TYPE_SAFE) { 69 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE); 70 goto fail; 71 } 72 arg = strsep(&cp, " "); /* tests */ 73 if (cp == NULL || *arg == '\0') 74 goto truncated; 75 /* Ensure prime has been tested and is not composite */ 76 n = strtonum(arg, 0, 0x1f, &errstr); 77 if (errstr != NULL || 78 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 79 error("moduli:%d: invalid moduli tests flag", linenum); 80 goto fail; 81 } 82 arg = strsep(&cp, " "); /* tries */ 83 if (cp == NULL || *arg == '\0') 84 goto truncated; 85 n = strtonum(arg, 0, 1<<30, &errstr); 86 if (errstr != NULL || n == 0) { 87 error("moduli:%d: invalid primality trial count", linenum); 88 goto fail; 89 } 90 strsize = strsep(&cp, " "); /* size */ 91 if (cp == NULL || *strsize == '\0' || 92 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 93 errstr) { 94 error("moduli:%d: invalid prime length", linenum); 95 goto fail; 96 } 97 /* The whole group is one bit larger */ 98 dhg->size++; 99 gen = strsep(&cp, " "); /* gen */ 100 if (cp == NULL || *gen == '\0') 101 goto truncated; 102 prime = strsep(&cp, " "); /* prime */ 103 if (cp != NULL || *prime == '\0') { 104 truncated: 105 error("moduli:%d: truncated", linenum); 106 goto fail; 107 } 108 109 if ((dhg->g = BN_new()) == NULL || 110 (dhg->p = BN_new()) == NULL) { 111 error("parse_prime: BN_new failed"); 112 goto fail; 113 } 114 if (BN_hex2bn(&dhg->g, gen) == 0) { 115 error("moduli:%d: could not parse generator value", linenum); 116 goto fail; 117 } 118 if (BN_hex2bn(&dhg->p, prime) == 0) { 119 error("moduli:%d: could not parse prime value", linenum); 120 goto fail; 121 } 122 if (BN_num_bits(dhg->p) != dhg->size) { 123 error("moduli:%d: prime has wrong size: actual %d listed %d", 124 linenum, BN_num_bits(dhg->p), dhg->size - 1); 125 goto fail; 126 } 127 if (BN_cmp(dhg->g, BN_value_one()) <= 0) { 128 error("moduli:%d: generator is invalid", linenum); 129 goto fail; 130 } 131 return 1; 132 133 fail: 134 if (dhg->g != NULL) 135 BN_clear_free(dhg->g); 136 if (dhg->p != NULL) 137 BN_clear_free(dhg->p); 138 dhg->g = dhg->p = NULL; 139 return 0; 140 } 141 142 DH * 143 choose_dh(int min, int wantbits, int max) 144 { 145 FILE *f; 146 char line[4096]; 147 int best, bestcount, which; 148 int linenum; 149 struct dhgroup dhg; 150 151 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL) { 152 logit("WARNING: could not open %s (%s), using fixed modulus", 153 _PATH_DH_MODULI, strerror(errno)); 154 return (dh_new_group_fallback(max)); 155 } 156 157 linenum = 0; 158 best = bestcount = 0; 159 while (fgets(line, sizeof(line), f)) { 160 linenum++; 161 if (!parse_prime(linenum, line, &dhg)) 162 continue; 163 BN_clear_free(dhg.g); 164 BN_clear_free(dhg.p); 165 166 if (dhg.size > max || dhg.size < min) 167 continue; 168 169 if ((dhg.size > wantbits && dhg.size < best) || 170 (dhg.size > best && best < wantbits)) { 171 best = dhg.size; 172 bestcount = 0; 173 } 174 if (dhg.size == best) 175 bestcount++; 176 } 177 rewind(f); 178 179 if (bestcount == 0) { 180 fclose(f); 181 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI); 182 return (dh_new_group_fallback(max)); 183 } 184 185 linenum = 0; 186 which = arc4random_uniform(bestcount); 187 while (fgets(line, sizeof(line), f)) { 188 if (!parse_prime(linenum, line, &dhg)) 189 continue; 190 if ((dhg.size > max || dhg.size < min) || 191 dhg.size != best || 192 linenum++ != which) { 193 BN_clear_free(dhg.g); 194 BN_clear_free(dhg.p); 195 continue; 196 } 197 break; 198 } 199 fclose(f); 200 if (linenum != which+1) { 201 logit("WARNING: line %d disappeared in %s, giving up", 202 which, _PATH_DH_MODULI); 203 return (dh_new_group_fallback(max)); 204 } 205 206 return (dh_new_group(dhg.g, dhg.p)); 207 } 208 209 /* diffie-hellman-groupN-sha1 */ 210 211 int 212 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 213 { 214 int i; 215 int n = BN_num_bits(dh_pub); 216 int bits_set = 0; 217 BIGNUM *tmp; 218 219 if (dh_pub->neg) { 220 logit("invalid public DH value: negative"); 221 return 0; 222 } 223 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 224 logit("invalid public DH value: <= 1"); 225 return 0; 226 } 227 228 if ((tmp = BN_new()) == NULL) { 229 error("%s: BN_new failed", __func__); 230 return 0; 231 } 232 if (!BN_sub(tmp, dh->p, BN_value_one()) || 233 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 234 BN_clear_free(tmp); 235 logit("invalid public DH value: >= p-1"); 236 return 0; 237 } 238 BN_clear_free(tmp); 239 240 for (i = 0; i <= n; i++) 241 if (BN_is_bit_set(dh_pub, i)) 242 bits_set++; 243 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 244 245 /* 246 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial 247 */ 248 if (bits_set < 4) { 249 logit("invalid public DH value (%d/%d)", 250 bits_set, BN_num_bits(dh->p)); 251 return 0; 252 } 253 return 1; 254 } 255 256 int 257 dh_gen_key(DH *dh, int need) 258 { 259 int pbits; 260 261 if (need < 0 || dh->p == NULL || 262 (pbits = BN_num_bits(dh->p)) <= 0 || 263 need > INT_MAX / 2 || 2 * need > pbits) 264 return SSH_ERR_INVALID_ARGUMENT; 265 if (need < 256) 266 need = 256; 267 /* 268 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)), 269 * so double requested need here. 270 */ 271 dh->length = MINIMUM(need * 2, pbits - 1); 272 if (DH_generate_key(dh) == 0 || 273 !dh_pub_is_valid(dh, dh->pub_key)) { 274 BN_clear_free(dh->priv_key); 275 return SSH_ERR_LIBCRYPTO_ERROR; 276 } 277 return 0; 278 } 279 280 DH * 281 dh_new_group_asc(const char *gen, const char *modulus) 282 { 283 DH *dh; 284 285 if ((dh = DH_new()) == NULL) 286 return NULL; 287 if (BN_hex2bn(&dh->p, modulus) == 0 || 288 BN_hex2bn(&dh->g, gen) == 0) { 289 DH_free(dh); 290 return NULL; 291 } 292 return (dh); 293 } 294 295 /* 296 * This just returns the group, we still need to generate the exchange 297 * value. 298 */ 299 300 DH * 301 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 302 { 303 DH *dh; 304 305 if ((dh = DH_new()) == NULL) 306 return NULL; 307 dh->p = modulus; 308 dh->g = gen; 309 310 return (dh); 311 } 312 313 /* rfc2409 "Second Oakley Group" (1024 bits) */ 314 DH * 315 dh_new_group1(void) 316 { 317 static char *gen = "2", *group1 = 318 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 319 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 320 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 321 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 322 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 323 "FFFFFFFF" "FFFFFFFF"; 324 325 return (dh_new_group_asc(gen, group1)); 326 } 327 328 /* rfc3526 group 14 "2048-bit MODP Group" */ 329 DH * 330 dh_new_group14(void) 331 { 332 static char *gen = "2", *group14 = 333 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 334 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 335 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 336 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 337 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 338 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 339 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 340 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 341 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 342 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 343 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 344 345 return (dh_new_group_asc(gen, group14)); 346 } 347 348 /* rfc3526 group 16 "4096-bit MODP Group" */ 349 DH * 350 dh_new_group16(void) 351 { 352 static char *gen = "2", *group16 = 353 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 354 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 355 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 356 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 357 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 358 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 359 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 360 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 361 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 362 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 363 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 364 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 365 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 366 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 367 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 368 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 369 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 370 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 371 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 372 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 373 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199" 374 "FFFFFFFF" "FFFFFFFF"; 375 376 return (dh_new_group_asc(gen, group16)); 377 } 378 379 /* rfc3526 group 18 "8192-bit MODP Group" */ 380 DH * 381 dh_new_group18(void) 382 { 383 static char *gen = "2", *group16 = 384 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 385 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 386 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 387 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 388 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 389 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 390 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 391 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 392 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 393 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 394 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 395 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 396 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 397 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 398 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 399 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 400 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 401 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 402 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 403 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 404 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492" 405 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD" 406 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831" 407 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B" 408 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF" 409 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6" 410 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3" 411 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA" 412 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328" 413 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C" 414 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE" 415 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4" 416 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300" 417 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568" 418 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9" 419 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B" 420 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A" 421 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36" 422 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1" 423 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92" 424 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47" 425 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71" 426 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF"; 427 428 return (dh_new_group_asc(gen, group16)); 429 } 430 431 /* Select fallback group used by DH-GEX if moduli file cannot be read. */ 432 DH * 433 dh_new_group_fallback(int max) 434 { 435 debug3("%s: requested max size %d", __func__, max); 436 if (max < 3072) { 437 debug3("using 2k bit group 14"); 438 return dh_new_group14(); 439 } else if (max < 6144) { 440 debug3("using 4k bit group 16"); 441 return dh_new_group16(); 442 } 443 debug3("using 8k bit group 18"); 444 return dh_new_group18(); 445 } 446 447 /* 448 * Estimates the group order for a Diffie-Hellman group that has an 449 * attack complexity approximately the same as O(2**bits). 450 * Values from NIST Special Publication 800-57: Recommendation for Key 451 * Management Part 1 (rev 3) limited by the recommended maximum value 452 * from RFC4419 section 3. 453 */ 454 u_int 455 dh_estimate(int bits) 456 { 457 if (bits <= 112) 458 return 2048; 459 if (bits <= 128) 460 return 3072; 461 if (bits <= 192) 462 return 7680; 463 return 8192; 464 } 465