1 /* 2 * Copyright (c) 2000 Niels Provos. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 17 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23 */ 24 25 #include "includes.h" 26 RCSID("$OpenBSD: dh.c,v 1.14 2001/04/15 08:43:45 markus Exp $"); 27 28 #include "xmalloc.h" 29 30 #include <openssl/bn.h> 31 #include <openssl/dh.h> 32 #include <openssl/evp.h> 33 34 #include "buffer.h" 35 #include "cipher.h" 36 #include "kex.h" 37 #include "dh.h" 38 #include "pathnames.h" 39 #include "log.h" 40 #include "misc.h" 41 42 int 43 parse_prime(int linenum, char *line, struct dhgroup *dhg) 44 { 45 char *cp, *arg; 46 char *strsize, *gen, *prime; 47 48 cp = line; 49 arg = strdelim(&cp); 50 /* Ignore leading whitespace */ 51 if (*arg == '\0') 52 arg = strdelim(&cp); 53 if (!*arg || *arg == '#') 54 return 0; 55 56 /* time */ 57 if (cp == NULL || *arg == '\0') 58 goto fail; 59 arg = strsep(&cp, " "); /* type */ 60 if (cp == NULL || *arg == '\0') 61 goto fail; 62 arg = strsep(&cp, " "); /* tests */ 63 if (cp == NULL || *arg == '\0') 64 goto fail; 65 arg = strsep(&cp, " "); /* tries */ 66 if (cp == NULL || *arg == '\0') 67 goto fail; 68 strsize = strsep(&cp, " "); /* size */ 69 if (cp == NULL || *strsize == '\0' || 70 (dhg->size = atoi(strsize)) == 0) 71 goto fail; 72 /* The whole group is one bit larger */ 73 dhg->size++; 74 gen = strsep(&cp, " "); /* gen */ 75 if (cp == NULL || *gen == '\0') 76 goto fail; 77 prime = strsep(&cp, " "); /* prime */ 78 if (cp != NULL || *prime == '\0') 79 goto fail; 80 81 dhg->g = BN_new(); 82 dhg->p = BN_new(); 83 if (BN_hex2bn(&dhg->g, gen) == 0) 84 goto failclean; 85 86 if (BN_hex2bn(&dhg->p, prime) == 0) 87 goto failclean; 88 89 if (BN_num_bits(dhg->p) != dhg->size) 90 goto failclean; 91 92 return (1); 93 94 failclean: 95 BN_free(dhg->g); 96 BN_free(dhg->p); 97 fail: 98 error("Bad prime description in line %d", linenum); 99 return (0); 100 } 101 102 DH * 103 choose_dh(int min, int wantbits, int max) 104 { 105 FILE *f; 106 char line[1024]; 107 int best, bestcount, which; 108 int linenum; 109 struct dhgroup dhg; 110 111 f = fopen(_PATH_DH_PRIMES, "r"); 112 if (!f) { 113 log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES); 114 return (dh_new_group1()); 115 } 116 117 linenum = 0; 118 best = bestcount = 0; 119 while (fgets(line, sizeof(line), f)) { 120 linenum++; 121 if (!parse_prime(linenum, line, &dhg)) 122 continue; 123 BN_free(dhg.g); 124 BN_free(dhg.p); 125 126 if (dhg.size > max || dhg.size < min) 127 continue; 128 129 if ((dhg.size > wantbits && dhg.size < best) || 130 (dhg.size > best && best < wantbits)) { 131 best = dhg.size; 132 bestcount = 0; 133 } 134 if (dhg.size == best) 135 bestcount++; 136 } 137 fclose (f); 138 139 if (bestcount == 0) { 140 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 141 return (NULL); 142 } 143 144 f = fopen(_PATH_DH_PRIMES, "r"); 145 if (!f) { 146 fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES); 147 } 148 149 linenum = 0; 150 which = arc4random() % bestcount; 151 while (fgets(line, sizeof(line), f)) { 152 if (!parse_prime(linenum, line, &dhg)) 153 continue; 154 if ((dhg.size > max || dhg.size < min) || 155 dhg.size != best || 156 linenum++ != which) { 157 BN_free(dhg.g); 158 BN_free(dhg.p); 159 continue; 160 } 161 break; 162 } 163 fclose(f); 164 if (linenum != which+1) 165 fatal("WARNING: line %d disappeared in %s, giving up", 166 which, _PATH_DH_PRIMES); 167 168 return (dh_new_group(dhg.g, dhg.p)); 169 } 170 171 /* diffie-hellman-group1-sha1 */ 172 173 int 174 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 175 { 176 int i; 177 int n = BN_num_bits(dh_pub); 178 int bits_set = 0; 179 180 if (dh_pub->neg) { 181 log("invalid public DH value: negativ"); 182 return 0; 183 } 184 for (i = 0; i <= n; i++) 185 if (BN_is_bit_set(dh_pub, i)) 186 bits_set++; 187 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 188 189 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 190 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 191 return 1; 192 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 193 return 0; 194 } 195 196 void 197 dh_gen_key(DH *dh, int need) 198 { 199 int i, bits_set = 0, tries = 0; 200 201 if (dh->p == NULL) 202 fatal("dh_gen_key: dh->p == NULL"); 203 if (2*need >= BN_num_bits(dh->p)) 204 fatal("dh_gen_key: group too small: %d (2*need %d)", 205 BN_num_bits(dh->p), 2*need); 206 do { 207 if (dh->priv_key != NULL) 208 BN_free(dh->priv_key); 209 dh->priv_key = BN_new(); 210 if (dh->priv_key == NULL) 211 fatal("dh_gen_key: BN_new failed"); 212 /* generate a 2*need bits random private exponent */ 213 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 214 fatal("dh_gen_key: BN_rand failed"); 215 if (DH_generate_key(dh) == 0) 216 fatal("DH_generate_key"); 217 for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 218 if (BN_is_bit_set(dh->priv_key, i)) 219 bits_set++; 220 debug("dh_gen_key: priv key bits set: %d/%d", 221 bits_set, BN_num_bits(dh->priv_key)); 222 if (tries++ > 10) 223 fatal("dh_gen_key: too many bad keys: giving up"); 224 } while (!dh_pub_is_valid(dh, dh->pub_key)); 225 } 226 227 DH * 228 dh_new_group_asc(const char *gen, const char *modulus) 229 { 230 DH *dh; 231 232 dh = DH_new(); 233 if (dh == NULL) 234 fatal("DH_new"); 235 236 if (BN_hex2bn(&dh->p, modulus) == 0) 237 fatal("BN_hex2bn p"); 238 if (BN_hex2bn(&dh->g, gen) == 0) 239 fatal("BN_hex2bn g"); 240 241 return (dh); 242 } 243 244 /* 245 * This just returns the group, we still need to generate the exchange 246 * value. 247 */ 248 249 DH * 250 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 251 { 252 DH *dh; 253 254 dh = DH_new(); 255 if (dh == NULL) 256 fatal("DH_new"); 257 dh->p = modulus; 258 dh->g = gen; 259 260 return (dh); 261 } 262 263 DH * 264 dh_new_group1(void) 265 { 266 static char *gen = "2", *group1 = 267 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 268 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 269 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 270 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 271 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 272 "FFFFFFFF" "FFFFFFFF"; 273 274 return (dh_new_group_asc(gen, group1)); 275 } 276 277 /* 278 * Estimates the group order for a Diffie-Hellman group that has an 279 * attack complexity approximately the same as O(2**bits). Estimate 280 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 281 */ 282 283 int 284 dh_estimate(int bits) 285 { 286 287 if (bits < 64) 288 return (512); /* O(2**63) */ 289 if (bits < 128) 290 return (1024); /* O(2**86) */ 291 if (bits < 192) 292 return (2048); /* O(2**116) */ 293 return (4096); /* O(2**156) */ 294 } 295