dh.c revision 137015
1193323Sed/* 2193323Sed * Copyright (c) 2000 Niels Provos. All rights reserved. 3193323Sed * 4193323Sed * Redistribution and use in source and binary forms, with or without 5193323Sed * modification, are permitted provided that the following conditions 6193323Sed * are met: 7193323Sed * 1. Redistributions of source code must retain the above copyright 8193323Sed * notice, this list of conditions and the following disclaimer. 9193323Sed * 2. Redistributions in binary form must reproduce the above copyright 10193323Sed * notice, this list of conditions and the following disclaimer in the 11193323Sed * documentation and/or other materials provided with the distribution. 12193323Sed * 13193323Sed * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 14193323Sed * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15193323Sed * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16193323Sed * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 17193323Sed * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18193323Sed * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19218893Sdim * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20193323Sed * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21193323Sed * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22193323Sed * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23193323Sed */ 24193323Sed 25193323Sed#include "includes.h" 26193323SedRCSID("$OpenBSD: dh.c,v 1.31 2004/08/04 10:37:52 djm Exp $"); 27193323Sed 28193323Sed#include "xmalloc.h" 29193323Sed 30193323Sed#include <openssl/bn.h> 31193323Sed#include <openssl/dh.h> 32193323Sed#include <openssl/evp.h> 33193323Sed 34193323Sed#include "buffer.h" 35193323Sed#include "cipher.h" 36193323Sed#include "kex.h" 37193323Sed#include "dh.h" 38193323Sed#include "pathnames.h" 39218893Sdim#include "log.h" 40193323Sed#include "misc.h" 41193323Sed 42193323Sedstatic int 43193323Sedparse_prime(int linenum, char *line, struct dhgroup *dhg) 44193323Sed{ 45193323Sed char *cp, *arg; 46218893Sdim char *strsize, *gen, *prime; 47193323Sed 48193323Sed cp = line; 49234353Sdim arg = strdelim(&cp); 50193323Sed /* Ignore leading whitespace */ 51193323Sed if (*arg == '\0') 52193323Sed arg = strdelim(&cp); 53193323Sed if (!arg || !*arg || *arg == '#') 54193323Sed return 0; 55193323Sed 56193323Sed /* time */ 57193323Sed if (cp == NULL || *arg == '\0') 58193323Sed goto fail; 59193323Sed arg = strsep(&cp, " "); /* type */ 60193323Sed if (cp == NULL || *arg == '\0') 61193323Sed goto fail; 62193323Sed arg = strsep(&cp, " "); /* tests */ 63193323Sed if (cp == NULL || *arg == '\0') 64193323Sed goto fail; 65193323Sed arg = strsep(&cp, " "); /* tries */ 66193323Sed if (cp == NULL || *arg == '\0') 67193323Sed goto fail; 68218893Sdim strsize = strsep(&cp, " "); /* size */ 69193323Sed if (cp == NULL || *strsize == '\0' || 70193323Sed (dhg->size = atoi(strsize)) == 0) 71193323Sed goto fail; 72208599Srdivacky /* The whole group is one bit larger */ 73193323Sed dhg->size++; 74193323Sed gen = strsep(&cp, " "); /* gen */ 75193323Sed if (cp == NULL || *gen == '\0') 76193323Sed goto fail; 77198892Srdivacky prime = strsep(&cp, " "); /* prime */ 78193323Sed if (cp != NULL || *prime == '\0') 79193323Sed goto fail; 80198892Srdivacky 81193323Sed if ((dhg->g = BN_new()) == NULL) 82218893Sdim fatal("parse_prime: BN_new failed"); 83208599Srdivacky if ((dhg->p = BN_new()) == NULL) 84193323Sed fatal("parse_prime: BN_new failed"); 85193323Sed if (BN_hex2bn(&dhg->g, gen) == 0) 86193323Sed goto failclean; 87234353Sdim 88193323Sed if (BN_hex2bn(&dhg->p, prime) == 0) 89193323Sed goto failclean; 90193323Sed 91234353Sdim if (BN_num_bits(dhg->p) != dhg->size) 92193323Sed goto failclean; 93198892Srdivacky 94193323Sed if (BN_is_zero(dhg->g) || BN_is_one(dhg->g)) 95198892Srdivacky goto failclean; 96193323Sed 97193323Sed return (1); 98193323Sed 99193323Sed failclean: 100193323Sed BN_clear_free(dhg->g); 101193323Sed BN_clear_free(dhg->p); 102193323Sed fail: 103193323Sed error("Bad prime description in line %d", linenum); 104193323Sed return (0); 105193323Sed} 106218893Sdim 107193323SedDH * 108193323Sedchoose_dh(int min, int wantbits, int max) 109218893Sdim{ 110193323Sed FILE *f; 111193323Sed char line[4096]; 112193323Sed int best, bestcount, which; 113193323Sed int linenum; 114193323Sed struct dhgroup dhg; 115193323Sed 116193323Sed if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 117193323Sed (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 118208599Srdivacky logit("WARNING: %s does not exist, using fixed modulus", 119208599Srdivacky _PATH_DH_MODULI); 120208599Srdivacky return (dh_new_group14()); 121208599Srdivacky } 122210299Sed 123208599Srdivacky linenum = 0; 124208599Srdivacky best = bestcount = 0; 125208599Srdivacky while (fgets(line, sizeof(line), f)) { 126208599Srdivacky linenum++; 127208599Srdivacky if (!parse_prime(linenum, line, &dhg)) 128208599Srdivacky continue; 129208599Srdivacky BN_clear_free(dhg.g); 130208599Srdivacky BN_clear_free(dhg.p); 131208599Srdivacky 132208599Srdivacky if (dhg.size > max || dhg.size < min) 133208599Srdivacky continue; 134208599Srdivacky 135208599Srdivacky if ((dhg.size > wantbits && dhg.size < best) || 136208599Srdivacky (dhg.size > best && best < wantbits)) { 137208599Srdivacky best = dhg.size; 138208599Srdivacky bestcount = 0; 139208599Srdivacky } 140218893Sdim if (dhg.size == best) 141218893Sdim bestcount++; 142218893Sdim } 143218893Sdim rewind(f); 144218893Sdim 145218893Sdim if (bestcount == 0) { 146218893Sdim fclose(f); 147218893Sdim logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 148218893Sdim return (dh_new_group14()); 149218893Sdim } 150218893Sdim 151218893Sdim linenum = 0; 152218893Sdim which = arc4random() % bestcount; 153 while (fgets(line, sizeof(line), f)) { 154 if (!parse_prime(linenum, line, &dhg)) 155 continue; 156 if ((dhg.size > max || dhg.size < min) || 157 dhg.size != best || 158 linenum++ != which) { 159 BN_clear_free(dhg.g); 160 BN_clear_free(dhg.p); 161 continue; 162 } 163 break; 164 } 165 fclose(f); 166 if (linenum != which+1) 167 fatal("WARNING: line %d disappeared in %s, giving up", 168 which, _PATH_DH_PRIMES); 169 170 return (dh_new_group(dhg.g, dhg.p)); 171} 172 173/* diffie-hellman-groupN-sha1 */ 174 175int 176dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 177{ 178 int i; 179 int n = BN_num_bits(dh_pub); 180 int bits_set = 0; 181 182 if (dh_pub->neg) { 183 logit("invalid public DH value: negativ"); 184 return 0; 185 } 186 for (i = 0; i <= n; i++) 187 if (BN_is_bit_set(dh_pub, i)) 188 bits_set++; 189 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 190 191 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 192 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 193 return 1; 194 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 195 return 0; 196} 197 198void 199dh_gen_key(DH *dh, int need) 200{ 201 int i, bits_set, tries = 0; 202 203 if (dh->p == NULL) 204 fatal("dh_gen_key: dh->p == NULL"); 205 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 206 fatal("dh_gen_key: group too small: %d (2*need %d)", 207 BN_num_bits(dh->p), 2*need); 208 do { 209 if (dh->priv_key != NULL) 210 BN_clear_free(dh->priv_key); 211 if ((dh->priv_key = BN_new()) == NULL) 212 fatal("dh_gen_key: BN_new failed"); 213 /* generate a 2*need bits random private exponent */ 214 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 215 fatal("dh_gen_key: BN_rand failed"); 216 if (DH_generate_key(dh) == 0) 217 fatal("DH_generate_key"); 218 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 219 if (BN_is_bit_set(dh->priv_key, i)) 220 bits_set++; 221 debug2("dh_gen_key: priv key bits set: %d/%d", 222 bits_set, BN_num_bits(dh->priv_key)); 223 if (tries++ > 10) 224 fatal("dh_gen_key: too many bad keys: giving up"); 225 } while (!dh_pub_is_valid(dh, dh->pub_key)); 226} 227 228DH * 229dh_new_group_asc(const char *gen, const char *modulus) 230{ 231 DH *dh; 232 233 if ((dh = DH_new()) == NULL) 234 fatal("dh_new_group_asc: DH_new"); 235 236 if (BN_hex2bn(&dh->p, modulus) == 0) 237 fatal("BN_hex2bn p"); 238 if (BN_hex2bn(&dh->g, gen) == 0) 239 fatal("BN_hex2bn g"); 240 241 return (dh); 242} 243 244/* 245 * This just returns the group, we still need to generate the exchange 246 * value. 247 */ 248 249DH * 250dh_new_group(BIGNUM *gen, BIGNUM *modulus) 251{ 252 DH *dh; 253 254 if ((dh = DH_new()) == NULL) 255 fatal("dh_new_group: DH_new"); 256 dh->p = modulus; 257 dh->g = gen; 258 259 return (dh); 260} 261 262DH * 263dh_new_group1(void) 264{ 265 static char *gen = "2", *group1 = 266 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 267 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 268 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 269 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 270 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 271 "FFFFFFFF" "FFFFFFFF"; 272 273 return (dh_new_group_asc(gen, group1)); 274} 275 276DH * 277dh_new_group14(void) 278{ 279 static char *gen = "2", *group14 = 280 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 281 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 282 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 283 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 284 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 285 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 286 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 287 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 288 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 289 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 290 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 291 292 return (dh_new_group_asc(gen, group14)); 293} 294 295/* 296 * Estimates the group order for a Diffie-Hellman group that has an 297 * attack complexity approximately the same as O(2**bits). Estimate 298 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 299 */ 300 301int 302dh_estimate(int bits) 303{ 304 305 if (bits <= 128) 306 return (1024); /* O(2**86) */ 307 if (bits <= 192) 308 return (2048); /* O(2**116) */ 309 return (4096); /* O(2**156) */ 310} 311