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 RCSID("$OpenBSD: dh.c,v 1.20 2002/03/06 00:20:54 markus Exp $");
  27
  28 #include "xmalloc.h"
  29
  30 #include <openssl/bn.h>
  31 #include <openssl/dh.h>
  32 #include <openssl/evp.h>
  33 #include <openssl/err.h>
  34
  35 #include "buffer.h"
  36 #include "cipher.h"
  37 #include "kex.h"
  38 #include "dh.h"
  39 #include "pathnames.h"
  40 #include "log.h"
  41 #include "misc.h"
  42
  43 static int
  44 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  45 {
  46         char *cp, *arg;
  47         char *strsize, *gen, *prime;
  48
  49         cp = line;
  50         arg = strdelim(&cp);
  51         /* Ignore leading whitespace */
  52         if (*arg == '\0')
  53                 arg = strdelim(&cp);
  54         if (!*arg || *arg == '#')
  55                 return 0;
  56
  57         /* time */
  58         if (cp == NULL || *arg == '\0')
  59                 goto fail;
  60         arg = strsep(&cp, " "); /* type */
  61         if (cp == NULL || *arg == '\0')
  62                 goto fail;
  63         arg = strsep(&cp, " "); /* tests */
  64         if (cp == NULL || *arg == '\0')
  65                 goto fail;
  66         arg = strsep(&cp, " "); /* tries */
  67         if (cp == NULL || *arg == '\0')
  68                 goto fail;
  69         strsize = strsep(&cp, " "); /* size */
  70         if (cp == NULL || *strsize == '\0' ||
  71             (dhg->size = atoi(strsize)) == 0)
  72                 goto fail;
  73         /* The whole group is one bit larger */
  74         dhg->size++;
  75         gen = strsep(&cp, " "); /* gen */
  76         if (cp == NULL || *gen == '\0')
  77                 goto fail;
  78         prime = strsep(&cp, " "); /* prime */
  79         if (cp != NULL || *prime == '\0')
  80                 goto fail;
  81
  82         if ((dhg->g = BN_new()) == NULL)
  83                 fatal("parse_prime: BN_new failed");
  84         if ((dhg->p = BN_new()) == NULL)
  85                 fatal("parse_prime: BN_new failed");
  86         if (BN_hex2bn(&dhg->g, gen) == 0)
  87                 goto failclean;
  88
  89         if (BN_hex2bn(&dhg->p, prime) == 0)
  90                 goto failclean;
  91
  92         if (BN_num_bits(dhg->p) != dhg->size)
  93                 goto failclean;
  94
  95         return (1);
  96
  97  failclean:
  98         BN_clear_free(dhg->g);
  99         BN_clear_free(dhg->p);
 100  fail:
 101         error("Bad prime description in line %d", linenum);
 102         return (0);
 103 }
 104
 105 DH *
 106 choose_dh(int min, int wantbits, int max)
 107 {
 108         FILE *f;
 109         char line[2048];
 110         int best, bestcount, which;
 111         int linenum;
 112         struct dhgroup dhg;
 113
 114         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 115             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 116                 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
 117                 return (dh_new_group1());
 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                 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 145                 return (NULL);
 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-group1-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
 179         if (dh_pub->neg) {
 180                 log("invalid public DH value: negativ");
 181                 return 0;
 182         }
 183         for (i = 0; i <= n; i++)
 184                 if (BN_is_bit_set(dh_pub, i))
 185                         bits_set++;
 186         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 187
 188         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 189         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 190                 return 1;
 191         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 192         return 0;
 193 }
 194
 195 void
 196 dh_gen_key(DH *dh, int need)
 197 {
 198         int i, bits_set = 0, tries = 0;
 199
 200         if (dh->p == NULL)
 201                 fatal("dh_gen_key: dh->p == NULL");
 202         if (2*need >= BN_num_bits(dh->p))
 203                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 204                     BN_num_bits(dh->p), 2*need);
 205         do {
 206                 if (dh->priv_key != NULL)
 207                         BN_clear_free(dh->priv_key);
 208                 if ((dh->priv_key = BN_new()) == NULL)
 209                         fatal("dh_gen_key: BN_new failed");
 210                 /* generate a 2*need bits random private exponent */
 211                 if (!BN_rand(dh->priv_key, 2*need, 0, 0)) {
 212                         int ecode = ERR_get_error();
 213                         fatal("dh_gen_key: BN_rand failed: %s", ERR_error_string(ecode, NULL));
 214                 }
 215                 if (DH_generate_key(dh) == 0)
 216                         fatal("DH_generate_key");
 217                 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
 218                         if (BN_is_bit_set(dh->priv_key, i))
 219                                 bits_set++;
 220                 debug("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 /*
 276  * Estimates the group order for a Diffie-Hellman group that has an
 277  * attack complexity approximately the same as O(2**bits).  Estimate
 278  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 279  */
 280
 281 int
 282 dh_estimate(int bits)
 283 {
 284
 285         if (bits < 64)
 286                 return (512);   /* O(2**63) */
 287         if (bits < 128)
 288                 return (1024);  /* O(2**86) */
 289         if (bits < 192)
 290                 return (2048);  /* O(2**116) */
 291         return (4096);          /* O(2**156) */
 292 }