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