dh.c

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