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