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.17 2001/06/23 15:12:18 itojun 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 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
112 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
113 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
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) {
141 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
146 which = arc4random() % bestcount;
147 while (fgets(line, sizeof(line), f)) {
148 if (!parse_prime(linenum, line, &dhg))
150 if ((dhg.size > max || dhg.size < min) ||
152 linenum++ != which) {
160 if (linenum != which+1)
161 fatal("WARNING: line %d disappeared in %s, giving up",
162 which, _PATH_DH_PRIMES);
164 return (dh_new_group(dhg.g, dhg.p));
167 /* diffie-hellman-group1-sha1 */
170 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
173 int n = BN_num_bits(dh_pub);
177 log("invalid public DH value: negativ");
180 for (i = 0; i <= n; i++)
181 if (BN_is_bit_set(dh_pub, i))
183 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
185 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
186 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
188 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
193 dh_gen_key(DH *dh, int need)
195 int i, bits_set = 0, tries = 0;
198 fatal("dh_gen_key: dh->p == NULL");
199 if (2*need >= BN_num_bits(dh->p))
200 fatal("dh_gen_key: group too small: %d (2*need %d)",
201 BN_num_bits(dh->p), 2*need);
203 if (dh->priv_key != NULL)
204 BN_free(dh->priv_key);
205 dh->priv_key = BN_new();
206 if (dh->priv_key == NULL)
207 fatal("dh_gen_key: BN_new failed");
208 /* generate a 2*need bits random private exponent */
209 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
210 fatal("dh_gen_key: BN_rand failed");
211 if (DH_generate_key(dh) == 0)
212 fatal("DH_generate_key");
213 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
214 if (BN_is_bit_set(dh->priv_key, i))
216 debug("dh_gen_key: priv key bits set: %d/%d",
217 bits_set, BN_num_bits(dh->priv_key));
219 fatal("dh_gen_key: too many bad keys: giving up");
220 } while (!dh_pub_is_valid(dh, dh->pub_key));
224 dh_new_group_asc(const char *gen, const char *modulus)
232 if (BN_hex2bn(&dh->p, modulus) == 0)
233 fatal("BN_hex2bn p");
234 if (BN_hex2bn(&dh->g, gen) == 0)
235 fatal("BN_hex2bn g");
241 * This just returns the group, we still need to generate the exchange
246 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
262 static char *gen = "2", *group1 =
263 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
264 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
265 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
266 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
267 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
268 "FFFFFFFF" "FFFFFFFF";
270 return (dh_new_group_asc(gen, group1));
274 * Estimates the group order for a Diffie-Hellman group that has an
275 * attack complexity approximately the same as O(2**bits). Estimate
276 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
280 dh_estimate(int bits)
284 return (512); /* O(2**63) */
286 return (1024); /* O(2**86) */
288 return (2048); /* O(2**116) */
289 return (4096); /* O(2**156) */