crypto/openssh/dh.c

   1 /* $OpenBSD: dh.c,v 1.62 2016/12/15 21:20:41 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
  29 #include <openssl/bn.h>
  30 #include <openssl/dh.h>
  31
  32 #include <errno.h>
  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                 logit("WARNING: could not open %s (%s), using fixed modulus",
 156                     _PATH_DH_MODULI, strerror(errno));
 157                 return (dh_new_group_fallback(max));
 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_MODULI);
 185                 return (dh_new_group_fallback(max));
 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                 logit("WARNING: line %d disappeared in %s, giving up",
 205                     which, _PATH_DH_MODULI);
 206                 return (dh_new_group_fallback(max));
 207         }
 208
 209         return (dh_new_group(dhg.g, dhg.p));
 210 }
 211
 212 /* diffie-hellman-groupN-sha1 */
 213
 214 int
 215 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 216 {
 217         int i;
 218         int n = BN_num_bits(dh_pub);
 219         int bits_set = 0;
 220         BIGNUM *tmp;
 221
 222         if (dh_pub->neg) {
 223                 logit("invalid public DH value: negative");
 224                 return 0;
 225         }
 226         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 227                 logit("invalid public DH value: <= 1");
 228                 return 0;
 229         }
 230
 231         if ((tmp = BN_new()) == NULL) {
 232                 error("%s: BN_new failed", __func__);
 233                 return 0;
 234         }
 235         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 236             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 237                 BN_clear_free(tmp);
 238                 logit("invalid public DH value: >= p-1");
 239                 return 0;
 240         }
 241         BN_clear_free(tmp);
 242
 243         for (i = 0; i <= n; i++)
 244                 if (BN_is_bit_set(dh_pub, i))
 245                         bits_set++;
 246         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 247
 248         /*
 249          * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
 250          */
 251         if (bits_set < 4) {
 252                 logit("invalid public DH value (%d/%d)",
 253                    bits_set, BN_num_bits(dh->p));
 254                 return 0;
 255         }
 256         return 1;
 257 }
 258
 259 int
 260 dh_gen_key(DH *dh, int need)
 261 {
 262         int pbits;
 263
 264         if (need < 0 || dh->p == NULL ||
 265             (pbits = BN_num_bits(dh->p)) <= 0 ||
 266             need > INT_MAX / 2 || 2 * need > pbits)
 267                 return SSH_ERR_INVALID_ARGUMENT;
 268         if (need < 256)
 269                 need = 256;
 270         /*
 271          * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
 272          * so double requested need here.
 273          */
 274         dh->length = MINIMUM(need * 2, pbits - 1);
 275         if (DH_generate_key(dh) == 0 ||
 276             !dh_pub_is_valid(dh, dh->pub_key)) {
 277                 BN_clear_free(dh->priv_key);
 278                 return SSH_ERR_LIBCRYPTO_ERROR;
 279         }
 280         return 0;
 281 }
 282
 283 DH *
 284 dh_new_group_asc(const char *gen, const char *modulus)
 285 {
 286         DH *dh;
 287
 288         if ((dh = DH_new()) == NULL)
 289                 return NULL;
 290         if (BN_hex2bn(&dh->p, modulus) == 0 ||
 291             BN_hex2bn(&dh->g, gen) == 0) {
 292                 DH_free(dh);
 293                 return NULL;
 294         }
 295         return (dh);
 296 }
 297
 298 /*
 299  * This just returns the group, we still need to generate the exchange
 300  * value.
 301  */
 302
 303 DH *
 304 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 305 {
 306         DH *dh;
 307
 308         if ((dh = DH_new()) == NULL)
 309                 return NULL;
 310         dh->p = modulus;
 311         dh->g = gen;
 312
 313         return (dh);
 314 }
 315
 316 /* rfc2409 "Second Oakley Group" (1024 bits) */
 317 DH *
 318 dh_new_group1(void)
 319 {
 320         static char *gen = "2", *group1 =
 321             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 322             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 323             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 324             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 325             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 326             "FFFFFFFF" "FFFFFFFF";
 327
 328         return (dh_new_group_asc(gen, group1));
 329 }
 330
 331 /* rfc3526 group 14 "2048-bit MODP Group" */
 332 DH *
 333 dh_new_group14(void)
 334 {
 335         static char *gen = "2", *group14 =
 336             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 337             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 338             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 339             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 340             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 341             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 342             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 343             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 344             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 345             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 346             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 347
 348         return (dh_new_group_asc(gen, group14));
 349 }
 350
 351 /* rfc3526 group 16 "4096-bit MODP Group" */
 352 DH *
 353 dh_new_group16(void)
 354 {
 355         static char *gen = "2", *group16 =
 356             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 357             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 358             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 359             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 360             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 361             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 362             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 363             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 364             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 365             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 366             "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
 367             "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
 368             "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
 369             "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
 370             "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
 371             "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
 372             "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
 373             "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
 374             "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
 375             "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
 376             "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
 377             "FFFFFFFF" "FFFFFFFF";
 378
 379         return (dh_new_group_asc(gen, group16));
 380 }
 381
 382 /* rfc3526 group 18 "8192-bit MODP Group" */
 383 DH *
 384 dh_new_group18(void)
 385 {
 386         static char *gen = "2", *group16 =
 387             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 388             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 389             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 390             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 391             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 392             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 393             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 394             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 395             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 396             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 397             "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
 398             "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
 399             "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
 400             "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
 401             "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
 402             "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
 403             "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
 404             "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
 405             "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
 406             "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
 407             "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
 408             "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
 409             "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
 410             "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
 411             "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
 412             "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
 413             "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
 414             "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
 415             "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
 416             "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
 417             "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
 418             "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
 419             "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
 420             "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
 421             "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
 422             "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
 423             "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
 424             "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
 425             "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
 426             "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
 427             "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
 428             "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
 429             "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
 430
 431         return (dh_new_group_asc(gen, group16));
 432 }
 433
 434 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
 435 DH *
 436 dh_new_group_fallback(int max)
 437 {
 438         debug3("%s: requested max size %d", __func__, max);
 439         if (max < 3072) {
 440                 debug3("using 2k bit group 14");
 441                 return dh_new_group14();
 442         } else if (max < 6144) {
 443                 debug3("using 4k bit group 16");
 444                 return dh_new_group16();
 445         }
 446         debug3("using 8k bit group 18");
 447         return dh_new_group18();
 448 }
 449
 450 /*
 451  * Estimates the group order for a Diffie-Hellman group that has an
 452  * attack complexity approximately the same as O(2**bits).
 453  * Values from NIST Special Publication 800-57: Recommendation for Key
 454  * Management Part 1 (rev 3) limited by the recommended maximum value
 455  * from RFC4419 section 3.
 456  */
 457 u_int
 458 dh_estimate(int bits)
 459 {
 460         if (bits <= 112)
 461                 return 2048;
 462         if (bits <= 128)
 463                 return 3072;
 464         if (bits <= 192)
 465                 return 7680;
 466         return 8192;
 467 }