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