1 /* $NetBSD: dh.c,v 1.9 2015/07/03 01:00:00 christos Exp $ */ 2 /* $OpenBSD: dh.c,v 1.57 2015/05/27 23:39:18 dtucker 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.9 2015/07/03 01:00:00 christos Exp $"); 29 #include <sys/param.h> 30 #include <sys/param.h> /* MIN */ 31 32 #include <openssl/bn.h> 33 #include <openssl/dh.h> 34 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 if (dhg->g != NULL) 141 BN_clear_free(dhg->g); 142 if (dhg->p != NULL) 143 BN_clear_free(dhg->p); 144 dhg->g = dhg->p = NULL; 145 return 0; 146 } 147 148 DH * 149 choose_dh(int min, int wantbits, int max) 150 { 151 FILE *f; 152 char line[4096]; 153 int best, bestcount, which; 154 int linenum; 155 struct dhgroup dhg; 156 157 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 158 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 159 logit("WARNING: %s does not exist, using fixed modulus", 160 _PATH_DH_MODULI); 161 return (dh_new_group_fallback(max)); 162 } 163 164 linenum = 0; 165 best = bestcount = 0; 166 while (fgets(line, sizeof(line), f)) { 167 linenum++; 168 if (!parse_prime(linenum, line, &dhg)) 169 continue; 170 BN_clear_free(dhg.g); 171 BN_clear_free(dhg.p); 172 173 if (dhg.size > max || dhg.size < min) 174 continue; 175 176 if ((dhg.size > wantbits && dhg.size < best) || 177 (dhg.size > best && best < wantbits)) { 178 best = dhg.size; 179 bestcount = 0; 180 } 181 if (dhg.size == best) 182 bestcount++; 183 } 184 rewind(f); 185 186 if (bestcount == 0) { 187 fclose(f); 188 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 189 return (dh_new_group_fallback(max)); 190 } 191 192 linenum = 0; 193 which = arc4random_uniform(bestcount); 194 while (fgets(line, sizeof(line), f)) { 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 fclose(f); 207 if (linenum != which+1) { 208 logit("WARNING: line %d disappeared in %s, giving up", 209 which, _PATH_DH_PRIMES); 210 return (dh_new_group_fallback(max)); 211 } 212 213 return (dh_new_group(dhg.g, dhg.p)); 214 } 215 216 /* diffie-hellman-groupN-sha1 */ 217 218 int 219 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 220 { 221 int i; 222 int n = BN_num_bits(dh_pub); 223 int bits_set = 0; 224 BIGNUM *tmp; 225 226 if (dh_pub->neg) { 227 logit("invalid public DH value: negative"); 228 return 0; 229 } 230 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 231 logit("invalid public DH value: <= 1"); 232 return 0; 233 } 234 235 if ((tmp = BN_new()) == NULL) { 236 error("%s: BN_new failed", __func__); 237 return 0; 238 } 239 if (!BN_sub(tmp, dh->p, BN_value_one()) || 240 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 241 BN_clear_free(tmp); 242 logit("invalid public DH value: >= p-1"); 243 return 0; 244 } 245 BN_clear_free(tmp); 246 247 for (i = 0; i <= n; i++) 248 if (BN_is_bit_set(dh_pub, i)) 249 bits_set++; 250 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 251 252 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 253 if (bits_set > 1) 254 return 1; 255 256 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 257 return 0; 258 } 259 260 int 261 dh_gen_key(DH *dh, int need) 262 { 263 int pbits; 264 265 if (need < 0 || dh->p == NULL || 266 (pbits = BN_num_bits(dh->p)) <= 0 || 267 need > INT_MAX / 2 || 2 * need > pbits) 268 return SSH_ERR_INVALID_ARGUMENT; 269 dh->length = MIN(need * 2, pbits - 1); 270 if (DH_generate_key(dh) == 0 || 271 !dh_pub_is_valid(dh, dh->pub_key)) { 272 BN_clear_free(dh->priv_key); 273 return SSH_ERR_LIBCRYPTO_ERROR; 274 } 275 return 0; 276 } 277 278 DH * 279 dh_new_group_asc(const char *gen, const char *modulus) 280 { 281 DH *dh; 282 283 if ((dh = DH_new()) == NULL) 284 return NULL; 285 if (BN_hex2bn(&dh->p, modulus) == 0 || 286 BN_hex2bn(&dh->g, gen) == 0) { 287 DH_free(dh); 288 return NULL; 289 } 290 return (dh); 291 } 292 293 /* 294 * This just returns the group, we still need to generate the exchange 295 * value. 296 */ 297 298 DH * 299 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 300 { 301 DH *dh; 302 303 if ((dh = DH_new()) == NULL) 304 return NULL; 305 dh->p = modulus; 306 dh->g = gen; 307 308 return (dh); 309 } 310 311 DH * 312 dh_new_group1(void) 313 { 314 static const char *gen = "2", *group1 = 315 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 316 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 317 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 318 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 319 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 320 "FFFFFFFF" "FFFFFFFF"; 321 322 return (dh_new_group_asc(gen, group1)); 323 } 324 325 DH * 326 dh_new_group14(void) 327 { 328 static const char *gen = "2", *group14 = 329 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 330 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 331 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 332 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 333 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 334 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 335 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 336 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 337 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 338 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 339 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 340 341 return (dh_new_group_asc(gen, group14)); 342 } 343 344 /* 345 * 4k bit fallback group used by DH-GEX if moduli file cannot be read. 346 * Source: MODP group 16 from RFC3526. 347 */ 348 DH * 349 dh_new_group_fallback(int max) 350 { 351 static const char *gen = "2", *group16 = 352 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 353 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 354 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 355 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 356 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 357 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 358 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 359 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 360 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 361 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 362 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64" 363 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7" 364 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B" 365 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C" 366 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31" 367 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7" 368 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA" 369 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6" 370 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED" 371 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9" 372 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199" 373 "FFFFFFFF" "FFFFFFFF"; 374 375 if (max < 4096) { 376 debug3("requested max size %d, using 2k bit group 14", max); 377 return dh_new_group14(); 378 } 379 debug3("using 4k bit group 16"); 380 return (dh_new_group_asc(gen, group16)); 381 } 382 383 /* 384 * Estimates the group order for a Diffie-Hellman group that has an 385 * attack complexity approximately the same as O(2**bits). 386 * Values from NIST Special Publication 800-57: Recommendation for Key 387 * Management Part 1 (rev 3) limited by the recommended maximum value 388 * from RFC4419 section 3. 389 */ 390 391 u_int 392 dh_estimate(int bits) 393 { 394 if (bits <= 112) 395 return 2048; 396 if (bits <= 128) 397 return 3072; 398 if (bits <= 192) 399 return 7680; 400 return 8192; 401 } 402