1 /* $OpenBSD: dh.c,v 1.51 2013/07/02 12:31:43 markus 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 #include <sys/param.h> 29 30 #include <openssl/bn.h> 31 #include <openssl/dh.h> 32 33 #include <stdarg.h> 34 #include <stdio.h> 35 #include <stdlib.h> 36 #include <string.h> 37 38 #include "dh.h" 39 #include "pathnames.h" 40 #include "log.h" 41 #include "misc.h" 42 43 static int 44 parse_prime(int linenum, char *line, struct dhgroup *dhg) 45 { 46 char *cp, *arg; 47 char *strsize, *gen, *prime; 48 const char *errstr = NULL; 49 long long n; 50 51 dhg->p = dhg->g = NULL; 52 cp = line; 53 if ((arg = strdelim(&cp)) == NULL) 54 return 0; 55 /* Ignore leading whitespace */ 56 if (*arg == '\0') 57 arg = strdelim(&cp); 58 if (!arg || !*arg || *arg == '#') 59 return 0; 60 61 /* time */ 62 if (cp == NULL || *arg == '\0') 63 goto truncated; 64 arg = strsep(&cp, " "); /* type */ 65 if (cp == NULL || *arg == '\0') 66 goto truncated; 67 /* Ensure this is a safe prime */ 68 n = strtonum(arg, 0, 5, &errstr); 69 if (errstr != NULL || n != MODULI_TYPE_SAFE) { 70 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE); 71 goto fail; 72 } 73 arg = strsep(&cp, " "); /* tests */ 74 if (cp == NULL || *arg == '\0') 75 goto truncated; 76 /* Ensure prime has been tested and is not composite */ 77 n = strtonum(arg, 0, 0x1f, &errstr); 78 if (errstr != NULL || 79 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 80 error("moduli:%d: invalid moduli tests flag", linenum); 81 goto fail; 82 } 83 arg = strsep(&cp, " "); /* tries */ 84 if (cp == NULL || *arg == '\0') 85 goto truncated; 86 n = strtonum(arg, 0, 1<<30, &errstr); 87 if (errstr != NULL || n == 0) { 88 error("moduli:%d: invalid primality trial count", linenum); 89 goto fail; 90 } 91 strsize = strsep(&cp, " "); /* size */ 92 if (cp == NULL || *strsize == '\0' || 93 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 94 errstr) { 95 error("moduli:%d: invalid prime length", linenum); 96 goto fail; 97 } 98 /* The whole group is one bit larger */ 99 dhg->size++; 100 gen = strsep(&cp, " "); /* gen */ 101 if (cp == NULL || *gen == '\0') 102 goto truncated; 103 prime = strsep(&cp, " "); /* prime */ 104 if (cp != NULL || *prime == '\0') { 105 truncated: 106 error("moduli:%d: truncated", linenum); 107 goto fail; 108 } 109 110 if ((dhg->g = BN_new()) == NULL) 111 fatal("parse_prime: BN_new failed"); 112 if ((dhg->p = BN_new()) == NULL) 113 fatal("parse_prime: BN_new failed"); 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 132 return 1; 133 134 fail: 135 if (dhg->g != NULL) 136 BN_clear_free(dhg->g); 137 if (dhg->p != NULL) 138 BN_clear_free(dhg->p); 139 dhg->g = dhg->p = NULL; 140 error("Bad prime description in line %d", linenum); 141 return 0; 142 } 143 144 DH * 145 choose_dh(int min, int wantbits, int max) 146 { 147 FILE *f; 148 char line[4096]; 149 int best, bestcount, which; 150 int linenum; 151 struct dhgroup dhg; 152 153 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 154 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 155 logit("WARNING: %s does not exist, using fixed modulus", 156 _PATH_DH_MODULI); 157 return (dh_new_group14()); 158 } 159 160 linenum = 0; 161 best = bestcount = 0; 162 while (fgets(line, sizeof(line), f)) { 163 linenum++; 164 if (!parse_prime(linenum, line, &dhg)) 165 continue; 166 BN_clear_free(dhg.g); 167 BN_clear_free(dhg.p); 168 169 if (dhg.size > max || dhg.size < min) 170 continue; 171 172 if ((dhg.size > wantbits && dhg.size < best) || 173 (dhg.size > best && best < wantbits)) { 174 best = dhg.size; 175 bestcount = 0; 176 } 177 if (dhg.size == best) 178 bestcount++; 179 } 180 rewind(f); 181 182 if (bestcount == 0) { 183 fclose(f); 184 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 185 return (dh_new_group14()); 186 } 187 188 linenum = 0; 189 which = arc4random_uniform(bestcount); 190 while (fgets(line, sizeof(line), f)) { 191 if (!parse_prime(linenum, line, &dhg)) 192 continue; 193 if ((dhg.size > max || dhg.size < min) || 194 dhg.size != best || 195 linenum++ != which) { 196 BN_clear_free(dhg.g); 197 BN_clear_free(dhg.p); 198 continue; 199 } 200 break; 201 } 202 fclose(f); 203 if (linenum != which+1) 204 fatal("WARNING: line %d disappeared in %s, giving up", 205 which, _PATH_DH_PRIMES); 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 void 255 dh_gen_key(DH *dh, int need) 256 { 257 int i, bits_set, tries = 0; 258 259 if (need < 0) 260 fatal("dh_gen_key: need < 0"); 261 if (dh->p == NULL) 262 fatal("dh_gen_key: dh->p == NULL"); 263 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 264 fatal("dh_gen_key: group too small: %d (2*need %d)", 265 BN_num_bits(dh->p), 2*need); 266 do { 267 if (dh->priv_key != NULL) 268 BN_clear_free(dh->priv_key); 269 if ((dh->priv_key = BN_new()) == NULL) 270 fatal("dh_gen_key: BN_new failed"); 271 /* generate a 2*need bits random private exponent */ 272 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 273 fatal("dh_gen_key: BN_rand failed"); 274 if (DH_generate_key(dh) == 0) 275 fatal("DH_generate_key"); 276 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 277 if (BN_is_bit_set(dh->priv_key, i)) 278 bits_set++; 279 debug2("dh_gen_key: priv key bits set: %d/%d", 280 bits_set, BN_num_bits(dh->priv_key)); 281 if (tries++ > 10) 282 fatal("dh_gen_key: too many bad keys: giving up"); 283 } while (!dh_pub_is_valid(dh, dh->pub_key)); 284 } 285 286 DH * 287 dh_new_group_asc(const char *gen, const char *modulus) 288 { 289 DH *dh; 290 291 if ((dh = DH_new()) == NULL) 292 fatal("dh_new_group_asc: DH_new"); 293 294 if (BN_hex2bn(&dh->p, modulus) == 0) 295 fatal("BN_hex2bn p"); 296 if (BN_hex2bn(&dh->g, gen) == 0) 297 fatal("BN_hex2bn g"); 298 299 return (dh); 300 } 301 302 /* 303 * This just returns the group, we still need to generate the exchange 304 * value. 305 */ 306 307 DH * 308 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 309 { 310 DH *dh; 311 312 if ((dh = DH_new()) == NULL) 313 fatal("dh_new_group: DH_new"); 314 dh->p = modulus; 315 dh->g = gen; 316 317 return (dh); 318 } 319 320 DH * 321 dh_new_group1(void) 322 { 323 static char *gen = "2", *group1 = 324 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 325 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 326 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 327 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 328 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 329 "FFFFFFFF" "FFFFFFFF"; 330 331 return (dh_new_group_asc(gen, group1)); 332 } 333 334 DH * 335 dh_new_group14(void) 336 { 337 static char *gen = "2", *group14 = 338 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 339 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 340 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 341 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 342 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 343 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 344 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 345 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 346 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 347 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 348 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 349 350 return (dh_new_group_asc(gen, group14)); 351 } 352 353 /* 354 * Estimates the group order for a Diffie-Hellman group that has an 355 * attack complexity approximately the same as O(2**bits). Estimate 356 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 357 */ 358 359 int 360 dh_estimate(int bits) 361 { 362 363 if (bits <= 128) 364 return (1024); /* O(2**86) */ 365 if (bits <= 192) 366 return (2048); /* O(2**116) */ 367 return (4096); /* O(2**156) */ 368 } 369