crypto/openssh-5/dh.c

   1 /* $OpenBSD: dh.c,v 1.45 2007/09/27 00:15:57 ray 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: negative");
 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                 error("%s: BN_new failed", __func__);
 198                 return 0;
 199         }
 200         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 201             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 202                 BN_clear_free(tmp);
 203                 logit("invalid public DH value: >= p-1");
 204                 return 0;
 205         }
 206         BN_clear_free(tmp);
 207
 208         for (i = 0; i <= n; i++)
 209                 if (BN_is_bit_set(dh_pub, i))
 210                         bits_set++;
 211         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 212
 213         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 214         if (bits_set > 1)
 215                 return 1;
 216
 217         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 218         return 0;
 219 }
 220
 221 void
 222 dh_gen_key(DH *dh, int need)
 223 {
 224         int i, bits_set, tries = 0;
 225
 226         if (dh->p == NULL)
 227                 fatal("dh_gen_key: dh->p == NULL");
 228         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 229                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 230                     BN_num_bits(dh->p), 2*need);
 231         do {
 232                 if (dh->priv_key != NULL)
 233                         BN_clear_free(dh->priv_key);
 234                 if ((dh->priv_key = BN_new()) == NULL)
 235                         fatal("dh_gen_key: BN_new failed");
 236                 /* generate a 2*need bits random private exponent */
 237                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 238                         fatal("dh_gen_key: BN_rand failed");
 239                 if (DH_generate_key(dh) == 0)
 240                         fatal("DH_generate_key");
 241                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 242                         if (BN_is_bit_set(dh->priv_key, i))
 243                                 bits_set++;
 244                 debug2("dh_gen_key: priv key bits set: %d/%d",
 245                     bits_set, BN_num_bits(dh->priv_key));
 246                 if (tries++ > 10)
 247                         fatal("dh_gen_key: too many bad keys: giving up");
 248         } while (!dh_pub_is_valid(dh, dh->pub_key));
 249 }
 250
 251 DH *
 252 dh_new_group_asc(const char *gen, const char *modulus)
 253 {
 254         DH *dh;
 255
 256         if ((dh = DH_new()) == NULL)
 257                 fatal("dh_new_group_asc: DH_new");
 258
 259         if (BN_hex2bn(&dh->p, modulus) == 0)
 260                 fatal("BN_hex2bn p");
 261         if (BN_hex2bn(&dh->g, gen) == 0)
 262                 fatal("BN_hex2bn g");
 263
 264         return (dh);
 265 }
 266
 267 /*
 268  * This just returns the group, we still need to generate the exchange
 269  * value.
 270  */
 271
 272 DH *
 273 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 274 {
 275         DH *dh;
 276
 277         if ((dh = DH_new()) == NULL)
 278                 fatal("dh_new_group: DH_new");
 279         dh->p = modulus;
 280         dh->g = gen;
 281
 282         return (dh);
 283 }
 284
 285 DH *
 286 dh_new_group1(void)
 287 {
 288         static char *gen = "2", *group1 =
 289             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 290             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 291             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 292             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 293             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 294             "FFFFFFFF" "FFFFFFFF";
 295
 296         return (dh_new_group_asc(gen, group1));
 297 }
 298
 299 DH *
 300 dh_new_group14(void)
 301 {
 302         static char *gen = "2", *group14 =
 303             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 304             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 305             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 306             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 307             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 308             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 309             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 310             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 311             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 312             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 313             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 314
 315         return (dh_new_group_asc(gen, group14));
 316 }
 317
 318 /*
 319  * Estimates the group order for a Diffie-Hellman group that has an
 320  * attack complexity approximately the same as O(2**bits).  Estimate
 321  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 322  */
 323
 324 int
 325 dh_estimate(int bits)
 326 {
 327
 328         if (bits <= 128)
 329                 return (1024);  /* O(2**86) */
 330         if (bits <= 192)
 331                 return (2048);  /* O(2**116) */
 332         return (4096);          /* O(2**156) */
 333 }