1 /* $OpenBSD: dh.c,v 1.57 2015/05/27 23:39:18 dtucker Exp $ */
3 * Copyright (c) 2000 Niels Provos. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
28 #include <sys/param.h> /* MIN */
30 #include <openssl/bn.h>
31 #include <openssl/dh.h>
40 #include "pathnames.h"
46 parse_prime(int linenum, char *line, struct dhgroup *dhg)
49 char *strsize, *gen, *prime;
50 const char *errstr = NULL;
53 dhg->p = dhg->g = NULL;
55 if ((arg = strdelim(&cp)) == NULL)
57 /* Ignore leading whitespace */
60 if (!arg || !*arg || *arg == '#')
64 if (cp == NULL || *arg == '\0')
66 arg = strsep(&cp, " "); /* type */
67 if (cp == NULL || *arg == '\0')
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);
75 arg = strsep(&cp, " "); /* tests */
76 if (cp == NULL || *arg == '\0')
78 /* Ensure prime has been tested and is not composite */
79 n = strtonum(arg, 0, 0x1f, &errstr);
81 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
82 error("moduli:%d: invalid moduli tests flag", linenum);
85 arg = strsep(&cp, " "); /* tries */
86 if (cp == NULL || *arg == '\0')
88 n = strtonum(arg, 0, 1<<30, &errstr);
89 if (errstr != NULL || n == 0) {
90 error("moduli:%d: invalid primality trial count", linenum);
93 strsize = strsep(&cp, " "); /* size */
94 if (cp == NULL || *strsize == '\0' ||
95 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
97 error("moduli:%d: invalid prime length", linenum);
100 /* The whole group is one bit larger */
102 gen = strsep(&cp, " "); /* gen */
103 if (cp == NULL || *gen == '\0')
105 prime = strsep(&cp, " "); /* prime */
106 if (cp != NULL || *prime == '\0') {
108 error("moduli:%d: truncated", linenum);
112 if ((dhg->g = BN_new()) == NULL ||
113 (dhg->p = BN_new()) == NULL) {
114 error("parse_prime: BN_new failed");
117 if (BN_hex2bn(&dhg->g, gen) == 0) {
118 error("moduli:%d: could not parse generator value", linenum);
121 if (BN_hex2bn(&dhg->p, prime) == 0) {
122 error("moduli:%d: could not parse prime value", linenum);
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);
130 if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
131 error("moduli:%d: generator is invalid", linenum);
138 BN_clear_free(dhg->g);
140 BN_clear_free(dhg->p);
141 dhg->g = dhg->p = NULL;
146 choose_dh(int min, int wantbits, int max)
150 int best, bestcount, which;
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",
158 return (dh_new_group_fallback(max));
162 best = bestcount = 0;
163 while (fgets(line, sizeof(line), f)) {
165 if (!parse_prime(linenum, line, &dhg))
167 BN_clear_free(dhg.g);
168 BN_clear_free(dhg.p);
170 if (dhg.size > max || dhg.size < min)
173 if ((dhg.size > wantbits && dhg.size < best) ||
174 (dhg.size > best && best < wantbits)) {
178 if (dhg.size == best)
183 if (bestcount == 0) {
185 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
186 return (dh_new_group_fallback(max));
190 which = arc4random_uniform(bestcount);
191 while (fgets(line, sizeof(line), f)) {
192 if (!parse_prime(linenum, line, &dhg))
194 if ((dhg.size > max || dhg.size < min) ||
196 linenum++ != which) {
197 BN_clear_free(dhg.g);
198 BN_clear_free(dhg.p);
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));
210 return (dh_new_group(dhg.g, dhg.p));
213 /* diffie-hellman-groupN-sha1 */
216 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
219 int n = BN_num_bits(dh_pub);
224 logit("invalid public DH value: negative");
227 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
228 logit("invalid public DH value: <= 1");
232 if ((tmp = BN_new()) == NULL) {
233 error("%s: BN_new failed", __func__);
236 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
237 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
239 logit("invalid public DH value: >= p-1");
244 for (i = 0; i <= n; i++)
245 if (BN_is_bit_set(dh_pub, i))
247 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
249 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
253 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
258 dh_gen_key(DH *dh, int need)
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 dh->length = MIN(need * 2, pbits - 1);
267 if (DH_generate_key(dh) == 0 ||
268 !dh_pub_is_valid(dh, dh->pub_key)) {
269 BN_clear_free(dh->priv_key);
270 return SSH_ERR_LIBCRYPTO_ERROR;
276 dh_new_group_asc(const char *gen, const char *modulus)
280 if ((dh = DH_new()) == NULL)
282 if (BN_hex2bn(&dh->p, modulus) == 0 ||
283 BN_hex2bn(&dh->g, gen) == 0) {
291 * This just returns the group, we still need to generate the exchange
296 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
300 if ((dh = DH_new()) == NULL)
311 static char *gen = "2", *group1 =
312 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
313 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
314 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
315 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
316 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
317 "FFFFFFFF" "FFFFFFFF";
319 return (dh_new_group_asc(gen, group1));
325 static char *gen = "2", *group14 =
326 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
327 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
328 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
329 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
330 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
331 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
332 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
333 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
334 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
335 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
336 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
338 return (dh_new_group_asc(gen, group14));
342 * 4k bit fallback group used by DH-GEX if moduli file cannot be read.
343 * Source: MODP group 16 from RFC3526.
346 dh_new_group_fallback(int max)
348 static char *gen = "2", *group16 =
349 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
350 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
351 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
352 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
353 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
354 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
355 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
356 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
357 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
358 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
359 "15728E5A" "8AAAC42D" "AD33170D" "04507A33" "A85521AB" "DF1CBA64"
360 "ECFB8504" "58DBEF0A" "8AEA7157" "5D060C7D" "B3970F85" "A6E1E4C7"
361 "ABF5AE8C" "DB0933D7" "1E8C94E0" "4A25619D" "CEE3D226" "1AD2EE6B"
362 "F12FFA06" "D98A0864" "D8760273" "3EC86A64" "521F2B18" "177B200C"
363 "BBE11757" "7A615D6C" "770988C0" "BAD946E2" "08E24FA0" "74E5AB31"
364 "43DB5BFC" "E0FD108E" "4B82D120" "A9210801" "1A723C12" "A787E6D7"
365 "88719A10" "BDBA5B26" "99C32718" "6AF4E23C" "1A946834" "B6150BDA"
366 "2583E9CA" "2AD44CE8" "DBBBC2DB" "04DE8EF9" "2E8EFC14" "1FBECAA6"
367 "287C5947" "4E6BC05D" "99B2964F" "A090C3A2" "233BA186" "515BE7ED"
368 "1F612970" "CEE2D7AF" "B81BDD76" "2170481C" "D0069127" "D5B05AA9"
369 "93B4EA98" "8D8FDDC1" "86FFB7DC" "90A6C08F" "4DF435C9" "34063199"
370 "FFFFFFFF" "FFFFFFFF";
373 debug3("requested max size %d, using 2k bit group 14", max);
374 return dh_new_group14();
376 debug3("using 4k bit group 16");
377 return (dh_new_group_asc(gen, group16));
381 * Estimates the group order for a Diffie-Hellman group that has an
382 * attack complexity approximately the same as O(2**bits).
383 * Values from NIST Special Publication 800-57: Recommendation for Key
384 * Management Part 1 (rev 3) limited by the recommended maximum value
385 * from RFC4419 section 3.
389 dh_estimate(int bits)