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.29 2004/02/27 22:49:27 dtucker 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 || *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')
81 if ((dhg->g = BN_new()) == NULL)
82 fatal("parse_prime: BN_new failed");
83 if ((dhg->p = BN_new()) == NULL)
84 fatal("parse_prime: BN_new failed");
85 if (BN_hex2bn(&dhg->g, gen) == 0)
88 if (BN_hex2bn(&dhg->p, prime) == 0)
91 if (BN_num_bits(dhg->p) != dhg->size)
94 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
100 BN_clear_free(dhg->g);
101 BN_clear_free(dhg->p);
103 error("Bad prime description in line %d", linenum);
108 choose_dh(int min, int wantbits, int max)
112 int best, bestcount, which;
116 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
117 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
118 logit("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
119 return (dh_new_group1());
123 best = bestcount = 0;
124 while (fgets(line, sizeof(line), f)) {
126 if (!parse_prime(linenum, line, &dhg))
128 BN_clear_free(dhg.g);
129 BN_clear_free(dhg.p);
131 if (dhg.size > max || dhg.size < min)
134 if ((dhg.size > wantbits && dhg.size < best) ||
135 (dhg.size > best && best < wantbits)) {
139 if (dhg.size == best)
144 if (bestcount == 0) {
146 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
151 which = arc4random() % bestcount;
152 while (fgets(line, sizeof(line), f)) {
153 if (!parse_prime(linenum, line, &dhg))
155 if ((dhg.size > max || dhg.size < min) ||
157 linenum++ != which) {
158 BN_clear_free(dhg.g);
159 BN_clear_free(dhg.p);
165 if (linenum != which+1)
166 fatal("WARNING: line %d disappeared in %s, giving up",
167 which, _PATH_DH_PRIMES);
169 return (dh_new_group(dhg.g, dhg.p));
172 /* diffie-hellman-group1-sha1 */
175 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
178 int n = BN_num_bits(dh_pub);
182 logit("invalid public DH value: negativ");
185 for (i = 0; i <= n; i++)
186 if (BN_is_bit_set(dh_pub, i))
188 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
190 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
191 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
193 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
198 dh_gen_key(DH *dh, int need)
200 int i, bits_set, tries = 0;
203 fatal("dh_gen_key: dh->p == NULL");
204 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
205 fatal("dh_gen_key: group too small: %d (2*need %d)",
206 BN_num_bits(dh->p), 2*need);
208 if (dh->priv_key != NULL)
209 BN_clear_free(dh->priv_key);
210 if ((dh->priv_key = BN_new()) == 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, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
218 if (BN_is_bit_set(dh->priv_key, i))
220 debug2("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)
232 if ((dh = DH_new()) == NULL)
233 fatal("dh_new_group_asc: DH_new");
235 if (BN_hex2bn(&dh->p, modulus) == 0)
236 fatal("BN_hex2bn p");
237 if (BN_hex2bn(&dh->g, gen) == 0)
238 fatal("BN_hex2bn g");
244 * This just returns the group, we still need to generate the exchange
249 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
253 if ((dh = DH_new()) == NULL)
254 fatal("dh_new_group: DH_new");
264 static char *gen = "2", *group1 =
265 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
266 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
267 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
268 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
269 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
270 "FFFFFFFF" "FFFFFFFF";
272 return (dh_new_group_asc(gen, group1));
276 * Estimates the group order for a Diffie-Hellman group that has an
277 * attack complexity approximately the same as O(2**bits). Estimate
278 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
282 dh_estimate(int bits)
286 return (1024); /* O(2**86) */
288 return (2048); /* O(2**116) */
289 return (4096); /* O(2**156) */