crypto/openssh-4/dh.c

   1 /* $OpenBSD: dh.c,v 1.42 2006/08/03 03:34:42 deraadt Exp $ */
   2 /*
   3  * Copyright (c) 2000 Niels Provos.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "includes.h"
  27
  28 #include <sys/param.h>
  29
  30 #include <openssl/bn.h>
  31 #include <openssl/dh.h>
  32
  33 #include <stdarg.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include "dh.h"
  39 #include "pathnames.h"
  40 #include "log.h"
  41 #include "misc.h"
  42
  43 static int
  44 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  45 {
  46         char *cp, *arg;
  47         char *strsize, *gen, *prime;
  48         const char *errstr = NULL;
  49
  50         cp = line;
  51         if ((arg = strdelim(&cp)) == NULL)
  52                 return 0;
  53         /* Ignore leading whitespace */
  54         if (*arg == '\0')
  55                 arg = strdelim(&cp);
  56         if (!arg || !*arg || *arg == '#')
  57                 return 0;
  58
  59         /* time */
  60         if (cp == NULL || *arg == '\0')
  61                 goto fail;
  62         arg = strsep(&cp, " "); /* type */
  63         if (cp == NULL || *arg == '\0')
  64                 goto fail;
  65         arg = strsep(&cp, " "); /* tests */
  66         if (cp == NULL || *arg == '\0')
  67                 goto fail;
  68         arg = strsep(&cp, " "); /* tries */
  69         if (cp == NULL || *arg == '\0')
  70                 goto fail;
  71         strsize = strsep(&cp, " "); /* size */
  72         if (cp == NULL || *strsize == '\0' ||
  73             (dhg->size = (u_int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
  74             errstr)
  75                 goto fail;
  76         /* The whole group is one bit larger */
  77         dhg->size++;
  78         gen = strsep(&cp, " "); /* gen */
  79         if (cp == NULL || *gen == '\0')
  80                 goto fail;
  81         prime = strsep(&cp, " "); /* prime */
  82         if (cp != NULL || *prime == '\0')
  83                 goto fail;
  84
  85         if ((dhg->g = BN_new()) == NULL)
  86                 fatal("parse_prime: BN_new failed");
  87         if ((dhg->p = BN_new()) == NULL)
  88                 fatal("parse_prime: BN_new failed");
  89         if (BN_hex2bn(&dhg->g, gen) == 0)
  90                 goto failclean;
  91
  92         if (BN_hex2bn(&dhg->p, prime) == 0)
  93                 goto failclean;
  94
  95         if (BN_num_bits(dhg->p) != dhg->size)
  96                 goto failclean;
  97
  98         if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
  99                 goto failclean;
 100
 101         return (1);
 102
 103  failclean:
 104         BN_clear_free(dhg->g);
 105         BN_clear_free(dhg->p);
 106  fail:
 107         error("Bad prime description in line %d", linenum);
 108         return (0);
 109 }
 110
 111 DH *
 112 choose_dh(int min, int wantbits, int max)
 113 {
 114         FILE *f;
 115         char line[4096];
 116         int best, bestcount, which;
 117         int linenum;
 118         struct dhgroup dhg;
 119
 120         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 121             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 122                 logit("WARNING: %s does not exist, using fixed modulus",
 123                     _PATH_DH_MODULI);
 124                 return (dh_new_group14());
 125         }
 126
 127         linenum = 0;
 128         best = bestcount = 0;
 129         while (fgets(line, sizeof(line), f)) {
 130                 linenum++;
 131                 if (!parse_prime(linenum, line, &dhg))
 132                         continue;
 133                 BN_clear_free(dhg.g);
 134                 BN_clear_free(dhg.p);
 135
 136                 if (dhg.size > max || dhg.size < min)
 137                         continue;
 138
 139                 if ((dhg.size > wantbits && dhg.size < best) ||
 140                     (dhg.size > best && best < wantbits)) {
 141                         best = dhg.size;
 142                         bestcount = 0;
 143                 }
 144                 if (dhg.size == best)
 145                         bestcount++;
 146         }
 147         rewind(f);
 148
 149         if (bestcount == 0) {
 150                 fclose(f);
 151                 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 152                 return (dh_new_group14());
 153         }
 154
 155         linenum = 0;
 156         which = arc4random() % bestcount;
 157         while (fgets(line, sizeof(line), f)) {
 158                 if (!parse_prime(linenum, line, &dhg))
 159                         continue;
 160                 if ((dhg.size > max || dhg.size < min) ||
 161                     dhg.size != best ||
 162                     linenum++ != which) {
 163                         BN_clear_free(dhg.g);
 164                         BN_clear_free(dhg.p);
 165                         continue;
 166                 }
 167                 break;
 168         }
 169         fclose(f);
 170         if (linenum != which+1)
 171                 fatal("WARNING: line %d disappeared in %s, giving up",
 172                     which, _PATH_DH_PRIMES);
 173
 174         return (dh_new_group(dhg.g, dhg.p));
 175 }
 176
 177 /* diffie-hellman-groupN-sha1 */
 178
 179 int
 180 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 181 {
 182         int i;
 183         int n = BN_num_bits(dh_pub);
 184         int bits_set = 0;
 185         BIGNUM *tmp;
 186
 187         if (dh_pub->neg) {
 188                 logit("invalid public DH value: negativ");
 189                 return 0;
 190         }
 191         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 192                 logit("invalid public DH value: <= 1");
 193                 return 0;
 194         }
 195
 196         if ((tmp = BN_new()) == NULL)
 197                 return (-1);
 198         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 199             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 200                 BN_clear_free(tmp);
 201                 logit("invalid public DH value: >= p-1");
 202                 return 0;
 203         }
 204         BN_clear_free(tmp);
 205
 206         for (i = 0; i <= n; i++)
 207                 if (BN_is_bit_set(dh_pub, i))
 208                         bits_set++;
 209         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 210
 211         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 212         if (bits_set > 1)
 213                 return 1;
 214
 215         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 216         return 0;
 217 }
 218
 219 void
 220 dh_gen_key(DH *dh, int need)
 221 {
 222         int i, bits_set, tries = 0;
 223
 224         if (dh->p == NULL)
 225                 fatal("dh_gen_key: dh->p == NULL");
 226         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 227                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 228                     BN_num_bits(dh->p), 2*need);
 229         do {
 230                 if (dh->priv_key != NULL)
 231                         BN_clear_free(dh->priv_key);
 232                 if ((dh->priv_key = BN_new()) == NULL)
 233                         fatal("dh_gen_key: BN_new failed");
 234                 /* generate a 2*need bits random private exponent */
 235                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 236                         fatal("dh_gen_key: BN_rand failed");
 237                 if (DH_generate_key(dh) == 0)
 238                         fatal("DH_generate_key");
 239                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 240                         if (BN_is_bit_set(dh->priv_key, i))
 241                                 bits_set++;
 242                 debug2("dh_gen_key: priv key bits set: %d/%d",
 243                     bits_set, BN_num_bits(dh->priv_key));
 244                 if (tries++ > 10)
 245                         fatal("dh_gen_key: too many bad keys: giving up");
 246         } while (!dh_pub_is_valid(dh, dh->pub_key));
 247 }
 248
 249 DH *
 250 dh_new_group_asc(const char *gen, const char *modulus)
 251 {
 252         DH *dh;
 253
 254         if ((dh = DH_new()) == NULL)
 255                 fatal("dh_new_group_asc: DH_new");
 256
 257         if (BN_hex2bn(&dh->p, modulus) == 0)
 258                 fatal("BN_hex2bn p");
 259         if (BN_hex2bn(&dh->g, gen) == 0)
 260                 fatal("BN_hex2bn g");
 261
 262         return (dh);
 263 }
 264
 265 /*
 266  * This just returns the group, we still need to generate the exchange
 267  * value.
 268  */
 269
 270 DH *
 271 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 272 {
 273         DH *dh;
 274
 275         if ((dh = DH_new()) == NULL)
 276                 fatal("dh_new_group: DH_new");
 277         dh->p = modulus;
 278         dh->g = gen;
 279
 280         return (dh);
 281 }
 282
 283 DH *
 284 dh_new_group1(void)
 285 {
 286         static char *gen = "2", *group1 =
 287             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 288             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 289             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 290             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 291             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 292             "FFFFFFFF" "FFFFFFFF";
 293
 294         return (dh_new_group_asc(gen, group1));
 295 }
 296
 297 DH *
 298 dh_new_group14(void)
 299 {
 300         static char *gen = "2", *group14 =
 301             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 302             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 303             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 304             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 305             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 306             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 307             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 308             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 309             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 310             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 311             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 312
 313         return (dh_new_group_asc(gen, group14));
 314 }
 315
 316 /*
 317  * Estimates the group order for a Diffie-Hellman group that has an
 318  * attack complexity approximately the same as O(2**bits).  Estimate
 319  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 320  */
 321
 322 int
 323 dh_estimate(int bits)
 324 {
 325
 326         if (bits <= 128)
 327                 return (1024);  /* O(2**86) */
 328         if (bits <= 192)
 329                 return (2048);  /* O(2**116) */
 330         return (4096);          /* O(2**156) */
 331 }