crypto/openssh/dh.c

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