1 /* $OpenBSD: dh.c,v 1.51 2013/07/02 12:31:43 markus 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>
30 #include <openssl/bn.h>
31 #include <openssl/dh.h>
39 #include "pathnames.h"
44 parse_prime(int linenum, char *line, struct dhgroup *dhg)
47 char *strsize, *gen, *prime;
48 const char *errstr = NULL;
51 dhg->p = dhg->g = NULL;
53 if ((arg = strdelim(&cp)) == NULL)
55 /* Ignore leading whitespace */
58 if (!arg || !*arg || *arg == '#')
62 if (cp == NULL || *arg == '\0')
64 arg = strsep(&cp, " "); /* type */
65 if (cp == NULL || *arg == '\0')
67 /* Ensure this is a safe prime */
68 n = strtonum(arg, 0, 5, &errstr);
69 if (errstr != NULL || n != MODULI_TYPE_SAFE) {
70 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
73 arg = strsep(&cp, " "); /* tests */
74 if (cp == NULL || *arg == '\0')
76 /* Ensure prime has been tested and is not composite */
77 n = strtonum(arg, 0, 0x1f, &errstr);
79 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
80 error("moduli:%d: invalid moduli tests flag", linenum);
83 arg = strsep(&cp, " "); /* tries */
84 if (cp == NULL || *arg == '\0')
86 n = strtonum(arg, 0, 1<<30, &errstr);
87 if (errstr != NULL || n == 0) {
88 error("moduli:%d: invalid primality trial count", linenum);
91 strsize = strsep(&cp, " "); /* size */
92 if (cp == NULL || *strsize == '\0' ||
93 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
95 error("moduli:%d: invalid prime length", linenum);
98 /* The whole group is one bit larger */
100 gen = strsep(&cp, " "); /* gen */
101 if (cp == NULL || *gen == '\0')
103 prime = strsep(&cp, " "); /* prime */
104 if (cp != NULL || *prime == '\0') {
106 error("moduli:%d: truncated", linenum);
110 if ((dhg->g = BN_new()) == NULL)
111 fatal("parse_prime: BN_new failed");
112 if ((dhg->p = BN_new()) == NULL)
113 fatal("parse_prime: BN_new failed");
114 if (BN_hex2bn(&dhg->g, gen) == 0) {
115 error("moduli:%d: could not parse generator value", linenum);
118 if (BN_hex2bn(&dhg->p, prime) == 0) {
119 error("moduli:%d: could not parse prime value", linenum);
122 if (BN_num_bits(dhg->p) != dhg->size) {
123 error("moduli:%d: prime has wrong size: actual %d listed %d",
124 linenum, BN_num_bits(dhg->p), dhg->size - 1);
127 if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
128 error("moduli:%d: generator is invalid", linenum);
136 BN_clear_free(dhg->g);
138 BN_clear_free(dhg->p);
139 dhg->g = dhg->p = NULL;
140 error("Bad prime description in line %d", linenum);
145 choose_dh(int min, int wantbits, int max)
149 int best, bestcount, which;
153 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
154 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
155 logit("WARNING: %s does not exist, using fixed modulus",
157 return (dh_new_group14());
161 best = bestcount = 0;
162 while (fgets(line, sizeof(line), f)) {
164 if (!parse_prime(linenum, line, &dhg))
166 BN_clear_free(dhg.g);
167 BN_clear_free(dhg.p);
169 if (dhg.size > max || dhg.size < min)
172 if ((dhg.size > wantbits && dhg.size < best) ||
173 (dhg.size > best && best < wantbits)) {
177 if (dhg.size == best)
182 if (bestcount == 0) {
184 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
185 return (dh_new_group14());
189 which = arc4random_uniform(bestcount);
190 while (fgets(line, sizeof(line), f)) {
191 if (!parse_prime(linenum, line, &dhg))
193 if ((dhg.size > max || dhg.size < min) ||
195 linenum++ != which) {
196 BN_clear_free(dhg.g);
197 BN_clear_free(dhg.p);
203 if (linenum != which+1)
204 fatal("WARNING: line %d disappeared in %s, giving up",
205 which, _PATH_DH_PRIMES);
207 return (dh_new_group(dhg.g, dhg.p));
210 /* diffie-hellman-groupN-sha1 */
213 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
216 int n = BN_num_bits(dh_pub);
221 logit("invalid public DH value: negative");
224 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
225 logit("invalid public DH value: <= 1");
229 if ((tmp = BN_new()) == NULL) {
230 error("%s: BN_new failed", __func__);
233 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
234 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
236 logit("invalid public DH value: >= p-1");
241 for (i = 0; i <= n; i++)
242 if (BN_is_bit_set(dh_pub, i))
244 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
246 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
250 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
255 dh_gen_key(DH *dh, int need)
257 int i, bits_set, tries = 0;
260 fatal("dh_gen_key: need < 0");
262 fatal("dh_gen_key: dh->p == NULL");
263 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
264 fatal("dh_gen_key: group too small: %d (2*need %d)",
265 BN_num_bits(dh->p), 2*need);
267 if (dh->priv_key != NULL)
268 BN_clear_free(dh->priv_key);
269 if ((dh->priv_key = BN_new()) == NULL)
270 fatal("dh_gen_key: BN_new failed");
271 /* generate a 2*need bits random private exponent */
272 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
273 fatal("dh_gen_key: BN_rand failed");
274 if (DH_generate_key(dh) == 0)
275 fatal("DH_generate_key");
276 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
277 if (BN_is_bit_set(dh->priv_key, i))
279 debug2("dh_gen_key: priv key bits set: %d/%d",
280 bits_set, BN_num_bits(dh->priv_key));
282 fatal("dh_gen_key: too many bad keys: giving up");
283 } while (!dh_pub_is_valid(dh, dh->pub_key));
287 dh_new_group_asc(const char *gen, const char *modulus)
291 if ((dh = DH_new()) == NULL)
292 fatal("dh_new_group_asc: DH_new");
294 if (BN_hex2bn(&dh->p, modulus) == 0)
295 fatal("BN_hex2bn p");
296 if (BN_hex2bn(&dh->g, gen) == 0)
297 fatal("BN_hex2bn g");
303 * This just returns the group, we still need to generate the exchange
308 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
312 if ((dh = DH_new()) == NULL)
313 fatal("dh_new_group: DH_new");
323 static char *gen = "2", *group1 =
324 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
325 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
326 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
327 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
328 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
329 "FFFFFFFF" "FFFFFFFF";
331 return (dh_new_group_asc(gen, group1));
337 static char *gen = "2", *group14 =
338 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
339 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
340 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
341 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
342 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
343 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
344 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
345 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
346 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
347 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
348 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
350 return (dh_new_group_asc(gen, group14));
354 * Estimates the group order for a Diffie-Hellman group that has an
355 * attack complexity approximately the same as O(2**bits). Estimate
356 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
360 dh_estimate(int bits)
364 return (1024); /* O(2**86) */
366 return (2048); /* O(2**116) */
367 return (4096); /* O(2**156) */