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