blob: 176fb74696fc09d88ea253caa2de59cb1703da4a [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"
Damien Millerf675fc42004-06-15 10:30:09 +100026RCSID("$OpenBSD: dh.c,v 1.30 2004/06/13 12:53:24 djm 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
Darren Tuckerfc113c92004-02-29 20:12:33 +110094 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
95 goto failclean;
96
Damien Miller874d77b2000-10-14 16:23:11 +110097 return (1);
Damien Miller23e526e2001-03-30 10:47:43 +100098
99 failclean:
Damien Miller9ef95dd2002-01-22 23:10:33 +1100100 BN_clear_free(dhg->g);
101 BN_clear_free(dhg->p);
Damien Miller874d77b2000-10-14 16:23:11 +1100102 fail:
Ben Lindstrom6df8ef42001-03-05 07:47:23 +0000103 error("Bad prime description in line %d", linenum);
Damien Miller874d77b2000-10-14 16:23:11 +1100104 return (0);
105}
106
107DH *
Ben Lindstromdf221392001-03-29 00:36:16 +0000108choose_dh(int min, int wantbits, int max)
Damien Miller874d77b2000-10-14 16:23:11 +1100109{
110 FILE *f;
Darren Tuckerc56c7ef2004-02-29 20:13:34 +1100111 char line[4096];
Damien Miller874d77b2000-10-14 16:23:11 +1100112 int best, bestcount, which;
113 int linenum;
114 struct dhgroup dhg;
115
Ben Lindstrom93a29e02001-06-25 04:13:25 +0000116 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
117 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
Damien Millerf675fc42004-06-15 10:30:09 +1000118 logit("WARNING: %s does not exist, using fixed modulus",
119 _PATH_DH_MODULI);
120 return (dh_new_group14());
Damien Miller874d77b2000-10-14 16:23:11 +1100121 }
122
123 linenum = 0;
124 best = bestcount = 0;
125 while (fgets(line, sizeof(line), f)) {
126 linenum++;
127 if (!parse_prime(linenum, line, &dhg))
128 continue;
Damien Miller9ef95dd2002-01-22 23:10:33 +1100129 BN_clear_free(dhg.g);
130 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100131
Ben Lindstromdf221392001-03-29 00:36:16 +0000132 if (dhg.size > max || dhg.size < min)
133 continue;
134
135 if ((dhg.size > wantbits && dhg.size < best) ||
136 (dhg.size > best && best < wantbits)) {
Damien Miller874d77b2000-10-14 16:23:11 +1100137 best = dhg.size;
138 bestcount = 0;
139 }
140 if (dhg.size == best)
141 bestcount++;
142 }
Ben Lindstromaf738802001-06-25 04:18:59 +0000143 rewind(f);
Damien Miller874d77b2000-10-14 16:23:11 +1100144
145 if (bestcount == 0) {
Ben Lindstromaf738802001-06-25 04:18:59 +0000146 fclose(f);
Damien Miller996acd22003-04-09 20:59:48 +1000147 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
Ben Lindstromdf221392001-03-29 00:36:16 +0000148 return (NULL);
Damien Miller874d77b2000-10-14 16:23:11 +1100149 }
150
Damien Miller874d77b2000-10-14 16:23:11 +1100151 linenum = 0;
152 which = arc4random() % bestcount;
153 while (fgets(line, sizeof(line), f)) {
154 if (!parse_prime(linenum, line, &dhg))
155 continue;
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000156 if ((dhg.size > max || dhg.size < min) ||
157 dhg.size != best ||
158 linenum++ != which) {
Damien Miller9ef95dd2002-01-22 23:10:33 +1100159 BN_clear_free(dhg.g);
160 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100161 continue;
162 }
163 break;
164 }
165 fclose(f);
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000166 if (linenum != which+1)
167 fatal("WARNING: line %d disappeared in %s, giving up",
168 which, _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100169
170 return (dh_new_group(dhg.g, dhg.p));
171}
Damien Miller9709f902001-03-30 10:50:10 +1000172
Damien Millerf675fc42004-06-15 10:30:09 +1000173/* diffie-hellman-groupN-sha1 */
Damien Miller9709f902001-03-30 10:50:10 +1000174
175int
176dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
177{
178 int i;
179 int n = BN_num_bits(dh_pub);
180 int bits_set = 0;
181
182 if (dh_pub->neg) {
Damien Miller996acd22003-04-09 20:59:48 +1000183 logit("invalid public DH value: negativ");
Damien Miller9709f902001-03-30 10:50:10 +1000184 return 0;
185 }
186 for (i = 0; i <= n; i++)
187 if (BN_is_bit_set(dh_pub, i))
188 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000189 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000190
191 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
192 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
193 return 1;
Damien Miller996acd22003-04-09 20:59:48 +1000194 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000195 return 0;
196}
197
198void
199dh_gen_key(DH *dh, int need)
200{
Darren Tuckereffc84c2004-02-29 20:15:08 +1100201 int i, bits_set, tries = 0;
Damien Miller9709f902001-03-30 10:50:10 +1000202
203 if (dh->p == NULL)
204 fatal("dh_gen_key: dh->p == NULL");
Darren Tuckerc0815c92003-09-22 21:05:50 +1000205 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
Damien Miller9709f902001-03-30 10:50:10 +1000206 fatal("dh_gen_key: group too small: %d (2*need %d)",
207 BN_num_bits(dh->p), 2*need);
208 do {
209 if (dh->priv_key != NULL)
Damien Miller9ef95dd2002-01-22 23:10:33 +1100210 BN_clear_free(dh->priv_key);
Damien Millerda755162002-01-22 23:09:22 +1100211 if ((dh->priv_key = BN_new()) == NULL)
Damien Miller9709f902001-03-30 10:50:10 +1000212 fatal("dh_gen_key: BN_new failed");
213 /* generate a 2*need bits random private exponent */
Damien Miller6d6c5d22002-03-07 12:58:42 +1100214 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
215 fatal("dh_gen_key: BN_rand failed");
Damien Miller9709f902001-03-30 10:50:10 +1000216 if (DH_generate_key(dh) == 0)
217 fatal("DH_generate_key");
Darren Tuckereffc84c2004-02-29 20:15:08 +1100218 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
Damien Miller9709f902001-03-30 10:50:10 +1000219 if (BN_is_bit_set(dh->priv_key, i))
220 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000221 debug2("dh_gen_key: priv key bits set: %d/%d",
Damien Miller9709f902001-03-30 10:50:10 +1000222 bits_set, BN_num_bits(dh->priv_key));
223 if (tries++ > 10)
224 fatal("dh_gen_key: too many bad keys: giving up");
225 } while (!dh_pub_is_valid(dh, dh->pub_key));
226}
227
228DH *
229dh_new_group_asc(const char *gen, const char *modulus)
230{
231 DH *dh;
Damien Miller9709f902001-03-30 10:50:10 +1000232
Damien Millerda755162002-01-22 23:09:22 +1100233 if ((dh = DH_new()) == NULL)
234 fatal("dh_new_group_asc: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000235
Ben Lindstrom206941f2001-04-15 14:27:16 +0000236 if (BN_hex2bn(&dh->p, modulus) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000237 fatal("BN_hex2bn p");
Ben Lindstrom206941f2001-04-15 14:27:16 +0000238 if (BN_hex2bn(&dh->g, gen) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000239 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
249DH *
250dh_new_group(BIGNUM *gen, BIGNUM *modulus)
251{
252 DH *dh;
253
Damien Millerda755162002-01-22 23:09:22 +1100254 if ((dh = DH_new()) == NULL)
255 fatal("dh_new_group: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000256 dh->p = modulus;
257 dh->g = gen;
258
259 return (dh);
260}
261
262DH *
263dh_new_group1(void)
264{
265 static char *gen = "2", *group1 =
266 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
267 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
268 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
269 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
270 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
271 "FFFFFFFF" "FFFFFFFF";
272
273 return (dh_new_group_asc(gen, group1));
274}
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000275
Damien Millerf675fc42004-06-15 10:30:09 +1000276DH *
277dh_new_group14(void)
278{
279 static char *gen = "2", *group14 =
280 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
281 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
282 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
283 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
284 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
285 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
286 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
287 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
288 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
289 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
290 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
291
292 return (dh_new_group_asc(gen, group14));
293}
294
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000295/*
296 * Estimates the group order for a Diffie-Hellman group that has an
297 * attack complexity approximately the same as O(2**bits). Estimate
298 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
299 */
300
301int
302dh_estimate(int bits)
303{
304
Damien Miller8975ddf2003-12-17 16:33:53 +1100305 if (bits <= 128)
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000306 return (1024); /* O(2**86) */
Damien Miller8975ddf2003-12-17 16:33:53 +1100307 if (bits <= 192)
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000308 return (2048); /* O(2**116) */
309 return (4096); /* O(2**156) */
310}