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.14 2001/04/15 08:43:45 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
 232         dh = DH_new();
 233         if (dh == NULL)
 234                 fatal("DH_new");
 235
 236         if (BN_hex2bn(&dh->p, modulus) == 0)
 237                 fatal("BN_hex2bn p");
 238         if (BN_hex2bn(&dh->g, gen) == 0)
 239                 fatal("BN_hex2bn g");
 240
 241         return (dh);
 242 }
 243
 244 /*
 245  * This just returns the group, we still need to generate the exchange
 246  * value.
 247  */
 248
 249 DH *
 250 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 251 {
 252         DH *dh;
 253
 254         dh = DH_new();
 255         if (dh == NULL)
 256                 fatal("DH_new");
 257         dh->p = modulus;
 258         dh->g = gen;
 259
 260         return (dh);
 261 }
 262
 263 DH *
 264 dh_new_group1(void)
 265 {
 266         static char *gen = "2", *group1 =
 267             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 268             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 269             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 270             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 271             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 272             "FFFFFFFF" "FFFFFFFF";
 273
 274         return (dh_new_group_asc(gen, group1));
 275 }
 276
 277 /*
 278  * Estimates the group order for a Diffie-Hellman group that has an
 279  * attack complexity approximately the same as O(2**bits).  Estimate
 280  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 281  */
 282
 283 int
 284 dh_estimate(int bits)
 285 {
 286
 287         if (bits < 64)
 288                 return (512);   /* O(2**63) */
 289         if (bits < 128)
 290                 return (1024);  /* O(2**86) */
 291         if (bits < 192)
 292                 return (2048);  /* O(2**116) */
 293         return (4096);          /* O(2**156) */
 294 }