dh.c

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