dh.c

   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"
  26
  27 #include "xmalloc.h"
  28
  29 #include <openssl/bn.h>
  30 #include <openssl/dh.h>
  31 #include <openssl/evp.h>
  32
  33 #include "buffer.h"
  34 #include "cipher.h"
  35 #include "kex.h"
  36 #include "dh.h"
  37 #include "pathnames.h"
  38 #include "log.h"
  39 #include "misc.h"
  40
  41 static int
  42 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  43 {
  44         char *cp, *arg;
  45         char *strsize, *gen, *prime;
  46
  47         cp = line;
  48         arg = strdelim(&cp);
  49         /* Ignore leading whitespace */
  50         if (*arg == '\0')
  51                 arg = strdelim(&cp);
  52         if (!arg || !*arg || *arg == '#')
  53                 return 0;
  54
  55         /* time */
  56         if (cp == NULL || *arg == '\0')
  57                 goto fail;
  58         arg = strsep(&cp, " "); /* type */
  59         if (cp == NULL || *arg == '\0')
  60                 goto fail;
  61         arg = strsep(&cp, " "); /* tests */
  62         if (cp == NULL || *arg == '\0')
  63                 goto fail;
  64         arg = strsep(&cp, " "); /* tries */
  65         if (cp == NULL || *arg == '\0')
  66                 goto fail;
  67         strsize = strsep(&cp, " "); /* size */
  68         if (cp == NULL || *strsize == '\0' ||
  69             (dhg->size = atoi(strsize)) == 0)
  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
 181         if (dh_pub->neg) {
 182                 logit("invalid public DH value: negativ");
 183                 return 0;
 184         }
 185         for (i = 0; i <= n; i++)
 186                 if (BN_is_bit_set(dh_pub, i))
 187                         bits_set++;
 188         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 189
 190         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 191         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 192                 return 1;
 193         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 194         return 0;
 195 }
 196
 197 void
 198 dh_gen_key(DH *dh, int need)
 199 {
 200         int i, bits_set, tries = 0;
 201
 202         if (dh->p == NULL)
 203                 fatal("dh_gen_key: dh->p == NULL");
 204         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 205                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 206                     BN_num_bits(dh->p), 2*need);
 207         do {
 208                 if (dh->priv_key != NULL)
 209                         BN_clear_free(dh->priv_key);
 210                 if ((dh->priv_key = BN_new()) == NULL)
 211                         fatal("dh_gen_key: BN_new failed");
 212                 /* generate a 2*need bits random private exponent */
 213                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 214                         fatal("dh_gen_key: BN_rand failed");
 215                 if (DH_generate_key(dh) == 0)
 216                         fatal("DH_generate_key");
 217                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 218                         if (BN_is_bit_set(dh->priv_key, i))
 219                                 bits_set++;
 220                 debug2("dh_gen_key: priv key bits set: %d/%d",
 221                     bits_set, BN_num_bits(dh->priv_key));
 222                 if (tries++ > 10)
 223                         fatal("dh_gen_key: too many bad keys: giving up");
 224         } while (!dh_pub_is_valid(dh, dh->pub_key));
 225 }
 226
 227 DH *
 228 dh_new_group_asc(const char *gen, const char *modulus)
 229 {
 230         DH *dh;
 231
 232         if ((dh = DH_new()) == NULL)
 233                 fatal("dh_new_group_asc: DH_new");
 234
 235         if (BN_hex2bn(&dh->p, modulus) == 0)
 236                 fatal("BN_hex2bn p");
 237         if (BN_hex2bn(&dh->g, gen) == 0)
 238                 fatal("BN_hex2bn g");
 239
 240         return (dh);
 241 }
 242
 243 /*
 244  * This just returns the group, we still need to generate the exchange
 245  * value.
 246  */
 247
 248 DH *
 249 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 250 {
 251         DH *dh;
 252
 253         if ((dh = DH_new()) == NULL)
 254                 fatal("dh_new_group: DH_new");
 255         dh->p = modulus;
 256         dh->g = gen;
 257
 258         return (dh);
 259 }
 260
 261 DH *
 262 dh_new_group1(void)
 263 {
 264         static char *gen = "2", *group1 =
 265             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 266             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 267             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 268             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 269             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 270             "FFFFFFFF" "FFFFFFFF";
 271
 272         return (dh_new_group_asc(gen, group1));
 273 }
 274
 275 DH *
 276 dh_new_group14(void)
 277 {
 278         static char *gen = "2", *group14 =
 279             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 280             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 281             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 282             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 283             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 284             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 285             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 286             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 287             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 288             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 289             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 290
 291         return (dh_new_group_asc(gen, group14));
 292 }
 293
 294 /*
 295  * Estimates the group order for a Diffie-Hellman group that has an
 296  * attack complexity approximately the same as O(2**bits).  Estimate
 297  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 298  */
 299
 300 int
 301 dh_estimate(int bits)
 302 {
 303
 304         if (bits <= 128)
 305                 return (1024);  /* O(2**86) */
 306         if (bits <= 192)
 307                 return (2048);  /* O(2**116) */
 308         return (4096);          /* O(2**156) */
 309 }