blob: b32a7efb556228c5623baa80b2f9f7787c8d2394 [file] [log] [blame]
Damien Miller5a73c1a2006-03-31 23:09:41 +11001/* $OpenBSD: dh.c,v 1.35 2006/03/27 13:03:54 deraadt Exp $ */
Damien Miller874d77b2000-10-14 16:23:11 +11002/*
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"
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;
Damien Miller5a73c1a2006-03-31 23:09:41 +110047 const char *errstr = NULL;
Damien Miller874d77b2000-10-14 16:23:11 +110048
49 cp = line;
Damien Miller928b2362006-03-26 13:53:32 +110050 if ((arg = strdelim(&cp)) == NULL)
51 return 0;
Damien Miller874d77b2000-10-14 16:23:11 +110052 /* Ignore leading whitespace */
53 if (*arg == '\0')
54 arg = strdelim(&cp);
Ben Lindstrom04f9af72002-07-04 00:03:56 +000055 if (!arg || !*arg || *arg == '#')
Damien Miller874d77b2000-10-14 16:23:11 +110056 return 0;
57
58 /* time */
59 if (cp == NULL || *arg == '\0')
60 goto fail;
61 arg = strsep(&cp, " "); /* type */
62 if (cp == NULL || *arg == '\0')
63 goto fail;
64 arg = strsep(&cp, " "); /* tests */
65 if (cp == NULL || *arg == '\0')
66 goto fail;
67 arg = strsep(&cp, " "); /* tries */
68 if (cp == NULL || *arg == '\0')
69 goto fail;
70 strsize = strsep(&cp, " "); /* size */
71 if (cp == NULL || *strsize == '\0' ||
Damien Miller5a73c1a2006-03-31 23:09:41 +110072 (dhg->size = (u_int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
73 errstr)
Damien Miller874d77b2000-10-14 16:23:11 +110074 goto fail;
Ben Lindstromdf221392001-03-29 00:36:16 +000075 /* The whole group is one bit larger */
76 dhg->size++;
Damien Miller874d77b2000-10-14 16:23:11 +110077 gen = strsep(&cp, " "); /* gen */
78 if (cp == NULL || *gen == '\0')
79 goto fail;
80 prime = strsep(&cp, " "); /* prime */
81 if (cp != NULL || *prime == '\0')
82 goto fail;
83
Damien Millerda755162002-01-22 23:09:22 +110084 if ((dhg->g = BN_new()) == NULL)
85 fatal("parse_prime: BN_new failed");
86 if ((dhg->p = BN_new()) == NULL)
87 fatal("parse_prime: BN_new failed");
Ben Lindstrom206941f2001-04-15 14:27:16 +000088 if (BN_hex2bn(&dhg->g, gen) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +100089 goto failclean;
90
Ben Lindstrom206941f2001-04-15 14:27:16 +000091 if (BN_hex2bn(&dhg->p, prime) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +100092 goto failclean;
93
94 if (BN_num_bits(dhg->p) != dhg->size)
95 goto failclean;
Damien Miller874d77b2000-10-14 16:23:11 +110096
Darren Tuckerfc113c92004-02-29 20:12:33 +110097 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
98 goto failclean;
99
Damien Miller874d77b2000-10-14 16:23:11 +1100100 return (1);
Damien Miller23e526e2001-03-30 10:47:43 +1000101
102 failclean:
Damien Miller9ef95dd2002-01-22 23:10:33 +1100103 BN_clear_free(dhg->g);
104 BN_clear_free(dhg->p);
Damien Miller874d77b2000-10-14 16:23:11 +1100105 fail:
Ben Lindstrom6df8ef42001-03-05 07:47:23 +0000106 error("Bad prime description in line %d", linenum);
Damien Miller874d77b2000-10-14 16:23:11 +1100107 return (0);
108}
109
110DH *
Ben Lindstromdf221392001-03-29 00:36:16 +0000111choose_dh(int min, int wantbits, int max)
Damien Miller874d77b2000-10-14 16:23:11 +1100112{
113 FILE *f;
Darren Tuckerc56c7ef2004-02-29 20:13:34 +1100114 char line[4096];
Damien Miller874d77b2000-10-14 16:23:11 +1100115 int best, bestcount, which;
116 int linenum;
117 struct dhgroup dhg;
118
Ben Lindstrom93a29e02001-06-25 04:13:25 +0000119 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
120 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
Damien Millerf675fc42004-06-15 10:30:09 +1000121 logit("WARNING: %s does not exist, using fixed modulus",
122 _PATH_DH_MODULI);
123 return (dh_new_group14());
Damien Miller874d77b2000-10-14 16:23:11 +1100124 }
125
126 linenum = 0;
127 best = bestcount = 0;
128 while (fgets(line, sizeof(line), f)) {
129 linenum++;
130 if (!parse_prime(linenum, line, &dhg))
131 continue;
Damien Miller9ef95dd2002-01-22 23:10:33 +1100132 BN_clear_free(dhg.g);
133 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100134
Ben Lindstromdf221392001-03-29 00:36:16 +0000135 if (dhg.size > max || dhg.size < min)
136 continue;
137
138 if ((dhg.size > wantbits && dhg.size < best) ||
139 (dhg.size > best && best < wantbits)) {
Damien Miller874d77b2000-10-14 16:23:11 +1100140 best = dhg.size;
141 bestcount = 0;
142 }
143 if (dhg.size == best)
144 bestcount++;
145 }
Ben Lindstromaf738802001-06-25 04:18:59 +0000146 rewind(f);
Damien Miller874d77b2000-10-14 16:23:11 +1100147
148 if (bestcount == 0) {
Ben Lindstromaf738802001-06-25 04:18:59 +0000149 fclose(f);
Damien Miller996acd22003-04-09 20:59:48 +1000150 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
Darren Tucker9a2bd112004-08-12 22:40:59 +1000151 return (dh_new_group14());
Damien Miller874d77b2000-10-14 16:23:11 +1100152 }
153
Damien Miller874d77b2000-10-14 16:23:11 +1100154 linenum = 0;
155 which = arc4random() % bestcount;
156 while (fgets(line, sizeof(line), f)) {
157 if (!parse_prime(linenum, line, &dhg))
158 continue;
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000159 if ((dhg.size > max || dhg.size < min) ||
160 dhg.size != best ||
161 linenum++ != which) {
Damien Miller9ef95dd2002-01-22 23:10:33 +1100162 BN_clear_free(dhg.g);
163 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100164 continue;
165 }
166 break;
167 }
168 fclose(f);
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000169 if (linenum != which+1)
170 fatal("WARNING: line %d disappeared in %s, giving up",
171 which, _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100172
173 return (dh_new_group(dhg.g, dhg.p));
174}
Damien Miller9709f902001-03-30 10:50:10 +1000175
Damien Millerf675fc42004-06-15 10:30:09 +1000176/* diffie-hellman-groupN-sha1 */
Damien Miller9709f902001-03-30 10:50:10 +1000177
178int
179dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
180{
181 int i;
182 int n = BN_num_bits(dh_pub);
183 int bits_set = 0;
184
185 if (dh_pub->neg) {
Damien Miller996acd22003-04-09 20:59:48 +1000186 logit("invalid public DH value: negativ");
Damien Miller9709f902001-03-30 10:50:10 +1000187 return 0;
188 }
189 for (i = 0; i <= n; i++)
190 if (BN_is_bit_set(dh_pub, i))
191 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000192 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000193
194 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
195 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
196 return 1;
Damien Miller996acd22003-04-09 20:59:48 +1000197 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000198 return 0;
199}
200
201void
202dh_gen_key(DH *dh, int need)
203{
Darren Tuckereffc84c2004-02-29 20:15:08 +1100204 int i, bits_set, tries = 0;
Damien Miller9709f902001-03-30 10:50:10 +1000205
206 if (dh->p == NULL)
207 fatal("dh_gen_key: dh->p == NULL");
Darren Tuckerc0815c92003-09-22 21:05:50 +1000208 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
Damien Miller9709f902001-03-30 10:50:10 +1000209 fatal("dh_gen_key: group too small: %d (2*need %d)",
210 BN_num_bits(dh->p), 2*need);
211 do {
212 if (dh->priv_key != NULL)
Damien Miller9ef95dd2002-01-22 23:10:33 +1100213 BN_clear_free(dh->priv_key);
Damien Millerda755162002-01-22 23:09:22 +1100214 if ((dh->priv_key = BN_new()) == NULL)
Damien Miller9709f902001-03-30 10:50:10 +1000215 fatal("dh_gen_key: BN_new failed");
216 /* generate a 2*need bits random private exponent */
Damien Miller6d6c5d22002-03-07 12:58:42 +1100217 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
218 fatal("dh_gen_key: BN_rand failed");
Damien Miller9709f902001-03-30 10:50:10 +1000219 if (DH_generate_key(dh) == 0)
220 fatal("DH_generate_key");
Darren Tuckereffc84c2004-02-29 20:15:08 +1100221 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
Damien Miller9709f902001-03-30 10:50:10 +1000222 if (BN_is_bit_set(dh->priv_key, i))
223 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000224 debug2("dh_gen_key: priv key bits set: %d/%d",
Damien Miller9709f902001-03-30 10:50:10 +1000225 bits_set, BN_num_bits(dh->priv_key));
226 if (tries++ > 10)
227 fatal("dh_gen_key: too many bad keys: giving up");
228 } while (!dh_pub_is_valid(dh, dh->pub_key));
229}
230
231DH *
232dh_new_group_asc(const char *gen, const char *modulus)
233{
234 DH *dh;
Damien Miller9709f902001-03-30 10:50:10 +1000235
Damien Millerda755162002-01-22 23:09:22 +1100236 if ((dh = DH_new()) == NULL)
237 fatal("dh_new_group_asc: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000238
Ben Lindstrom206941f2001-04-15 14:27:16 +0000239 if (BN_hex2bn(&dh->p, modulus) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000240 fatal("BN_hex2bn p");
Ben Lindstrom206941f2001-04-15 14:27:16 +0000241 if (BN_hex2bn(&dh->g, gen) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000242 fatal("BN_hex2bn g");
243
244 return (dh);
245}
246
247/*
248 * This just returns the group, we still need to generate the exchange
249 * value.
250 */
251
252DH *
253dh_new_group(BIGNUM *gen, BIGNUM *modulus)
254{
255 DH *dh;
256
Damien Millerda755162002-01-22 23:09:22 +1100257 if ((dh = DH_new()) == NULL)
258 fatal("dh_new_group: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000259 dh->p = modulus;
260 dh->g = gen;
261
262 return (dh);
263}
264
265DH *
266dh_new_group1(void)
267{
268 static char *gen = "2", *group1 =
269 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
270 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
271 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
272 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
273 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
274 "FFFFFFFF" "FFFFFFFF";
275
276 return (dh_new_group_asc(gen, group1));
277}
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000278
Damien Millerf675fc42004-06-15 10:30:09 +1000279DH *
280dh_new_group14(void)
281{
282 static char *gen = "2", *group14 =
283 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
284 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
285 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
286 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
287 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
288 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
289 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
290 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
291 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
292 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
293 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
294
295 return (dh_new_group_asc(gen, group14));
296}
297
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000298/*
299 * Estimates the group order for a Diffie-Hellman group that has an
300 * attack complexity approximately the same as O(2**bits). Estimate
301 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
302 */
303
304int
305dh_estimate(int bits)
306{
307
Damien Miller8975ddf2003-12-17 16:33:53 +1100308 if (bits <= 128)
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000309 return (1024); /* O(2**86) */
Damien Miller8975ddf2003-12-17 16:33:53 +1100310 if (bits <= 192)
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000311 return (2048); /* O(2**116) */
312 return (4096); /* O(2**156) */
313}