1 /* $NetBSD: dh.c,v 1.4 2011/07/25 03:03:10 christos Exp $ */ 2 /* $OpenBSD: dh.c,v 1.48 2009/10/01 11:37:33 grunk Exp $ */ 3 /* 4 * Copyright (c) 2000 Niels Provos. All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #include "includes.h" 28 __RCSID("$NetBSD: dh.c,v 1.4 2011/07/25 03:03:10 christos Exp $"); 29 #include <sys/param.h> 30 31 #include <openssl/bn.h> 32 #include <openssl/dh.h> 33 34 #include <stdio.h> 35 #include <stdlib.h> 36 #include <string.h> 37 #include <time.h> 38 39 #include "dh.h" 40 #include "pathnames.h" 41 #include "log.h" 42 #include "misc.h" 43 #include "random.h" 44 45 static int 46 parse_prime(int linenum, char *line, struct dhgroup *dhg) 47 { 48 char *cp, *arg; 49 char *strsize, *gen, *prime; 50 const char *errstr = NULL; 51 long long n; 52 53 cp = line; 54 if ((arg = strdelim(&cp)) == NULL) 55 return 0; 56 /* Ignore leading whitespace */ 57 if (*arg == '\0') 58 arg = strdelim(&cp); 59 if (!arg || !*arg || *arg == '#') 60 return 0; 61 62 /* time */ 63 if (cp == NULL || *arg == '\0') 64 goto fail; 65 arg = strsep(&cp, " "); /* type */ 66 if (cp == NULL || *arg == '\0') 67 goto fail; 68 /* Ensure this is a safe prime */ 69 n = strtonum(arg, 0, 5, &errstr); 70 if (errstr != NULL || n != MODULI_TYPE_SAFE) 71 goto fail; 72 arg = strsep(&cp, " "); /* tests */ 73 if (cp == NULL || *arg == '\0') 74 goto fail; 75 /* Ensure prime has been tested and is not composite */ 76 n = strtonum(arg, 0, 0x1f, &errstr); 77 if (errstr != NULL || 78 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) 79 goto fail; 80 arg = strsep(&cp, " "); /* tries */ 81 if (cp == NULL || *arg == '\0') 82 goto fail; 83 n = strtonum(arg, 0, 1<<30, &errstr); 84 if (errstr != NULL || n == 0) 85 goto fail; 86 strsize = strsep(&cp, " "); /* size */ 87 if (cp == NULL || *strsize == '\0' || 88 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 89 errstr) 90 goto fail; 91 /* The whole group is one bit larger */ 92 dhg->size++; 93 gen = strsep(&cp, " "); /* gen */ 94 if (cp == NULL || *gen == '\0') 95 goto fail; 96 prime = strsep(&cp, " "); /* prime */ 97 if (cp != NULL || *prime == '\0') 98 goto fail; 99 100 if ((dhg->g = BN_new()) == NULL) 101 fatal("parse_prime: BN_new failed"); 102 if ((dhg->p = BN_new()) == NULL) 103 fatal("parse_prime: BN_new failed"); 104 if (BN_hex2bn(&dhg->g, gen) == 0) 105 goto failclean; 106 107 if (BN_hex2bn(&dhg->p, prime) == 0) 108 goto failclean; 109 110 if (BN_num_bits(dhg->p) != dhg->size) 111 goto failclean; 112 113 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g)) 114 goto failclean; 115 116 return (1); 117 118 failclean: 119 BN_clear_free(dhg->g); 120 BN_clear_free(dhg->p); 121 fail: 122 error("Bad prime description in line %d", linenum); 123 return (0); 124 } 125 126 DH * 127 choose_dh(int min, int wantbits, int max) 128 { 129 FILE *f; 130 char line[4096]; 131 int best, bestcount, which; 132 int linenum; 133 struct dhgroup dhg; 134 135 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 136 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 137 logit("WARNING: %s does not exist, using fixed modulus", 138 _PATH_DH_MODULI); 139 return (dh_new_group14()); 140 } 141 142 linenum = 0; 143 best = bestcount = 0; 144 while (fgets(line, sizeof(line), f)) { 145 linenum++; 146 if (!parse_prime(linenum, line, &dhg)) 147 continue; 148 BN_clear_free(dhg.g); 149 BN_clear_free(dhg.p); 150 151 if (dhg.size > max || dhg.size < min) 152 continue; 153 154 if ((dhg.size > wantbits && dhg.size < best) || 155 (dhg.size > best && best < wantbits)) { 156 best = dhg.size; 157 bestcount = 0; 158 } 159 if (dhg.size == best) 160 bestcount++; 161 } 162 rewind(f); 163 164 if (bestcount == 0) { 165 fclose(f); 166 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 167 return (dh_new_group14()); 168 } 169 170 linenum = 0; 171 which = arc4random_uniform(bestcount); 172 while (fgets(line, sizeof(line), f)) { 173 if (!parse_prime(linenum, line, &dhg)) 174 continue; 175 if ((dhg.size > max || dhg.size < min) || 176 dhg.size != best || 177 linenum++ != which) { 178 BN_clear_free(dhg.g); 179 BN_clear_free(dhg.p); 180 continue; 181 } 182 break; 183 } 184 fclose(f); 185 if (linenum != which+1) 186 fatal("WARNING: line %d disappeared in %s, giving up", 187 which, _PATH_DH_PRIMES); 188 189 return (dh_new_group(dhg.g, dhg.p)); 190 } 191 192 /* diffie-hellman-groupN-sha1 */ 193 194 int 195 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 196 { 197 int i; 198 int n = BN_num_bits(dh_pub); 199 int bits_set = 0; 200 BIGNUM *tmp; 201 202 if (dh_pub->neg) { 203 logit("invalid public DH value: negative"); 204 return 0; 205 } 206 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 207 logit("invalid public DH value: <= 1"); 208 return 0; 209 } 210 211 if ((tmp = BN_new()) == NULL) { 212 error("%s: BN_new failed", __func__); 213 return 0; 214 } 215 if (!BN_sub(tmp, dh->p, BN_value_one()) || 216 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 217 BN_clear_free(tmp); 218 logit("invalid public DH value: >= p-1"); 219 return 0; 220 } 221 BN_clear_free(tmp); 222 223 for (i = 0; i <= n; i++) 224 if (BN_is_bit_set(dh_pub, i)) 225 bits_set++; 226 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 227 228 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 229 if (bits_set > 1) 230 return 1; 231 232 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 233 return 0; 234 } 235 236 void 237 dh_gen_key(DH *dh, int need) 238 { 239 int i, bits_set, tries = 0; 240 241 if (dh->p == NULL) 242 fatal("dh_gen_key: dh->p == NULL"); 243 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 244 fatal("dh_gen_key: group too small: %d (2*need %d)", 245 BN_num_bits(dh->p), 2*need); 246 do { 247 if (dh->priv_key != NULL) 248 BN_clear_free(dh->priv_key); 249 if ((dh->priv_key = BN_new()) == NULL) 250 fatal("dh_gen_key: BN_new failed"); 251 /* generate a 2*need bits random private exponent */ 252 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 253 fatal("dh_gen_key: BN_rand failed"); 254 if (DH_generate_key(dh) == 0) 255 fatal("DH_generate_key"); 256 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 257 if (BN_is_bit_set(dh->priv_key, i)) 258 bits_set++; 259 debug2("dh_gen_key: priv key bits set: %d/%d", 260 bits_set, BN_num_bits(dh->priv_key)); 261 if (tries++ > 10) 262 fatal("dh_gen_key: too many bad keys: giving up"); 263 } while (!dh_pub_is_valid(dh, dh->pub_key)); 264 } 265 266 DH * 267 dh_new_group_asc(const char *gen, const char *modulus) 268 { 269 DH *dh; 270 271 if ((dh = DH_new()) == NULL) 272 fatal("dh_new_group_asc: DH_new"); 273 274 if (BN_hex2bn(&dh->p, modulus) == 0) 275 fatal("BN_hex2bn p"); 276 if (BN_hex2bn(&dh->g, gen) == 0) 277 fatal("BN_hex2bn g"); 278 279 return (dh); 280 } 281 282 /* 283 * This just returns the group, we still need to generate the exchange 284 * value. 285 */ 286 287 DH * 288 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 289 { 290 DH *dh; 291 292 if ((dh = DH_new()) == NULL) 293 fatal("dh_new_group: DH_new"); 294 dh->p = modulus; 295 dh->g = gen; 296 297 return (dh); 298 } 299 300 DH * 301 dh_new_group1(void) 302 { 303 static const char *gen = "2", *group1 = 304 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 305 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 306 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 307 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 308 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 309 "FFFFFFFF" "FFFFFFFF"; 310 311 return (dh_new_group_asc(gen, group1)); 312 } 313 314 DH * 315 dh_new_group14(void) 316 { 317 static const char *gen = "2", *group14 = 318 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 319 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 320 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 321 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 322 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 323 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 324 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 325 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 326 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 327 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 328 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 329 330 return (dh_new_group_asc(gen, group14)); 331 } 332 333 /* 334 * Estimates the group order for a Diffie-Hellman group that has an 335 * attack complexity approximately the same as O(2**bits). Estimate 336 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 337 */ 338 339 int 340 dh_estimate(int bits) 341 { 342 343 if (bits <= 128) 344 return (1024); /* O(2**86) */ 345 if (bits <= 192) 346 return (2048); /* O(2**116) */ 347 return (4096); /* O(2**156) */ 348 } 349