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.29 2004/02/27 22:49:27 dtucker 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 || *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 if ((dhg->g = BN_new()) == NULL) 82 fatal("parse_prime: BN_new failed"); 83 if ((dhg->p = BN_new()) == NULL) 84 fatal("parse_prime: BN_new failed"); 85 if (BN_hex2bn(&dhg->g, gen) == 0) 86 goto failclean; 87 88 if (BN_hex2bn(&dhg->p, prime) == 0) 89 goto failclean; 90 91 if (BN_num_bits(dhg->p) != dhg->size) 92 goto failclean; 93 94 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g)) 95 goto failclean; 96 97 return (1); 98 99 failclean: 100 BN_clear_free(dhg->g); 101 BN_clear_free(dhg->p); 102 fail: 103 error("Bad prime description in line %d", linenum); 104 return (0); 105 } 106 107 DH * 108 choose_dh(int min, int wantbits, int max) 109 { 110 FILE *f; 111 char line[4096]; 112 int best, bestcount, which; 113 int linenum; 114 struct dhgroup dhg; 115 116 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 117 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 118 logit("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 119 return (dh_new_group1()); 120 } 121 122 linenum = 0; 123 best = bestcount = 0; 124 while (fgets(line, sizeof(line), f)) { 125 linenum++; 126 if (!parse_prime(linenum, line, &dhg)) 127 continue; 128 BN_clear_free(dhg.g); 129 BN_clear_free(dhg.p); 130 131 if (dhg.size > max || dhg.size < min) 132 continue; 133 134 if ((dhg.size > wantbits && dhg.size < best) || 135 (dhg.size > best && best < wantbits)) { 136 best = dhg.size; 137 bestcount = 0; 138 } 139 if (dhg.size == best) 140 bestcount++; 141 } 142 rewind(f); 143 144 if (bestcount == 0) { 145 fclose(f); 146 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 147 return (NULL); 148 } 149 150 linenum = 0; 151 which = arc4random() % bestcount; 152 while (fgets(line, sizeof(line), f)) { 153 if (!parse_prime(linenum, line, &dhg)) 154 continue; 155 if ((dhg.size > max || dhg.size < min) || 156 dhg.size != best || 157 linenum++ != which) { 158 BN_clear_free(dhg.g); 159 BN_clear_free(dhg.p); 160 continue; 161 } 162 break; 163 } 164 fclose(f); 165 if (linenum != which+1) 166 fatal("WARNING: line %d disappeared in %s, giving up", 167 which, _PATH_DH_PRIMES); 168 169 return (dh_new_group(dhg.g, dhg.p)); 170 } 171 172 /* diffie-hellman-group1-sha1 */ 173 174 int 175 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 176 { 177 int i; 178 int n = BN_num_bits(dh_pub); 179 int bits_set = 0; 180 181 if (dh_pub->neg) { 182 logit("invalid public DH value: negativ"); 183 return 0; 184 } 185 for (i = 0; i <= n; i++) 186 if (BN_is_bit_set(dh_pub, i)) 187 bits_set++; 188 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 189 190 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 191 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 192 return 1; 193 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 194 return 0; 195 } 196 197 void 198 dh_gen_key(DH *dh, int need) 199 { 200 int i, bits_set, tries = 0; 201 202 if (dh->p == NULL) 203 fatal("dh_gen_key: dh->p == NULL"); 204 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 205 fatal("dh_gen_key: group too small: %d (2*need %d)", 206 BN_num_bits(dh->p), 2*need); 207 do { 208 if (dh->priv_key != NULL) 209 BN_clear_free(dh->priv_key); 210 if ((dh->priv_key = BN_new()) == 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, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 218 if (BN_is_bit_set(dh->priv_key, i)) 219 bits_set++; 220 debug2("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 if ((dh = DH_new()) == NULL) 233 fatal("dh_new_group_asc: DH_new"); 234 235 if (BN_hex2bn(&dh->p, modulus) == 0) 236 fatal("BN_hex2bn p"); 237 if (BN_hex2bn(&dh->g, gen) == 0) 238 fatal("BN_hex2bn g"); 239 240 return (dh); 241 } 242 243 /* 244 * This just returns the group, we still need to generate the exchange 245 * value. 246 */ 247 248 DH * 249 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 250 { 251 DH *dh; 252 253 if ((dh = DH_new()) == NULL) 254 fatal("dh_new_group: DH_new"); 255 dh->p = modulus; 256 dh->g = gen; 257 258 return (dh); 259 } 260 261 DH * 262 dh_new_group1(void) 263 { 264 static char *gen = "2", *group1 = 265 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 266 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 267 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 268 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 269 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 270 "FFFFFFFF" "FFFFFFFF"; 271 272 return (dh_new_group_asc(gen, group1)); 273 } 274 275 /* 276 * Estimates the group order for a Diffie-Hellman group that has an 277 * attack complexity approximately the same as O(2**bits). Estimate 278 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 279 */ 280 281 int 282 dh_estimate(int bits) 283 { 284 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