1 /* $OpenBSD: dh.c,v 1.49 2011/12/07 05:44:38 djm 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;
52 if ((arg = strdelim(&cp)) == NULL)
54 /* Ignore leading whitespace */
57 if (!arg || !*arg || *arg == '#')
61 if (cp == NULL || *arg == '\0')
63 arg = strsep(&cp, " "); /* type */
64 if (cp == NULL || *arg == '\0')
66 /* Ensure this is a safe prime */
67 n = strtonum(arg, 0, 5, &errstr);
68 if (errstr != NULL || n != MODULI_TYPE_SAFE)
70 arg = strsep(&cp, " "); /* tests */
71 if (cp == NULL || *arg == '\0')
73 /* Ensure prime has been tested and is not composite */
74 n = strtonum(arg, 0, 0x1f, &errstr);
76 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
78 arg = strsep(&cp, " "); /* tries */
79 if (cp == NULL || *arg == '\0')
81 n = strtonum(arg, 0, 1<<30, &errstr);
82 if (errstr != NULL || n == 0)
84 strsize = strsep(&cp, " "); /* size */
85 if (cp == NULL || *strsize == '\0' ||
86 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
89 /* The whole group is one bit larger */
91 gen = strsep(&cp, " "); /* gen */
92 if (cp == NULL || *gen == '\0')
94 prime = strsep(&cp, " "); /* prime */
95 if (cp != NULL || *prime == '\0')
98 if ((dhg->g = BN_new()) == NULL)
99 fatal("parse_prime: BN_new failed");
100 if ((dhg->p = BN_new()) == NULL)
101 fatal("parse_prime: BN_new failed");
102 if (BN_hex2bn(&dhg->g, gen) == 0)
105 if (BN_hex2bn(&dhg->p, prime) == 0)
108 if (BN_num_bits(dhg->p) != dhg->size)
111 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
117 BN_clear_free(dhg->g);
118 BN_clear_free(dhg->p);
120 error("Bad prime description in line %d", linenum);
125 choose_dh(int min, int wantbits, int max)
129 int best, bestcount, which;
133 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
134 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
135 logit("WARNING: %s does not exist, using fixed modulus",
137 return (dh_new_group14());
141 best = bestcount = 0;
142 while (fgets(line, sizeof(line), f)) {
144 if (!parse_prime(linenum, line, &dhg))
146 BN_clear_free(dhg.g);
147 BN_clear_free(dhg.p);
149 if (dhg.size > max || dhg.size < min)
152 if ((dhg.size > wantbits && dhg.size < best) ||
153 (dhg.size > best && best < wantbits)) {
157 if (dhg.size == best)
162 if (bestcount == 0) {
164 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
165 return (dh_new_group14());
169 which = arc4random_uniform(bestcount);
170 while (fgets(line, sizeof(line), f)) {
171 if (!parse_prime(linenum, line, &dhg))
173 if ((dhg.size > max || dhg.size < min) ||
175 linenum++ != which) {
176 BN_clear_free(dhg.g);
177 BN_clear_free(dhg.p);
183 if (linenum != which+1)
184 fatal("WARNING: line %d disappeared in %s, giving up",
185 which, _PATH_DH_PRIMES);
187 return (dh_new_group(dhg.g, dhg.p));
190 /* diffie-hellman-groupN-sha1 */
193 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
196 int n = BN_num_bits(dh_pub);
201 logit("invalid public DH value: negative");
204 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
205 logit("invalid public DH value: <= 1");
209 if ((tmp = BN_new()) == NULL) {
210 error("%s: BN_new failed", __func__);
213 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
214 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
216 logit("invalid public DH value: >= p-1");
221 for (i = 0; i <= n; i++)
222 if (BN_is_bit_set(dh_pub, i))
224 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
226 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
230 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
235 dh_gen_key(DH *dh, int need)
237 int i, bits_set, tries = 0;
240 fatal("dh_gen_key: need < 0");
242 fatal("dh_gen_key: dh->p == NULL");
243 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
244 fatal("dh_gen_key: group too small: %d (2*need %d)",
245 BN_num_bits(dh->p), 2*need);
247 if (dh->priv_key != NULL)
248 BN_clear_free(dh->priv_key);
249 if ((dh->priv_key = BN_new()) == NULL)
250 fatal("dh_gen_key: BN_new failed");
251 /* generate a 2*need bits random private exponent */
252 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
253 fatal("dh_gen_key: BN_rand failed");
254 if (DH_generate_key(dh) == 0)
255 fatal("DH_generate_key");
256 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
257 if (BN_is_bit_set(dh->priv_key, i))
259 debug2("dh_gen_key: priv key bits set: %d/%d",
260 bits_set, BN_num_bits(dh->priv_key));
262 fatal("dh_gen_key: too many bad keys: giving up");
263 } while (!dh_pub_is_valid(dh, dh->pub_key));
267 dh_new_group_asc(const char *gen, const char *modulus)
271 if ((dh = DH_new()) == NULL)
272 fatal("dh_new_group_asc: DH_new");
274 if (BN_hex2bn(&dh->p, modulus) == 0)
275 fatal("BN_hex2bn p");
276 if (BN_hex2bn(&dh->g, gen) == 0)
277 fatal("BN_hex2bn g");
283 * This just returns the group, we still need to generate the exchange
288 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
292 if ((dh = DH_new()) == NULL)
293 fatal("dh_new_group: DH_new");
303 static char *gen = "2", *group1 =
304 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
305 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
306 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
307 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
308 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
309 "FFFFFFFF" "FFFFFFFF";
311 return (dh_new_group_asc(gen, group1));
317 static char *gen = "2", *group14 =
318 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
319 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
320 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
321 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
322 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
323 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
324 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
325 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
326 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
327 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
328 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
330 return (dh_new_group_asc(gen, group14));
334 * Estimates the group order for a Diffie-Hellman group that has an
335 * attack complexity approximately the same as O(2**bits). Estimate
336 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
340 dh_estimate(int bits)
344 return (1024); /* O(2**86) */
346 return (2048); /* O(2**116) */
347 return (4096); /* O(2**156) */