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"
26RCSID("$OpenBSD: dh.c,v 1.31 2004/08/04 10:37:52 djm 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
42static int
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 || *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 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
95 goto failclean;
96
97 return (1);
98
99 failclean:
100 BN_clear_free(dhg->g);
101 BN_clear_free(dhg->p);
102 fail:
103 error("Bad prime description in line %d", linenum);
104 return (0);
105}
106
107DH *
108choose_dh(int min, int wantbits, int max)
109{
110 FILE *f;
111 char line[4096];
112 int best, bestcount, which;
113 int linenum;
114 struct dhgroup dhg;
115
116 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
117 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
118 logit("WARNING: %s does not exist, using fixed modulus",
119 _PATH_DH_MODULI);
120 return (dh_new_group14());
121 }
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;
129 BN_clear_free(dhg.g);
130 BN_clear_free(dhg.p);
131
132 if (dhg.size > max || dhg.size < min)
133 continue;
134
135 if ((dhg.size > wantbits && dhg.size < best) ||
136 (dhg.size > best && best < wantbits)) {
137 best = dhg.size;
138 bestcount = 0;
139 }
140 if (dhg.size == best)
141 bestcount++;
142 }
143 rewind(f);
144
145 if (bestcount == 0) {
146 fclose(f);
147 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
148 return (dh_new_group14());
149 }
150
151 linenum = 0;
152 which = arc4random() % bestcount;
153 while (fgets(line, sizeof(line), f)) {
154 if (!parse_prime(linenum, line, &dhg))
155 continue;
156 if ((dhg.size > max || dhg.size < min) ||
157 dhg.size != best ||
158 linenum++ != which) {
159 BN_clear_free(dhg.g);
160 BN_clear_free(dhg.p);
161 continue;
162 }
163 break;
164 }
165 fclose(f);
166 if (linenum != which+1)
167 fatal("WARNING: line %d disappeared in %s, giving up",
168 which, _PATH_DH_PRIMES);
169
170 return (dh_new_group(dhg.g, dhg.p));
171}
172
173/* diffie-hellman-groupN-sha1 */
174
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) {
183 logit("invalid public DH value: negativ");
184 return 0;
185 }
186 for (i = 0; i <= n; i++)
187 if (BN_is_bit_set(dh_pub, i))
188 bits_set++;
189 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
190
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;
194 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
195 return 0;
196}
197
198void
199dh_gen_key(DH *dh, int need)
200{
201 int i, bits_set, tries = 0;
202
203 if (dh->p == NULL)
204 fatal("dh_gen_key: dh->p == NULL");
205 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
206 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)
210 BN_clear_free(dh->priv_key);
211 if ((dh->priv_key = BN_new()) == NULL)
212 fatal("dh_gen_key: BN_new failed");
213 /* generate a 2*need bits random private exponent */
214 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
215 fatal("dh_gen_key: BN_rand failed");
216 if (DH_generate_key(dh) == 0)
217 fatal("DH_generate_key");
218 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
219 if (BN_is_bit_set(dh->priv_key, i))
220 bits_set++;
221 debug2("dh_gen_key: priv key bits set: %d/%d",
222 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;
232
233 if ((dh = DH_new()) == NULL)
234 fatal("dh_new_group_asc: DH_new");
235
236 if (BN_hex2bn(&dh->p, modulus) == 0)
237 fatal("BN_hex2bn p");
238 if (BN_hex2bn(&dh->g, gen) == 0)
239 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 if ((dh = DH_new()) == NULL)
255 fatal("dh_new_group: DH_new");
256 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}
275
276DH *
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
295/*
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
305 if (bits <= 128)
306 return (1024); /* O(2**86) */
307 if (bits <= 192)
308 return (2048); /* O(2**116) */
309 return (4096); /* O(2**156) */
310}
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"
26RCSID("$OpenBSD: dh.c,v 1.31 2004/08/04 10:37:52 djm 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
42static int
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 || *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 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
95 goto failclean;
96
97 return (1);
98
99 failclean:
100 BN_clear_free(dhg->g);
101 BN_clear_free(dhg->p);
102 fail:
103 error("Bad prime description in line %d", linenum);
104 return (0);
105}
106
107DH *
108choose_dh(int min, int wantbits, int max)
109{
110 FILE *f;
111 char line[4096];
112 int best, bestcount, which;
113 int linenum;
114 struct dhgroup dhg;
115
116 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
117 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
118 logit("WARNING: %s does not exist, using fixed modulus",
119 _PATH_DH_MODULI);
120 return (dh_new_group14());
121 }
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;
129 BN_clear_free(dhg.g);
130 BN_clear_free(dhg.p);
131
132 if (dhg.size > max || dhg.size < min)
133 continue;
134
135 if ((dhg.size > wantbits && dhg.size < best) ||
136 (dhg.size > best && best < wantbits)) {
137 best = dhg.size;
138 bestcount = 0;
139 }
140 if (dhg.size == best)
141 bestcount++;
142 }
143 rewind(f);
144
145 if (bestcount == 0) {
146 fclose(f);
147 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
148 return (dh_new_group14());
149 }
150
151 linenum = 0;
152 which = arc4random() % bestcount;
153 while (fgets(line, sizeof(line), f)) {
154 if (!parse_prime(linenum, line, &dhg))
155 continue;
156 if ((dhg.size > max || dhg.size < min) ||
157 dhg.size != best ||
158 linenum++ != which) {
159 BN_clear_free(dhg.g);
160 BN_clear_free(dhg.p);
161 continue;
162 }
163 break;
164 }
165 fclose(f);
166 if (linenum != which+1)
167 fatal("WARNING: line %d disappeared in %s, giving up",
168 which, _PATH_DH_PRIMES);
169
170 return (dh_new_group(dhg.g, dhg.p));
171}
172
173/* diffie-hellman-groupN-sha1 */
174
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) {
183 logit("invalid public DH value: negativ");
184 return 0;
185 }
186 for (i = 0; i <= n; i++)
187 if (BN_is_bit_set(dh_pub, i))
188 bits_set++;
189 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
190
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;
194 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
195 return 0;
196}
197
198void
199dh_gen_key(DH *dh, int need)
200{
201 int i, bits_set, tries = 0;
202
203 if (dh->p == NULL)
204 fatal("dh_gen_key: dh->p == NULL");
205 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
206 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)
210 BN_clear_free(dh->priv_key);
211 if ((dh->priv_key = BN_new()) == NULL)
212 fatal("dh_gen_key: BN_new failed");
213 /* generate a 2*need bits random private exponent */
214 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
215 fatal("dh_gen_key: BN_rand failed");
216 if (DH_generate_key(dh) == 0)
217 fatal("DH_generate_key");
218 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
219 if (BN_is_bit_set(dh->priv_key, i))
220 bits_set++;
221 debug2("dh_gen_key: priv key bits set: %d/%d",
222 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;
232
233 if ((dh = DH_new()) == NULL)
234 fatal("dh_new_group_asc: DH_new");
235
236 if (BN_hex2bn(&dh->p, modulus) == 0)
237 fatal("BN_hex2bn p");
238 if (BN_hex2bn(&dh->g, gen) == 0)
239 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 if ((dh = DH_new()) == NULL)
255 fatal("dh_new_group: DH_new");
256 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}
275
276DH *
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
295/*
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
305 if (bits <= 128)
306 return (1024); /* O(2**86) */
307 if (bits <= 192)
308 return (2048); /* O(2**116) */
309 return (4096); /* O(2**156) */
310}