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.17 2001/06/23 15:12:18 itojun 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 static 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[2048]; 107 int best, bestcount, which; 108 int linenum; 109 struct dhgroup dhg; 110 111 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 112 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 113 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 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 rewind(f); 138 139 if (bestcount == 0) { 140 fclose(f); 141 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 142 return (NULL); 143 } 144 145 linenum = 0; 146 which = arc4random() % bestcount; 147 while (fgets(line, sizeof(line), f)) { 148 if (!parse_prime(linenum, line, &dhg)) 149 continue; 150 if ((dhg.size > max || dhg.size < min) || 151 dhg.size != best || 152 linenum++ != which) { 153 BN_free(dhg.g); 154 BN_free(dhg.p); 155 continue; 156 } 157 break; 158 } 159 fclose(f); 160 if (linenum != which+1) 161 fatal("WARNING: line %d disappeared in %s, giving up", 162 which, _PATH_DH_PRIMES); 163 164 return (dh_new_group(dhg.g, dhg.p)); 165 } 166 167 /* diffie-hellman-group1-sha1 */ 168 169 int 170 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 171 { 172 int i; 173 int n = BN_num_bits(dh_pub); 174 int bits_set = 0; 175 176 if (dh_pub->neg) { 177 log("invalid public DH value: negativ"); 178 return 0; 179 } 180 for (i = 0; i <= n; i++) 181 if (BN_is_bit_set(dh_pub, i)) 182 bits_set++; 183 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 184 185 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 186 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 187 return 1; 188 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 189 return 0; 190 } 191 192 void 193 dh_gen_key(DH *dh, int need) 194 { 195 int i, bits_set = 0, tries = 0; 196 197 if (dh->p == NULL) 198 fatal("dh_gen_key: dh->p == NULL"); 199 if (2*need >= BN_num_bits(dh->p)) 200 fatal("dh_gen_key: group too small: %d (2*need %d)", 201 BN_num_bits(dh->p), 2*need); 202 do { 203 if (dh->priv_key != NULL) 204 BN_free(dh->priv_key); 205 dh->priv_key = BN_new(); 206 if (dh->priv_key == NULL) 207 fatal("dh_gen_key: BN_new failed"); 208 /* generate a 2*need bits random private exponent */ 209 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 210 fatal("dh_gen_key: BN_rand failed"); 211 if (DH_generate_key(dh) == 0) 212 fatal("DH_generate_key"); 213 for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 214 if (BN_is_bit_set(dh->priv_key, i)) 215 bits_set++; 216 debug("dh_gen_key: priv key bits set: %d/%d", 217 bits_set, BN_num_bits(dh->priv_key)); 218 if (tries++ > 10) 219 fatal("dh_gen_key: too many bad keys: giving up"); 220 } while (!dh_pub_is_valid(dh, dh->pub_key)); 221 } 222 223 DH * 224 dh_new_group_asc(const char *gen, const char *modulus) 225 { 226 DH *dh; 227 228 dh = DH_new(); 229 if (dh == NULL) 230 fatal("DH_new"); 231 232 if (BN_hex2bn(&dh->p, modulus) == 0) 233 fatal("BN_hex2bn p"); 234 if (BN_hex2bn(&dh->g, gen) == 0) 235 fatal("BN_hex2bn g"); 236 237 return (dh); 238 } 239 240 /* 241 * This just returns the group, we still need to generate the exchange 242 * value. 243 */ 244 245 DH * 246 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 247 { 248 DH *dh; 249 250 dh = DH_new(); 251 if (dh == NULL) 252 fatal("DH_new"); 253 dh->p = modulus; 254 dh->g = gen; 255 256 return (dh); 257 } 258 259 DH * 260 dh_new_group1(void) 261 { 262 static char *gen = "2", *group1 = 263 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 264 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 265 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 266 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 267 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 268 "FFFFFFFF" "FFFFFFFF"; 269 270 return (dh_new_group_asc(gen, group1)); 271 } 272 273 /* 274 * Estimates the group order for a Diffie-Hellman group that has an 275 * attack complexity approximately the same as O(2**bits). Estimate 276 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 277 */ 278 279 int 280 dh_estimate(int bits) 281 { 282 283 if (bits < 64) 284 return (512); /* O(2**63) */ 285 if (bits < 128) 286 return (1024); /* O(2**86) */ 287 if (bits < 192) 288 return (2048); /* O(2**116) */ 289 return (4096); /* O(2**156) */ 290 } 291