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