crypto/openssh-3.8.1p1/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.29 2004/02/27 22:49:27 dtucker 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 || *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         if ((dhg->g = BN_new()) == NULL)
  82                 fatal("parse_prime: BN_new failed");
  83         if ((dhg->p = BN_new()) == NULL)
  84                 fatal("parse_prime: BN_new failed");
  85         if (BN_hex2bn(&dhg->g, gen) == 0)
  86                 goto failclean;
  87
  88         if (BN_hex2bn(&dhg->p, prime) == 0)
  89                 goto failclean;
  90
  91         if (BN_num_bits(dhg->p) != dhg->size)
  92                 goto failclean;
  93
  94         if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
  95                 goto failclean;
  96
  97         return (1);
  98
  99  failclean:
 100         BN_clear_free(dhg->g);
 101         BN_clear_free(dhg->p);
 102  fail:
 103         error("Bad prime description in line %d", linenum);
 104         return (0);
 105 }
 106
 107 DH *
 108 choose_dh(int min, int wantbits, int max)
 109 {
 110         FILE *f;
 111         char line[4096];
 112         int best, bestcount, which;
 113         int linenum;
 114         struct dhgroup dhg;
 115
 116         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 117             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 118                 logit("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
 119                 return (dh_new_group1());
 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 (NULL);
 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-group1-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 /*
 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 <= 128)
 286                 return (1024);  /* O(2**86) */
 287         if (bits <= 192)
 288                 return (2048);  /* O(2**116) */
 289         return (4096);          /* O(2**156) */
 290 }