blob: 575522ddb5ec1a12dbba0ecf0825b73a96c84ec6 [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 Lindstrom206941f2001-04-15 14:27:16 +000026RCSID("$OpenBSD: dh.c,v 1.14 2001/04/15 08:43:45 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
42int
43parse_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;
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
81 dhg->g = BN_new();
Damien Miller874d77b2000-10-14 16:23:11 +110082 dhg->p = BN_new();
Ben Lindstrom206941f2001-04-15 14:27:16 +000083 if (BN_hex2bn(&dhg->g, gen) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +100084 goto failclean;
85
Ben Lindstrom206941f2001-04-15 14:27:16 +000086 if (BN_hex2bn(&dhg->p, prime) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +100087 goto failclean;
88
89 if (BN_num_bits(dhg->p) != dhg->size)
90 goto failclean;
Damien Miller874d77b2000-10-14 16:23:11 +110091
92 return (1);
Damien Miller23e526e2001-03-30 10:47:43 +100093
94 failclean:
95 BN_free(dhg->g);
96 BN_free(dhg->p);
Damien Miller874d77b2000-10-14 16:23:11 +110097 fail:
Ben Lindstrom6df8ef42001-03-05 07:47:23 +000098 error("Bad prime description in line %d", linenum);
Damien Miller874d77b2000-10-14 16:23:11 +110099 return (0);
100}
101
102DH *
Ben Lindstromdf221392001-03-29 00:36:16 +0000103choose_dh(int min, int wantbits, int max)
Damien Miller874d77b2000-10-14 16:23:11 +1100104{
105 FILE *f;
106 char line[1024];
107 int best, bestcount, which;
108 int linenum;
109 struct dhgroup dhg;
110
Ben Lindstrom226cfa02001-01-22 05:34:40 +0000111 f = fopen(_PATH_DH_PRIMES, "r");
Damien Miller874d77b2000-10-14 16:23:11 +1100112 if (!f) {
Ben Lindstrom226cfa02001-01-22 05:34:40 +0000113 log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100114 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
Ben Lindstromdf221392001-03-29 00:36:16 +0000126 if (dhg.size > max || dhg.size < min)
127 continue;
128
129 if ((dhg.size > wantbits && dhg.size < best) ||
130 (dhg.size > best && best < wantbits)) {
Damien Miller874d77b2000-10-14 16:23:11 +1100131 best = dhg.size;
132 bestcount = 0;
133 }
134 if (dhg.size == best)
135 bestcount++;
136 }
137 fclose (f);
138
139 if (bestcount == 0) {
Ben Lindstromdf221392001-03-29 00:36:16 +0000140 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
141 return (NULL);
Damien Miller874d77b2000-10-14 16:23:11 +1100142 }
143
Ben Lindstrom226cfa02001-01-22 05:34:40 +0000144 f = fopen(_PATH_DH_PRIMES, "r");
Damien Miller874d77b2000-10-14 16:23:11 +1100145 if (!f) {
Ben Lindstrombe6a5a62001-03-06 01:13:06 +0000146 fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100147 }
148
149 linenum = 0;
150 which = arc4random() % bestcount;
151 while (fgets(line, sizeof(line), f)) {
152 if (!parse_prime(linenum, line, &dhg))
153 continue;
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000154 if ((dhg.size > max || dhg.size < min) ||
155 dhg.size != best ||
156 linenum++ != which) {
Damien Miller874d77b2000-10-14 16:23:11 +1100157 BN_free(dhg.g);
158 BN_free(dhg.p);
159 continue;
160 }
161 break;
162 }
163 fclose(f);
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000164 if (linenum != which+1)
165 fatal("WARNING: line %d disappeared in %s, giving up",
166 which, _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100167
168 return (dh_new_group(dhg.g, dhg.p));
169}
Damien Miller9709f902001-03-30 10:50:10 +1000170
171/* diffie-hellman-group1-sha1 */
172
173int
174dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
175{
176 int i;
177 int n = BN_num_bits(dh_pub);
178 int bits_set = 0;
179
180 if (dh_pub->neg) {
181 log("invalid public DH value: negativ");
182 return 0;
183 }
184 for (i = 0; i <= n; i++)
185 if (BN_is_bit_set(dh_pub, i))
186 bits_set++;
187 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
188
189 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
190 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
191 return 1;
192 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
193 return 0;
194}
195
196void
197dh_gen_key(DH *dh, int need)
198{
199 int i, bits_set = 0, tries = 0;
200
201 if (dh->p == NULL)
202 fatal("dh_gen_key: dh->p == NULL");
203 if (2*need >= BN_num_bits(dh->p))
204 fatal("dh_gen_key: group too small: %d (2*need %d)",
205 BN_num_bits(dh->p), 2*need);
206 do {
207 if (dh->priv_key != NULL)
208 BN_free(dh->priv_key);
209 dh->priv_key = BN_new();
210 if (dh->priv_key == NULL)
211 fatal("dh_gen_key: BN_new failed");
212 /* generate a 2*need bits random private exponent */
213 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
214 fatal("dh_gen_key: BN_rand failed");
215 if (DH_generate_key(dh) == 0)
216 fatal("DH_generate_key");
217 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
218 if (BN_is_bit_set(dh->priv_key, i))
219 bits_set++;
220 debug("dh_gen_key: priv key bits set: %d/%d",
221 bits_set, BN_num_bits(dh->priv_key));
222 if (tries++ > 10)
223 fatal("dh_gen_key: too many bad keys: giving up");
224 } while (!dh_pub_is_valid(dh, dh->pub_key));
225}
226
227DH *
228dh_new_group_asc(const char *gen, const char *modulus)
229{
230 DH *dh;
Damien Miller9709f902001-03-30 10:50:10 +1000231
232 dh = DH_new();
233 if (dh == NULL)
234 fatal("DH_new");
235
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
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
263DH *
264dh_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}
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000276
277/*
278 * Estimates the group order for a Diffie-Hellman group that has an
279 * attack complexity approximately the same as O(2**bits). Estimate
280 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
281 */
282
283int
284dh_estimate(int bits)
285{
286
287 if (bits < 64)
288 return (512); /* O(2**63) */
289 if (bits < 128)
290 return (1024); /* O(2**86) */
291 if (bits < 192)
292 return (2048); /* O(2**116) */
293 return (4096); /* O(2**156) */
294}