crypto/openssh/dh.c

   1 /* $OpenBSD: dh.c,v 1.47 2008/06/26 09:19:39 djm 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         long long n;
  50
  51         cp = line;
  52         if ((arg = strdelim(&cp)) == NULL)
  53                 return 0;
  54         /* Ignore leading whitespace */
  55         if (*arg == '\0')
  56                 arg = strdelim(&cp);
  57         if (!arg || !*arg || *arg == '#')
  58                 return 0;
  59
  60         /* time */
  61         if (cp == NULL || *arg == '\0')
  62                 goto fail;
  63         arg = strsep(&cp, " "); /* type */
  64         if (cp == NULL || *arg == '\0')
  65                 goto fail;
  66         /* Ensure this is a safe prime */
  67         n = strtonum(arg, 0, 5, &errstr);
  68         if (errstr != NULL || n != MODULI_TYPE_SAFE)
  69                 goto fail;
  70         arg = strsep(&cp, " "); /* tests */
  71         if (cp == NULL || *arg == '\0')
  72                 goto fail;
  73         /* Ensure prime has been tested and is not composite */
  74         n = strtonum(arg, 0, 0x1f, &errstr);
  75         if (errstr != NULL ||
  76             (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
  77                 goto fail;
  78         arg = strsep(&cp, " "); /* tries */
  79         if (cp == NULL || *arg == '\0')
  80                 goto fail;
  81         n = strtonum(arg, 0, 1<<30, &errstr);
  82         if (errstr != NULL || n == 0)
  83                 goto fail;
  84         strsize = strsep(&cp, " "); /* size */
  85         if (cp == NULL || *strsize == '\0' ||
  86             (dhg->size = (u_int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
  87             errstr)
  88                 goto fail;
  89         /* The whole group is one bit larger */
  90         dhg->size++;
  91         gen = strsep(&cp, " "); /* gen */
  92         if (cp == NULL || *gen == '\0')
  93                 goto fail;
  94         prime = strsep(&cp, " "); /* prime */
  95         if (cp != NULL || *prime == '\0')
  96                 goto fail;
  97
  98         if ((dhg->g = BN_new()) == NULL)
  99                 fatal("parse_prime: BN_new failed");
 100         if ((dhg->p = BN_new()) == NULL)
 101                 fatal("parse_prime: BN_new failed");
 102         if (BN_hex2bn(&dhg->g, gen) == 0)
 103                 goto failclean;
 104
 105         if (BN_hex2bn(&dhg->p, prime) == 0)
 106                 goto failclean;
 107
 108         if (BN_num_bits(dhg->p) != dhg->size)
 109                 goto failclean;
 110
 111         if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
 112                 goto failclean;
 113
 114         return (1);
 115
 116  failclean:
 117         BN_clear_free(dhg->g);
 118         BN_clear_free(dhg->p);
 119  fail:
 120         error("Bad prime description in line %d", linenum);
 121         return (0);
 122 }
 123
 124 DH *
 125 choose_dh(int min, int wantbits, int max)
 126 {
 127         FILE *f;
 128         char line[4096];
 129         int best, bestcount, which;
 130         int linenum;
 131         struct dhgroup dhg;
 132
 133         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 134             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 135                 logit("WARNING: %s does not exist, using fixed modulus",
 136                     _PATH_DH_MODULI);
 137                 return (dh_new_group14());
 138         }
 139
 140         linenum = 0;
 141         best = bestcount = 0;
 142         while (fgets(line, sizeof(line), f)) {
 143                 linenum++;
 144                 if (!parse_prime(linenum, line, &dhg))
 145                         continue;
 146                 BN_clear_free(dhg.g);
 147                 BN_clear_free(dhg.p);
 148
 149                 if (dhg.size > max || dhg.size < min)
 150                         continue;
 151
 152                 if ((dhg.size > wantbits && dhg.size < best) ||
 153                     (dhg.size > best && best < wantbits)) {
 154                         best = dhg.size;
 155                         bestcount = 0;
 156                 }
 157                 if (dhg.size == best)
 158                         bestcount++;
 159         }
 160         rewind(f);
 161
 162         if (bestcount == 0) {
 163                 fclose(f);
 164                 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 165                 return (dh_new_group14());
 166         }
 167
 168         linenum = 0;
 169         which = arc4random_uniform(bestcount);
 170         while (fgets(line, sizeof(line), f)) {
 171                 if (!parse_prime(linenum, line, &dhg))
 172                         continue;
 173                 if ((dhg.size > max || dhg.size < min) ||
 174                     dhg.size != best ||
 175                     linenum++ != which) {
 176                         BN_clear_free(dhg.g);
 177                         BN_clear_free(dhg.p);
 178                         continue;
 179                 }
 180                 break;
 181         }
 182         fclose(f);
 183         if (linenum != which+1)
 184                 fatal("WARNING: line %d disappeared in %s, giving up",
 185                     which, _PATH_DH_PRIMES);
 186
 187         return (dh_new_group(dhg.g, dhg.p));
 188 }
 189
 190 /* diffie-hellman-groupN-sha1 */
 191
 192 int
 193 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 194 {
 195         int i;
 196         int n = BN_num_bits(dh_pub);
 197         int bits_set = 0;
 198         BIGNUM *tmp;
 199
 200         if (dh_pub->neg) {
 201                 logit("invalid public DH value: negative");
 202                 return 0;
 203         }
 204         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 205                 logit("invalid public DH value: <= 1");
 206                 return 0;
 207         }
 208
 209         if ((tmp = BN_new()) == NULL) {
 210                 error("%s: BN_new failed", __func__);
 211                 return 0;
 212         }
 213         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 214             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 215                 BN_clear_free(tmp);
 216                 logit("invalid public DH value: >= p-1");
 217                 return 0;
 218         }
 219         BN_clear_free(tmp);
 220
 221         for (i = 0; i <= n; i++)
 222                 if (BN_is_bit_set(dh_pub, i))
 223                         bits_set++;
 224         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 225
 226         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 227         if (bits_set > 1)
 228                 return 1;
 229
 230         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 231         return 0;
 232 }
 233
 234 void
 235 dh_gen_key(DH *dh, int need)
 236 {
 237         int i, bits_set, tries = 0;
 238
 239         if (dh->p == NULL)
 240                 fatal("dh_gen_key: dh->p == NULL");
 241         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 242                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 243                     BN_num_bits(dh->p), 2*need);
 244         do {
 245                 if (dh->priv_key != NULL)
 246                         BN_clear_free(dh->priv_key);
 247                 if ((dh->priv_key = BN_new()) == NULL)
 248                         fatal("dh_gen_key: BN_new failed");
 249                 /* generate a 2*need bits random private exponent */
 250                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 251                         fatal("dh_gen_key: BN_rand failed");
 252                 if (DH_generate_key(dh) == 0)
 253                         fatal("DH_generate_key");
 254                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 255                         if (BN_is_bit_set(dh->priv_key, i))
 256                                 bits_set++;
 257                 debug2("dh_gen_key: priv key bits set: %d/%d",
 258                     bits_set, BN_num_bits(dh->priv_key));
 259                 if (tries++ > 10)
 260                         fatal("dh_gen_key: too many bad keys: giving up");
 261         } while (!dh_pub_is_valid(dh, dh->pub_key));
 262 }
 263
 264 DH *
 265 dh_new_group_asc(const char *gen, const char *modulus)
 266 {
 267         DH *dh;
 268
 269         if ((dh = DH_new()) == NULL)
 270                 fatal("dh_new_group_asc: DH_new");
 271
 272         if (BN_hex2bn(&dh->p, modulus) == 0)
 273                 fatal("BN_hex2bn p");
 274         if (BN_hex2bn(&dh->g, gen) == 0)
 275                 fatal("BN_hex2bn g");
 276
 277         return (dh);
 278 }
 279
 280 /*
 281  * This just returns the group, we still need to generate the exchange
 282  * value.
 283  */
 284
 285 DH *
 286 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 287 {
 288         DH *dh;
 289
 290         if ((dh = DH_new()) == NULL)
 291                 fatal("dh_new_group: DH_new");
 292         dh->p = modulus;
 293         dh->g = gen;
 294
 295         return (dh);
 296 }
 297
 298 DH *
 299 dh_new_group1(void)
 300 {
 301         static char *gen = "2", *group1 =
 302             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 303             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 304             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 305             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 306             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 307             "FFFFFFFF" "FFFFFFFF";
 308
 309         return (dh_new_group_asc(gen, group1));
 310 }
 311
 312 DH *
 313 dh_new_group14(void)
 314 {
 315         static char *gen = "2", *group14 =
 316             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 317             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 318             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 319             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 320             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 321             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 322             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 323             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 324             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 325             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 326             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 327
 328         return (dh_new_group_asc(gen, group14));
 329 }
 330
 331 /*
 332  * Estimates the group order for a Diffie-Hellman group that has an
 333  * attack complexity approximately the same as O(2**bits).  Estimate
 334  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 335  */
 336
 337 int
 338 dh_estimate(int bits)
 339 {
 340
 341         if (bits <= 128)
 342                 return (1024);  /* O(2**86) */
 343         if (bits <= 192)
 344                 return (2048);  /* O(2**116) */
 345         return (4096);          /* O(2**156) */
 346 }