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/opensslconf.h>
31 #include <openssl/bn.h>
32 #include <openssl/dh.h>
33 #include <openssl/evp.h>
34
35 #include "buffer.h"
36 #include "cipher.h"
37 #include "kex.h"
38 #include "dh.h"
39 #include "pathnames.h"
40 #include "log.h"
41 #include "misc.h"
42
43 static int
44 parse_prime(int linenum, char *line, struct dhgroup *dhg)
45 {
46 char *cp, *arg;
47 char *strsize, *gen, *prime;
48
49 cp = line;
50 arg = strdelim(&cp);
51 /* Ignore leading whitespace */
52 if (*arg == '\0')
53 arg = strdelim(&cp);
54 if (!arg || !*arg || *arg == '#')
55 return 0;
56
57 /* time */
58 if (cp == NULL || *arg == '\0')
59 goto fail;
60 arg = strsep(&cp, " "); /* type */
61 if (cp == NULL || *arg == '\0')
62 goto fail;
63 arg = strsep(&cp, " "); /* tests */
64 if (cp == NULL || *arg == '\0')
65 goto fail;
66 arg = strsep(&cp, " "); /* tries */
67 if (cp == NULL || *arg == '\0')
68 goto fail;
69 strsize = strsep(&cp, " "); /* size */
70 if (cp == NULL || *strsize == '\0' ||
71 (dhg->size = atoi(strsize)) == 0)
72 goto fail;
73 /* The whole group is one bit larger */
74 dhg->size++;
75 gen = strsep(&cp, " "); /* gen */
76 if (cp == NULL || *gen == '\0')
77 goto fail;
78 prime = strsep(&cp, " "); /* prime */
79 if (cp != NULL || *prime == '\0')
80 goto fail;
81
82 if ((dhg->g = BN_new()) == NULL)
83 fatal("parse_prime: BN_new failed");
84 if ((dhg->p = BN_new()) == NULL)
85 fatal("parse_prime: BN_new failed");
86 if (BN_hex2bn(&dhg->g, gen) == 0)
87 goto failclean;
88
89 if (BN_hex2bn(&dhg->p, prime) == 0)
90 goto failclean;
91
92 if (BN_num_bits(dhg->p) != dhg->size)
93 goto failclean;
94
95 return (1);
96
97 failclean:
98 BN_clear_free(dhg->g);
99 BN_clear_free(dhg->p);
100 fail:
101 error("Bad prime description in line %d", linenum);
102 return (0);
103 }
104
105 DH *
106 choose_dh(int min, int wantbits, int max)
107 {
108 FILE *f;
109 char line[2048];
110 int best, bestcount, which;
111 int linenum;
112 struct dhgroup dhg;
113
114 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
115 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
116 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
117 return (dh_new_group1());
118 }
119
120 linenum = 0;
121 best = bestcount = 0;
122 while (fgets(line, sizeof(line), f)) {
123 linenum++;
124 if (!parse_prime(linenum, line, &dhg))
125 continue;
126 BN_clear_free(dhg.g);
127 BN_clear_free(dhg.p);
128
129 if (dhg.size > max || dhg.size < min)
130 continue;
131
132 if ((dhg.size > wantbits && dhg.size < best) ||
133 (dhg.size > best && best < wantbits)) {
134 best = dhg.size;
135 bestcount = 0;
136 }
137 if (dhg.size == best)
138 bestcount++;
139 }
140 rewind(f);
141
142 if (bestcount == 0) {
143 fclose(f);
144 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
145 return (NULL);
146 }
147
148 linenum = 0;
149 which = arc4random() % bestcount;
150 while (fgets(line, sizeof(line), f)) {
151 if (!parse_prime(linenum, line, &dhg))
152 continue;
153 if ((dhg.size > max || dhg.size < min) ||
154 dhg.size != best ||
155 linenum++ != which) {
156 BN_clear_free(dhg.g);
157 BN_clear_free(dhg.p);
158 continue;
159 }
160 break;
161 }
162 fclose(f);
163 if (linenum != which+1)
164 fatal("WARNING: line %d disappeared in %s, giving up",
165 which, _PATH_DH_PRIMES);
166
167 return (dh_new_group(dhg.g, dhg.p));
168 }
169
170 /* diffie-hellman-group1-sha1 */
171
172 int
173 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
174 {
175 int i;
176 int n = BN_num_bits(dh_pub);
177 int bits_set = 0;
178
179 if (dh_pub->neg) {
180 log("invalid public DH value: negativ");
181 return 0;
182 }
183 for (i = 0; i <= n; i++)
184 if (BN_is_bit_set(dh_pub, i))
185 bits_set++;
186 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
187
188 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
189 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
190 return 1;
191 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
192 return 0;
193 }
194
195 void
196 dh_gen_key(DH *dh, int need)
197 {
198 int i, bits_set = 0, tries = 0;
199
200 if (dh->p == NULL)
201 fatal("dh_gen_key: dh->p == NULL");
202 if (2*need >= BN_num_bits(dh->p))
203 fatal("dh_gen_key: group too small: %d (2*need %d)",
204 BN_num_bits(dh->p), 2*need);
205 do {
206 if (dh->priv_key != NULL)
207 BN_clear_free(dh->priv_key);
208 if ((dh->priv_key = BN_new()) == NULL)
209 fatal("dh_gen_key: BN_new failed");
210 /* generate a 2*need bits random private exponent */
211 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
212 fatal("dh_gen_key: BN_rand failed");
213 if (DH_generate_key(dh) == 0)
214 fatal("dh_gen_key: DH_generate_key() failed");
215 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
216 if (BN_is_bit_set(dh->priv_key, i))
217 bits_set++;
218 debug("dh_gen_key: priv key bits set: %d/%d",
219 bits_set, BN_num_bits(dh->priv_key));
220 if (tries++ > 10)
221 fatal("dh_gen_key: too many bad keys: giving up");
222 } while (!dh_pub_is_valid(dh, dh->pub_key));
223 }
224
225 DH *
226 dh_new_group_asc(const char *gen, const char *modulus)
227 {
228 DH *dh;
229
230 if ((dh = DH_new()) == NULL)
231 fatal("dh_new_group_asc: DH_new");
232
233 if (BN_hex2bn(&dh->p, modulus) == 0)
234 fatal("BN_hex2bn p");
235 if (BN_hex2bn(&dh->g, gen) == 0)
236 fatal("BN_hex2bn g");
237
238 return (dh);
239 }
240
241 /*
242 * This just returns the group, we still need to generate the exchange
243 * value.
244 */
245
246 DH *
247 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
248 {
249 DH *dh;
250
251 if ((dh = DH_new()) == NULL)
252 fatal("dh_new_group: DH_new");
253 dh->p = modulus;
254 dh->g = gen;
255
256 return (dh);
257 }
258
259 DH *
260 dh_new_group1(void)
261 {
262 static char *gen = "2", *group1 =
263 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
264 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
265 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
266 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
267 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
268 "FFFFFFFF" "FFFFFFFF";
269
270 return (dh_new_group_asc(gen, group1));
271 }
272
273 /*
274 * Estimates the group order for a Diffie-Hellman group that has an
275 * attack complexity approximately the same as O(2**bits). Estimate
276 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
277 */
278
279 int
280 dh_estimate(int bits)
281 {
282
283 if (bits < 64)
284 return (512); /* O(2**63) */
285 if (bits < 128)
286 return (1024); /* O(2**86) */
287 if (bits < 192)
288 return (2048); /* O(2**116) */
289 return (4096); /* O(2**156) */
290 }