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