Branch data Line data Source code
1 : : /* $OpenBSD: dh.c,v 1.53 2013/11/21 00:45:44 djm Exp $ */
2 : : /*
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"
27 : :
28 : : #include <sys/param.h>
29 : :
30 : : #include <openssl/bn.h>
31 : : #include <openssl/dh.h>
32 : :
33 : : #include <stdarg.h>
34 : : #include <stdio.h>
35 : : #include <stdlib.h>
36 : : #include <string.h>
37 : :
38 : : #include "dh.h"
39 : : #include "pathnames.h"
40 : : #include "log.h"
41 : : #include "misc.h"
42 : :
43 : : static int
44 : 0 : parse_prime(int linenum, char *line, struct dhgroup *dhg)
45 : : {
46 : : char *cp, *arg;
47 : : char *strsize, *gen, *prime;
48 : 0 : const char *errstr = NULL;
49 : : long long n;
50 : :
51 : 0 : dhg->p = dhg->g = NULL;
52 : 0 : cp = line;
53 [ # # ]: 0 : if ((arg = strdelim(&cp)) == NULL)
54 : : return 0;
55 : : /* Ignore leading whitespace */
56 [ # # ]: 0 : if (*arg == '\0')
57 : 0 : arg = strdelim(&cp);
58 [ # # ][ # # ]: 0 : if (!arg || !*arg || *arg == '#')
[ # # ]
59 : : return 0;
60 : :
61 : : /* time */
62 [ # # ][ # # ]: 0 : if (cp == NULL || *arg == '\0')
63 : : goto truncated;
64 : 0 : arg = strsep(&cp, " "); /* type */
65 [ # # ][ # # ]: 0 : if (cp == NULL || *arg == '\0')
66 : : goto truncated;
67 : : /* Ensure this is a safe prime */
68 : 0 : n = strtonum(arg, 0, 5, &errstr);
69 [ # # ][ # # ]: 0 : if (errstr != NULL || n != MODULI_TYPE_SAFE) {
70 : 0 : error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
71 : 0 : goto fail;
72 : : }
73 : 0 : arg = strsep(&cp, " "); /* tests */
74 [ # # ][ # # ]: 0 : if (cp == NULL || *arg == '\0')
75 : : goto truncated;
76 : : /* Ensure prime has been tested and is not composite */
77 : 0 : n = strtonum(arg, 0, 0x1f, &errstr);
78 [ # # ][ # # ]: 0 : if (errstr != NULL ||
79 [ # # ]: 0 : (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
80 : 0 : error("moduli:%d: invalid moduli tests flag", linenum);
81 : 0 : goto fail;
82 : : }
83 : 0 : arg = strsep(&cp, " "); /* tries */
84 [ # # ][ # # ]: 0 : if (cp == NULL || *arg == '\0')
85 : : goto truncated;
86 : 0 : n = strtonum(arg, 0, 1<<30, &errstr);
87 [ # # ][ # # ]: 0 : if (errstr != NULL || n == 0) {
88 : 0 : error("moduli:%d: invalid primality trial count", linenum);
89 : 0 : goto fail;
90 : : }
91 : 0 : strsize = strsep(&cp, " "); /* size */
92 [ # # ]: 0 : if (cp == NULL || *strsize == '\0' ||
[ # # # # ]
93 [ # # ]: 0 : (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
94 : : errstr) {
95 : 0 : error("moduli:%d: invalid prime length", linenum);
96 : 0 : goto fail;
97 : : }
98 : : /* The whole group is one bit larger */
99 : 0 : dhg->size++;
100 : 0 : gen = strsep(&cp, " "); /* gen */
101 [ # # ][ # # ]: 0 : if (cp == NULL || *gen == '\0')
102 : : goto truncated;
103 : 0 : prime = strsep(&cp, " "); /* prime */
104 [ # # ][ # # ]: 0 : if (cp != NULL || *prime == '\0') {
105 : : truncated:
106 : 0 : error("moduli:%d: truncated", linenum);
107 : 0 : goto fail;
108 : : }
109 : :
110 [ # # ]: 0 : if ((dhg->g = BN_new()) == NULL)
111 : 0 : fatal("parse_prime: BN_new failed");
112 [ # # ]: 0 : if ((dhg->p = BN_new()) == NULL)
113 : 0 : fatal("parse_prime: BN_new failed");
114 [ # # ]: 0 : if (BN_hex2bn(&dhg->g, gen) == 0) {
115 : 0 : error("moduli:%d: could not parse generator value", linenum);
116 : 0 : goto fail;
117 : : }
118 [ # # ]: 0 : if (BN_hex2bn(&dhg->p, prime) == 0) {
119 : 0 : error("moduli:%d: could not parse prime value", linenum);
120 : 0 : goto fail;
121 : : }
122 [ # # ]: 0 : if (BN_num_bits(dhg->p) != dhg->size) {
123 : 0 : error("moduli:%d: prime has wrong size: actual %d listed %d",
124 : 0 : linenum, BN_num_bits(dhg->p), dhg->size - 1);
125 : 0 : goto fail;
126 : : }
127 [ # # ]: 0 : if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
128 : 0 : error("moduli:%d: generator is invalid", linenum);
129 : 0 : goto fail;
130 : : }
131 : :
132 : : return 1;
133 : :
134 : : fail:
135 [ # # ]: 0 : if (dhg->g != NULL)
136 : 0 : BN_clear_free(dhg->g);
137 [ # # ]: 0 : if (dhg->p != NULL)
138 : 0 : BN_clear_free(dhg->p);
139 : 0 : dhg->g = dhg->p = NULL;
140 : 0 : error("Bad prime description in line %d", linenum);
141 : 0 : return 0;
142 : : }
143 : :
144 : : DH *
145 : 16 : choose_dh(int min, int wantbits, int max)
146 : : {
147 : : FILE *f;
148 : : char line[4096];
149 : : int best, bestcount, which;
150 : : int linenum;
151 : : struct dhgroup dhg;
152 : :
153 [ + - ][ + - ]: 16 : if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
154 : : (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
155 : 16 : logit("WARNING: %s does not exist, using fixed modulus",
156 : : _PATH_DH_MODULI);
157 : 16 : return (dh_new_group14());
158 : : }
159 : :
160 : 0 : linenum = 0;
161 : 0 : best = bestcount = 0;
162 [ # # ]: 0 : while (fgets(line, sizeof(line), f)) {
163 : 0 : linenum++;
164 [ # # ]: 0 : if (!parse_prime(linenum, line, &dhg))
165 : 0 : continue;
166 : 0 : BN_clear_free(dhg.g);
167 : 0 : BN_clear_free(dhg.p);
168 : :
169 [ # # ][ # # ]: 0 : if (dhg.size > max || dhg.size < min)
170 : 0 : continue;
171 : :
172 [ # # ][ # # ]: 0 : if ((dhg.size > wantbits && dhg.size < best) ||
[ # # ]
173 [ # # ]: 0 : (dhg.size > best && best < wantbits)) {
174 : 0 : best = dhg.size;
175 : 0 : bestcount = 0;
176 : : }
177 [ # # ]: 0 : if (dhg.size == best)
178 : 0 : bestcount++;
179 : : }
180 : 0 : rewind(f);
181 : :
182 [ # # ]: 0 : if (bestcount == 0) {
183 : 0 : fclose(f);
184 : 0 : logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
185 : 0 : return (dh_new_group14());
186 : : }
187 : :
188 : 0 : linenum = 0;
189 : 0 : which = arc4random_uniform(bestcount);
190 [ # # ]: 0 : while (fgets(line, sizeof(line), f)) {
191 [ # # ]: 0 : if (!parse_prime(linenum, line, &dhg))
192 : 0 : continue;
193 [ # # ][ # # ]: 0 : if ((dhg.size > max || dhg.size < min) ||
[ # # ]
194 [ # # ]: 0 : dhg.size != best ||
195 : 0 : linenum++ != which) {
196 : 0 : BN_clear_free(dhg.g);
197 : 0 : BN_clear_free(dhg.p);
198 : 0 : continue;
199 : : }
200 : : break;
201 : : }
202 : 0 : fclose(f);
203 [ # # ]: 0 : if (linenum != which+1)
204 : 0 : fatal("WARNING: line %d disappeared in %s, giving up",
205 : : which, _PATH_DH_PRIMES);
206 : :
207 : 0 : return (dh_new_group(dhg.g, dhg.p));
208 : : }
209 : :
210 : : /* diffie-hellman-groupN-sha1 */
211 : :
212 : : int
213 : 334 : dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
214 : : {
215 : : int i;
216 : 334 : int n = BN_num_bits(dh_pub);
217 : 334 : int bits_set = 0;
218 : : BIGNUM *tmp;
219 : :
220 [ - + ]: 334 : if (dh_pub->neg) {
221 : 0 : logit("invalid public DH value: negative");
222 : 0 : return 0;
223 : : }
224 [ - + ]: 334 : if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
225 : 0 : logit("invalid public DH value: <= 1");
226 : 0 : return 0;
227 : : }
228 : :
229 [ - + ]: 334 : if ((tmp = BN_new()) == NULL) {
230 : 0 : error("%s: BN_new failed", __func__);
231 : 0 : return 0;
232 : : }
233 [ + - - + ]: 668 : if (!BN_sub(tmp, dh->p, BN_value_one()) ||
234 : 334 : BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
235 : 0 : BN_clear_free(tmp);
236 : 0 : logit("invalid public DH value: >= p-1");
237 : 0 : return 0;
238 : : }
239 : 334 : BN_clear_free(tmp);
240 : :
241 [ + + ]: 553314 : for (i = 0; i <= n; i++)
242 [ + + ]: 552980 : if (BN_is_bit_set(dh_pub, i))
243 : 276108 : bits_set++;
244 : 334 : debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
245 : :
246 : : /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
247 [ - + ]: 334 : if (bits_set > 1)
248 : : return 1;
249 : :
250 : 0 : logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
251 : 0 : return 0;
252 : : }
253 : :
254 : : void
255 : 167 : dh_gen_key(DH *dh, int need)
256 : : {
257 : : int pbits;
258 : :
259 [ - + ]: 167 : if (need <= 0)
260 : 0 : fatal("%s: need <= 0", __func__);
261 [ - + ]: 167 : if (dh->p == NULL)
262 : 0 : fatal("%s: dh->p == NULL", __func__);
263 [ - + ]: 167 : if ((pbits = BN_num_bits(dh->p)) <= 0)
264 : 0 : fatal("%s: bits(p) <= 0", __func__);
265 : 167 : dh->length = MIN(need * 2, pbits - 1);
266 [ - + ]: 167 : if (DH_generate_key(dh) == 0)
267 : 0 : fatal("%s: key generation failed", __func__);
268 [ - + ]: 167 : if (!dh_pub_is_valid(dh, dh->pub_key))
269 : 0 : fatal("%s: generated invalid key", __func__);
270 : 167 : }
271 : :
272 : : DH *
273 : 119 : dh_new_group_asc(const char *gen, const char *modulus)
274 : : {
275 : : DH *dh;
276 : :
277 [ - + ]: 119 : if ((dh = DH_new()) == NULL)
278 : 0 : fatal("dh_new_group_asc: DH_new");
279 : :
280 [ - + ]: 119 : if (BN_hex2bn(&dh->p, modulus) == 0)
281 : 0 : fatal("BN_hex2bn p");
282 [ - + ]: 119 : if (BN_hex2bn(&dh->g, gen) == 0)
283 : 0 : fatal("BN_hex2bn g");
284 : :
285 : 119 : return (dh);
286 : : }
287 : :
288 : : /*
289 : : * This just returns the group, we still need to generate the exchange
290 : : * value.
291 : : */
292 : :
293 : : DH *
294 : 64 : dh_new_group(BIGNUM *gen, BIGNUM *modulus)
295 : : {
296 : : DH *dh;
297 : :
298 [ - + ]: 64 : if ((dh = DH_new()) == NULL)
299 : 0 : fatal("dh_new_group: DH_new");
300 : 64 : dh->p = modulus;
301 : 64 : dh->g = gen;
302 : :
303 : 64 : return (dh);
304 : : }
305 : :
306 : : DH *
307 : 64 : dh_new_group1(void)
308 : : {
309 : : static char *gen = "2", *group1 =
310 : : "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
311 : : "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
312 : : "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
313 : : "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
314 : : "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
315 : : "FFFFFFFF" "FFFFFFFF";
316 : :
317 : 64 : return (dh_new_group_asc(gen, group1));
318 : : }
319 : :
320 : : DH *
321 : 39 : dh_new_group14(void)
322 : : {
323 : : static char *gen = "2", *group14 =
324 : : "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
325 : : "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
326 : : "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
327 : : "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
328 : : "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
329 : : "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
330 : : "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
331 : : "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
332 : : "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
333 : : "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
334 : : "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
335 : :
336 : 55 : return (dh_new_group_asc(gen, group14));
337 : : }
338 : :
339 : : /*
340 : : * Estimates the group order for a Diffie-Hellman group that has an
341 : : * attack complexity approximately the same as O(2**bits).
342 : : * Values from NIST Special Publication 800-57: Recommendation for Key
343 : : * Management Part 1 (rev 3) limited by the recommended maximum value
344 : : * from RFC4419 section 3.
345 : : */
346 : :
347 : : int
348 : 48 : dh_estimate(int bits)
349 : : {
350 [ + - ]: 48 : if (bits <= 112)
351 : : return 2048;
352 [ + + ]: 48 : if (bits <= 128)
353 : : return 3072;
354 [ + - ]: 20 : if (bits <= 192)
355 : : return 7680;
356 : 20 : return 8192;
357 : : }
|
