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.21 2002/03/06 00:23:27 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')
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)
97 BN_clear_free(dhg->g);
98 BN_clear_free(dhg->p);
100 error("Bad prime description in line %d", linenum);
105 choose_dh(int min, int wantbits, int max)
109 int best, bestcount, which;
113 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
114 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
115 log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI);
116 return (dh_new_group1());
120 best = bestcount = 0;
121 while (fgets(line, sizeof(line), f)) {
123 if (!parse_prime(linenum, line, &dhg))
125 BN_clear_free(dhg.g);
126 BN_clear_free(dhg.p);
128 if (dhg.size > max || dhg.size < min)
131 if ((dhg.size > wantbits && dhg.size < best) ||
132 (dhg.size > best && best < wantbits)) {
136 if (dhg.size == best)
141 if (bestcount == 0) {
143 log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
148 which = arc4random() % bestcount;
149 while (fgets(line, sizeof(line), f)) {
150 if (!parse_prime(linenum, line, &dhg))
152 if ((dhg.size > max || dhg.size < min) ||
154 linenum++ != which) {
155 BN_clear_free(dhg.g);
156 BN_clear_free(dhg.p);
162 if (linenum != which+1)
163 fatal("WARNING: line %d disappeared in %s, giving up",
164 which, _PATH_DH_PRIMES);
166 return (dh_new_group(dhg.g, dhg.p));
169 /* diffie-hellman-group1-sha1 */
172 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
175 int n = BN_num_bits(dh_pub);
179 log("invalid public DH value: negativ");
182 for (i = 0; i <= n; i++)
183 if (BN_is_bit_set(dh_pub, i))
185 debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
187 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
188 if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
190 log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
195 dh_gen_key(DH *dh, int need)
197 int i, bits_set = 0, tries = 0;
200 fatal("dh_gen_key: dh->p == NULL");
201 if (2*need >= BN_num_bits(dh->p))
202 fatal("dh_gen_key: group too small: %d (2*need %d)",
203 BN_num_bits(dh->p), 2*need);
205 if (dh->priv_key != NULL)
206 BN_clear_free(dh->priv_key);
207 if ((dh->priv_key = BN_new()) == NULL)
208 fatal("dh_gen_key: BN_new failed");
209 /* generate a 2*need bits random private exponent */
210 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
211 fatal("dh_gen_key: BN_rand failed");
212 if (DH_generate_key(dh) == 0)
213 fatal("DH_generate_key");
214 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
215 if (BN_is_bit_set(dh->priv_key, i))
217 debug("dh_gen_key: priv key bits set: %d/%d",
218 bits_set, BN_num_bits(dh->priv_key));
220 fatal("dh_gen_key: too many bad keys: giving up");
221 } while (!dh_pub_is_valid(dh, dh->pub_key));
225 dh_new_group_asc(const char *gen, const char *modulus)
229 if ((dh = DH_new()) == NULL)
230 fatal("dh_new_group_asc: DH_new");
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)
250 if ((dh = DH_new()) == NULL)
251 fatal("dh_new_group: DH_new");
261 static char *gen = "2", *group1 =
262 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
263 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
264 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
265 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
266 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
267 "FFFFFFFF" "FFFFFFFF";
269 return (dh_new_group_asc(gen, group1));
273 * Estimates the group order for a Diffie-Hellman group that has an
274 * attack complexity approximately the same as O(2**bits). Estimate
275 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
279 dh_estimate(int bits)
283 return (512); /* O(2**63) */
285 return (1024); /* O(2**86) */
287 return (2048); /* O(2**116) */
288 return (4096); /* O(2**156) */