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