1 /* $OpenBSD: dh.c,v 1.74 2021/04/03 06:18:40 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 #ifdef WITH_OPENSSL
29
30 #include <errno.h>
31 #include <stdarg.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <limits.h>
36
37 #include <openssl/bn.h>
38 #include <openssl/dh.h>
39
40 #include "dh.h"
41 #include "pathnames.h"
42 #include "log.h"
43 #include "misc.h"
44 #include "ssherr.h"
45
46 #include "openbsd-compat/openssl-compat.h"
47
48 static const char *moduli_filename;
49
dh_set_moduli_file(const char * filename)50 void dh_set_moduli_file(const char *filename)
51 {
52 moduli_filename = filename;
53 }
54
get_moduli_filename(void)55 static const char * get_moduli_filename(void)
56 {
57 return moduli_filename ? moduli_filename : _PATH_DH_MODULI;
58 }
59
60 static int
parse_prime(int linenum,char * line,struct dhgroup * dhg)61 parse_prime(int linenum, char *line, struct dhgroup *dhg)
62 {
63 char *cp, *arg;
64 char *strsize, *gen, *prime;
65 const char *errstr = NULL;
66 long long n;
67
68 dhg->p = dhg->g = NULL;
69 cp = line;
70 if ((arg = strdelim(&cp)) == NULL)
71 return 0;
72 /* Ignore leading whitespace */
73 if (*arg == '\0')
74 arg = strdelim(&cp);
75 if (!arg || !*arg || *arg == '#')
76 return 0;
77
78 /* time */
79 if (cp == NULL || *arg == '\0')
80 goto truncated;
81 arg = strsep(&cp, " "); /* type */
82 if (cp == NULL || *arg == '\0')
83 goto truncated;
84 /* Ensure this is a safe prime */
85 n = strtonum(arg, 0, 5, &errstr);
86 if (errstr != NULL || n != MODULI_TYPE_SAFE) {
87 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
88 goto fail;
89 }
90 arg = strsep(&cp, " "); /* tests */
91 if (cp == NULL || *arg == '\0')
92 goto truncated;
93 /* Ensure prime has been tested and is not composite */
94 n = strtonum(arg, 0, 0x1f, &errstr);
95 if (errstr != NULL ||
96 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
97 error("moduli:%d: invalid moduli tests flag", linenum);
98 goto fail;
99 }
100 arg = strsep(&cp, " "); /* tries */
101 if (cp == NULL || *arg == '\0')
102 goto truncated;
103 n = strtonum(arg, 0, 1<<30, &errstr);
104 if (errstr != NULL || n == 0) {
105 error("moduli:%d: invalid primality trial count", linenum);
106 goto fail;
107 }
108 strsize = strsep(&cp, " "); /* size */
109 if (cp == NULL || *strsize == '\0' ||
110 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
111 errstr) {
112 error("moduli:%d: invalid prime length", linenum);
113 goto fail;
114 }
115 /* The whole group is one bit larger */
116 dhg->size++;
117 gen = strsep(&cp, " "); /* gen */
118 if (cp == NULL || *gen == '\0')
119 goto truncated;
120 prime = strsep(&cp, " "); /* prime */
121 if (cp != NULL || *prime == '\0') {
122 truncated:
123 error("moduli:%d: truncated", linenum);
124 goto fail;
125 }
126
127 if ((dhg->g = BN_new()) == NULL ||
128 (dhg->p = BN_new()) == NULL) {
129 error("parse_prime: BN_new failed");
130 goto fail;
131 }
132 if (BN_hex2bn(&dhg->g, gen) == 0) {
133 error("moduli:%d: could not parse generator value", linenum);
134 goto fail;
135 }
136 if (BN_hex2bn(&dhg->p, prime) == 0) {
137 error("moduli:%d: could not parse prime value", linenum);
138 goto fail;
139 }
140 if (BN_num_bits(dhg->p) != dhg->size) {
141 error("moduli:%d: prime has wrong size: actual %d listed %d",
142 linenum, BN_num_bits(dhg->p), dhg->size - 1);
143 goto fail;
144 }
145 if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
146 error("moduli:%d: generator is invalid", linenum);
147 goto fail;
148 }
149 return 1;
150
151 fail:
152 BN_clear_free(dhg->g);
153 BN_clear_free(dhg->p);
154 dhg->g = dhg->p = NULL;
155 return 0;
156 }
157
158 DH *
choose_dh(int min,int wantbits,int max)159 choose_dh(int min, int wantbits, int max)
160 {
161 FILE *f;
162 char *line = NULL;
163 size_t linesize = 0;
164 int best, bestcount, which, linenum;
165 struct dhgroup dhg;
166
167 if ((f = fopen(get_moduli_filename(), "r")) == NULL) {
168 logit("WARNING: could not open %s (%s), using fixed modulus",
169 get_moduli_filename(), strerror(errno));
170 return (dh_new_group_fallback(max));
171 }
172
173 linenum = 0;
174 best = bestcount = 0;
175 while (getline(&line, &linesize, f) != -1) {
176 linenum++;
177 if (!parse_prime(linenum, line, &dhg))
178 continue;
179 BN_clear_free(dhg.g);
180 BN_clear_free(dhg.p);
181
182 if (dhg.size > max || dhg.size < min)
183 continue;
184
185 if ((dhg.size > wantbits && dhg.size < best) ||
186 (dhg.size > best && best < wantbits)) {
187 best = dhg.size;
188 bestcount = 0;
189 }
190 if (dhg.size == best)
191 bestcount++;
192 }
193 free(line);
194 line = NULL;
195 linesize = 0;
196 rewind(f);
197
198 if (bestcount == 0) {
199 fclose(f);
200 logit("WARNING: no suitable primes in %s",
201 get_moduli_filename());
202 return (dh_new_group_fallback(max));
203 }
204 which = arc4random_uniform(bestcount);
205
206 linenum = 0;
207 bestcount = 0;
208 while (getline(&line, &linesize, f) != -1) {
209 linenum++;
210 if (!parse_prime(linenum, line, &dhg))
211 continue;
212 if ((dhg.size > max || dhg.size < min) ||
213 dhg.size != best ||
214 bestcount++ != which) {
215 BN_clear_free(dhg.g);
216 BN_clear_free(dhg.p);
217 continue;
218 }
219 break;
220 }
221 free(line);
222 line = NULL;
223 fclose(f);
224 if (bestcount != which + 1) {
225 logit("WARNING: selected prime disappeared in %s, giving up",
226 get_moduli_filename());
227 return (dh_new_group_fallback(max));
228 }
229
230 return (dh_new_group(dhg.g, dhg.p));
231 }
232
233 /* diffie-hellman-groupN-sha1 */
234
235 int
dh_pub_is_valid(const DH * dh,const BIGNUM * dh_pub)236 dh_pub_is_valid(const DH *dh, const BIGNUM *dh_pub)
237 {
238 int i;
239 int n = BN_num_bits(dh_pub);
240 int bits_set = 0;
241 BIGNUM *tmp;
242 const BIGNUM *dh_p;
243
244 DH_get0_pqg(dh, &dh_p, NULL, NULL);
245
246 if (BN_is_negative(dh_pub)) {
247 logit("invalid public DH value: negative");
248 return 0;
249 }
250 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
251 logit("invalid public DH value: <= 1");
252 return 0;
253 }
254
255 if ((tmp = BN_new()) == NULL) {
256 error_f("BN_new failed");
257 return 0;
258 }
259 if (!BN_sub(tmp, dh_p, BN_value_one()) ||
260 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
261 BN_clear_free(tmp);
262 logit("invalid public DH value: >= p-1");
263 return 0;
264 }
265 BN_clear_free(tmp);
266
267 for (i = 0; i <= n; i++)
268 if (BN_is_bit_set(dh_pub, i))
269 bits_set++;
270 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh_p));
271
272 /*
273 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial
274 */
275 if (bits_set < 4) {
276 logit("invalid public DH value (%d/%d)",
277 bits_set, BN_num_bits(dh_p));
278 return 0;
279 }
280 return 1;
281 }
282
283 int
dh_gen_key(DH * dh,int need)284 dh_gen_key(DH *dh, int need)
285 {
286 int pbits;
287 const BIGNUM *dh_p, *pub_key;
288
289 DH_get0_pqg(dh, &dh_p, NULL, NULL);
290
291 if (need < 0 || dh_p == NULL ||
292 (pbits = BN_num_bits(dh_p)) <= 0 ||
293 need > INT_MAX / 2 || 2 * need > pbits)
294 return SSH_ERR_INVALID_ARGUMENT;
295 if (need < 256)
296 need = 256;
297 /*
298 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
299 * so double requested need here.
300 */
301 if (!DH_set_length(dh, MINIMUM(need * 2, pbits - 1)))
302 return SSH_ERR_LIBCRYPTO_ERROR;
303
304 if (DH_generate_key(dh) == 0)
305 return SSH_ERR_LIBCRYPTO_ERROR;
306 DH_get0_key(dh, &pub_key, NULL);
307 if (!dh_pub_is_valid(dh, pub_key))
308 return SSH_ERR_INVALID_FORMAT;
309 return 0;
310 }
311
312 DH *
dh_new_group_asc(const char * gen,const char * modulus)313 dh_new_group_asc(const char *gen, const char *modulus)
314 {
315 DH *dh;
316 BIGNUM *dh_p = NULL, *dh_g = NULL;
317
318 if ((dh = DH_new()) == NULL)
319 return NULL;
320 if (BN_hex2bn(&dh_p, modulus) == 0 ||
321 BN_hex2bn(&dh_g, gen) == 0)
322 goto fail;
323 if (!DH_set0_pqg(dh, dh_p, NULL, dh_g))
324 goto fail;
325 return dh;
326 fail:
327 DH_free(dh);
328 BN_clear_free(dh_p);
329 BN_clear_free(dh_g);
330 return NULL;
331 }
332
333 /*
334 * This just returns the group, we still need to generate the exchange
335 * value.
336 */
337 DH *
dh_new_group(BIGNUM * gen,BIGNUM * modulus)338 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
339 {
340 DH *dh;
341
342 if ((dh = DH_new()) == NULL)
343 return NULL;
344 if (!DH_set0_pqg(dh, modulus, NULL, gen)) {
345 DH_free(dh);
346 return NULL;
347 }
348
349 return dh;
350 }
351
352 /* rfc2409 "Second Oakley Group" (1024 bits) */
353 DH *
dh_new_group1(void)354 dh_new_group1(void)
355 {
356 static char *gen = "2", *group1 =
357 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
358 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
359 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
360 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
361 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
362 "FFFFFFFF" "FFFFFFFF";
363
364 return (dh_new_group_asc(gen, group1));
365 }
366
367 /* rfc3526 group 14 "2048-bit MODP Group" */
368 DH *
dh_new_group14(void)369 dh_new_group14(void)
370 {
371 static char *gen = "2", *group14 =
372 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
373 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
374 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
375 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
376 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
377 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
378 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
379 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
380 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
381 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
382 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
383
384 return (dh_new_group_asc(gen, group14));
385 }
386
387 /* rfc3526 group 16 "4096-bit MODP Group" */
388 DH *
dh_new_group16(void)389 dh_new_group16(void)
390 {
391 static char *gen = "2", *group16 =
392 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
393 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
394 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
395 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
396 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
397 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
398 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
399 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
400 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
401 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
402 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
403 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
404 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
405 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
406 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
407 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
408 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
409 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
410 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
411 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
412 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
413 "FFFFFFFF" "FFFFFFFF";
414
415 return (dh_new_group_asc(gen, group16));
416 }
417
418 /* rfc3526 group 18 "8192-bit MODP Group" */
419 DH *
dh_new_group18(void)420 dh_new_group18(void)
421 {
422 static char *gen = "2", *group18 =
423 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
424 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
425 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
426 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
427 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
428 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
429 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
430 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
431 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
432 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
433 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
434 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
435 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
436 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
437 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
438 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
439 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
440 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
441 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
442 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
443 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34028492"
444 "36C3FAB4" "D27C7026" "C1D4DCB2" "602646DE" "C9751E76" "3DBA37BD"
445 "F8FF9406" "AD9E530E" "E5DB382F" "413001AE" "B06A53ED" "9027D831"
446 "179727B0" "865A8918" "DA3EDBEB" "CF9B14ED" "44CE6CBA" "CED4BB1B"
447 "DB7F1447" "E6CC254B" "33205151" "2BD7AF42" "6FB8F401" "378CD2BF"
448 "5983CA01" "C64B92EC" "F032EA15" "D1721D03" "F482D7CE" "6E74FEF6"
449 "D55E702F" "46980C82" "B5A84031" "900B1C9E" "59E7C97F" "BEC7E8F3"
450 "23A97A7E" "36CC88BE" "0F1D45B7" "FF585AC5" "4BD407B2" "2B4154AA"
451 "CC8F6D7E" "BF48E1D8" "14CC5ED2" "0F8037E0" "A79715EE" "F29BE328"
452 "06A1D58B" "B7C5DA76" "F550AA3D" "8A1FBFF0" "EB19CCB1" "A313D55C"
453 "DA56C9EC" "2EF29632" "387FE8D7" "6E3C0468" "043E8F66" "3F4860EE"
454 "12BF2D5B" "0B7474D6" "E694F91E" "6DBE1159" "74A3926F" "12FEE5E4"
455 "38777CB6" "A932DF8C" "D8BEC4D0" "73B931BA" "3BC832B6" "8D9DD300"
456 "741FA7BF" "8AFC47ED" "2576F693" "6BA42466" "3AAB639C" "5AE4F568"
457 "3423B474" "2BF1C978" "238F16CB" "E39D652D" "E3FDB8BE" "FC848AD9"
458 "22222E04" "A4037C07" "13EB57A8" "1A23F0C7" "3473FC64" "6CEA306B"
459 "4BCBC886" "2F8385DD" "FA9D4B7F" "A2C087E8" "79683303" "ED5BDD3A"
460 "062B3CF5" "B3A278A6" "6D2A13F8" "3F44F82D" "DF310EE0" "74AB6A36"
461 "4597E899" "A0255DC1" "64F31CC5" "0846851D" "F9AB4819" "5DED7EA1"
462 "B1D510BD" "7EE74D73" "FAF36BC3" "1ECFA268" "359046F4" "EB879F92"
463 "4009438B" "481C6CD7" "889A002E" "D5EE382B" "C9190DA6" "FC026E47"
464 "9558E447" "5677E9AA" "9E3050E2" "765694DF" "C81F56E8" "80B96E71"
465 "60C980DD" "98EDD3DF" "FFFFFFFF" "FFFFFFFF";
466
467 return (dh_new_group_asc(gen, group18));
468 }
469
470 /* Select fallback group used by DH-GEX if moduli file cannot be read. */
471 DH *
dh_new_group_fallback(int max)472 dh_new_group_fallback(int max)
473 {
474 debug3_f("requested max size %d", max);
475 if (max < 3072) {
476 debug3("using 2k bit group 14");
477 return dh_new_group14();
478 } else if (max < 6144) {
479 debug3("using 4k bit group 16");
480 return dh_new_group16();
481 }
482 debug3("using 8k bit group 18");
483 return dh_new_group18();
484 }
485
486 /*
487 * Estimates the group order for a Diffie-Hellman group that has an
488 * attack complexity approximately the same as O(2**bits).
489 * Values from NIST Special Publication 800-57: Recommendation for Key
490 * Management Part 1 (rev 3) limited by the recommended maximum value
491 * from RFC4419 section 3.
492 */
493 u_int
dh_estimate(int bits)494 dh_estimate(int bits)
495 {
496 if (bits <= 112)
497 return 2048;
498 if (bits <= 128)
499 return 3072;
500 if (bits <= 192)
501 return 7680;
502 return 8192;
503 }
504
505 #endif /* WITH_OPENSSL */
506