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.22 2002/06/27 08:49:44 markus Exp $"); 27 28 #pragma ident "%Z%%M% %I% %E% SMI" 29 30 #include "xmalloc.h" 31 32 #include <openssl/bn.h> 33 #include <openssl/dh.h> 34 #include <openssl/evp.h> 35 36 #include "buffer.h" 37 #include "cipher.h" 38 #include "kex.h" 39 #include "dh.h" 40 #include "pathnames.h" 41 #include "log.h" 42 #include "misc.h" 43 44 static int 45 parse_prime(int linenum, char *line, struct dhgroup *dhg) 46 { 47 char *cp, *arg; 48 char *strsize, *gen, *prime; 49 50 cp = line; 51 arg = strdelim(&cp); 52 /* Ignore leading whitespace */ 53 if (*arg == '\0') 54 arg = strdelim(&cp); 55 if (!arg || !*arg || *arg == '#') 56 return 0; 57 58 /* time */ 59 if (cp == NULL || *arg == '\0') 60 goto fail; 61 arg = strsep(&cp, " "); /* type */ 62 if (cp == NULL || *arg == '\0') 63 goto fail; 64 arg = strsep(&cp, " "); /* tests */ 65 if (cp == NULL || *arg == '\0') 66 goto fail; 67 arg = strsep(&cp, " "); /* tries */ 68 if (cp == NULL || *arg == '\0') 69 goto fail; 70 strsize = strsep(&cp, " "); /* size */ 71 if (cp == NULL || *strsize == '\0' || 72 (dhg->size = atoi(strsize)) == 0) 73 goto fail; 74 /* The whole group is one bit larger */ 75 dhg->size++; 76 gen = strsep(&cp, " "); /* gen */ 77 if (cp == NULL || *gen == '\0') 78 goto fail; 79 prime = strsep(&cp, " "); /* prime */ 80 if (cp != NULL || *prime == '\0') 81 goto fail; 82 83 if ((dhg->g = BN_new()) == NULL) 84 fatal("parse_prime: BN_new failed"); 85 if ((dhg->p = BN_new()) == NULL) 86 fatal("parse_prime: BN_new failed"); 87 if (BN_hex2bn(&dhg->g, gen) == 0) 88 goto failclean; 89 90 if (BN_hex2bn(&dhg->p, prime) == 0) 91 goto failclean; 92 93 if (BN_num_bits(dhg->p) != dhg->size) 94 goto failclean; 95 96 return (1); 97 98 failclean: 99 BN_clear_free(dhg->g); 100 BN_clear_free(dhg->p); 101 fail: 102 error("Bad prime description in line %d", linenum); 103 return (0); 104 } 105 106 DH * 107 choose_dh(int min, int wantbits, int max) 108 { 109 FILE *f; 110 char line[2048]; 111 int best, bestcount, which; 112 int linenum; 113 struct dhgroup dhg; 114 115 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 116 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 117 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 118 return (dh_new_group1()); 119 } 120 121 linenum = 0; 122 best = bestcount = 0; 123 while (fgets(line, sizeof(line), f)) { 124 linenum++; 125 if (!parse_prime(linenum, line, &dhg)) 126 continue; 127 BN_clear_free(dhg.g); 128 BN_clear_free(dhg.p); 129 130 if (dhg.size > max || dhg.size < min) 131 continue; 132 133 if ((dhg.size > wantbits && dhg.size < best) || 134 (dhg.size > best && best < wantbits)) { 135 best = dhg.size; 136 bestcount = 0; 137 } 138 if (dhg.size == best) 139 bestcount++; 140 } 141 rewind(f); 142 143 if (bestcount == 0) { 144 fclose(f); 145 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 146 return (NULL); 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_clear_free(dhg.g); 158 BN_clear_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_clear_free(dh->priv_key); 209 if ((dh->priv_key = BN_new()) == NULL) 210 fatal("dh_gen_key: BN_new failed"); 211 /* generate a 2*need bits random private exponent */ 212 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 213 fatal("dh_gen_key: BN_rand failed"); 214 if (DH_generate_key(dh) == 0) 215 fatal("DH_generate_key"); 216 for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 217 if (BN_is_bit_set(dh->priv_key, i)) 218 bits_set++; 219 debug("dh_gen_key: priv key bits set: %d/%d", 220 bits_set, BN_num_bits(dh->priv_key)); 221 if (tries++ > 10) 222 fatal("dh_gen_key: too many bad keys: giving up"); 223 } while (!dh_pub_is_valid(dh, dh->pub_key)); 224 } 225 226 DH * 227 dh_new_group_asc(const char *gen, const char *modulus) 228 { 229 DH *dh; 230 231 if ((dh = DH_new()) == NULL) 232 fatal("dh_new_group_asc: DH_new"); 233 234 if (BN_hex2bn(&dh->p, modulus) == 0) 235 fatal("BN_hex2bn p"); 236 if (BN_hex2bn(&dh->g, gen) == 0) 237 fatal("BN_hex2bn g"); 238 239 return (dh); 240 } 241 242 /* 243 * This just returns the group, we still need to generate the exchange 244 * value. 245 */ 246 247 DH * 248 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 249 { 250 DH *dh; 251 252 if ((dh = DH_new()) == NULL) 253 fatal("dh_new_group: DH_new"); 254 dh->p = modulus; 255 dh->g = gen; 256 257 return (dh); 258 } 259 260 DH * 261 dh_new_group1(void) 262 { 263 static char *gen = "2", *group1 = 264 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 265 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 266 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 267 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 268 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 269 "FFFFFFFF" "FFFFFFFF"; 270 271 return (dh_new_group_asc(gen, group1)); 272 } 273 274 /* 275 * Estimates the group order for a Diffie-Hellman group that has an 276 * attack complexity approximately the same as O(2**bits). Estimate 277 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 278 */ 279 280 int 281 dh_estimate(int bits) 282 { 283 284 if (bits < 64) 285 return (512); /* O(2**63) */ 286 if (bits < 128) 287 return (1024); /* O(2**86) */ 288 if (bits < 192) 289 return (2048); /* O(2**116) */ 290 return (4096); /* O(2**156) */ 291 } 292