crypto/openssh/dh.c

   1 /* $OpenBSD: dh.c,v 1.53 2013/11/21 00:45:44 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         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 pbits;
 258
 259         if (need <= 0)
 260                 fatal("%s: need <= 0", __func__);
 261         if (dh->p == NULL)
 262                 fatal("%s: dh->p == NULL", __func__);
 263         if ((pbits = BN_num_bits(dh->p)) <= 0)
 264                 fatal("%s: bits(p) <= 0", __func__);
 265         dh->length = MIN(need * 2, pbits - 1);
 266         if (DH_generate_key(dh) == 0)
 267                 fatal("%s: key generation failed", __func__);
 268         if (!dh_pub_is_valid(dh, dh->pub_key))
 269                 fatal("%s: generated invalid key", __func__);
 270 }
 271
 272 DH *
 273 dh_new_group_asc(const char *gen, const char *modulus)
 274 {
 275         DH *dh;
 276
 277         if ((dh = DH_new()) == NULL)
 278                 fatal("dh_new_group_asc: DH_new");
 279
 280         if (BN_hex2bn(&dh->p, modulus) == 0)
 281                 fatal("BN_hex2bn p");
 282         if (BN_hex2bn(&dh->g, gen) == 0)
 283                 fatal("BN_hex2bn g");
 284
 285         return (dh);
 286 }
 287
 288 /*
 289  * This just returns the group, we still need to generate the exchange
 290  * value.
 291  */
 292
 293 DH *
 294 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 295 {
 296         DH *dh;
 297
 298         if ((dh = DH_new()) == NULL)
 299                 fatal("dh_new_group: DH_new");
 300         dh->p = modulus;
 301         dh->g = gen;
 302
 303         return (dh);
 304 }
 305
 306 DH *
 307 dh_new_group1(void)
 308 {
 309         static char *gen = "2", *group1 =
 310             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 311             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 312             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 313             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 314             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 315             "FFFFFFFF" "FFFFFFFF";
 316
 317         return (dh_new_group_asc(gen, group1));
 318 }
 319
 320 DH *
 321 dh_new_group14(void)
 322 {
 323         static char *gen = "2", *group14 =
 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" "ECE45B3D"
 329             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 330             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 331             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 332             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 333             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 334             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 335
 336         return (dh_new_group_asc(gen, group14));
 337 }
 338
 339 /*
 340  * Estimates the group order for a Diffie-Hellman group that has an
 341  * attack complexity approximately the same as O(2**bits).
 342  * Values from NIST Special Publication 800-57: Recommendation for Key
 343  * Management Part 1 (rev 3) limited by the recommended maximum value
 344  * from RFC4419 section 3.
 345  */
 346
 347 int
 348 dh_estimate(int bits)
 349 {
 350         if (bits <= 112)
 351                 return 2048;
 352         if (bits <= 128)
 353                 return 3072;
 354         if (bits <= 192)
 355                 return 7680;
 356         return 8192;
 357 }