crypto/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.22 2002/06/27 08:49:44 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 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         return (1);
  95
  96  failclean:
  97         BN_clear_free(dhg->g);
  98         BN_clear_free(dhg->p);
  99  fail:
 100         error("Bad prime description in line %d", linenum);
 101         return (0);
 102 }
 103
 104 DH *
 105 choose_dh(int min, int wantbits, int max)
 106 {
 107         FILE *f;
 108         char line[2048];
 109         int best, bestcount, which;
 110         int linenum;
 111         struct dhgroup dhg;
 112
 113         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 114             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 115                 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
 116                 return (dh_new_group1());
 117         }
 118
 119         linenum = 0;
 120         best = bestcount = 0;
 121         while (fgets(line, sizeof(line), f)) {
 122                 linenum++;
 123                 if (!parse_prime(linenum, line, &dhg))
 124                         continue;
 125                 BN_clear_free(dhg.g);
 126                 BN_clear_free(dhg.p);
 127
 128                 if (dhg.size > max || dhg.size < min)
 129                         continue;
 130
 131                 if ((dhg.size > wantbits && dhg.size < best) ||
 132                     (dhg.size > best && best < wantbits)) {
 133                         best = dhg.size;
 134                         bestcount = 0;
 135                 }
 136                 if (dhg.size == best)
 137                         bestcount++;
 138         }
 139         rewind(f);
 140
 141         if (bestcount == 0) {
 142                 fclose(f);
 143                 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 144                 return (NULL);
 145         }
 146
 147         linenum = 0;
 148         which = arc4random() % bestcount;
 149         while (fgets(line, sizeof(line), f)) {
 150                 if (!parse_prime(linenum, line, &dhg))
 151                         continue;
 152                 if ((dhg.size > max || dhg.size < min) ||
 153                     dhg.size != best ||
 154                     linenum++ != which) {
 155                         BN_clear_free(dhg.g);
 156                         BN_clear_free(dhg.p);
 157                         continue;
 158                 }
 159                 break;
 160         }
 161         fclose(f);
 162         if (linenum != which+1)
 163                 fatal("WARNING: line %d disappeared in %s, giving up",
 164                     which, _PATH_DH_PRIMES);
 165
 166         return (dh_new_group(dhg.g, dhg.p));
 167 }
 168
 169 /* diffie-hellman-group1-sha1 */
 170
 171 int
 172 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 173 {
 174         int i;
 175         int n = BN_num_bits(dh_pub);
 176         int bits_set = 0;
 177
 178         if (dh_pub->neg) {
 179                 log("invalid public DH value: negativ");
 180                 return 0;
 181         }
 182         for (i = 0; i <= n; i++)
 183                 if (BN_is_bit_set(dh_pub, i))
 184                         bits_set++;
 185         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 186
 187         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 188         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 189                 return 1;
 190         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 191         return 0;
 192 }
 193
 194 void
 195 dh_gen_key(DH *dh, int need)
 196 {
 197         int i, bits_set = 0, tries = 0;
 198
 199         if (dh->p == NULL)
 200                 fatal("dh_gen_key: dh->p == NULL");
 201         if (2*need >= BN_num_bits(dh->p))
 202                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 203                     BN_num_bits(dh->p), 2*need);
 204         do {
 205                 if (dh->priv_key != NULL)
 206                         BN_clear_free(dh->priv_key);
 207                 if ((dh->priv_key = BN_new()) == NULL)
 208                         fatal("dh_gen_key: BN_new failed");
 209                 /* generate a 2*need bits random private exponent */
 210                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 211                         fatal("dh_gen_key: BN_rand failed");
 212                 if (DH_generate_key(dh) == 0)
 213                         fatal("DH_generate_key");
 214                 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
 215                         if (BN_is_bit_set(dh->priv_key, i))
 216                                 bits_set++;
 217                 debug("dh_gen_key: priv key bits set: %d/%d",
 218                     bits_set, BN_num_bits(dh->priv_key));
 219                 if (tries++ > 10)
 220                         fatal("dh_gen_key: too many bad keys: giving up");
 221         } while (!dh_pub_is_valid(dh, dh->pub_key));
 222 }
 223
 224 DH *
 225 dh_new_group_asc(const char *gen, const char *modulus)
 226 {
 227         DH *dh;
 228
 229         if ((dh = DH_new()) == NULL)
 230                 fatal("dh_new_group_asc: 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         if ((dh = DH_new()) == NULL)
 251                 fatal("dh_new_group: DH_new");
 252         dh->p = modulus;
 253         dh->g = gen;
 254
 255         return (dh);
 256 }
 257
 258 DH *
 259 dh_new_group1(void)
 260 {
 261         static char *gen = "2", *group1 =
 262             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 263             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 264             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 265             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 266             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 267             "FFFFFFFF" "FFFFFFFF";
 268
 269         return (dh_new_group_asc(gen, group1));
 270 }
 271
 272 /*
 273  * Estimates the group order for a Diffie-Hellman group that has an
 274  * attack complexity approximately the same as O(2**bits).  Estimate
 275  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 276  */
 277
 278 int
 279 dh_estimate(int bits)
 280 {
 281
 282         if (bits < 64)
 283                 return (512);   /* O(2**63) */
 284         if (bits < 128)
 285                 return (1024);  /* O(2**86) */
 286         if (bits < 192)
 287                 return (2048);  /* O(2**116) */
 288         return (4096);          /* O(2**156) */
 289 }