dh.c

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