dh.c

   1 /* $OpenBSD: dh.c,v 1.63 2018/02/07 02:06:50 jsing 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 #ifdef WITH_OPENSSL
  29
  30 #include <openssl/bn.h>
  31 #include <openssl/dh.h>
  32
  33 #include <errno.h>
  34 #include <stdarg.h>
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include <limits.h>
  39
  40 #include "dh.h"
  41 #include "pathnames.h"
  42 #include "log.h"
  43 #include "misc.h"
  44 #include "ssherr.h"
  45
  46 static int
  47 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  48 {
  49         char *cp, *arg;
  50         char *strsize, *gen, *prime;
  51         const char *errstr = NULL;
  52         long long n;
  53
  54         dhg->p = dhg->g = NULL;
  55         cp = line;
  56         if ((arg = strdelim(&cp)) == NULL)
  57                 return 0;
  58         /* Ignore leading whitespace */
  59         if (*arg == '\0')
  60                 arg = strdelim(&cp);
  61         if (!arg || !*arg || *arg == '#')
  62                 return 0;
  63
  64         /* time */
  65         if (cp == NULL || *arg == '\0')
  66                 goto truncated;
  67         arg = strsep(&cp, " "); /* type */
  68         if (cp == NULL || *arg == '\0')
  69                 goto truncated;
  70         /* Ensure this is a safe prime */
  71         n = strtonum(arg, 0, 5, &errstr);
  72         if (errstr != NULL || n != MODULI_TYPE_SAFE) {
  73                 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
  74                 goto fail;
  75         }
  76         arg = strsep(&cp, " "); /* tests */
  77         if (cp == NULL || *arg == '\0')
  78                 goto truncated;
  79         /* Ensure prime has been tested and is not composite */
  80         n = strtonum(arg, 0, 0x1f, &errstr);
  81         if (errstr != NULL ||
  82             (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
  83                 error("moduli:%d: invalid moduli tests flag", linenum);
  84                 goto fail;
  85         }
  86         arg = strsep(&cp, " "); /* tries */
  87         if (cp == NULL || *arg == '\0')
  88                 goto truncated;
  89         n = strtonum(arg, 0, 1<<30, &errstr);
  90         if (errstr != NULL || n == 0) {
  91                 error("moduli:%d: invalid primality trial count", linenum);
  92                 goto fail;
  93         }
  94         strsize = strsep(&cp, " "); /* size */
  95         if (cp == NULL || *strsize == '\0' ||
  96             (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
  97             errstr) {
  98                 error("moduli:%d: invalid prime length", linenum);
  99                 goto fail;
 100         }
 101         /* The whole group is one bit larger */
 102         dhg->size++;
 103         gen = strsep(&cp, " "); /* gen */
 104         if (cp == NULL || *gen == '\0')
 105                 goto truncated;
 106         prime = strsep(&cp, " "); /* prime */
 107         if (cp != NULL || *prime == '\0') {
 108  truncated:
 109                 error("moduli:%d: truncated", linenum);
 110                 goto fail;
 111         }
 112
 113         if ((dhg->g = BN_new()) == NULL ||
 114             (dhg->p = BN_new()) == NULL) {
 115                 error("parse_prime: BN_new failed");
 116                 goto fail;
 117         }
 118         if (BN_hex2bn(&dhg->g, gen) == 0) {
 119                 error("moduli:%d: could not parse generator value", linenum);
 120                 goto fail;
 121         }
 122         if (BN_hex2bn(&dhg->p, prime) == 0) {
 123                 error("moduli:%d: could not parse prime value", linenum);
 124                 goto fail;
 125         }
 126         if (BN_num_bits(dhg->p) != dhg->size) {
 127                 error("moduli:%d: prime has wrong size: actual %d listed %d",
 128                     linenum, BN_num_bits(dhg->p), dhg->size - 1);
 129                 goto fail;
 130         }
 131         if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
 132                 error("moduli:%d: generator is invalid", linenum);
 133                 goto fail;
 134         }
 135         return 1;
 136
 137  fail:
 138         BN_clear_free(dhg->g);
 139         BN_clear_free(dhg->p);
 140         dhg->g = dhg->p = NULL;
 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                 logit("WARNING: could not open %s (%s), using fixed modulus",
 155                     _PATH_DH_MODULI, strerror(errno));
 156                 return (dh_new_group_fallback(max));
 157         }
 158
 159         linenum = 0;
 160         best = bestcount = 0;
 161         while (fgets(line, sizeof(line), f)) {
 162                 linenum++;
 163                 if (!parse_prime(linenum, line, &dhg))
 164                         continue;
 165                 BN_clear_free(dhg.g);
 166                 BN_clear_free(dhg.p);
 167
 168                 if (dhg.size > max || dhg.size < min)
 169                         continue;
 170
 171                 if ((dhg.size > wantbits && dhg.size < best) ||
 172                     (dhg.size > best && best < wantbits)) {
 173                         best = dhg.size;
 174                         bestcount = 0;
 175                 }
 176                 if (dhg.size == best)
 177                         bestcount++;
 178         }
 179         rewind(f);
 180
 181         if (bestcount == 0) {
 182                 fclose(f);
 183                 logit("WARNING: no suitable primes in %s", _PATH_DH_MODULI);
 184                 return (dh_new_group_fallback(max));
 185         }
 186
 187         linenum = 0;
 188         which = arc4random_uniform(bestcount);
 189         while (fgets(line, sizeof(line), f)) {
 190                 if (!parse_prime(linenum, line, &dhg))
 191                         continue;
 192                 if ((dhg.size > max || dhg.size < min) ||
 193                     dhg.size != best ||
 194                     linenum++ != which) {
 195                         BN_clear_free(dhg.g);
 196                         BN_clear_free(dhg.p);
 197                         continue;
 198                 }
 199                 break;
 200         }
 201         fclose(f);
 202         if (linenum != which+1) {
 203                 logit("WARNING: line %d disappeared in %s, giving up",
 204                     which, _PATH_DH_MODULI);
 205                 return (dh_new_group_fallback(max));
 206         }
 207
 208         return (dh_new_group(dhg.g, dhg.p));
 209 }
 210
 211 /* diffie-hellman-groupN-sha1 */
 212
 213 int
 214 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 215 {
 216         int i;
 217         int n = BN_num_bits(dh_pub);
 218         int bits_set = 0;
 219         BIGNUM *tmp;
 220
 221         if (dh_pub->neg) {
 222                 logit("invalid public DH value: negative");
 223                 return 0;
 224         }
 225         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 226                 logit("invalid public DH value: <= 1");
 227                 return 0;
 228         }
 229
 230         if ((tmp = BN_new()) == NULL) {
 231                 error("%s: BN_new failed", __func__);
 232                 return 0;
 233         }
 234         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 235             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 236                 BN_clear_free(tmp);
 237                 logit("invalid public DH value: >= p-1");
 238                 return 0;
 239         }
 240         BN_clear_free(tmp);
 241
 242         for (i = 0; i <= n; i++)
 243                 if (BN_is_bit_set(dh_pub, i))
 244                         bits_set++;
 245         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 246
 247         /*
 248          * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
 249          */
 250         if (bits_set < 4) {
 251                 logit("invalid public DH value (%d/%d)",
 252                    bits_set, BN_num_bits(dh->p));
 253                 return 0;
 254         }
 255         return 1;
 256 }
 257
 258 int
 259 dh_gen_key(DH *dh, int need)
 260 {
 261         int pbits;
 262
 263         if (need < 0 || dh->p == NULL ||
 264             (pbits = BN_num_bits(dh->p)) <= 0 ||
 265             need > INT_MAX / 2 || 2 * need > pbits)
 266                 return SSH_ERR_INVALID_ARGUMENT;
 267         if (need < 256)
 268                 need = 256;
 269         /*
 270          * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
 271          * so double requested need here.
 272          */
 273         dh->length = MINIMUM(need * 2, pbits - 1);
 274         if (DH_generate_key(dh) == 0 ||
 275             !dh_pub_is_valid(dh, dh->pub_key)) {
 276                 BN_clear_free(dh->priv_key);
 277                 return SSH_ERR_LIBCRYPTO_ERROR;
 278         }
 279         return 0;
 280 }
 281
 282 DH *
 283 dh_new_group_asc(const char *gen, const char *modulus)
 284 {
 285         DH *dh;
 286
 287         if ((dh = DH_new()) == NULL)
 288                 return NULL;
 289         if (BN_hex2bn(&dh->p, modulus) == 0 ||
 290             BN_hex2bn(&dh->g, gen) == 0) {
 291                 DH_free(dh);
 292                 return NULL;
 293         }
 294         return (dh);
 295 }
 296
 297 /*
 298  * This just returns the group, we still need to generate the exchange
 299  * value.
 300  */
 301
 302 DH *
 303 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 304 {
 305         DH *dh;
 306
 307         if ((dh = DH_new()) == NULL)
 308                 return NULL;
 309         dh->p = modulus;
 310         dh->g = gen;
 311
 312         return (dh);
 313 }
 314
 315 /* rfc2409 "Second Oakley Group" (1024 bits) */
 316 DH *
 317 dh_new_group1(void)
 318 {
 319         static char *gen = "2", *group1 =
 320             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 321             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 322             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 323             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 324             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 325             "FFFFFFFF" "FFFFFFFF";
 326
 327         return (dh_new_group_asc(gen, group1));
 328 }
 329
 330 /* rfc3526 group 14 "2048-bit MODP Group" */
 331 DH *
 332 dh_new_group14(void)
 333 {
 334         static char *gen = "2", *group14 =
 335             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 336             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 337             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 338             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 339             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 340             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 341             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 342             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 343             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 344             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 345             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 346
 347         return (dh_new_group_asc(gen, group14));
 348 }
 349
 350 /* rfc3526 group 16 "4096-bit MODP Group" */
 351 DH *
 352 dh_new_group16(void)
 353 {
 354         static char *gen = "2", *group16 =
 355             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 356             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 357             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 358             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 359             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 360             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 361             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 362             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 363             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 364             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 365             "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
 366             "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
 367             "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
 368             "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
 369             "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
 370             "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
 371             "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
 372             "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
 373             "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
 374             "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
 375             "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
 376             "FFFFFFFF" "FFFFFFFF";
 377
 378         return (dh_new_group_asc(gen, group16));
 379 }
 380
 381 /* rfc3526 group 18 "8192-bit MODP Group" */
 382 DH *
 383 dh_new_group18(void)
 384 {
 385         static char *gen = "2", *group16 =
 386             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 387             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 388             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 389             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 390             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 391             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 392             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 393             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 394             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 395             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 396             "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
 397             "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
 398             "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
 399             "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
 400             "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
 401             "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
 402             "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
 403             "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
 404             "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
 405             "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
 406             "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
 407             "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
 408             "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
 409             "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
 410             "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
 411             "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
 412             "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
 413             "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
 414             "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
 415             "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
 416             "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
 417             "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
 418             "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
 419             "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
 420             "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
 421             "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
 422             "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
 423             "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
 424             "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
 425             "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
 426             "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
 427             "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
 428             "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
 429
 430         return (dh_new_group_asc(gen, group16));
 431 }
 432
 433 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
 434 DH *
 435 dh_new_group_fallback(int max)
 436 {
 437         debug3("%s: requested max size %d", __func__, max);
 438         if (max < 3072) {
 439                 debug3("using 2k bit group 14");
 440                 return dh_new_group14();
 441         } else if (max < 6144) {
 442                 debug3("using 4k bit group 16");
 443                 return dh_new_group16();
 444         }
 445         debug3("using 8k bit group 18");
 446         return dh_new_group18();
 447 }
 448
 449 /*
 450  * Estimates the group order for a Diffie-Hellman group that has an
 451  * attack complexity approximately the same as O(2**bits).
 452  * Values from NIST Special Publication 800-57: Recommendation for Key
 453  * Management Part 1 (rev 3) limited by the recommended maximum value
 454  * from RFC4419 section 3.
 455  */
 456 u_int
 457 dh_estimate(int bits)
 458 {
 459         if (bits <= 112)
 460                 return 2048;
 461         if (bits <= 128)
 462                 return 3072;
 463         if (bits <= 192)
 464                 return 7680;
 465         return 8192;
 466 }
 467
 468 #endif /* WITH_OPENSSL */