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