1 /* $OpenBSD: dh.c,v 1.56 2015/03/26 06:59:28 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 <sys/param.h> /* MIN */ 27 28 #include <openssl/bn.h> 29 #include <openssl/dh.h> 30 31 #include <stdio.h> 32 #include <stdlib.h> 33 #include <string.h> 34 #include <limits.h> 35 36 #include "dh.h" 37 #include "pathnames.h" 38 #include "log.h" 39 #include "misc.h" 40 #include "ssherr.h" 41 42 static int 43 parse_prime(int linenum, char *line, struct dhgroup *dhg) 44 { 45 char *cp, *arg; 46 char *strsize, *gen, *prime; 47 const char *errstr = NULL; 48 long long n; 49 50 dhg->p = dhg->g = NULL; 51 cp = line; 52 if ((arg = strdelim(&cp)) == NULL) 53 return 0; 54 /* Ignore leading whitespace */ 55 if (*arg == '\0') 56 arg = strdelim(&cp); 57 if (!arg || !*arg || *arg == '#') 58 return 0; 59 60 /* time */ 61 if (cp == NULL || *arg == '\0') 62 goto truncated; 63 arg = strsep(&cp, " "); /* type */ 64 if (cp == NULL || *arg == '\0') 65 goto truncated; 66 /* Ensure this is a safe prime */ 67 n = strtonum(arg, 0, 5, &errstr); 68 if (errstr != NULL || n != MODULI_TYPE_SAFE) { 69 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE); 70 goto fail; 71 } 72 arg = strsep(&cp, " "); /* tests */ 73 if (cp == NULL || *arg == '\0') 74 goto truncated; 75 /* Ensure prime has been tested and is not composite */ 76 n = strtonum(arg, 0, 0x1f, &errstr); 77 if (errstr != NULL || 78 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 79 error("moduli:%d: invalid moduli tests flag", linenum); 80 goto fail; 81 } 82 arg = strsep(&cp, " "); /* tries */ 83 if (cp == NULL || *arg == '\0') 84 goto truncated; 85 n = strtonum(arg, 0, 1<<30, &errstr); 86 if (errstr != NULL || n == 0) { 87 error("moduli:%d: invalid primality trial count", linenum); 88 goto fail; 89 } 90 strsize = strsep(&cp, " "); /* size */ 91 if (cp == NULL || *strsize == '\0' || 92 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 93 errstr) { 94 error("moduli:%d: invalid prime length", linenum); 95 goto fail; 96 } 97 /* The whole group is one bit larger */ 98 dhg->size++; 99 gen = strsep(&cp, " "); /* gen */ 100 if (cp == NULL || *gen == '\0') 101 goto truncated; 102 prime = strsep(&cp, " "); /* prime */ 103 if (cp != NULL || *prime == '\0') { 104 truncated: 105 error("moduli:%d: truncated", linenum); 106 goto fail; 107 } 108 109 if ((dhg->g = BN_new()) == NULL || 110 (dhg->p = BN_new()) == NULL) { 111 error("parse_prime: BN_new failed"); 112 goto fail; 113 } 114 if (BN_hex2bn(&dhg->g, gen) == 0) { 115 error("moduli:%d: could not parse generator value", linenum); 116 goto fail; 117 } 118 if (BN_hex2bn(&dhg->p, prime) == 0) { 119 error("moduli:%d: could not parse prime value", linenum); 120 goto fail; 121 } 122 if (BN_num_bits(dhg->p) != dhg->size) { 123 error("moduli:%d: prime has wrong size: actual %d listed %d", 124 linenum, BN_num_bits(dhg->p), dhg->size - 1); 125 goto fail; 126 } 127 if (BN_cmp(dhg->g, BN_value_one()) <= 0) { 128 error("moduli:%d: generator is invalid", linenum); 129 goto fail; 130 } 131 return 1; 132 133 fail: 134 if (dhg->g != NULL) 135 BN_clear_free(dhg->g); 136 if (dhg->p != NULL) 137 BN_clear_free(dhg->p); 138 dhg->g = dhg->p = NULL; 139 return 0; 140 } 141 142 DH * 143 choose_dh(int min, int wantbits, int max) 144 { 145 FILE *f; 146 char line[4096]; 147 int best, bestcount, which; 148 int linenum; 149 struct dhgroup dhg; 150 151 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 152 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 153 logit("WARNING: %s does not exist, using fixed modulus", 154 _PATH_DH_MODULI); 155 return (dh_new_group14()); 156 } 157 158 linenum = 0; 159 best = bestcount = 0; 160 while (fgets(line, sizeof(line), f)) { 161 linenum++; 162 if (!parse_prime(linenum, line, &dhg)) 163 continue; 164 BN_clear_free(dhg.g); 165 BN_clear_free(dhg.p); 166 167 if (dhg.size > max || dhg.size < min) 168 continue; 169 170 if ((dhg.size > wantbits && dhg.size < best) || 171 (dhg.size > best && best < wantbits)) { 172 best = dhg.size; 173 bestcount = 0; 174 } 175 if (dhg.size == best) 176 bestcount++; 177 } 178 rewind(f); 179 180 if (bestcount == 0) { 181 fclose(f); 182 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 183 return (dh_new_group14()); 184 } 185 186 linenum = 0; 187 which = arc4random_uniform(bestcount); 188 while (fgets(line, sizeof(line), f)) { 189 if (!parse_prime(linenum, line, &dhg)) 190 continue; 191 if ((dhg.size > max || dhg.size < min) || 192 dhg.size != best || 193 linenum++ != which) { 194 BN_clear_free(dhg.g); 195 BN_clear_free(dhg.p); 196 continue; 197 } 198 break; 199 } 200 fclose(f); 201 if (linenum != which+1) { 202 logit("WARNING: line %d disappeared in %s, giving up", 203 which, _PATH_DH_PRIMES); 204 return (dh_new_group14()); 205 } 206 207 return (dh_new_group(dhg.g, dhg.p)); 208 } 209 210 /* diffie-hellman-groupN-sha1 */ 211 212 int 213 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 214 { 215 int i; 216 int n = BN_num_bits(dh_pub); 217 int bits_set = 0; 218 BIGNUM *tmp; 219 220 if (dh_pub->neg) { 221 logit("invalid public DH value: negative"); 222 return 0; 223 } 224 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 225 logit("invalid public DH value: <= 1"); 226 return 0; 227 } 228 229 if ((tmp = BN_new()) == NULL) { 230 error("%s: BN_new failed", __func__); 231 return 0; 232 } 233 if (!BN_sub(tmp, dh->p, BN_value_one()) || 234 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 235 BN_clear_free(tmp); 236 logit("invalid public DH value: >= p-1"); 237 return 0; 238 } 239 BN_clear_free(tmp); 240 241 for (i = 0; i <= n; i++) 242 if (BN_is_bit_set(dh_pub, i)) 243 bits_set++; 244 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 245 246 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 247 if (bits_set > 1) 248 return 1; 249 250 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 251 return 0; 252 } 253 254 int 255 dh_gen_key(DH *dh, int need) 256 { 257 int pbits; 258 259 if (need < 0 || dh->p == NULL || 260 (pbits = BN_num_bits(dh->p)) <= 0 || 261 need > INT_MAX / 2 || 2 * need > pbits) 262 return SSH_ERR_INVALID_ARGUMENT; 263 dh->length = MIN(need * 2, pbits - 1); 264 if (DH_generate_key(dh) == 0 || 265 !dh_pub_is_valid(dh, dh->pub_key)) { 266 BN_clear_free(dh->priv_key); 267 return SSH_ERR_LIBCRYPTO_ERROR; 268 } 269 return 0; 270 } 271 272 DH * 273 dh_new_group_asc(const char *gen, const char *modulus) 274 { 275 DH *dh; 276 277 if ((dh = DH_new()) == NULL) 278 return NULL; 279 if (BN_hex2bn(&dh->p, modulus) == 0 || 280 BN_hex2bn(&dh->g, gen) == 0) { 281 DH_free(dh); 282 return NULL; 283 } 284 return (dh); 285 } 286 287 /* 288 * This just returns the group, we still need to generate the exchange 289 * value. 290 */ 291 292 DH * 293 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 294 { 295 DH *dh; 296 297 if ((dh = DH_new()) == NULL) 298 return NULL; 299 dh->p = modulus; 300 dh->g = gen; 301 302 return (dh); 303 } 304 305 DH * 306 dh_new_group1(void) 307 { 308 static char *gen = "2", *group1 = 309 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 310 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 311 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 312 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 313 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 314 "FFFFFFFF" "FFFFFFFF"; 315 316 return (dh_new_group_asc(gen, group1)); 317 } 318 319 DH * 320 dh_new_group14(void) 321 { 322 static char *gen = "2", *group14 = 323 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 324 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 325 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 326 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 327 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 328 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 329 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 330 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 331 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 332 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 333 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 334 335 return (dh_new_group_asc(gen, group14)); 336 } 337 338 /* 339 * Estimates the group order for a Diffie-Hellman group that has an 340 * attack complexity approximately the same as O(2**bits). 341 * Values from NIST Special Publication 800-57: Recommendation for Key 342 * Management Part 1 (rev 3) limited by the recommended maximum value 343 * from RFC4419 section 3. 344 */ 345 346 u_int 347 dh_estimate(int bits) 348 { 349 if (bits <= 112) 350 return 2048; 351 if (bits <= 128) 352 return 3072; 353 if (bits <= 192) 354 return 7680; 355 return 8192; 356 } 357