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