1 /* $OpenBSD: dh.c,v 1.46 2008/04/13 00:22:17 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
;
51 if ((arg
= strdelim(&cp
)) == NULL
)
53 /* Ignore leading whitespace */
56 if (!arg
|| !*arg
|| *arg
== '#')
60 if (cp
== NULL
|| *arg
== '\0')
62 arg
= strsep(&cp
, " "); /* type */
63 if (cp
== NULL
|| *arg
== '\0')
65 arg
= strsep(&cp
, " "); /* tests */
66 if (cp
== NULL
|| *arg
== '\0')
68 arg
= strsep(&cp
, " "); /* tries */
69 if (cp
== NULL
|| *arg
== '\0')
71 strsize
= strsep(&cp
, " "); /* size */
72 if (cp
== NULL
|| *strsize
== '\0' ||
73 (dhg
->size
= (u_int
)strtonum(strsize
, 0, 64*1024, &errstr
)) == 0 ||
76 /* The whole group is one bit larger */
78 gen
= strsep(&cp
, " "); /* gen */
79 if (cp
== NULL
|| *gen
== '\0')
81 prime
= strsep(&cp
, " "); /* prime */
82 if (cp
!= NULL
|| *prime
== '\0')
85 if ((dhg
->g
= BN_new()) == NULL
)
86 fatal("parse_prime: BN_new failed");
87 if ((dhg
->p
= BN_new()) == NULL
)
88 fatal("parse_prime: BN_new failed");
89 if (BN_hex2bn(&dhg
->g
, gen
) == 0)
92 if (BN_hex2bn(&dhg
->p
, prime
) == 0)
95 if (BN_num_bits(dhg
->p
) != dhg
->size
)
98 if (BN_is_zero(dhg
->g
) || BN_is_one(dhg
->g
))
104 BN_clear_free(dhg
->g
);
105 BN_clear_free(dhg
->p
);
107 error("Bad prime description in line %d", linenum
);
112 choose_dh(int min
, int wantbits
, int max
)
116 int best
, bestcount
, which
;
120 if ((f
= fopen(_PATH_DH_MODULI
, "r")) == NULL
&&
121 (f
= fopen(_PATH_DH_PRIMES
, "r")) == NULL
) {
122 logit("WARNING: %s does not exist, using fixed modulus",
124 return (dh_new_group14());
128 best
= bestcount
= 0;
129 while (fgets(line
, sizeof(line
), f
)) {
131 if (!parse_prime(linenum
, line
, &dhg
))
133 BN_clear_free(dhg
.g
);
134 BN_clear_free(dhg
.p
);
136 if (dhg
.size
> max
|| dhg
.size
< min
)
139 if ((dhg
.size
> wantbits
&& dhg
.size
< best
) ||
140 (dhg
.size
> best
&& best
< wantbits
)) {
144 if (dhg
.size
== best
)
149 if (bestcount
== 0) {
151 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES
);
152 return (dh_new_group14());
156 which
= arc4random_uniform(bestcount
);
157 while (fgets(line
, sizeof(line
), f
)) {
158 if (!parse_prime(linenum
, line
, &dhg
))
160 if ((dhg
.size
> max
|| dhg
.size
< min
) ||
162 linenum
++ != which
) {
163 BN_clear_free(dhg
.g
);
164 BN_clear_free(dhg
.p
);
170 if (linenum
!= which
+1)
171 fatal("WARNING: line %d disappeared in %s, giving up",
172 which
, _PATH_DH_PRIMES
);
174 return (dh_new_group(dhg
.g
, dhg
.p
));
177 /* diffie-hellman-groupN-sha1 */
180 dh_pub_is_valid(DH
*dh
, BIGNUM
*dh_pub
)
183 int n
= BN_num_bits(dh_pub
);
188 logit("invalid public DH value: negative");
191 if (BN_cmp(dh_pub
, BN_value_one()) != 1) { /* pub_exp <= 1 */
192 logit("invalid public DH value: <= 1");
196 if ((tmp
= BN_new()) == NULL
) {
197 error("%s: BN_new failed", __func__
);
200 if (!BN_sub(tmp
, dh
->p
, BN_value_one()) ||
201 BN_cmp(dh_pub
, tmp
) != -1) { /* pub_exp > p-2 */
203 logit("invalid public DH value: >= p-1");
208 for (i
= 0; i
<= n
; i
++)
209 if (BN_is_bit_set(dh_pub
, i
))
211 debug2("bits set: %d/%d", bits_set
, BN_num_bits(dh
->p
));
213 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
217 logit("invalid public DH value (%d/%d)", bits_set
, BN_num_bits(dh
->p
));
222 dh_gen_key(DH
*dh
, int need
)
224 int i
, bits_set
, tries
= 0;
227 fatal("dh_gen_key: dh->p == NULL");
228 if (need
> INT_MAX
/ 2 || 2 * need
>= BN_num_bits(dh
->p
))
229 fatal("dh_gen_key: group too small: %d (2*need %d)",
230 BN_num_bits(dh
->p
), 2*need
);
232 if (dh
->priv_key
!= NULL
)
233 BN_clear_free(dh
->priv_key
);
234 if ((dh
->priv_key
= BN_new()) == NULL
)
235 fatal("dh_gen_key: BN_new failed");
236 /* generate a 2*need bits random private exponent */
237 if (!BN_rand(dh
->priv_key
, 2*need
, 0, 0))
238 fatal("dh_gen_key: BN_rand failed");
239 if (DH_generate_key(dh
) == 0)
240 fatal("DH_generate_key");
241 for (i
= 0, bits_set
= 0; i
<= BN_num_bits(dh
->priv_key
); i
++)
242 if (BN_is_bit_set(dh
->priv_key
, i
))
244 debug2("dh_gen_key: priv key bits set: %d/%d",
245 bits_set
, BN_num_bits(dh
->priv_key
));
247 fatal("dh_gen_key: too many bad keys: giving up");
248 } while (!dh_pub_is_valid(dh
, dh
->pub_key
));
252 dh_new_group_asc(const char *gen
, const char *modulus
)
256 if ((dh
= DH_new()) == NULL
)
257 fatal("dh_new_group_asc: DH_new");
259 if (BN_hex2bn(&dh
->p
, modulus
) == 0)
260 fatal("BN_hex2bn p");
261 if (BN_hex2bn(&dh
->g
, gen
) == 0)
262 fatal("BN_hex2bn g");
268 * This just returns the group, we still need to generate the exchange
273 dh_new_group(BIGNUM
*gen
, BIGNUM
*modulus
)
277 if ((dh
= DH_new()) == NULL
)
278 fatal("dh_new_group: DH_new");
288 static char *gen
= "2", *group1
=
289 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
290 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
291 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
292 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
293 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
294 "FFFFFFFF" "FFFFFFFF";
296 return (dh_new_group_asc(gen
, group1
));
302 static char *gen
= "2", *group14
=
303 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
304 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
305 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
306 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
307 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
308 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
309 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
310 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
311 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
312 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
313 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
315 return (dh_new_group_asc(gen
, group14
));
319 * Estimates the group order for a Diffie-Hellman group that has an
320 * attack complexity approximately the same as O(2**bits). Estimate
321 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
325 dh_estimate(int bits
)
329 return (1024); /* O(2**86) */
331 return (2048); /* O(2**116) */
332 return (4096); /* O(2**156) */