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.13 2001/04/04 23:09:17 markus Exp $");
  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 int
  43 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  44 {
  45         char *cp, *arg;
  46         char *strsize, *gen, *prime;
  47
  48         cp = line;
  49         arg = strdelim(&cp);
  50         /* Ignore leading whitespace */
  51         if (*arg == '\0')
  52                 arg = strdelim(&cp);
  53         if (!*arg || *arg == '#')
  54                 return 0;
  55
  56         /* time */
  57         if (cp == NULL || *arg == '\0')
  58                 goto fail;
  59         arg = strsep(&cp, " "); /* type */
  60         if (cp == NULL || *arg == '\0')
  61                 goto fail;
  62         arg = strsep(&cp, " "); /* tests */
  63         if (cp == NULL || *arg == '\0')
  64                 goto fail;
  65         arg = strsep(&cp, " "); /* tries */
  66         if (cp == NULL || *arg == '\0')
  67                 goto fail;
  68         strsize = strsep(&cp, " "); /* size */
  69         if (cp == NULL || *strsize == '\0' ||
  70             (dhg->size = atoi(strsize)) == 0)
  71                 goto fail;
  72         /* The whole group is one bit larger */
  73         dhg->size++;
  74         gen = strsep(&cp, " "); /* gen */
  75         if (cp == NULL || *gen == '\0')
  76                 goto fail;
  77         prime = strsep(&cp, " "); /* prime */
  78         if (cp != NULL || *prime == '\0')
  79                 goto fail;
  80
  81         dhg->g = BN_new();
  82         dhg->p = BN_new();
  83         if (BN_hex2bn(&dhg->g, gen) < 0)
  84                 goto failclean;
  85
  86         if (BN_hex2bn(&dhg->p, prime) < 0)
  87                 goto failclean;
  88
  89         if (BN_num_bits(dhg->p) != dhg->size)
  90                 goto failclean;
  91
  92         return (1);
  93
  94  failclean:
  95         BN_free(dhg->g);
  96         BN_free(dhg->p);
  97  fail:
  98         error("Bad prime description in line %d", linenum);
  99         return (0);
 100 }
 101
 102 DH *
 103 choose_dh(int min, int wantbits, int max)
 104 {
 105         FILE *f;
 106         char line[1024];
 107         int best, bestcount, which;
 108         int linenum;
 109         struct dhgroup dhg;
 110
 111         f = fopen(_PATH_DH_PRIMES, "r");
 112         if (!f) {
 113                 log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES);
 114                 return (dh_new_group1());
 115         }
 116
 117         linenum = 0;
 118         best = bestcount = 0;
 119         while (fgets(line, sizeof(line), f)) {
 120                 linenum++;
 121                 if (!parse_prime(linenum, line, &dhg))
 122                         continue;
 123                 BN_free(dhg.g);
 124                 BN_free(dhg.p);
 125
 126                 if (dhg.size > max || dhg.size < min)
 127                         continue;
 128
 129                 if ((dhg.size > wantbits && dhg.size < best) ||
 130                     (dhg.size > best && best < wantbits)) {
 131                         best = dhg.size;
 132                         bestcount = 0;
 133                 }
 134                 if (dhg.size == best)
 135                         bestcount++;
 136         }
 137         fclose (f);
 138
 139         if (bestcount == 0) {
 140                 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 141                 return (NULL);
 142         }
 143
 144         f = fopen(_PATH_DH_PRIMES, "r");
 145         if (!f) {
 146                 fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES);
 147         }
 148
 149         linenum = 0;
 150         which = arc4random() % bestcount;
 151         while (fgets(line, sizeof(line), f)) {
 152                 if (!parse_prime(linenum, line, &dhg))
 153                         continue;
 154                 if ((dhg.size > max || dhg.size < min) ||
 155                     dhg.size != best ||
 156                     linenum++ != which) {
 157                         BN_free(dhg.g);
 158                         BN_free(dhg.p);
 159                         continue;
 160                 }
 161                 break;
 162         }
 163         fclose(f);
 164         if (linenum != which+1)
 165                 fatal("WARNING: line %d disappeared in %s, giving up",
 166                     which, _PATH_DH_PRIMES);
 167
 168         return (dh_new_group(dhg.g, dhg.p));
 169 }
 170
 171 /* diffie-hellman-group1-sha1 */
 172
 173 int
 174 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 175 {
 176         int i;
 177         int n = BN_num_bits(dh_pub);
 178         int bits_set = 0;
 179
 180         if (dh_pub->neg) {
 181                 log("invalid public DH value: negativ");
 182                 return 0;
 183         }
 184         for (i = 0; i <= n; i++)
 185                 if (BN_is_bit_set(dh_pub, i))
 186                         bits_set++;
 187         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 188
 189         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 190         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 191                 return 1;
 192         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 193         return 0;
 194 }
 195
 196 void
 197 dh_gen_key(DH *dh, int need)
 198 {
 199         int i, bits_set = 0, tries = 0;
 200
 201         if (dh->p == NULL)
 202                 fatal("dh_gen_key: dh->p == NULL");
 203         if (2*need >= BN_num_bits(dh->p))
 204                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 205                     BN_num_bits(dh->p), 2*need);
 206         do {
 207                 if (dh->priv_key != NULL)
 208                         BN_free(dh->priv_key);
 209                 dh->priv_key = BN_new();
 210                 if (dh->priv_key == 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; 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         int ret;
 232
 233         dh = DH_new();
 234         if (dh == NULL)
 235                 fatal("DH_new");
 236
 237         if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
 238                 fatal("BN_hex2bn p");
 239         if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
 240                 fatal("BN_hex2bn g");
 241
 242         return (dh);
 243 }
 244
 245 /*
 246  * This just returns the group, we still need to generate the exchange
 247  * value.
 248  */
 249
 250 DH *
 251 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 252 {
 253         DH *dh;
 254
 255         dh = DH_new();
 256         if (dh == NULL)
 257                 fatal("DH_new");
 258         dh->p = modulus;
 259         dh->g = gen;
 260
 261         return (dh);
 262 }
 263
 264 DH *
 265 dh_new_group1(void)
 266 {
 267         static char *gen = "2", *group1 =
 268             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 269             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 270             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 271             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 272             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 273             "FFFFFFFF" "FFFFFFFF";
 274
 275         return (dh_new_group_asc(gen, group1));
 276 }
 277
 278 /*
 279  * Estimates the group order for a Diffie-Hellman group that has an
 280  * attack complexity approximately the same as O(2**bits).  Estimate
 281  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 282  */
 283
 284 int
 285 dh_estimate(int bits)
 286 {
 287
 288         if (bits < 64)
 289                 return (512);   /* O(2**63) */
 290         if (bits < 128)
 291                 return (1024);  /* O(2**86) */
 292         if (bits < 192)
 293                 return (2048);  /* O(2**116) */
 294         return (4096);          /* O(2**156) */
 295 }