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