blob: b9029d867e18e42cd390314597b35fdf1179eb81 [file] [log] [blame]
Darren Tucker759cb2a2009-10-07 09:01:50 +11001/* $OpenBSD: dh.c,v 1.48 2009/10/01 11:37:33 grunk Exp $ */
Damien Miller874d77b2000-10-14 16:23:11 +11002/*
3 * Copyright (c) 2000 Niels Provos. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
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.
13 *
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.
24 */
25
26#include "includes.h"
Damien Miller874d77b2000-10-14 16:23:11 +110027
Damien Miller8dbffe72006-08-05 11:02:17 +100028#include <sys/param.h>
29
Damien Miller874d77b2000-10-14 16:23:11 +110030#include <openssl/bn.h>
31#include <openssl/dh.h>
Damien Miller874d77b2000-10-14 16:23:11 +110032
Damien Millerded319c2006-09-01 15:38:36 +100033#include <stdarg.h>
Damien Millera7a73ee2006-08-05 11:37:59 +100034#include <stdio.h>
Damien Millere7a1e5c2006-08-05 11:34:19 +100035#include <stdlib.h>
Damien Millere3476ed2006-07-24 14:13:33 +100036#include <string.h>
37
Damien Miller874d77b2000-10-14 16:23:11 +110038#include "dh.h"
Ben Lindstrom226cfa02001-01-22 05:34:40 +000039#include "pathnames.h"
40#include "log.h"
41#include "misc.h"
Damien Miller874d77b2000-10-14 16:23:11 +110042
Ben Lindstrombba81212001-06-25 05:01:22 +000043static int
Damien Miller874d77b2000-10-14 16:23:11 +110044parse_prime(int linenum, char *line, struct dhgroup *dhg)
45{
46 char *cp, *arg;
47 char *strsize, *gen, *prime;
Damien Miller5a73c1a2006-03-31 23:09:41 +110048 const char *errstr = NULL;
Damien Miller2e9cf492008-06-29 22:47:04 +100049 long long n;
Damien Miller874d77b2000-10-14 16:23:11 +110050
51 cp = line;
Damien Miller928b2362006-03-26 13:53:32 +110052 if ((arg = strdelim(&cp)) == NULL)
53 return 0;
Damien Miller874d77b2000-10-14 16:23:11 +110054 /* Ignore leading whitespace */
55 if (*arg == '\0')
56 arg = strdelim(&cp);
Ben Lindstrom04f9af72002-07-04 00:03:56 +000057 if (!arg || !*arg || *arg == '#')
Damien Miller874d77b2000-10-14 16:23:11 +110058 return 0;
59
60 /* time */
61 if (cp == NULL || *arg == '\0')
62 goto fail;
63 arg = strsep(&cp, " "); /* type */
64 if (cp == NULL || *arg == '\0')
65 goto fail;
Damien Miller2e9cf492008-06-29 22:47:04 +100066 /* Ensure this is a safe prime */
67 n = strtonum(arg, 0, 5, &errstr);
68 if (errstr != NULL || n != MODULI_TYPE_SAFE)
69 goto fail;
Damien Miller874d77b2000-10-14 16:23:11 +110070 arg = strsep(&cp, " "); /* tests */
71 if (cp == NULL || *arg == '\0')
72 goto fail;
Damien Miller2e9cf492008-06-29 22:47:04 +100073 /* Ensure prime has been tested and is not composite */
74 n = strtonum(arg, 0, 0x1f, &errstr);
75 if (errstr != NULL ||
76 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE))
77 goto fail;
Damien Miller874d77b2000-10-14 16:23:11 +110078 arg = strsep(&cp, " "); /* tries */
79 if (cp == NULL || *arg == '\0')
80 goto fail;
Damien Miller2e9cf492008-06-29 22:47:04 +100081 n = strtonum(arg, 0, 1<<30, &errstr);
82 if (errstr != NULL || n == 0)
83 goto fail;
Damien Miller874d77b2000-10-14 16:23:11 +110084 strsize = strsep(&cp, " "); /* size */
85 if (cp == NULL || *strsize == '\0' ||
Darren Tucker759cb2a2009-10-07 09:01:50 +110086 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
Damien Miller5a73c1a2006-03-31 23:09:41 +110087 errstr)
Damien Miller874d77b2000-10-14 16:23:11 +110088 goto fail;
Ben Lindstromdf221392001-03-29 00:36:16 +000089 /* The whole group is one bit larger */
90 dhg->size++;
Damien Miller874d77b2000-10-14 16:23:11 +110091 gen = strsep(&cp, " "); /* gen */
92 if (cp == NULL || *gen == '\0')
93 goto fail;
94 prime = strsep(&cp, " "); /* prime */
95 if (cp != NULL || *prime == '\0')
96 goto fail;
97
Damien Millerda755162002-01-22 23:09:22 +110098 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");
Ben Lindstrom206941f2001-04-15 14:27:16 +0000102 if (BN_hex2bn(&dhg->g, gen) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +1000103 goto failclean;
104
Ben Lindstrom206941f2001-04-15 14:27:16 +0000105 if (BN_hex2bn(&dhg->p, prime) == 0)
Damien Miller23e526e2001-03-30 10:47:43 +1000106 goto failclean;
107
108 if (BN_num_bits(dhg->p) != dhg->size)
109 goto failclean;
Damien Miller874d77b2000-10-14 16:23:11 +1100110
Darren Tuckerfc113c92004-02-29 20:12:33 +1100111 if (BN_is_zero(dhg->g) || BN_is_one(dhg->g))
112 goto failclean;
113
Damien Miller874d77b2000-10-14 16:23:11 +1100114 return (1);
Damien Miller23e526e2001-03-30 10:47:43 +1000115
116 failclean:
Damien Miller9ef95dd2002-01-22 23:10:33 +1100117 BN_clear_free(dhg->g);
118 BN_clear_free(dhg->p);
Damien Miller874d77b2000-10-14 16:23:11 +1100119 fail:
Ben Lindstrom6df8ef42001-03-05 07:47:23 +0000120 error("Bad prime description in line %d", linenum);
Damien Miller874d77b2000-10-14 16:23:11 +1100121 return (0);
122}
123
124DH *
Ben Lindstromdf221392001-03-29 00:36:16 +0000125choose_dh(int min, int wantbits, int max)
Damien Miller874d77b2000-10-14 16:23:11 +1100126{
127 FILE *f;
Darren Tuckerc56c7ef2004-02-29 20:13:34 +1100128 char line[4096];
Damien Miller874d77b2000-10-14 16:23:11 +1100129 int best, bestcount, which;
130 int linenum;
131 struct dhgroup dhg;
132
Ben Lindstrom93a29e02001-06-25 04:13:25 +0000133 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
134 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
Damien Millerf675fc42004-06-15 10:30:09 +1000135 logit("WARNING: %s does not exist, using fixed modulus",
136 _PATH_DH_MODULI);
137 return (dh_new_group14());
Damien Miller874d77b2000-10-14 16:23:11 +1100138 }
139
140 linenum = 0;
141 best = bestcount = 0;
142 while (fgets(line, sizeof(line), f)) {
143 linenum++;
144 if (!parse_prime(linenum, line, &dhg))
145 continue;
Damien Miller9ef95dd2002-01-22 23:10:33 +1100146 BN_clear_free(dhg.g);
147 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100148
Ben Lindstromdf221392001-03-29 00:36:16 +0000149 if (dhg.size > max || dhg.size < min)
150 continue;
151
152 if ((dhg.size > wantbits && dhg.size < best) ||
153 (dhg.size > best && best < wantbits)) {
Damien Miller874d77b2000-10-14 16:23:11 +1100154 best = dhg.size;
155 bestcount = 0;
156 }
157 if (dhg.size == best)
158 bestcount++;
159 }
Ben Lindstromaf738802001-06-25 04:18:59 +0000160 rewind(f);
Damien Miller874d77b2000-10-14 16:23:11 +1100161
162 if (bestcount == 0) {
Ben Lindstromaf738802001-06-25 04:18:59 +0000163 fclose(f);
Damien Miller996acd22003-04-09 20:59:48 +1000164 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
Darren Tucker9a2bd112004-08-12 22:40:59 +1000165 return (dh_new_group14());
Damien Miller874d77b2000-10-14 16:23:11 +1100166 }
167
Damien Miller874d77b2000-10-14 16:23:11 +1100168 linenum = 0;
Damien Miller354c48c2008-05-19 14:50:00 +1000169 which = arc4random_uniform(bestcount);
Damien Miller874d77b2000-10-14 16:23:11 +1100170 while (fgets(line, sizeof(line), f)) {
171 if (!parse_prime(linenum, line, &dhg))
172 continue;
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000173 if ((dhg.size > max || dhg.size < min) ||
174 dhg.size != best ||
175 linenum++ != which) {
Damien Miller9ef95dd2002-01-22 23:10:33 +1100176 BN_clear_free(dhg.g);
177 BN_clear_free(dhg.p);
Damien Miller874d77b2000-10-14 16:23:11 +1100178 continue;
179 }
180 break;
181 }
182 fclose(f);
Ben Lindstrom5ba23b32001-04-05 02:05:21 +0000183 if (linenum != which+1)
184 fatal("WARNING: line %d disappeared in %s, giving up",
185 which, _PATH_DH_PRIMES);
Damien Miller874d77b2000-10-14 16:23:11 +1100186
187 return (dh_new_group(dhg.g, dhg.p));
188}
Damien Miller9709f902001-03-30 10:50:10 +1000189
Damien Millerf675fc42004-06-15 10:30:09 +1000190/* diffie-hellman-groupN-sha1 */
Damien Miller9709f902001-03-30 10:50:10 +1000191
192int
193dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
194{
195 int i;
196 int n = BN_num_bits(dh_pub);
197 int bits_set = 0;
Darren Tucker31cde682006-05-06 17:43:33 +1000198 BIGNUM *tmp;
Damien Miller9709f902001-03-30 10:50:10 +1000199
200 if (dh_pub->neg) {
Damien Miller603077a2007-10-26 14:25:55 +1000201 logit("invalid public DH value: negative");
Damien Miller9709f902001-03-30 10:50:10 +1000202 return 0;
203 }
Darren Tucker31cde682006-05-06 17:43:33 +1000204 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
205 logit("invalid public DH value: <= 1");
206 return 0;
207 }
208
Damien Miller603077a2007-10-26 14:25:55 +1000209 if ((tmp = BN_new()) == NULL) {
210 error("%s: BN_new failed", __func__);
211 return 0;
212 }
Darren Tucker31cde682006-05-06 17:43:33 +1000213 if (!BN_sub(tmp, dh->p, BN_value_one()) ||
214 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
215 BN_clear_free(tmp);
216 logit("invalid public DH value: >= p-1");
217 return 0;
218 }
219 BN_clear_free(tmp);
220
Damien Miller9709f902001-03-30 10:50:10 +1000221 for (i = 0; i <= n; i++)
222 if (BN_is_bit_set(dh_pub, i))
223 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000224 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000225
226 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
Darren Tucker31cde682006-05-06 17:43:33 +1000227 if (bits_set > 1)
Damien Miller9709f902001-03-30 10:50:10 +1000228 return 1;
Darren Tucker31cde682006-05-06 17:43:33 +1000229
Damien Miller996acd22003-04-09 20:59:48 +1000230 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
Damien Miller9709f902001-03-30 10:50:10 +1000231 return 0;
232}
233
234void
235dh_gen_key(DH *dh, int need)
236{
Darren Tuckereffc84c2004-02-29 20:15:08 +1100237 int i, bits_set, tries = 0;
Damien Miller9709f902001-03-30 10:50:10 +1000238
239 if (dh->p == NULL)
240 fatal("dh_gen_key: dh->p == NULL");
Darren Tuckerc0815c92003-09-22 21:05:50 +1000241 if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))
Damien Miller9709f902001-03-30 10:50:10 +1000242 fatal("dh_gen_key: group too small: %d (2*need %d)",
243 BN_num_bits(dh->p), 2*need);
244 do {
245 if (dh->priv_key != NULL)
Damien Miller9ef95dd2002-01-22 23:10:33 +1100246 BN_clear_free(dh->priv_key);
Damien Millerda755162002-01-22 23:09:22 +1100247 if ((dh->priv_key = BN_new()) == NULL)
Damien Miller9709f902001-03-30 10:50:10 +1000248 fatal("dh_gen_key: BN_new failed");
249 /* generate a 2*need bits random private exponent */
Damien Miller6d6c5d22002-03-07 12:58:42 +1100250 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
251 fatal("dh_gen_key: BN_rand failed");
Damien Miller9709f902001-03-30 10:50:10 +1000252 if (DH_generate_key(dh) == 0)
253 fatal("DH_generate_key");
Darren Tuckereffc84c2004-02-29 20:15:08 +1100254 for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)
Damien Miller9709f902001-03-30 10:50:10 +1000255 if (BN_is_bit_set(dh->priv_key, i))
256 bits_set++;
Ben Lindstrom1f530832002-12-23 02:03:02 +0000257 debug2("dh_gen_key: priv key bits set: %d/%d",
Damien Miller9709f902001-03-30 10:50:10 +1000258 bits_set, BN_num_bits(dh->priv_key));
259 if (tries++ > 10)
260 fatal("dh_gen_key: too many bad keys: giving up");
261 } while (!dh_pub_is_valid(dh, dh->pub_key));
262}
263
264DH *
265dh_new_group_asc(const char *gen, const char *modulus)
266{
267 DH *dh;
Damien Miller9709f902001-03-30 10:50:10 +1000268
Damien Millerda755162002-01-22 23:09:22 +1100269 if ((dh = DH_new()) == NULL)
270 fatal("dh_new_group_asc: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000271
Darren Tuckerb0781f72006-11-08 10:01:36 +1100272 if (BN_hex2bn(&dh->p, modulus) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000273 fatal("BN_hex2bn p");
Darren Tuckerb0781f72006-11-08 10:01:36 +1100274 if (BN_hex2bn(&dh->g, gen) == 0)
Damien Miller9709f902001-03-30 10:50:10 +1000275 fatal("BN_hex2bn g");
276
277 return (dh);
278}
279
280/*
281 * This just returns the group, we still need to generate the exchange
282 * value.
283 */
284
285DH *
286dh_new_group(BIGNUM *gen, BIGNUM *modulus)
287{
288 DH *dh;
289
Damien Millerda755162002-01-22 23:09:22 +1100290 if ((dh = DH_new()) == NULL)
291 fatal("dh_new_group: DH_new");
Damien Miller9709f902001-03-30 10:50:10 +1000292 dh->p = modulus;
293 dh->g = gen;
294
295 return (dh);
296}
297
298DH *
299dh_new_group1(void)
300{
301 static char *gen = "2", *group1 =
302 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
303 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
304 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
305 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
306 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
307 "FFFFFFFF" "FFFFFFFF";
308
309 return (dh_new_group_asc(gen, group1));
310}
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000311
Damien Millerf675fc42004-06-15 10:30:09 +1000312DH *
313dh_new_group14(void)
314{
315 static char *gen = "2", *group14 =
316 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
317 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
318 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
319 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
320 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
321 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
322 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
323 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
324 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
325 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
326 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
327
328 return (dh_new_group_asc(gen, group14));
329}
330
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000331/*
332 * Estimates the group order for a Diffie-Hellman group that has an
333 * attack complexity approximately the same as O(2**bits). Estimate
334 * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
335 */
336
337int
338dh_estimate(int bits)
339{
340
Damien Miller8975ddf2003-12-17 16:33:53 +1100341 if (bits <= 128)
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000342 return (1024); /* O(2**86) */
Damien Miller8975ddf2003-12-17 16:33:53 +1100343 if (bits <= 192)
Ben Lindstrom20d7c7b2001-04-04 01:56:17 +0000344 return (2048); /* O(2**116) */
345 return (4096); /* O(2**156) */
346}