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