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