dh.c

   1 /* $OpenBSD: dh.c,v 1.55 2015/01/20 23:14:00 deraadt 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_group14());
 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_group14());
 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_group14());
 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 #if !defined(OPENSSL_IS_BORINGSSL)
 267         /* BoringSSL renamed |length| to |priv_length| to better reflect its
 268          * actual use. Also, BoringSSL recognises common groups and chooses the
 269          * length of the private exponent accoringly. */
 270         dh->length = MIN(need * 2, pbits - 1);
 271 #endif
 272         if (DH_generate_key(dh) == 0 ||
 273             !dh_pub_is_valid(dh, dh->pub_key)) {
 274                 BN_clear_free(dh->priv_key);
 275                 return SSH_ERR_LIBCRYPTO_ERROR;
 276         }
 277         return 0;
 278 }
 279
 280 DH *
 281 dh_new_group_asc(const char *gen, const char *modulus)
 282 {
 283         DH *dh;
 284
 285         if ((dh = DH_new()) == NULL)
 286                 return NULL;
 287         if (BN_hex2bn(&dh->p, modulus) == 0 ||
 288             BN_hex2bn(&dh->g, gen) == 0) {
 289                 DH_free(dh);
 290                 return NULL;
 291         }
 292         return (dh);
 293 }
 294
 295 /*
 296  * This just returns the group, we still need to generate the exchange
 297  * value.
 298  */
 299
 300 DH *
 301 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 302 {
 303         DH *dh;
 304
 305         if ((dh = DH_new()) == NULL)
 306                 return NULL;
 307         dh->p = modulus;
 308         dh->g = gen;
 309
 310         return (dh);
 311 }
 312
 313 DH *
 314 dh_new_group1(void)
 315 {
 316         static char *gen = "2", *group1 =
 317             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 318             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 319             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 320             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 321             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 322             "FFFFFFFF" "FFFFFFFF";
 323
 324         return (dh_new_group_asc(gen, group1));
 325 }
 326
 327 DH *
 328 dh_new_group14(void)
 329 {
 330         static char *gen = "2", *group14 =
 331             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 332             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 333             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 334             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 335             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 336             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 337             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 338             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 339             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 340             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 341             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 342
 343         return (dh_new_group_asc(gen, group14));
 344 }
 345
 346 /*
 347  * Estimates the group order for a Diffie-Hellman group that has an
 348  * attack complexity approximately the same as O(2**bits).
 349  * Values from NIST Special Publication 800-57: Recommendation for Key
 350  * Management Part 1 (rev 3) limited by the recommended maximum value
 351  * from RFC4419 section 3.
 352  */
 353
 354 u_int
 355 dh_estimate(int bits)
 356 {
 357         if (bits <= 112)
 358                 return 2048;
 359         if (bits <= 128)
 360                 return 3072;
 361         if (bits <= 192)
 362                 return 7680;
 363         return 8192;
 364 }