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.22 2002/06/27 08:49:44 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 static 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 || *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 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");
85 if (BN_hex2bn(&dhg->g, gen) == 0)
86 goto failclean;
87
88 if (BN_hex2bn(&dhg->p, prime) == 0)
89 goto failclean;
90
91 if (BN_num_bits(dhg->p) != dhg->size)
92 goto failclean;
93
94 return (1);
95
96 failclean:
97 BN_clear_free(dhg->g);
98 BN_clear_free(dhg->p);
99 fail:
100 error("Bad prime description in line %d", linenum);
101 return (0);
102 }
103
104 DH *
105 choose_dh(int min, int wantbits, int max)
106 {
107 FILE *f;
108 char line[2048];
109 int best, bestcount, which;
110 int linenum;
111 struct dhgroup dhg;
112
113 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);
116 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;
125 BN_clear_free(dhg.g);
126 BN_clear_free(dhg.p);
127
128 if (dhg.size > max || dhg.size < min)
129 continue;
130
131 if ((dhg.size > wantbits && dhg.size < best) ||
132 (dhg.size > best && best < wantbits)) {
133 best = dhg.size;
134 bestcount = 0;
135 }
136 if (dhg.size == best)
137 bestcount++;
138 }
139 rewind(f);
140
141 if (bestcount == 0) {
142 fclose(f);
143 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
144 return (NULL);
145 }
146
147 linenum = 0;
148 which = arc4random() % bestcount;
149 while (fgets(line, sizeof(line), f)) {
150 if (!parse_prime(linenum, line, &dhg))
151 continue;
152 if ((dhg.size > max || dhg.size < min) ||
153 dhg.size != best ||
154 linenum++ != which) {
155 BN_clear_free(dhg.g);
156 BN_clear_free(dhg.p);
157 continue;
158 }
159 break;
160 }
161 fclose(f);
162 if (linenum != which+1)
163 fatal("WARNING: line %d disappeared in %s, giving up",
164 which, _PATH_DH_PRIMES);
165
166 return (dh_new_group(dhg.g, dhg.p));
167 }
168
169 /* diffie-hellman-group1-sha1 */
170
171 int
172 dh_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++;
185 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
186
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
194 void
195 dh_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)
206 BN_clear_free(dh->priv_key);
207 if ((dh->priv_key = BN_new()) == NULL)
208 fatal("dh_gen_key: BN_new failed");
209 /* generate a 2*need bits random private exponent */
210 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
211 fatal("dh_gen_key: BN_rand failed");
212 if (DH_generate_key(dh) == 0)
213 fatal("dh_gen_key: DH_generate_key() failed");
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++;
217 debug("dh_gen_key: priv key bits set: %d/%d",
218 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
224 DH *
225 dh_new_group_asc(const char *gen, const char *modulus)
226 {
227 DH *dh;
228
229 if ((dh = DH_new()) == NULL)
230 fatal("dh_new_group_asc: DH_new");
231
232 if (BN_hex2bn(&dh->p, modulus) == 0)
233 fatal("BN_hex2bn p");
234 if (BN_hex2bn(&dh->g, gen) == 0)
235 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
245 DH *
246 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
247 {
248 DH *dh;
249
250 if ((dh = DH_new()) == NULL)
251 fatal("dh_new_group: DH_new");
252 dh->p = modulus;
253 dh->g = gen;
254
255 return (dh);
256 }
257
258 DH *
259 dh_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 }
271
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
278 int
279 dh_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 }