dh.c revision 92555
1/* 2 * Copyright (c) 2000 Niels Provos. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 17 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23 */ 24 25#include "includes.h" 26RCSID("$OpenBSD: dh.c,v 1.21 2002/03/06 00:23:27 markus Exp $"); 27 28#include "xmalloc.h" 29 30#include <openssl/bn.h> 31#include <openssl/dh.h> 32#include <openssl/evp.h> 33 34#include "buffer.h" 35#include "cipher.h" 36#include "kex.h" 37#include "dh.h" 38#include "pathnames.h" 39#include "log.h" 40#include "misc.h" 41 42static int 43parse_prime(int linenum, char *line, struct dhgroup *dhg) 44{ 45 char *cp, *arg; 46 char *strsize, *gen, *prime; 47 48 cp = line; 49 arg = strdelim(&cp); 50 /* Ignore leading whitespace */ 51 if (*arg == '\0') 52 arg = strdelim(&cp); 53 if (!*arg || *arg == '#') 54 return 0; 55 56 /* time */ 57 if (cp == NULL || *arg == '\0') 58 goto fail; 59 arg = strsep(&cp, " "); /* type */ 60 if (cp == NULL || *arg == '\0') 61 goto fail; 62 arg = strsep(&cp, " "); /* tests */ 63 if (cp == NULL || *arg == '\0') 64 goto fail; 65 arg = strsep(&cp, " "); /* tries */ 66 if (cp == NULL || *arg == '\0') 67 goto fail; 68 strsize = strsep(&cp, " "); /* size */ 69 if (cp == NULL || *strsize == '\0' || 70 (dhg->size = atoi(strsize)) == 0) 71 goto fail; 72 /* The whole group is one bit larger */ 73 dhg->size++; 74 gen = strsep(&cp, " "); /* gen */ 75 if (cp == NULL || *gen == '\0') 76 goto fail; 77 prime = strsep(&cp, " "); /* prime */ 78 if (cp != NULL || *prime == '\0') 79 goto fail; 80 81 if ((dhg->g = BN_new()) == NULL) 82 fatal("parse_prime: BN_new failed"); 83 if ((dhg->p = BN_new()) == NULL) 84 fatal("parse_prime: BN_new failed"); 85 if (BN_hex2bn(&dhg->g, gen) == 0) 86 goto failclean; 87 88 if (BN_hex2bn(&dhg->p, prime) == 0) 89 goto failclean; 90 91 if (BN_num_bits(dhg->p) != dhg->size) 92 goto failclean; 93 94 return (1); 95 96 failclean: 97 BN_clear_free(dhg->g); 98 BN_clear_free(dhg->p); 99 fail: 100 error("Bad prime description in line %d", linenum); 101 return (0); 102} 103 104DH * 105choose_dh(int min, int wantbits, int max) 106{ 107 FILE *f; 108 char line[2048]; 109 int best, bestcount, which; 110 int linenum; 111 struct dhgroup dhg; 112 113 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 114 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 115 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 116 return (dh_new_group1()); 117 } 118 119 linenum = 0; 120 best = bestcount = 0; 121 while (fgets(line, sizeof(line), f)) { 122 linenum++; 123 if (!parse_prime(linenum, line, &dhg)) 124 continue; 125 BN_clear_free(dhg.g); 126 BN_clear_free(dhg.p); 127 128 if (dhg.size > max || dhg.size < min) 129 continue; 130 131 if ((dhg.size > wantbits && dhg.size < best) || 132 (dhg.size > best && best < wantbits)) { 133 best = dhg.size; 134 bestcount = 0; 135 } 136 if (dhg.size == best) 137 bestcount++; 138 } 139 rewind(f); 140 141 if (bestcount == 0) { 142 fclose(f); 143 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 144 return (NULL); 145 } 146 147 linenum = 0; 148 which = arc4random() % bestcount; 149 while (fgets(line, sizeof(line), f)) { 150 if (!parse_prime(linenum, line, &dhg)) 151 continue; 152 if ((dhg.size > max || dhg.size < min) || 153 dhg.size != best || 154 linenum++ != which) { 155 BN_clear_free(dhg.g); 156 BN_clear_free(dhg.p); 157 continue; 158 } 159 break; 160 } 161 fclose(f); 162 if (linenum != which+1) 163 fatal("WARNING: line %d disappeared in %s, giving up", 164 which, _PATH_DH_PRIMES); 165 166 return (dh_new_group(dhg.g, dhg.p)); 167} 168 169/* diffie-hellman-group1-sha1 */ 170 171int 172dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 173{ 174 int i; 175 int n = BN_num_bits(dh_pub); 176 int bits_set = 0; 177 178 if (dh_pub->neg) { 179 log("invalid public DH value: negativ"); 180 return 0; 181 } 182 for (i = 0; i <= n; i++) 183 if (BN_is_bit_set(dh_pub, i)) 184 bits_set++; 185 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 186 187 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 188 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 189 return 1; 190 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 191 return 0; 192} 193 194void 195dh_gen_key(DH *dh, int need) 196{ 197 int i, bits_set = 0, tries = 0; 198 199 if (dh->p == NULL) 200 fatal("dh_gen_key: dh->p == NULL"); 201 if (2*need >= BN_num_bits(dh->p)) 202 fatal("dh_gen_key: group too small: %d (2*need %d)", 203 BN_num_bits(dh->p), 2*need); 204 do { 205 if (dh->priv_key != NULL) 206 BN_clear_free(dh->priv_key); 207 if ((dh->priv_key = BN_new()) == NULL) 208 fatal("dh_gen_key: BN_new failed"); 209 /* generate a 2*need bits random private exponent */ 210 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 211 fatal("dh_gen_key: BN_rand failed"); 212 if (DH_generate_key(dh) == 0) 213 fatal("DH_generate_key"); 214 for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 215 if (BN_is_bit_set(dh->priv_key, i)) 216 bits_set++; 217 debug("dh_gen_key: priv key bits set: %d/%d", 218 bits_set, BN_num_bits(dh->priv_key)); 219 if (tries++ > 10) 220 fatal("dh_gen_key: too many bad keys: giving up"); 221 } while (!dh_pub_is_valid(dh, dh->pub_key)); 222} 223 224DH * 225dh_new_group_asc(const char *gen, const char *modulus) 226{ 227 DH *dh; 228 229 if ((dh = DH_new()) == NULL) 230 fatal("dh_new_group_asc: DH_new"); 231 232 if (BN_hex2bn(&dh->p, modulus) == 0) 233 fatal("BN_hex2bn p"); 234 if (BN_hex2bn(&dh->g, gen) == 0) 235 fatal("BN_hex2bn g"); 236 237 return (dh); 238} 239 240/* 241 * This just returns the group, we still need to generate the exchange 242 * value. 243 */ 244 245DH * 246dh_new_group(BIGNUM *gen, BIGNUM *modulus) 247{ 248 DH *dh; 249 250 if ((dh = DH_new()) == NULL) 251 fatal("dh_new_group: DH_new"); 252 dh->p = modulus; 253 dh->g = gen; 254 255 return (dh); 256} 257 258DH * 259dh_new_group1(void) 260{ 261 static char *gen = "2", *group1 = 262 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 263 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 264 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 265 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 266 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 267 "FFFFFFFF" "FFFFFFFF"; 268 269 return (dh_new_group_asc(gen, group1)); 270} 271 272/* 273 * Estimates the group order for a Diffie-Hellman group that has an 274 * attack complexity approximately the same as O(2**bits). Estimate 275 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 276 */ 277 278int 279dh_estimate(int bits) 280{ 281 282 if (bits < 64) 283 return (512); /* O(2**63) */ 284 if (bits < 128) 285 return (1024); /* O(2**86) */ 286 if (bits < 192) 287 return (2048); /* O(2**116) */ 288 return (4096); /* O(2**156) */ 289} 290