crypto/openssh/dh.c

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