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