openssh/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.17 2001/06/23 15:12:18 itojun 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 static 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[2048];
 107         int best, bestcount, which;
 108         int linenum;
 109         struct dhgroup dhg;
 110
 111         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 112             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 113                 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
 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         rewind(f);
 138
 139         if (bestcount == 0) {
 140                 fclose(f);
 141                 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 142                 return (NULL);
 143         }
 144
 145         linenum = 0;
 146         which = arc4random() % bestcount;
 147         while (fgets(line, sizeof(line), f)) {
 148                 if (!parse_prime(linenum, line, &dhg))
 149                         continue;
 150                 if ((dhg.size > max || dhg.size < min) ||
 151                     dhg.size != best ||
 152                     linenum++ != which) {
 153                         BN_free(dhg.g);
 154                         BN_free(dhg.p);
 155                         continue;
 156                 }
 157                 break;
 158         }
 159         fclose(f);
 160         if (linenum != which+1)
 161                 fatal("WARNING: line %d disappeared in %s, giving up",
 162                     which, _PATH_DH_PRIMES);
 163
 164         return (dh_new_group(dhg.g, dhg.p));
 165 }
 166
 167 /* diffie-hellman-group1-sha1 */
 168
 169 int
 170 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 171 {
 172         int i;
 173         int n = BN_num_bits(dh_pub);
 174         int bits_set = 0;
 175
 176         if (dh_pub->neg) {
 177                 log("invalid public DH value: negativ");
 178                 return 0;
 179         }
 180         for (i = 0; i <= n; i++)
 181                 if (BN_is_bit_set(dh_pub, i))
 182                         bits_set++;
 183         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 184
 185         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 186         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 187                 return 1;
 188         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 189         return 0;
 190 }
 191
 192 void
 193 dh_gen_key(DH *dh, int need)
 194 {
 195         int i, bits_set = 0, tries = 0;
 196
 197         if (dh->p == NULL)
 198                 fatal("dh_gen_key: dh->p == NULL");
 199         if (2*need >= BN_num_bits(dh->p))
 200                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 201                     BN_num_bits(dh->p), 2*need);
 202         do {
 203                 if (dh->priv_key != NULL)
 204                         BN_free(dh->priv_key);
 205                 dh->priv_key = BN_new();
 206                 if (dh->priv_key == NULL)
 207                         fatal("dh_gen_key: BN_new failed");
 208                 /* generate a 2*need bits random private exponent */
 209                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 210                         fatal("dh_gen_key: BN_rand failed");
 211                 if (DH_generate_key(dh) == 0)
 212                         fatal("DH_generate_key");
 213                 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
 214                         if (BN_is_bit_set(dh->priv_key, i))
 215                                 bits_set++;
 216                 debug("dh_gen_key: priv key bits set: %d/%d",
 217                     bits_set, BN_num_bits(dh->priv_key));
 218                 if (tries++ > 10)
 219                         fatal("dh_gen_key: too many bad keys: giving up");
 220         } while (!dh_pub_is_valid(dh, dh->pub_key));
 221 }
 222
 223 DH *
 224 dh_new_group_asc(const char *gen, const char *modulus)
 225 {
 226         DH *dh;
 227
 228         dh = DH_new();
 229         if (dh == NULL)
 230                 fatal("DH_new");
 231
 232         if (BN_hex2bn(&dh->p, modulus) == 0)
 233                 fatal("BN_hex2bn p");
 234         if (BN_hex2bn(&dh->g, gen) == 0)
 235                 fatal("BN_hex2bn g");
 236
 237         return (dh);
 238 }
 239
 240 /*
 241  * This just returns the group, we still need to generate the exchange
 242  * value.
 243  */
 244
 245 DH *
 246 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 247 {
 248         DH *dh;
 249
 250         dh = DH_new();
 251         if (dh == NULL)
 252                 fatal("DH_new");
 253         dh->p = modulus;
 254         dh->g = gen;
 255
 256         return (dh);
 257 }
 258
 259 DH *
 260 dh_new_group1(void)
 261 {
 262         static char *gen = "2", *group1 =
 263             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 264             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 265             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 266             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 267             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 268             "FFFFFFFF" "FFFFFFFF";
 269
 270         return (dh_new_group_asc(gen, group1));
 271 }
 272
 273 /*
 274  * Estimates the group order for a Diffie-Hellman group that has an
 275  * attack complexity approximately the same as O(2**bits).  Estimate
 276  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 277  */
 278
 279 int
 280 dh_estimate(int bits)
 281 {
 282
 283         if (bits < 64)
 284                 return (512);   /* O(2**63) */
 285         if (bits < 128)
 286                 return (1024);  /* O(2**86) */
 287         if (bits < 192)
 288                 return (2048);  /* O(2**116) */
 289         return (4096);          /* O(2**156) */
 290 }