2 * Copyright (c) 2000 Niels Provos. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
14 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
15 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
16 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
17 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
18 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
20 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
22 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 RCSID("$OpenBSD: dh.c,v 1.14 2001/04/15 08:43:45 markus Exp $");
30 #include <openssl/bn.h>
31 #include <openssl/dh.h>
32 #include <openssl/evp.h>
38 #include "pathnames.h"
43 parse_prime(int linenum, char *line, struct dhgroup *dhg)
46 char *strsize, *gen, *prime;
50 /* Ignore leading whitespace */
53 if (!*arg || *arg == '#')
57 if (cp == NULL || *arg == '\0')
59 arg = strsep(&cp, " "); /* type */
60 if (cp == NULL || *arg == '\0')
62 arg = strsep(&cp, " "); /* tests */
63 if (cp == NULL || *arg == '\0')
65 arg = strsep(&cp, " "); /* tries */
66 if (cp == NULL || *arg == '\0')
68 strsize = strsep(&cp, " "); /* size */
69 if (cp == NULL || *strsize == '\0' ||
70 (dhg->size = atoi(strsize)) == 0)
72 /* The whole group is one bit larger */
74 gen = strsep(&cp, " "); /* gen */
75 if (cp == NULL || *gen == '\0')
77 prime = strsep(&cp, " "); /* prime */
78 if (cp != NULL || *prime == '\0')
83 if (BN_hex2bn(&dhg->g, gen) == 0)
86 if (BN_hex2bn(&dhg->p, prime) == 0)
89 if (BN_num_bits(dhg->p) != dhg->size)
98 error("Bad prime description in line %d", linenum);
103 choose_dh(int min, int wantbits, int max)
107 int best, bestcount, which;
111 f = fopen(_PATH_DH_PRIMES, "r");
113 log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES);
114 return (dh_new_group1());
118 best = bestcount = 0;
119 while (fgets(line, sizeof(line), f)) {
121 if (!parse_prime(linenum, line, &dhg))
126 if (dhg.size > max || dhg.size < min)
129 if ((dhg.size > wantbits && dhg.size < best) ||
130 (dhg.size > best && best < wantbits)) {
134 if (dhg.size == best)
139 if (bestcount == 0) {
140 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
144 f = fopen(_PATH_DH_PRIMES, "r");
146 fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES);
150 which = arc4random() % bestcount;
151 while (fgets(line, sizeof(line), f)) {
152 if (!parse_prime(linenum, line, &dhg))
154 if ((dhg.size > max || dhg.size < min) ||
156 linenum++ != which) {
164 if (linenum != which+1)
165 fatal("WARNING: line %d disappeared in %s, giving up",
166 which, _PATH_DH_PRIMES);
168 return (dh_new_group(dhg.g, dhg.p));
171 /* diffie-hellman-group1-sha1 */
174 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
177 int n = BN_num_bits(dh_pub);
181 log("invalid public DH value: negativ");
184 for (i = 0; i <= n; i++)
185 if (BN_is_bit_set(dh_pub, i))
187 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
189 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
190 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
192 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
197 dh_gen_key(DH *dh, int need)
199 int i, bits_set = 0, tries = 0;
202 fatal("dh_gen_key: dh->p == NULL");
203 if (2*need >= BN_num_bits(dh->p))
204 fatal("dh_gen_key: group too small: %d (2*need %d)",
205 BN_num_bits(dh->p), 2*need);
207 if (dh->priv_key != NULL)
208 BN_free(dh->priv_key);
209 dh->priv_key = BN_new();
210 if (dh->priv_key == NULL)
211 fatal("dh_gen_key: BN_new failed");
212 /* generate a 2*need bits random private exponent */
213 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
214 fatal("dh_gen_key: BN_rand failed");
215 if (DH_generate_key(dh) == 0)
216 fatal("DH_generate_key");
217 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
218 if (BN_is_bit_set(dh->priv_key, i))
220 debug("dh_gen_key: priv key bits set: %d/%d",
221 bits_set, BN_num_bits(dh->priv_key));
223 fatal("dh_gen_key: too many bad keys: giving up");
224 } while (!dh_pub_is_valid(dh, dh->pub_key));
228 dh_new_group_asc(const char *gen, const char *modulus)
236 if (BN_hex2bn(&dh->p, modulus) == 0)
237 fatal("BN_hex2bn p");
238 if (BN_hex2bn(&dh->g, gen) == 0)
239 fatal("BN_hex2bn g");
245 * This just returns the group, we still need to generate the exchange
250 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
266 static char *gen = "2", *group1 =
267 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
268 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
269 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
270 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
271 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
272 "FFFFFFFF" "FFFFFFFF";
274 return (dh_new_group_asc(gen, group1));
278 * Estimates the group order for a Diffie-Hellman group that has an
279 * attack complexity approximately the same as O(2**bits). Estimate
280 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
284 dh_estimate(int bits)
288 return (512); /* O(2**63) */
290 return (1024); /* O(2**86) */
292 return (2048); /* O(2**116) */
293 return (4096); /* O(2**156) */