crypto/openssh/dh.c

   1 /* $OpenBSD: dh.c,v 1.49 2011/12/07 05:44:38 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>
  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
  38 #include "dh.h"
  39 #include "pathnames.h"
  40 #include "log.h"
  41 #include "misc.h"
  42
  43 static int
  44 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  45 {
  46         char *cp, *arg;
  47         char *strsize, *gen, *prime;
  48         const char *errstr = NULL;
  49         long long n;
  50
  51         cp = line;
  52         if ((arg = strdelim(&cp)) == NULL)
  53                 return 0;
  54         /* Ignore leading whitespace */
  55         if (*arg == '\0')
  56                 arg = strdelim(&cp);
  57         if (!arg || !*arg || *arg == '#')
  58                 return 0;
  59
  60         /* time */
  61         if (cp == NULL || *arg == '\0')
  62                 goto fail;
  63         arg = strsep(&cp, " "); /* type */
  64         if (cp == NULL || *arg == '\0')
  65                 goto fail;
  66         /* Ensure this is a safe prime */
  67         n = strtonum(arg, 0, 5, &errstr);
  68         if (errstr != NULL || n != MODULI_TYPE_SAFE)
  69                 goto fail;
  70         arg = strsep(&cp, " "); /* tests */
  71         if (cp == NULL || *arg == '\0')
  72                 goto fail;
  73         /* Ensure prime has been tested and is not composite */
  74         n = strtonum(arg, 0, 0x1f, &errstr);
  75         if (errstr != NULL ||
  76             (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
  77                 goto fail;
  78         arg = strsep(&cp, " "); /* tries */
  79         if (cp == NULL || *arg == '\0')
  80                 goto fail;
  81         n = strtonum(arg, 0, 1<<30, &errstr);
  82         if (errstr != NULL || n == 0)
  83                 goto fail;
  84         strsize = strsep(&cp, " "); /* size */
  85         if (cp == NULL || *strsize == '\0' ||
  86             (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
  87             errstr)
  88                 goto fail;
  89         /* The whole group is one bit larger */
  90         dhg->size++;
  91         gen = strsep(&cp, " "); /* gen */
  92         if (cp == NULL || *gen == '\0')
  93                 goto fail;
  94         prime = strsep(&cp, " "); /* prime */
  95         if (cp != NULL || *prime == '\0')
  96                 goto fail;
  97
  98         if ((dhg->g = BN_new()) == NULL)
  99                 fatal("parse_prime: BN_new failed");
 100         if ((dhg->p = BN_new()) == NULL)
 101                 fatal("parse_prime: BN_new failed");
 102         if (BN_hex2bn(&dhg->g, gen) == 0)
 103                 goto failclean;
 104
 105         if (BN_hex2bn(&dhg->p, prime) == 0)
 106                 goto failclean;
 107
 108         if (BN_num_bits(dhg->p) != dhg->size)
 109                 goto failclean;
 110
 111         if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
 112                 goto failclean;
 113
 114         return (1);
 115
 116  failclean:
 117         BN_clear_free(dhg->g);
 118         BN_clear_free(dhg->p);
 119  fail:
 120         error("Bad prime description in line %d", linenum);
 121         return (0);
 122 }
 123
 124 DH *
 125 choose_dh(int min, int wantbits, int max)
 126 {
 127         FILE *f;
 128         char line[4096];
 129         int best, bestcount, which;
 130         int linenum;
 131         struct dhgroup dhg;
 132
 133         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 134             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 135                 logit("WARNING: %s does not exist, using fixed modulus",
 136                     _PATH_DH_MODULI);
 137                 return (dh_new_group14());
 138         }
 139
 140         linenum = 0;
 141         best = bestcount = 0;
 142         while (fgets(line, sizeof(line), f)) {
 143                 linenum++;
 144                 if (!parse_prime(linenum, line, &dhg))
 145                         continue;
 146                 BN_clear_free(dhg.g);
 147                 BN_clear_free(dhg.p);
 148
 149                 if (dhg.size > max || dhg.size < min)
 150                         continue;
 151
 152                 if ((dhg.size > wantbits && dhg.size < best) ||
 153                     (dhg.size > best && best < wantbits)) {
 154                         best = dhg.size;
 155                         bestcount = 0;
 156                 }
 157                 if (dhg.size == best)
 158                         bestcount++;
 159         }
 160         rewind(f);
 161
 162         if (bestcount == 0) {
 163                 fclose(f);
 164                 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 165                 return (dh_new_group14());
 166         }
 167
 168         linenum = 0;
 169         which = arc4random_uniform(bestcount);
 170         while (fgets(line, sizeof(line), f)) {
 171                 if (!parse_prime(linenum, line, &dhg))
 172                         continue;
 173                 if ((dhg.size > max || dhg.size < min) ||
 174                     dhg.size != best ||
 175                     linenum++ != which) {
 176                         BN_clear_free(dhg.g);
 177                         BN_clear_free(dhg.p);
 178                         continue;
 179                 }
 180                 break;
 181         }
 182         fclose(f);
 183         if (linenum != which+1)
 184                 fatal("WARNING: line %d disappeared in %s, giving up",
 185                     which, _PATH_DH_PRIMES);
 186
 187         return (dh_new_group(dhg.g, dhg.p));
 188 }
 189
 190 /* diffie-hellman-groupN-sha1 */
 191
 192 int
 193 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 194 {
 195         int i;
 196         int n = BN_num_bits(dh_pub);
 197         int bits_set = 0;
 198         BIGNUM *tmp;
 199
 200         if (dh_pub->neg) {
 201                 logit("invalid public DH value: negative");
 202                 return 0;
 203         }
 204         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 205                 logit("invalid public DH value: <= 1");
 206                 return 0;
 207         }
 208
 209         if ((tmp = BN_new()) == NULL) {
 210                 error("%s: BN_new failed", __func__);
 211                 return 0;
 212         }
 213         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 214             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 215                 BN_clear_free(tmp);
 216                 logit("invalid public DH value: >= p-1");
 217                 return 0;
 218         }
 219         BN_clear_free(tmp);
 220
 221         for (i = 0; i <= n; i++)
 222                 if (BN_is_bit_set(dh_pub, i))
 223                         bits_set++;
 224         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 225
 226         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 227         if (bits_set > 1)
 228                 return 1;
 229
 230         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 231         return 0;
 232 }
 233
 234 void
 235 dh_gen_key(DH *dh, int need)
 236 {
 237         int i, bits_set, tries = 0;
 238
 239         if (need < 0)
 240                 fatal("dh_gen_key: need < 0");
 241         if (dh->p == NULL)
 242                 fatal("dh_gen_key: dh->p == NULL");
 243         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 244                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 245                     BN_num_bits(dh->p), 2*need);
 246         do {
 247                 if (dh->priv_key != NULL)
 248                         BN_clear_free(dh->priv_key);
 249                 if ((dh->priv_key = BN_new()) == NULL)
 250                         fatal("dh_gen_key: BN_new failed");
 251                 /* generate a 2*need bits random private exponent */
 252                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 253                         fatal("dh_gen_key: BN_rand failed");
 254                 if (DH_generate_key(dh) == 0)
 255                         fatal("DH_generate_key");
 256                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 257                         if (BN_is_bit_set(dh->priv_key, i))
 258                                 bits_set++;
 259                 debug2("dh_gen_key: priv key bits set: %d/%d",
 260                     bits_set, BN_num_bits(dh->priv_key));
 261                 if (tries++ > 10)
 262                         fatal("dh_gen_key: too many bad keys: giving up");
 263         } while (!dh_pub_is_valid(dh, dh->pub_key));
 264 }
 265
 266 DH *
 267 dh_new_group_asc(const char *gen, const char *modulus)
 268 {
 269         DH *dh;
 270
 271         if ((dh = DH_new()) == NULL)
 272                 fatal("dh_new_group_asc: DH_new");
 273
 274         if (BN_hex2bn(&dh->p, modulus) == 0)
 275                 fatal("BN_hex2bn p");
 276         if (BN_hex2bn(&dh->g, gen) == 0)
 277                 fatal("BN_hex2bn g");
 278
 279         return (dh);
 280 }
 281
 282 /*
 283  * This just returns the group, we still need to generate the exchange
 284  * value.
 285  */
 286
 287 DH *
 288 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 289 {
 290         DH *dh;
 291
 292         if ((dh = DH_new()) == NULL)
 293                 fatal("dh_new_group: DH_new");
 294         dh->p = modulus;
 295         dh->g = gen;
 296
 297         return (dh);
 298 }
 299
 300 DH *
 301 dh_new_group1(void)
 302 {
 303         static char *gen = "2", *group1 =
 304             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 305             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 306             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 307             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 308             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 309             "FFFFFFFF" "FFFFFFFF";
 310
 311         return (dh_new_group_asc(gen, group1));
 312 }
 313
 314 DH *
 315 dh_new_group14(void)
 316 {
 317         static char *gen = "2", *group14 =
 318             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 319             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 320             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 321             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 322             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 323             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 324             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 325             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 326             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 327             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 328             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 329
 330         return (dh_new_group_asc(gen, group14));
 331 }
 332
 333 /*
 334  * Estimates the group order for a Diffie-Hellman group that has an
 335  * attack complexity approximately the same as O(2**bits).  Estimate
 336  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 337  */
 338
 339 int
 340 dh_estimate(int bits)
 341 {
 342
 343         if (bits <= 128)
 344                 return (1024);  /* O(2**86) */
 345         if (bits <= 192)
 346                 return (2048);  /* O(2**116) */
 347         return (4096);          /* O(2**156) */
 348 }