dh.c

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