1 /* $OpenBSD: dh.c,v 1.57 2015/05/27 23:39:18 dtucker 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> /* MIN */
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 #include <limits.h>
38
39 #include "dh.h"
40 #include "pathnames.h"
41 #include "log.h"
42 #include "misc.h"
43 #include "ssherr.h"
44
45 static int
parse_prime(int linenum,char * line,struct dhgroup * dhg)46 parse_prime(int linenum, char *line, struct dhgroup *dhg)
47 {
48 char *cp, *arg;
49 char *strsize, *gen, *prime;
50 const char *errstr = NULL;
51 long long n;
52
53 dhg->p = dhg->g = NULL;
54 cp = line;
55 if ((arg = strdelim(&cp)) == NULL)
56 return 0;
57 /* Ignore leading whitespace */
58 if (*arg == '\0')
59 arg = strdelim(&cp);
60 if (!arg || !*arg || *arg == '#')
61 return 0;
62
63 /* time */
64 if (cp == NULL || *arg == '\0')
65 goto truncated;
66 arg = strsep(&cp, " "); /* type */
67 if (cp == NULL || *arg == '\0')
68 goto truncated;
69 /* Ensure this is a safe prime */
70 n = strtonum(arg, 0, 5, &errstr);
71 if (errstr != NULL || n != MODULI_TYPE_SAFE) {
72 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
73 goto fail;
74 }
75 arg = strsep(&cp, " "); /* tests */
76 if (cp == NULL || *arg == '\0')
77 goto truncated;
78 /* Ensure prime has been tested and is not composite */
79 n = strtonum(arg, 0, 0x1f, &errstr);
80 if (errstr != NULL ||
81 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
82 error("moduli:%d: invalid moduli tests flag", linenum);
83 goto fail;
84 }
85 arg = strsep(&cp, " "); /* tries */
86 if (cp == NULL || *arg == '\0')
87 goto truncated;
88 n = strtonum(arg, 0, 1<<30, &errstr);
89 if (errstr != NULL || n == 0) {
90 error("moduli:%d: invalid primality trial count", linenum);
91 goto fail;
92 }
93 strsize = strsep(&cp, " "); /* size */
94 if (cp == NULL || *strsize == '\0' ||
95 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
96 errstr) {
97 error("moduli:%d: invalid prime length", linenum);
98 goto fail;
99 }
100 /* The whole group is one bit larger */
101 dhg->size++;
102 gen = strsep(&cp, " "); /* gen */
103 if (cp == NULL || *gen == '\0')
104 goto truncated;
105 prime = strsep(&cp, " "); /* prime */
106 if (cp != NULL || *prime == '\0') {
107 truncated:
108 error("moduli:%d: truncated", linenum);
109 goto fail;
110 }
111
112 if ((dhg->g = BN_new()) == NULL ||
113 (dhg->p = BN_new()) == NULL) {
114 error("parse_prime: BN_new failed");
115 goto fail;
116 }
117 if (BN_hex2bn(&dhg->g, gen) == 0) {
118 error("moduli:%d: could not parse generator value", linenum);
119 goto fail;
120 }
121 if (BN_hex2bn(&dhg->p, prime) == 0) {
122 error("moduli:%d: could not parse prime value", linenum);
123 goto fail;
124 }
125 if (BN_num_bits(dhg->p) != dhg->size) {
126 error("moduli:%d: prime has wrong size: actual %d listed %d",
127 linenum, BN_num_bits(dhg->p), dhg->size - 1);
128 goto fail;
129 }
130 if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
131 error("moduli:%d: generator is invalid", linenum);
132 goto fail;
133 }
134 return 1;
135
136 fail:
137 if (dhg->g != NULL)
138 BN_clear_free(dhg->g);
139 if (dhg->p != NULL)
140 BN_clear_free(dhg->p);
141 dhg->g = dhg->p = NULL;
142 return 0;
143 }
144
145 DH *
choose_dh(int min,int wantbits,int max)146 choose_dh(int min, int wantbits, int max)
147 {
148 FILE *f;
149 char line[4096];
150 int best, bestcount, which;
151 int linenum;
152 struct dhgroup dhg;
153
154 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
155 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
156 logit("WARNING: %s does not exist, using fixed modulus",
157 _PATH_DH_MODULI);
158 return (dh_new_group_fallback(max));
159 }
160
161 linenum = 0;
162 best = bestcount = 0;
163 while (fgets(line, sizeof(line), f)) {
164 linenum++;
165 if (!parse_prime(linenum, line, &dhg))
166 continue;
167 BN_clear_free(dhg.g);
168 BN_clear_free(dhg.p);
169
170 if (dhg.size > max || dhg.size < min)
171 continue;
172
173 if ((dhg.size > wantbits && dhg.size < best) ||
174 (dhg.size > best && best < wantbits)) {
175 best = dhg.size;
176 bestcount = 0;
177 }
178 if (dhg.size == best)
179 bestcount++;
180 }
181 rewind(f);
182
183 if (bestcount == 0) {
184 fclose(f);
185 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
186 return (dh_new_group_fallback(max));
187 }
188
189 linenum = 0;
190 which = arc4random_uniform(bestcount);
191 while (fgets(line, sizeof(line), f)) {
192 if (!parse_prime(linenum, line, &dhg))
193 continue;
194 if ((dhg.size > max || dhg.size < min) ||
195 dhg.size != best ||
196 linenum++ != which) {
197 BN_clear_free(dhg.g);
198 BN_clear_free(dhg.p);
199 continue;
200 }
201 break;
202 }
203 fclose(f);
204 if (linenum != which+1) {
205 logit("WARNING: line %d disappeared in %s, giving up",
206 which, _PATH_DH_PRIMES);
207 return (dh_new_group_fallback(max));
208 }
209
210 return (dh_new_group(dhg.g, dhg.p));
211 }
212
213 /* diffie-hellman-groupN-sha1 */
214
215 int
dh_pub_is_valid(DH * dh,BIGNUM * dh_pub)216 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
217 {
218 int i;
219 int n = BN_num_bits(dh_pub);
220 int bits_set = 0;
221 BIGNUM *tmp;
222
223 if (dh_pub->neg) {
224 logit("invalid public DH value: negative");
225 return 0;
226 }
227 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
228 logit("invalid public DH value: <= 1");
229 return 0;
230 }
231
232 if ((tmp = BN_new()) == NULL) {
233 error("%s: BN_new failed", __func__);
234 return 0;
235 }
236 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
237 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
238 BN_clear_free(tmp);
239 logit("invalid public DH value: >= p-1");
240 return 0;
241 }
242 BN_clear_free(tmp);
243
244 for (i = 0; i <= n; i++)
245 if (BN_is_bit_set(dh_pub, i))
246 bits_set++;
247 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
248
249 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
250 if (bits_set > 1)
251 return 1;
252
253 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
254 return 0;
255 }
256
257 int
dh_gen_key(DH * dh,int need)258 dh_gen_key(DH *dh, int need)
259 {
260 int pbits;
261
262 if (need < 0 || dh->p == NULL ||
263 (pbits = BN_num_bits(dh->p)) <= 0 ||
264 need > INT_MAX / 2 || 2 * need > pbits)
265 return SSH_ERR_INVALID_ARGUMENT;
266 #if !defined(OPENSSL_IS_BORINGSSL)
267 /* BoringSSL renamed |length| to |priv_length| to better reflect its
268 * actual use. Also, BoringSSL recognises common groups and chooses the
269 * length of the private exponent accoringly. */
270 dh->length = MIN(need * 2, pbits - 1);
271 #endif
272 if (DH_generate_key(dh) == 0 ||
273 !dh_pub_is_valid(dh, dh->pub_key)) {
274 BN_clear_free(dh->priv_key);
275 return SSH_ERR_LIBCRYPTO_ERROR;
276 }
277 return 0;
278 }
279
280 DH *
dh_new_group_asc(const char * gen,const char * modulus)281 dh_new_group_asc(const char *gen, const char *modulus)
282 {
283 DH *dh;
284
285 if ((dh = DH_new()) == NULL)
286 return NULL;
287 if (BN_hex2bn(&dh->p, modulus) == 0 ||
288 BN_hex2bn(&dh->g, gen) == 0) {
289 DH_free(dh);
290 return NULL;
291 }
292 return (dh);
293 }
294
295 /*
296 * This just returns the group, we still need to generate the exchange
297 * value.
298 */
299
300 DH *
dh_new_group(BIGNUM * gen,BIGNUM * modulus)301 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
302 {
303 DH *dh;
304
305 if ((dh = DH_new()) == NULL)
306 return NULL;
307 dh->p = modulus;
308 dh->g = gen;
309
310 return (dh);
311 }
312
313 DH *
dh_new_group1(void)314 dh_new_group1(void)
315 {
316 static char *gen = "2", *group1 =
317 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
318 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
319 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
320 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
321 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
322 "FFFFFFFF" "FFFFFFFF";
323
324 return (dh_new_group_asc(gen, group1));
325 }
326
327 DH *
dh_new_group14(void)328 dh_new_group14(void)
329 {
330 static char *gen = "2", *group14 =
331 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
332 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
333 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
334 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
335 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
336 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
337 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
338 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
339 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
340 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
341 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
342
343 return (dh_new_group_asc(gen, group14));
344 }
345
346 /*
347 * 4k bit fallback group used by DH-GEX if moduli file cannot be read.
348 * Source: MODP group 16 from RFC3526.
349 */
350 DH *
dh_new_group_fallback(int max)351 dh_new_group_fallback(int max)
352 {
353 static char *gen = "2", *group16 =
354 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
355 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
356 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
357 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
358 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
359 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
360 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
361 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
362 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
363 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
364 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
365 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
366 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
367 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
368 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
369 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
370 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
371 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
372 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
373 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
374 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
375 "FFFFFFFF" "FFFFFFFF";
376
377 if (max < 4096) {
378 debug3("requested max size %d, using 2k bit group 14", max);
379 return dh_new_group14();
380 }
381 debug3("using 4k bit group 16");
382 return (dh_new_group_asc(gen, group16));
383 }
384
385 /*
386 * Estimates the group order for a Diffie-Hellman group that has an
387 * attack complexity approximately the same as O(2**bits).
388 * Values from NIST Special Publication 800-57: Recommendation for Key
389 * Management Part 1 (rev 3) limited by the recommended maximum value
390 * from RFC4419 section 3.
391 */
392
393 u_int
dh_estimate(int bits)394 dh_estimate(int bits)
395 {
396 if (bits <= 112)
397 return 2048;
398 if (bits <= 128)
399 return 3072;
400 if (bits <= 192)
401 return 7680;
402 return 8192;
403 }
404