blob: 1be51953c6e2f02b545b21e12b0384e35d2352a0 [file] [log] [blame]
Damien Miller874d77b2000-10-14 16:23:11 +11001/*
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"
Ben Lindstrom1f530832002-12-23 02:03:02 +000026RCSID("$OpenBSD: dh.c,v 1.23 2002/11/21 22:22:50 markus Exp $");
Damien Miller874d77b2000-10-14 16:23:11 +110027
28#include "xmalloc.h"
29
30#include <openssl/bn.h>
31#include <openssl/dh.h>
32#include <openssl/evp.h>
33
Damien Miller874d77b2000-10-14 16:23:11 +110034#include "buffer.h"
Ben Lindstrom226cfa02001-01-22 05:34:40 +000035#include "cipher.h"
Damien Miller874d77b2000-10-14 16:23:11 +110036#include "kex.h"
37#include "dh.h"
Ben Lindstrom226cfa02001-01-22 05:34:40 +000038#include "pathnames.h"
39#include "log.h"
40#include "misc.h"
Damien Miller874d77b2000-10-14 16:23:11 +110041
Ben Lindstrombba81212001-06-25 05:01:22 +000042static int
Damien Miller874d77b2000-10-14 16:23:11 +110043parse_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);
Ben Lindstrom04f9af72002-07-04 00:03:56 +000053 if (!arg || !*arg || *arg == '#')
Damien Miller874d77b2000-10-14 16:23:11 +110054 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;
Ben Lindstromdf221392001-03-29 00:36:16 +000072 /* The whole group is one bit larger */
73 dhg->size++;
Damien Miller874d77b2000-10-14 16:23:11 +110074 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
Damien Millerda755162002-01-22 23:09:22 +110081 if ((dhg->g = BN_new()) == NULL)
82 fatal("parse_prime: BN_new failed");
83 if ((dhg->p = BN_new()) == NULL)
84 fatal("parse_prime: BN_new failed");
Ben Lindstrom206941f2001-04-15 14:27:16 +000085 if (BN_hex2bn(&dhg->g, gen) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +100086 goto failclean;
87
Ben Lindstrom206941f2001-04-15 14:27:16 +000088 if (BN_hex2bn(&dhg->p, prime) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +100089 goto failclean;
90
91 if (BN_num_bits(dhg->p) != dhg->size)
92 goto failclean;
Damien Miller874d77b2000-10-14 16:23:11 +110093
94 return (1);
Damien Miller23e526e2001-03-30 10:47:43 +100095
96 failclean:
Damien Miller9ef95dd2002-01-22 23:10:33 +110097 BN_clear_free(dhg->g);
98 BN_clear_free(dhg->p);
Damien Miller874d77b2000-10-14 16:23:11 +110099 fail:
Ben Lindstrom6df8ef42001-03-05 07:47:23 +0000100 error("Bad prime description in line %d", linenum);
Damien Miller874d77b2000-10-14 16:23:11 +1100101 return (0);
102}
103
104DH *
Ben Lindstromdf221392001-03-29 00:36:16 +0000105choose_dh(int min, int wantbits, int max)
Damien Miller874d77b2000-10-14 16:23:11 +1100106{
107 FILE *f;
Ben Lindstromaf738802001-06-25 04:18:59 +0000108 char line[2048];
Damien Miller874d77b2000-10-14 16:23:11 +1100109 int best, bestcount, which;
110 int linenum;
111 struct dhgroup dhg;
112
Ben Lindstrom93a29e02001-06-25 04:13:25 +0000113 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
114 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
115 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
Damien Miller874d77b2000-10-14 16:23:11 +1100116 return (dh_new_group1());
117 }
118
119 linenum = 0;
120 best = bestcount = 0;
121 while (fgets(line, sizeof(line), f)) {
122 linenum++;
123 if (!parse_prime(linenum, line, &dhg))
124 continue;
Damien Miller9ef95dd2002-01-22 23:10:33 +1100125 BN_clear_free(dhg.g);
126 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100127
Ben Lindstromdf221392001-03-29 00:36:16 +0000128 if (dhg.size > max || dhg.size < min)
129 continue;
130
131 if ((dhg.size > wantbits && dhg.size < best) ||
132 (dhg.size > best && best < wantbits)) {
Damien Miller874d77b2000-10-14 16:23:11 +1100133 best = dhg.size;
134 bestcount = 0;
135 }
136 if (dhg.size == best)
137 bestcount++;
138 }
Ben Lindstromaf738802001-06-25 04:18:59 +0000139 rewind(f);
Damien Miller874d77b2000-10-14 16:23:11 +1100140
141 if (bestcount == 0) {
Ben Lindstromaf738802001-06-25 04:18:59 +0000142 fclose(f);
Ben Lindstromdf221392001-03-29 00:36:16 +0000143 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
144 return (NULL);
Damien Miller874d77b2000-10-14 16:23:11 +1100145 }
146
Damien Miller874d77b2000-10-14 16:23:11 +1100147 linenum = 0;
148 which = arc4random() % bestcount;
149 while (fgets(line, sizeof(line), f)) {
150 if (!parse_prime(linenum, line, &dhg))
151 continue;
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000152 if ((dhg.size > max || dhg.size < min) ||
153 dhg.size != best ||
154 linenum++ != which) {
Damien Miller9ef95dd2002-01-22 23:10:33 +1100155 BN_clear_free(dhg.g);
156 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100157 continue;
158 }
159 break;
160 }
161 fclose(f);
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000162 if (linenum != which+1)
163 fatal("WARNING: line %d disappeared in %s, giving up",
164 which, _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100165
166 return (dh_new_group(dhg.g, dhg.p));
167}
Damien Miller9709f902001-03-30 10:50:10 +1000168
169/* diffie-hellman-group1-sha1 */
170
171int
172dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
173{
174 int i;
175 int n = BN_num_bits(dh_pub);
176 int bits_set = 0;
177
178 if (dh_pub->neg) {
179 log("invalid public DH value: negativ");
180 return 0;
181 }
182 for (i = 0; i <= n; i++)
183 if (BN_is_bit_set(dh_pub, i))
184 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000185 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000186
187 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
188 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
189 return 1;
190 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
191 return 0;
192}
193
194void
195dh_gen_key(DH *dh, int need)
196{
197 int i, bits_set = 0, tries = 0;
198
199 if (dh->p == NULL)
200 fatal("dh_gen_key: dh->p == NULL");
201 if (2*need >= BN_num_bits(dh->p))
202 fatal("dh_gen_key: group too small: %d (2*need %d)",
203 BN_num_bits(dh->p), 2*need);
204 do {
205 if (dh->priv_key != NULL)
Damien Miller9ef95dd2002-01-22 23:10:33 +1100206 BN_clear_free(dh->priv_key);
Damien Millerda755162002-01-22 23:09:22 +1100207 if ((dh->priv_key = BN_new()) == NULL)
Damien Miller9709f902001-03-30 10:50:10 +1000208 fatal("dh_gen_key: BN_new failed");
209 /* generate a 2*need bits random private exponent */
Damien Miller6d6c5d22002-03-07 12:58:42 +1100210 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
211 fatal("dh_gen_key: BN_rand failed");
Damien Miller9709f902001-03-30 10:50:10 +1000212 if (DH_generate_key(dh) == 0)
213 fatal("DH_generate_key");
214 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
215 if (BN_is_bit_set(dh->priv_key, i))
216 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000217 debug2("dh_gen_key: priv key bits set: %d/%d",
Damien Miller9709f902001-03-30 10:50:10 +1000218 bits_set, BN_num_bits(dh->priv_key));
219 if (tries++ > 10)
220 fatal("dh_gen_key: too many bad keys: giving up");
221 } while (!dh_pub_is_valid(dh, dh->pub_key));
222}
223
224DH *
225dh_new_group_asc(const char *gen, const char *modulus)
226{
227 DH *dh;
Damien Miller9709f902001-03-30 10:50:10 +1000228
Damien Millerda755162002-01-22 23:09:22 +1100229 if ((dh = DH_new()) == NULL)
230 fatal("dh_new_group_asc: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000231
Ben Lindstrom206941f2001-04-15 14:27:16 +0000232 if (BN_hex2bn(&dh->p, modulus) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000233 fatal("BN_hex2bn p");
Ben Lindstrom206941f2001-04-15 14:27:16 +0000234 if (BN_hex2bn(&dh->g, gen) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000235 fatal("BN_hex2bn g");
236
237 return (dh);
238}
239
240/*
241 * This just returns the group, we still need to generate the exchange
242 * value.
243 */
244
245DH *
246dh_new_group(BIGNUM *gen, BIGNUM *modulus)
247{
248 DH *dh;
249
Damien Millerda755162002-01-22 23:09:22 +1100250 if ((dh = DH_new()) == NULL)
251 fatal("dh_new_group: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000252 dh->p = modulus;
253 dh->g = gen;
254
255 return (dh);
256}
257
258DH *
259dh_new_group1(void)
260{
261 static char *gen = "2", *group1 =
262 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
263 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
264 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
265 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
266 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
267 "FFFFFFFF" "FFFFFFFF";
268
269 return (dh_new_group_asc(gen, group1));
270}
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000271
272/*
273 * Estimates the group order for a Diffie-Hellman group that has an
274 * attack complexity approximately the same as O(2**bits). Estimate
275 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
276 */
277
278int
279dh_estimate(int bits)
280{
281
282 if (bits < 64)
283 return (512); /* O(2**63) */
284 if (bits < 128)
285 return (1024); /* O(2**86) */
286 if (bits < 192)
287 return (2048); /* O(2**116) */
288 return (4096); /* O(2**156) */
289}