crypto/openssh/dh.c

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