dh.c

   1 /* $OpenBSD: dh.c,v 1.34 2006/03/25 13:17:01 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 "xmalloc.h"
  29
  30 #include <openssl/bn.h>
  31 #include <openssl/dh.h>
  32 #include <openssl/evp.h>
  33
  34 #include "buffer.h"
  35 #include "cipher.h"
  36 #include "kex.h"
  37 #include "dh.h"
  38 #include "pathnames.h"
  39 #include "log.h"
  40 #include "misc.h"
  41
  42 static int
  43 parse_prime(int linenum, char *line, struct dhgroup *dhg)
  44 {
  45         char *cp, *arg;
  46         char *strsize, *gen, *prime;
  47
  48         cp = line;
  49         if ((arg = strdelim(&cp)) == NULL)
  50                 return 0;
  51         /* Ignore leading whitespace */
  52         if (*arg == '\0')
  53                 arg = strdelim(&cp);
  54         if (!arg || !*arg || *arg == '#')
  55                 return 0;
  56
  57         /* time */
  58         if (cp == NULL || *arg == '\0')
  59                 goto fail;
  60         arg = strsep(&cp, " "); /* type */
  61         if (cp == NULL || *arg == '\0')
  62                 goto fail;
  63         arg = strsep(&cp, " "); /* tests */
  64         if (cp == NULL || *arg == '\0')
  65                 goto fail;
  66         arg = strsep(&cp, " "); /* tries */
  67         if (cp == NULL || *arg == '\0')
  68                 goto fail;
  69         strsize = strsep(&cp, " "); /* size */
  70         if (cp == NULL || *strsize == '\0' ||
  71             (dhg->size = atoi(strsize)) == 0)
  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
 183         if (dh_pub->neg) {
 184                 logit("invalid public DH value: negativ");
 185                 return 0;
 186         }
 187         for (i = 0; i <= n; i++)
 188                 if (BN_is_bit_set(dh_pub, i))
 189                         bits_set++;
 190         debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 191
 192         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 193         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 194                 return 1;
 195         logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 196         return 0;
 197 }
 198
 199 void
 200 dh_gen_key(DH *dh, int need)
 201 {
 202         int i, bits_set, tries = 0;
 203
 204         if (dh->p == NULL)
 205                 fatal("dh_gen_key: dh->p == NULL");
 206         if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
 207                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 208                     BN_num_bits(dh->p), 2*need);
 209         do {
 210                 if (dh->priv_key != NULL)
 211                         BN_clear_free(dh->priv_key);
 212                 if ((dh->priv_key = BN_new()) == NULL)
 213                         fatal("dh_gen_key: BN_new failed");
 214                 /* generate a 2*need bits random private exponent */
 215                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 216                         fatal("dh_gen_key: BN_rand failed");
 217                 if (DH_generate_key(dh) == 0)
 218                         fatal("DH_generate_key");
 219                 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
 220                         if (BN_is_bit_set(dh->priv_key, i))
 221                                 bits_set++;
 222                 debug2("dh_gen_key: priv key bits set: %d/%d",
 223                     bits_set, BN_num_bits(dh->priv_key));
 224                 if (tries++ > 10)
 225                         fatal("dh_gen_key: too many bad keys: giving up");
 226         } while (!dh_pub_is_valid(dh, dh->pub_key));
 227 }
 228
 229 DH *
 230 dh_new_group_asc(const char *gen, const char *modulus)
 231 {
 232         DH *dh;
 233
 234         if ((dh = DH_new()) == NULL)
 235                 fatal("dh_new_group_asc: DH_new");
 236
 237         if (BN_hex2bn(&dh->p, modulus) == 0)
 238                 fatal("BN_hex2bn p");
 239         if (BN_hex2bn(&dh->g, gen) == 0)
 240                 fatal("BN_hex2bn g");
 241
 242         return (dh);
 243 }
 244
 245 /*
 246  * This just returns the group, we still need to generate the exchange
 247  * value.
 248  */
 249
 250 DH *
 251 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 252 {
 253         DH *dh;
 254
 255         if ((dh = DH_new()) == NULL)
 256                 fatal("dh_new_group: DH_new");
 257         dh->p = modulus;
 258         dh->g = gen;
 259
 260         return (dh);
 261 }
 262
 263 DH *
 264 dh_new_group1(void)
 265 {
 266         static char *gen = "2", *group1 =
 267             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 268             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 269             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 270             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 271             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 272             "FFFFFFFF" "FFFFFFFF";
 273
 274         return (dh_new_group_asc(gen, group1));
 275 }
 276
 277 DH *
 278 dh_new_group14(void)
 279 {
 280         static char *gen = "2", *group14 =
 281             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 282             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 283             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 284             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 285             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
 286             "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
 287             "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
 288             "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
 289             "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
 290             "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
 291             "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
 292
 293         return (dh_new_group_asc(gen, group14));
 294 }
 295
 296 /*
 297  * Estimates the group order for a Diffie-Hellman group that has an
 298  * attack complexity approximately the same as O(2**bits).  Estimate
 299  * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 300  */
 301
 302 int
 303 dh_estimate(int bits)
 304 {
 305
 306         if (bits <= 128)
 307                 return (1024);  /* O(2**86) */
 308         if (bits <= 192)
 309                 return (2048);  /* O(2**116) */
 310         return (4096);          /* O(2**156) */
 311 }