dh.c

   1 /*
   2  * Copyright (c) 2000 Niels Provos.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  14  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  15  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  16  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  17  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  18  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  19  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  20  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  22  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 #include "includes.h"
  26 RCSID("$OpenBSD: dh.c,v 1.11 2001/03/29 21:17:39 markus Exp $");
  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 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         arg = strdelim(&cp);
  50         /* Ignore leading whitespace */
  51         if (*arg == '\0')
  52                 arg = strdelim(&cp);
  53         if (!*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 = atoi(strsize)) == 0)
  71                 goto fail;
  72         /* The whole group is one bit larger */
  73         dhg->size++;
  74         gen = strsep(&cp, " "); /* gen */
  75         if (cp == NULL || *gen == '\0')
  76                 goto fail;
  77         prime = strsep(&cp, " "); /* prime */
  78         if (cp != NULL || *prime == '\0')
  79                 goto fail;
  80
  81         dhg->g = BN_new();
  82         dhg->p = BN_new();
  83         if (BN_hex2bn(&dhg->g, gen) < 0)
  84                 goto failclean;
  85
  86         if (BN_hex2bn(&dhg->p, prime) < 0)
  87                 goto failclean;
  88
  89         if (BN_num_bits(dhg->p) != dhg->size)
  90                 goto failclean;
  91
  92         return (1);
  93
  94  failclean:
  95         BN_free(dhg->g);
  96         BN_free(dhg->p);
  97  fail:
  98         error("Bad prime description in line %d", linenum);
  99         return (0);
 100 }
 101
 102 DH *
 103 choose_dh(int min, int wantbits, int max)
 104 {
 105         FILE *f;
 106         char line[1024];
 107         int best, bestcount, which;
 108         int linenum;
 109         struct dhgroup dhg;
 110
 111         f = fopen(_PATH_DH_PRIMES, "r");
 112         if (!f) {
 113                 log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES);
 114                 return (dh_new_group1());
 115         }
 116
 117         linenum = 0;
 118         best = bestcount = 0;
 119         while (fgets(line, sizeof(line), f)) {
 120                 linenum++;
 121                 if (!parse_prime(linenum, line, &dhg))
 122                         continue;
 123                 BN_free(dhg.g);
 124                 BN_free(dhg.p);
 125
 126                 if (dhg.size > max || dhg.size < min)
 127                         continue;
 128
 129                 if ((dhg.size > wantbits && dhg.size < best) ||
 130                     (dhg.size > best && best < wantbits)) {
 131                         best = dhg.size;
 132                         bestcount = 0;
 133                 }
 134                 if (dhg.size == best)
 135                         bestcount++;
 136         }
 137         fclose (f);
 138
 139         if (bestcount == 0) {
 140                 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
 141                 return (NULL);
 142         }
 143
 144         f = fopen(_PATH_DH_PRIMES, "r");
 145         if (!f) {
 146                 fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES);
 147         }
 148
 149         linenum = 0;
 150         which = arc4random() % bestcount;
 151         while (fgets(line, sizeof(line), f)) {
 152                 if (!parse_prime(linenum, line, &dhg))
 153                         continue;
 154                 if (dhg.size > max || dhg.size < min)
 155                         continue;
 156                 if (dhg.size != best)
 157                         continue;
 158                 if (linenum++ != which) {
 159                         BN_free(dhg.g);
 160                         BN_free(dhg.p);
 161                         continue;
 162                 }
 163                 break;
 164         }
 165         fclose(f);
 166
 167         return (dh_new_group(dhg.g, dhg.p));
 168 }
 169
 170 /* diffie-hellman-group1-sha1 */
 171
 172 int
 173 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 174 {
 175         int i;
 176         int n = BN_num_bits(dh_pub);
 177         int bits_set = 0;
 178
 179         if (dh_pub->neg) {
 180                 log("invalid public DH value: negativ");
 181                 return 0;
 182         }
 183         for (i = 0; i <= n; i++)
 184                 if (BN_is_bit_set(dh_pub, i))
 185                         bits_set++;
 186         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 187
 188         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 189         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 190                 return 1;
 191         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 192         return 0;
 193 }
 194
 195 void
 196 dh_gen_key(DH *dh, int need)
 197 {
 198         int i, bits_set = 0, tries = 0;
 199
 200         if (dh->p == NULL)
 201                 fatal("dh_gen_key: dh->p == NULL");
 202         if (2*need >= BN_num_bits(dh->p))
 203                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 204                     BN_num_bits(dh->p), 2*need);
 205         do {
 206                 if (dh->priv_key != NULL)
 207                         BN_free(dh->priv_key);
 208                 dh->priv_key = BN_new();
 209                 if (dh->priv_key == NULL)
 210                         fatal("dh_gen_key: BN_new failed");
 211                 /* generate a 2*need bits random private exponent */
 212                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 213                         fatal("dh_gen_key: BN_rand failed");
 214                 if (DH_generate_key(dh) == 0)
 215                         fatal("DH_generate_key");
 216                 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
 217                         if (BN_is_bit_set(dh->priv_key, i))
 218                                 bits_set++;
 219                 debug("dh_gen_key: priv key bits set: %d/%d",
 220                     bits_set, BN_num_bits(dh->priv_key));
 221                 if (tries++ > 10)
 222                         fatal("dh_gen_key: too many bad keys: giving up");
 223         } while (!dh_pub_is_valid(dh, dh->pub_key));
 224 }
 225
 226 DH *
 227 dh_new_group_asc(const char *gen, const char *modulus)
 228 {
 229         DH *dh;
 230         int ret;
 231
 232         dh = DH_new();
 233         if (dh == NULL)
 234                 fatal("DH_new");
 235
 236         if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
 237                 fatal("BN_hex2bn p");
 238         if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
 239                 fatal("BN_hex2bn g");
 240
 241         return (dh);
 242 }
 243
 244 /*
 245  * This just returns the group, we still need to generate the exchange
 246  * value.
 247  */
 248
 249 DH *
 250 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 251 {
 252         DH *dh;
 253
 254         dh = DH_new();
 255         if (dh == NULL)
 256                 fatal("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 }