1 /* $OpenBSD: dh.c,v 1.66 2018/08/04 00:55:06 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 <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 192 linenum = 0; 193 which = arc4random_uniform(bestcount); 194 while (getline(&line, &linesize, f) != -1) { 195 if (!parse_prime(linenum, line, &dhg)) 196 continue; 197 if ((dhg.size > max || dhg.size < min) || 198 dhg.size != best || 199 linenum++ != which) { 200 BN_clear_free(dhg.g); 201 BN_clear_free(dhg.p); 202 continue; 203 } 204 break; 205 } 206 free(line); 207 line = NULL; 208 fclose(f); 209 if (linenum != which+1) { 210 logit("WARNING: line %d disappeared in %s, giving up", 211 which, _PATH_DH_MODULI); 212 return (dh_new_group_fallback(max)); 213 } 214 215 return (dh_new_group(dhg.g, dhg.p)); 216 } 217 218 /* diffie-hellman-groupN-sha1 */ 219 220 int 221 dh_pub_is_valid(const DH *dh, const BIGNUM *dh_pub) 222 { 223 int i; 224 int n = BN_num_bits(dh_pub); 225 int bits_set = 0; 226 BIGNUM *tmp; 227 const BIGNUM *dh_p; 228 229 DH_get0_pqg(dh, &dh_p, NULL, NULL); 230 231 if (BN_is_negative(dh_pub)) { 232 logit("invalid public DH value: negative"); 233 return 0; 234 } 235 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 236 logit("invalid public DH value: <= 1"); 237 return 0; 238 } 239 240 if ((tmp = BN_new()) == NULL) { 241 error("%s: BN_new failed", __func__); 242 return 0; 243 } 244 if (!BN_sub(tmp, dh_p, BN_value_one()) || 245 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 246 BN_clear_free(tmp); 247 logit("invalid public DH value: >= p-1"); 248 return 0; 249 } 250 BN_clear_free(tmp); 251 252 for (i = 0; i <= n; i++) 253 if (BN_is_bit_set(dh_pub, i)) 254 bits_set++; 255 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh_p)); 256 257 /* 258 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial 259 */ 260 if (bits_set < 4) { 261 logit("invalid public DH value (%d/%d)", 262 bits_set, BN_num_bits(dh_p)); 263 return 0; 264 } 265 return 1; 266 } 267 268 int 269 dh_gen_key(DH *dh, int need) 270 { 271 int pbits; 272 const BIGNUM *dh_p, *pub_key; 273 274 DH_get0_pqg(dh, &dh_p, NULL, NULL); 275 276 if (need < 0 || dh_p == NULL || 277 (pbits = BN_num_bits(dh_p)) <= 0 || 278 need > INT_MAX / 2 || 2 * need > pbits) 279 return SSH_ERR_INVALID_ARGUMENT; 280 if (need < 256) 281 need = 256; 282 /* 283 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)), 284 * so double requested need here. 285 */ 286 if (!DH_set_length(dh, MINIMUM(need * 2, pbits - 1))) 287 return SSH_ERR_LIBCRYPTO_ERROR; 288 289 if (DH_generate_key(dh) == 0) 290 return SSH_ERR_LIBCRYPTO_ERROR; 291 DH_get0_key(dh, &pub_key, NULL); 292 if (!dh_pub_is_valid(dh, pub_key)) 293 return SSH_ERR_INVALID_FORMAT; 294 return 0; 295 } 296 297 DH * 298 dh_new_group_asc(const char *gen, const char *modulus) 299 { 300 DH *dh; 301 BIGNUM *dh_p = NULL, *dh_g = NULL; 302 303 if ((dh = DH_new()) == NULL) 304 return NULL; 305 if (BN_hex2bn(&dh_p, modulus) == 0 || 306 BN_hex2bn(&dh_g, gen) == 0) 307 goto fail; 308 if (!DH_set0_pqg(dh, dh_p, NULL, dh_g)) 309 goto fail; 310 return dh; 311 fail: 312 DH_free(dh); 313 BN_clear_free(dh_p); 314 BN_clear_free(dh_g); 315 return NULL; 316 } 317 318 /* 319 * This just returns the group, we still need to generate the exchange 320 * value. 321 */ 322 DH * 323 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 324 { 325 DH *dh; 326 327 if ((dh = DH_new()) == NULL) 328 return NULL; 329 if (!DH_set0_pqg(dh, modulus, NULL, gen)) { 330 DH_free(dh); 331 return NULL; 332 } 333 334 return dh; 335 } 336 337 /* rfc2409 "Second Oakley Group" (1024 bits) */ 338 DH * 339 dh_new_group1(void) 340 { 341 static char *gen = "2", *group1 = 342 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 343 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 344 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 345 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 346 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 347 "FFFFFFFF" "FFFFFFFF"; 348 349 return (dh_new_group_asc(gen, group1)); 350 } 351 352 /* rfc3526 group 14 "2048-bit MODP Group" */ 353 DH * 354 dh_new_group14(void) 355 { 356 static char *gen = "2", *group14 = 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" "ECE45B3D" 362 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 363 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 364 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 365 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 366 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 367 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 368 369 return (dh_new_group_asc(gen, group14)); 370 } 371 372 /* rfc3526 group 16 "4096-bit MODP Group" */ 373 DH * 374 dh_new_group16(void) 375 { 376 static char *gen = "2", *group16 = 377 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 378 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 379 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 380 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 381 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 382 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 383 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 384 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 385 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 386 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 387 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 388 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 389 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 390 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 391 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 392 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 393 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 394 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 395 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 396 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 397 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199" 398 "FFFFFFFF" "FFFFFFFF"; 399 400 return (dh_new_group_asc(gen, group16)); 401 } 402 403 /* rfc3526 group 18 "8192-bit MODP Group" */ 404 DH * 405 dh_new_group18(void) 406 { 407 static char *gen = "2", *group16 = 408 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 409 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 410 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 411 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 412 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 413 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 414 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 415 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 416 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 417 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 418 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 419 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 420 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 421 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 422 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 423 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 424 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 425 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 426 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 427 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 428 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492" 429 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD" 430 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831" 431 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B" 432 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF" 433 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6" 434 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3" 435 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA" 436 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328" 437 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C" 438 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE" 439 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4" 440 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300" 441 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568" 442 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9" 443 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B" 444 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A" 445 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36" 446 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1" 447 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92" 448 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47" 449 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71" 450 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF"; 451 452 return (dh_new_group_asc(gen, group16)); 453 } 454 455 /* Select fallback group used by DH-GEX if moduli file cannot be read. */ 456 DH * 457 dh_new_group_fallback(int max) 458 { 459 debug3("%s: requested max size %d", __func__, max); 460 if (max < 3072) { 461 debug3("using 2k bit group 14"); 462 return dh_new_group14(); 463 } else if (max < 6144) { 464 debug3("using 4k bit group 16"); 465 return dh_new_group16(); 466 } 467 debug3("using 8k bit group 18"); 468 return dh_new_group18(); 469 } 470 471 /* 472 * Estimates the group order for a Diffie-Hellman group that has an 473 * attack complexity approximately the same as O(2**bits). 474 * Values from NIST Special Publication 800-57: Recommendation for Key 475 * Management Part 1 (rev 3) limited by the recommended maximum value 476 * from RFC4419 section 3. 477 */ 478 u_int 479 dh_estimate(int bits) 480 { 481 if (bits <= 112) 482 return 2048; 483 if (bits <= 128) 484 return 3072; 485 if (bits <= 192) 486 return 7680; 487 return 8192; 488 } 489 490 #endif /* WITH_OPENSSL */ 491