crypto/openssh/dh.c

   1 /* $OpenBSD: dh.c,v 1.57 2015/05/27 23:39:18 dtucker 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>  /* MIN */
  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 #include <limits.h>
  38
  39 #include "dh.h"
  40 #include "pathnames.h"
  41 #include "log.h"
  42 #include "misc.h"
  43 #include "ssherr.h"
  44
  45 static int
  46 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  47 {
  48         char *cp, *arg;
  49         char *strsize, *gen, *prime;
  50         const char *errstr = NULL;
  51         long long n;
  52
  53         dhg->p = dhg->g = NULL;
  54         cp = line;
  55         if ((arg = strdelim(&cp)) == NULL)
  56                 return 0;
  57         /* Ignore leading whitespace */
  58         if (*arg == '\0')
  59                 arg = strdelim(&cp);
  60         if (!arg || !*arg || *arg == '#')
  61                 return 0;
  62
  63         /* time */
  64         if (cp == NULL || *arg == '\0')
  65                 goto truncated;
  66         arg = strsep(&cp, " "); /* type */
  67         if (cp == NULL || *arg == '\0')
  68                 goto truncated;
  69         /* Ensure this is a safe prime */
  70         n = strtonum(arg, 0, 5, &errstr);
  71         if (errstr != NULL || n != MODULI_TYPE_SAFE) {
  72                 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
  73                 goto fail;
  74         }
  75         arg = strsep(&cp, " "); /* tests */
  76         if (cp == NULL || *arg == '\0')
  77                 goto truncated;
  78         /* Ensure prime has been tested and is not composite */
  79         n = strtonum(arg, 0, 0x1f, &errstr);
  80         if (errstr != NULL ||
  81             (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
  82                 error("moduli:%d: invalid moduli tests flag", linenum);
  83                 goto fail;
  84         }
  85         arg = strsep(&cp, " "); /* tries */
  86         if (cp == NULL || *arg == '\0')
  87                 goto truncated;
  88         n = strtonum(arg, 0, 1<<30, &errstr);
  89         if (errstr != NULL || n == 0) {
  90                 error("moduli:%d: invalid primality trial count", linenum);
  91                 goto fail;
  92         }
  93         strsize = strsep(&cp, " "); /* size */
  94         if (cp == NULL || *strsize == '\0' ||
  95             (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
  96             errstr) {
  97                 error("moduli:%d: invalid prime length", linenum);
  98                 goto fail;
  99         }
 100         /* The whole group is one bit larger */
 101         dhg->size++;
 102         gen = strsep(&cp, " "); /* gen */
 103         if (cp == NULL || *gen == '\0')
 104                 goto truncated;
 105         prime = strsep(&cp, " "); /* prime */
 106         if (cp != NULL || *prime == '\0') {
 107  truncated:
 108                 error("moduli:%d: truncated", linenum);
 109                 goto fail;
 110         }
 111
 112         if ((dhg->g = BN_new()) == NULL ||
 113             (dhg->p = BN_new()) == NULL) {
 114                 error("parse_prime: BN_new failed");
 115                 goto fail;
 116         }
 117         if (BN_hex2bn(&dhg->g, gen) == 0) {
 118                 error("moduli:%d: could not parse generator value", linenum);
 119                 goto fail;
 120         }
 121         if (BN_hex2bn(&dhg->p, prime) == 0) {
 122                 error("moduli:%d: could not parse prime value", linenum);
 123                 goto fail;
 124         }
 125         if (BN_num_bits(dhg->p) != dhg->size) {
 126                 error("moduli:%d: prime has wrong size: actual %d listed %d",
 127                     linenum, BN_num_bits(dhg->p), dhg->size - 1);
 128                 goto fail;
 129         }
 130         if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
 131                 error("moduli:%d: generator is invalid", linenum);
 132                 goto fail;
 133         }
 134         return 1;
 135
 136  fail:
 137         if (dhg->g != NULL)
 138                 BN_clear_free(dhg->g);
 139         if (dhg->p != NULL)
 140                 BN_clear_free(dhg->p);
 141         dhg->g = dhg->p = NULL;
 142         return 0;
 143 }
 144
 145 DH *
 146 choose_dh(int min, int wantbits, int max)
 147 {
 148         FILE *f;
 149         char line[4096];
 150         int best, bestcount, which;
 151         int linenum;
 152         struct dhgroup dhg;
 153
 154         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 155             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 156                 logit("WARNING: %s does not exist, using fixed modulus",
 157                     _PATH_DH_MODULI);
 158                 return (dh_new_group_fallback(max));
 159         }
 160
 161         linenum = 0;
 162         best = bestcount = 0;
 163         while (fgets(line, sizeof(line), f)) {
 164                 linenum++;
 165                 if (!parse_prime(linenum, line, &dhg))
 166                         continue;
 167                 BN_clear_free(dhg.g);
 168                 BN_clear_free(dhg.p);
 169
 170                 if (dhg.size > max || dhg.size < min)
 171                         continue;
 172
 173                 if ((dhg.size > wantbits && dhg.size < best) ||
 174                     (dhg.size > best && best < wantbits)) {
 175                         best = dhg.size;
 176                         bestcount = 0;
 177                 }
 178                 if (dhg.size == best)
 179                         bestcount++;
 180         }
 181         rewind(f);
 182
 183         if (bestcount == 0) {
 184                 fclose(f);
 185                 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 186                 return (dh_new_group_fallback(max));
 187         }
 188
 189         linenum = 0;
 190         which = arc4random_uniform(bestcount);
 191         while (fgets(line, sizeof(line), f)) {
 192                 if (!parse_prime(linenum, line, &dhg))
 193                         continue;
 194                 if ((dhg.size > max || dhg.size < min) ||
 195                     dhg.size != best ||
 196                     linenum++ != which) {
 197                         BN_clear_free(dhg.g);
 198                         BN_clear_free(dhg.p);
 199                         continue;
 200                 }
 201                 break;
 202         }
 203         fclose(f);
 204         if (linenum != which+1) {
 205                 logit("WARNING: line %d disappeared in %s, giving up",
 206                     which, _PATH_DH_PRIMES);
 207                 return (dh_new_group_fallback(max));
 208         }
 209
 210         return (dh_new_group(dhg.g, dhg.p));
 211 }
 212
 213 /* diffie-hellman-groupN-sha1 */
 214
 215 int
 216 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 217 {
 218         int i;
 219         int n = BN_num_bits(dh_pub);
 220         int bits_set = 0;
 221         BIGNUM *tmp;
 222
 223         if (dh_pub->neg) {
 224                 logit("invalid public DH value: negative");
 225                 return 0;
 226         }
 227         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 228                 logit("invalid public DH value: <= 1");
 229                 return 0;
 230         }
 231
 232         if ((tmp = BN_new()) == NULL) {
 233                 error("%s: BN_new failed", __func__);
 234                 return 0;
 235         }
 236         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 237             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 238                 BN_clear_free(tmp);
 239                 logit("invalid public DH value: >= p-1");
 240                 return 0;
 241         }
 242         BN_clear_free(tmp);
 243
 244         for (i = 0; i <= n; i++)
 245                 if (BN_is_bit_set(dh_pub, i))
 246                         bits_set++;
 247         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 248
 249         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 250         if (bits_set > 1)
 251                 return 1;
 252
 253         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 254         return 0;
 255 }
 256
 257 int
 258 dh_gen_key(DH *dh, int need)
 259 {
 260         int pbits;
 261
 262         if (need < 0 || dh->p == NULL ||
 263             (pbits = BN_num_bits(dh->p)) <= 0 ||
 264             need > INT_MAX / 2 || 2 * need > pbits)
 265                 return SSH_ERR_INVALID_ARGUMENT;
 266         dh->length = MIN(need * 2, pbits - 1);
 267         if (DH_generate_key(dh) == 0 ||
 268             !dh_pub_is_valid(dh, dh->pub_key)) {
 269                 BN_clear_free(dh->priv_key);
 270                 return SSH_ERR_LIBCRYPTO_ERROR;
 271         }
 272         return 0;
 273 }
 274
 275 DH *
 276 dh_new_group_asc(const char *gen, const char *modulus)
 277 {
 278         DH *dh;
 279
 280         if ((dh = DH_new()) == NULL)
 281                 return NULL;
 282         if (BN_hex2bn(&dh->p, modulus) == 0 ||
 283             BN_hex2bn(&dh->g, gen) == 0) {
 284                 DH_free(dh);
 285                 return NULL;
 286         }
 287         return (dh);
 288 }
 289
 290 /*
 291  * This just returns the group, we still need to generate the exchange
 292  * value.
 293  */
 294
 295 DH *
 296 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 297 {
 298         DH *dh;
 299
 300         if ((dh = DH_new()) == NULL)
 301                 return NULL;
 302         dh->p = modulus;
 303         dh->g = gen;
 304
 305         return (dh);
 306 }
 307
 308 DH *
 309 dh_new_group1(void)
 310 {
 311         static char *gen = "2", *group1 =
 312             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 313             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 314             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 315             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 316             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 317             "FFFFFFFF" "FFFFFFFF";
 318
 319         return (dh_new_group_asc(gen, group1));
 320 }
 321
 322 DH *
 323 dh_new_group14(void)
 324 {
 325         static char *gen = "2", *group14 =
 326             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 327             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 328             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 329             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 330             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 331             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 332             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 333             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 334             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 335             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 336             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 337
 338         return (dh_new_group_asc(gen, group14));
 339 }
 340
 341 /*
 342  * 4k bit fallback group used by DH-GEX if moduli file cannot be read.
 343  * Source: MODP group 16 from RFC3526.
 344  */
 345 DH *
 346 dh_new_group_fallback(int max)
 347 {
 348         static char *gen = "2", *group16 =
 349             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 350             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 351             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 352             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 353             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 354             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 355             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 356             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 357             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 358             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 359             "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
 360             "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
 361             "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
 362             "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
 363             "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
 364             "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
 365             "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
 366             "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
 367             "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
 368             "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
 369             "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
 370             "FFFFFFFF" "FFFFFFFF";
 371
 372         if (max < 4096) {
 373                 debug3("requested max size %d, using 2k bit group 14", max);
 374                 return dh_new_group14();
 375         }
 376         debug3("using 4k bit group 16");
 377         return (dh_new_group_asc(gen, group16));
 378 }
 379
 380 /*
 381  * Estimates the group order for a Diffie-Hellman group that has an
 382  * attack complexity approximately the same as O(2**bits).
 383  * Values from NIST Special Publication 800-57: Recommendation for Key
 384  * Management Part 1 (rev 3) limited by the recommended maximum value
 385  * from RFC4419 section 3.
 386  */
 387
 388 u_int
 389 dh_estimate(int bits)
 390 {
 391         if (bits <= 112)
 392                 return 2048;
 393         if (bits <= 128)
 394                 return 3072;
 395         if (bits <= 192)
 396                 return 7680;
 397         return 8192;
 398 }