crypto/openssh-4/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.31 2004/08/04 10:37:52 djm 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 fixed modulus",
 119                     _PATH_DH_MODULI);
 120                 return (dh_new_group14());
 121         }
 122
 123         linenum = 0;
 124         best = bestcount = 0;
 125         while (fgets(line, sizeof(line), f)) {
 126                 linenum++;
 127                 if (!parse_prime(linenum, line, &dhg))
 128                         continue;
 129                 BN_clear_free(dhg.g);
 130                 BN_clear_free(dhg.p);
 131
 132                 if (dhg.size > max || dhg.size < min)
 133                         continue;
 134
 135                 if ((dhg.size > wantbits && dhg.size < best) ||
 136                     (dhg.size > best && best < wantbits)) {
 137                         best = dhg.size;
 138                         bestcount = 0;
 139                 }
 140                 if (dhg.size == best)
 141                         bestcount++;
 142         }
 143         rewind(f);
 144
 145         if (bestcount == 0) {
 146                 fclose(f);
 147                 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 148                 return (dh_new_group14());
 149         }
 150
 151         linenum = 0;
 152         which = arc4random() % bestcount;
 153         while (fgets(line, sizeof(line), f)) {
 154                 if (!parse_prime(linenum, line, &dhg))
 155                         continue;
 156                 if ((dhg.size > max || dhg.size < min) ||
 157                     dhg.size != best ||
 158                     linenum++ != which) {
 159                         BN_clear_free(dhg.g);
 160                         BN_clear_free(dhg.p);
 161                         continue;
 162                 }
 163                 break;
 164         }
 165         fclose(f);
 166         if (linenum != which+1)
 167                 fatal("WARNING: line %d disappeared in %s, giving up",
 168                     which, _PATH_DH_PRIMES);
 169
 170         return (dh_new_group(dhg.g, dhg.p));
 171 }
 172
 173 /* diffie-hellman-groupN-sha1 */
 174
 175 int
 176 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 177 {
 178         int i;
 179         int n = BN_num_bits(dh_pub);
 180         int bits_set = 0;
 181
 182         if (dh_pub->neg) {
 183                 logit("invalid public DH value: negativ");
 184                 return 0;
 185         }
 186         for (i = 0; i <= n; i++)
 187                 if (BN_is_bit_set(dh_pub, i))
 188                         bits_set++;
 189         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 190
 191         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 192         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 193                 return 1;
 194         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 195         return 0;
 196 }
 197
 198 void
 199 dh_gen_key(DH *dh, int need)
 200 {
 201         int i, bits_set, tries = 0;
 202
 203         if (dh->p == NULL)
 204                 fatal("dh_gen_key: dh->p == NULL");
 205         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 206                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 207                     BN_num_bits(dh->p), 2*need);
 208         do {
 209                 if (dh->priv_key != NULL)
 210                         BN_clear_free(dh->priv_key);
 211                 if ((dh->priv_key = BN_new()) == NULL)
 212                         fatal("dh_gen_key: BN_new failed");
 213                 /* generate a 2*need bits random private exponent */
 214                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 215                         fatal("dh_gen_key: BN_rand failed");
 216                 if (DH_generate_key(dh) == 0)
 217                         fatal("DH_generate_key");
 218                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 219                         if (BN_is_bit_set(dh->priv_key, i))
 220                                 bits_set++;
 221                 debug2("dh_gen_key: priv key bits set: %d/%d",
 222                     bits_set, BN_num_bits(dh->priv_key));
 223                 if (tries++ > 10)
 224                         fatal("dh_gen_key: too many bad keys: giving up");
 225         } while (!dh_pub_is_valid(dh, dh->pub_key));
 226 }
 227
 228 DH *
 229 dh_new_group_asc(const char *gen, const char *modulus)
 230 {
 231         DH *dh;
 232
 233         if ((dh = DH_new()) == NULL)
 234                 fatal("dh_new_group_asc: 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         if ((dh = DH_new()) == NULL)
 255                 fatal("dh_new_group: DH_new");
 256         dh->p = modulus;
 257         dh->g = gen;
 258
 259         return (dh);
 260 }
 261
 262 DH *
 263 dh_new_group1(void)
 264 {
 265         static char *gen = "2", *group1 =
 266             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 267             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 268             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 269             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 270             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 271             "FFFFFFFF" "FFFFFFFF";
 272
 273         return (dh_new_group_asc(gen, group1));
 274 }
 275
 276 DH *
 277 dh_new_group14(void)
 278 {
 279         static char *gen = "2", *group14 =
 280             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 281             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 282             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 283             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 284             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 285             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 286             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 287             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 288             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 289             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 290             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 291
 292         return (dh_new_group_asc(gen, group14));
 293 }
 294
 295 /*
 296  * Estimates the group order for a Diffie-Hellman group that has an
 297  * attack complexity approximately the same as O(2**bits).  Estimate
 298  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 299  */
 300
 301 int
 302 dh_estimate(int bits)
 303 {
 304
 305         if (bits <= 128)
 306                 return (1024);  /* O(2**86) */
 307         if (bits <= 192)
 308                 return (2048);  /* O(2**116) */
 309         return (4096);          /* O(2**156) */
 310 }