crypto/external/bsd/openssh/dist/dh.c

   1 /*      $NetBSD$        */
   2 /* $OpenBSD: dh.c,v 1.47 2008/06/26 09:19:39 djm Exp $ */
   3 /*
   4  * Copyright (c) 2000 Niels Provos.  All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "includes.h"
  28 __RCSID("$NetBSD: dh.c,v 1.18 2009/02/16 20:53:54 christos Exp $");
  29 #include <sys/param.h>
  30
  31 #include <openssl/bn.h>
  32 #include <openssl/dh.h>
  33
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37 #include <time.h>
  38
  39 #include "dh.h"
  40 #include "pathnames.h"
  41 #include "log.h"
  42 #include "misc.h"
  43 #include "random.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         cp = line;
  54         if ((arg = strdelim(&cp)) == NULL)
  55                 return 0;
  56         /* Ignore leading whitespace */
  57         if (*arg == '\0')
  58                 arg = strdelim(&cp);
  59         if (!arg || !*arg || *arg == '#')
  60                 return 0;
  61
  62         /* time */
  63         if (cp == NULL || *arg == '\0')
  64                 goto fail;
  65         arg = strsep(&cp, " "); /* type */
  66         if (cp == NULL || *arg == '\0')
  67                 goto fail;
  68         /* Ensure this is a safe prime */
  69         n = strtonum(arg, 0, 5, &errstr);
  70         if (errstr != NULL || n != MODULI_TYPE_SAFE)
  71                 goto fail;
  72         arg = strsep(&cp, " "); /* tests */
  73         if (cp == NULL || *arg == '\0')
  74                 goto fail;
  75         /* Ensure prime has been tested and is not composite */
  76         n = strtonum(arg, 0, 0x1f, &errstr);
  77         if (errstr != NULL ||
  78             (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
  79                 goto fail;
  80         arg = strsep(&cp, " "); /* tries */
  81         if (cp == NULL || *arg == '\0')
  82                 goto fail;
  83         n = strtonum(arg, 0, 1<<30, &errstr);
  84         if (errstr != NULL || n == 0)
  85                 goto fail;
  86         strsize = strsep(&cp, " "); /* size */
  87         if (cp == NULL || *strsize == '\0' ||
  88             (dhg->size = (u_int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
  89             errstr)
  90                 goto fail;
  91         /* The whole group is one bit larger */
  92         dhg->size++;
  93         gen = strsep(&cp, " "); /* gen */
  94         if (cp == NULL || *gen == '\0')
  95                 goto fail;
  96         prime = strsep(&cp, " "); /* prime */
  97         if (cp != NULL || *prime == '\0')
  98                 goto fail;
  99
 100         if ((dhg->g = BN_new()) == NULL)
 101                 fatal("parse_prime: BN_new failed");
 102         if ((dhg->p = BN_new()) == NULL)
 103                 fatal("parse_prime: BN_new failed");
 104         if (BN_hex2bn(&dhg->g, gen) == 0)
 105                 goto failclean;
 106
 107         if (BN_hex2bn(&dhg->p, prime) == 0)
 108                 goto failclean;
 109
 110         if (BN_num_bits(dhg->p) != dhg->size)
 111                 goto failclean;
 112
 113         if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
 114                 goto failclean;
 115
 116         return (1);
 117
 118  failclean:
 119         BN_clear_free(dhg->g);
 120         BN_clear_free(dhg->p);
 121  fail:
 122         error("Bad prime description in line %d", linenum);
 123         return (0);
 124 }
 125
 126 DH *
 127 choose_dh(int min, int wantbits, int max)
 128 {
 129         FILE *f;
 130         char line[4096];
 131         int best, bestcount, which;
 132         int linenum;
 133         struct dhgroup dhg;
 134
 135         if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
 136             (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
 137                 logit("WARNING: %s does not exist, using fixed modulus",
 138                     _PATH_DH_MODULI);
 139                 return (dh_new_group14());
 140         }
 141
 142         linenum = 0;
 143         best = bestcount = 0;
 144         while (fgets(line, sizeof(line), f)) {
 145                 linenum++;
 146                 if (!parse_prime(linenum, line, &dhg))
 147                         continue;
 148                 BN_clear_free(dhg.g);
 149                 BN_clear_free(dhg.p);
 150
 151                 if (dhg.size > max || dhg.size < min)
 152                         continue;
 153
 154                 if ((dhg.size > wantbits && dhg.size < best) ||
 155                     (dhg.size > best && best < wantbits)) {
 156                         best = dhg.size;
 157                         bestcount = 0;
 158                 }
 159                 if (dhg.size == best)
 160                         bestcount++;
 161         }
 162         rewind(f);
 163
 164         if (bestcount == 0) {
 165                 fclose(f);
 166                 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 167                 return (dh_new_group14());
 168         }
 169
 170         linenum = 0;
 171         which = arc4random_uniform(bestcount);
 172         while (fgets(line, sizeof(line), f)) {
 173                 if (!parse_prime(linenum, line, &dhg))
 174                         continue;
 175                 if ((dhg.size > max || dhg.size < min) ||
 176                     dhg.size != best ||
 177                     linenum++ != which) {
 178                         BN_clear_free(dhg.g);
 179                         BN_clear_free(dhg.p);
 180                         continue;
 181                 }
 182                 break;
 183         }
 184         fclose(f);
 185         if (linenum != which+1)
 186                 fatal("WARNING: line %d disappeared in %s, giving up",
 187                     which, _PATH_DH_PRIMES);
 188
 189         return (dh_new_group(dhg.g, dhg.p));
 190 }
 191
 192 /* diffie-hellman-groupN-sha1 */
 193
 194 int
 195 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 196 {
 197         int i;
 198         int n = BN_num_bits(dh_pub);
 199         int bits_set = 0;
 200         BIGNUM *tmp;
 201
 202         if (dh_pub->neg) {
 203                 logit("invalid public DH value: negative");
 204                 return 0;
 205         }
 206         if (BN_cmp(dh_pub, BN_value_one()) != 1) {      /* pub_exp <= 1 */
 207                 logit("invalid public DH value: <= 1");
 208                 return 0;
 209         }
 210
 211         if ((tmp = BN_new()) == NULL) {
 212                 error("%s: BN_new failed", __func__);
 213                 return 0;
 214         }
 215         if (!BN_sub(tmp, dh->p, BN_value_one()) ||
 216             BN_cmp(dh_pub, tmp) != -1) {                /* pub_exp > p-2 */
 217                 BN_clear_free(tmp);
 218                 logit("invalid public DH value: >= p-1");
 219                 return 0;
 220         }
 221         BN_clear_free(tmp);
 222
 223         for (i = 0; i <= n; i++)
 224                 if (BN_is_bit_set(dh_pub, i))
 225                         bits_set++;
 226         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 227
 228         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 229         if (bits_set > 1)
 230                 return 1;
 231
 232         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 233         return 0;
 234 }
 235
 236 void
 237 dh_gen_key(DH *dh, int need)
 238 {
 239         int i, bits_set, tries = 0;
 240
 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 }