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