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