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