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