Annotation of src/usr.bin/ssh/dh.c, Revision 1.55
1.55 ! deraadt 1: /* $OpenBSD: dh.c,v 1.54 2015/01/19 20:16:15 markus Exp $ */
1.1 provos 2: /*
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: */
1.39 stevesk 25:
1.55 ! deraadt 26: #include <sys/param.h> /* MIN */
1.1 provos 27:
28: #include <openssl/bn.h>
29: #include <openssl/dh.h>
1.38 stevesk 30:
1.41 stevesk 31: #include <stdio.h>
1.40 stevesk 32: #include <stdlib.h>
1.38 stevesk 33: #include <string.h>
1.55 ! deraadt 34: #include <limits.h>
1.1 provos 35:
36: #include "dh.h"
1.5 markus 37: #include "pathnames.h"
1.6 markus 38: #include "log.h"
39: #include "misc.h"
1.54 markus 40: #include "ssherr.h"
1.1 provos 41:
1.17 itojun 42: static int
1.1 provos 43: parse_prime(int linenum, char *line, struct dhgroup *dhg)
44: {
45: char *cp, *arg;
46: char *strsize, *gen, *prime;
1.35 deraadt 47: const char *errstr = NULL;
1.47 djm 48: long long n;
1.1 provos 49:
1.51 markus 50: dhg->p = dhg->g = NULL;
1.1 provos 51: cp = line;
1.32 djm 52: if ((arg = strdelim(&cp)) == NULL)
53: return 0;
1.1 provos 54: /* Ignore leading whitespace */
55: if (*arg == '\0')
56: arg = strdelim(&cp);
1.22 markus 57: if (!arg || !*arg || *arg == '#')
1.1 provos 58: return 0;
59:
60: /* time */
61: if (cp == NULL || *arg == '\0')
1.50 djm 62: goto truncated;
1.1 provos 63: arg = strsep(&cp, " "); /* type */
64: if (cp == NULL || *arg == '\0')
1.50 djm 65: goto truncated;
1.47 djm 66: /* Ensure this is a safe prime */
67: n = strtonum(arg, 0, 5, &errstr);
1.50 djm 68: if (errstr != NULL || n != MODULI_TYPE_SAFE) {
69: error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE);
1.47 djm 70: goto fail;
1.50 djm 71: }
1.1 provos 72: arg = strsep(&cp, " "); /* tests */
73: if (cp == NULL || *arg == '\0')
1.50 djm 74: goto truncated;
1.47 djm 75: /* Ensure prime has been tested and is not composite */
76: n = strtonum(arg, 0, 0x1f, &errstr);
77: if (errstr != NULL ||
1.50 djm 78: (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) {
79: error("moduli:%d: invalid moduli tests flag", linenum);
1.47 djm 80: goto fail;
1.50 djm 81: }
1.1 provos 82: arg = strsep(&cp, " "); /* tries */
83: if (cp == NULL || *arg == '\0')
1.50 djm 84: goto truncated;
1.47 djm 85: n = strtonum(arg, 0, 1<<30, &errstr);
1.50 djm 86: if (errstr != NULL || n == 0) {
87: error("moduli:%d: invalid primality trial count", linenum);
1.1 provos 88: goto fail;
1.50 djm 89: }
1.1 provos 90: strsize = strsep(&cp, " "); /* size */
91: if (cp == NULL || *strsize == '\0' ||
1.48 grunk 92: (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 ||
1.50 djm 93: errstr) {
94: error("moduli:%d: invalid prime length", linenum);
1.1 provos 95: goto fail;
1.50 djm 96: }
1.9 provos 97: /* The whole group is one bit larger */
98: dhg->size++;
1.1 provos 99: gen = strsep(&cp, " "); /* gen */
100: if (cp == NULL || *gen == '\0')
1.50 djm 101: goto truncated;
1.1 provos 102: prime = strsep(&cp, " "); /* prime */
1.50 djm 103: if (cp != NULL || *prime == '\0') {
104: truncated:
105: error("moduli:%d: truncated", linenum);
1.1 provos 106: goto fail;
1.50 djm 107: }
1.1 provos 108:
1.54 markus 109: if ((dhg->g = BN_new()) == NULL ||
110: (dhg->p = BN_new()) == NULL) {
111: error("parse_prime: BN_new failed");
112: goto fail;
113: }
1.50 djm 114: if (BN_hex2bn(&dhg->g, gen) == 0) {
115: error("moduli:%d: could not parse generator value", linenum);
116: goto fail;
117: }
118: if (BN_hex2bn(&dhg->p, prime) == 0) {
119: error("moduli:%d: could not parse prime value", linenum);
120: goto fail;
121: }
122: if (BN_num_bits(dhg->p) != dhg->size) {
123: error("moduli:%d: prime has wrong size: actual %d listed %d",
124: linenum, BN_num_bits(dhg->p), dhg->size - 1);
125: goto fail;
126: }
127: if (BN_cmp(dhg->g, BN_value_one()) <= 0) {
128: error("moduli:%d: generator is invalid", linenum);
129: goto fail;
130: }
131: return 1;
1.10 provos 132:
1.1 provos 133: fail:
1.50 djm 134: if (dhg->g != NULL)
135: BN_clear_free(dhg->g);
136: if (dhg->p != NULL)
137: BN_clear_free(dhg->p);
138: dhg->g = dhg->p = NULL;
139: return 0;
1.1 provos 140: }
141:
142: DH *
1.9 provos 143: choose_dh(int min, int wantbits, int max)
1.1 provos 144: {
145: FILE *f;
1.28 dtucker 146: char line[4096];
1.1 provos 147: int best, bestcount, which;
148: int linenum;
149: struct dhgroup dhg;
150:
1.15 provos 151: if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL &&
152: (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) {
1.30 djm 153: logit("WARNING: %s does not exist, using fixed modulus",
154: _PATH_DH_MODULI);
155: return (dh_new_group14());
1.1 provos 156: }
157:
158: linenum = 0;
159: best = bestcount = 0;
160: while (fgets(line, sizeof(line), f)) {
161: linenum++;
162: if (!parse_prime(linenum, line, &dhg))
163: continue;
1.19 markus 164: BN_clear_free(dhg.g);
165: BN_clear_free(dhg.p);
1.1 provos 166:
1.9 provos 167: if (dhg.size > max || dhg.size < min)
168: continue;
169:
170: if ((dhg.size > wantbits && dhg.size < best) ||
171: (dhg.size > best && best < wantbits)) {
1.1 provos 172: best = dhg.size;
173: bestcount = 0;
174: }
175: if (dhg.size == best)
176: bestcount++;
177: }
1.16 provos 178: rewind(f);
1.1 provos 179:
180: if (bestcount == 0) {
1.16 provos 181: fclose(f);
1.24 itojun 182: logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES);
1.31 djm 183: return (dh_new_group14());
1.1 provos 184: }
185:
186: linenum = 0;
1.46 djm 187: which = arc4random_uniform(bestcount);
1.1 provos 188: while (fgets(line, sizeof(line), f)) {
189: if (!parse_prime(linenum, line, &dhg))
1.9 provos 190: continue;
1.13 markus 191: if ((dhg.size > max || dhg.size < min) ||
192: dhg.size != best ||
193: linenum++ != which) {
1.19 markus 194: BN_clear_free(dhg.g);
195: BN_clear_free(dhg.p);
1.1 provos 196: continue;
197: }
198: break;
199: }
200: fclose(f);
1.54 markus 201: if (linenum != which+1) {
202: logit("WARNING: line %d disappeared in %s, giving up",
1.13 markus 203: which, _PATH_DH_PRIMES);
1.54 markus 204: return (dh_new_group14());
205: }
1.1 provos 206:
207: return (dh_new_group(dhg.g, dhg.p));
1.11 markus 208: }
209:
1.30 djm 210: /* diffie-hellman-groupN-sha1 */
1.11 markus 211:
212: int
213: dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
214: {
215: int i;
216: int n = BN_num_bits(dh_pub);
217: int bits_set = 0;
1.36 djm 218: BIGNUM *tmp;
1.11 markus 219:
220: if (dh_pub->neg) {
1.45 ray 221: logit("invalid public DH value: negative");
1.11 markus 222: return 0;
223: }
1.36 djm 224: if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */
225: logit("invalid public DH value: <= 1");
226: return 0;
227: }
228:
1.45 ray 229: if ((tmp = BN_new()) == NULL) {
230: error("%s: BN_new failed", __func__);
231: return 0;
232: }
1.36 djm 233: if (!BN_sub(tmp, dh->p, BN_value_one()) ||
234: BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */
235: BN_clear_free(tmp);
236: logit("invalid public DH value: >= p-1");
237: return 0;
238: }
239: BN_clear_free(tmp);
240:
1.11 markus 241: for (i = 0; i <= n; i++)
242: if (BN_is_bit_set(dh_pub, i))
243: bits_set++;
1.23 markus 244: debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
1.11 markus 245:
246: /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
1.36 djm 247: if (bits_set > 1)
1.11 markus 248: return 1;
1.36 djm 249:
1.24 itojun 250: logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
1.11 markus 251: return 0;
252: }
253:
1.54 markus 254: int
1.11 markus 255: dh_gen_key(DH *dh, int need)
256: {
1.53 djm 257: int pbits;
1.11 markus 258:
1.54 markus 259: if (need < 0 || dh->p == NULL ||
260: (pbits = BN_num_bits(dh->p)) <= 0 ||
261: need > INT_MAX / 2 || 2 * need >= pbits)
262: return SSH_ERR_INVALID_ARGUMENT;
1.53 djm 263: dh->length = MIN(need * 2, pbits - 1);
1.54 markus 264: if (DH_generate_key(dh) == 0 ||
265: !dh_pub_is_valid(dh, dh->pub_key)) {
266: BN_clear_free(dh->priv_key);
267: return SSH_ERR_LIBCRYPTO_ERROR;
268: }
269: return 0;
1.11 markus 270: }
271:
272: DH *
273: dh_new_group_asc(const char *gen, const char *modulus)
274: {
275: DH *dh;
276:
1.18 markus 277: if ((dh = DH_new()) == NULL)
1.54 markus 278: return NULL;
279: if (BN_hex2bn(&dh->p, modulus) == 0 ||
280: BN_hex2bn(&dh->g, gen) == 0) {
281: DH_free(dh);
282: return NULL;
283: }
1.11 markus 284: return (dh);
285: }
286:
287: /*
288: * This just returns the group, we still need to generate the exchange
289: * value.
290: */
291:
292: DH *
293: dh_new_group(BIGNUM *gen, BIGNUM *modulus)
294: {
295: DH *dh;
296:
1.18 markus 297: if ((dh = DH_new()) == NULL)
1.54 markus 298: return NULL;
1.11 markus 299: dh->p = modulus;
300: dh->g = gen;
301:
302: return (dh);
303: }
304:
305: DH *
306: dh_new_group1(void)
307: {
308: static char *gen = "2", *group1 =
309: "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
310: "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
311: "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
312: "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
313: "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
314: "FFFFFFFF" "FFFFFFFF";
315:
316: return (dh_new_group_asc(gen, group1));
1.30 djm 317: }
318:
319: DH *
320: dh_new_group14(void)
321: {
322: static char *gen = "2", *group14 =
323: "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
324: "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
325: "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
326: "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
327: "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D"
328: "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F"
329: "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D"
330: "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B"
331: "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9"
332: "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510"
333: "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF";
334:
335: return (dh_new_group_asc(gen, group14));
1.12 markus 336: }
337:
338: /*
339: * Estimates the group order for a Diffie-Hellman group that has an
1.52 dtucker 340: * attack complexity approximately the same as O(2**bits).
341: * Values from NIST Special Publication 800-57: Recommendation for Key
342: * Management Part 1 (rev 3) limited by the recommended maximum value
343: * from RFC4419 section 3.
1.12 markus 344: */
345:
1.54 markus 346: u_int
1.12 markus 347: dh_estimate(int bits)
348: {
1.52 dtucker 349: if (bits <= 112)
350: return 2048;
1.26 markus 351: if (bits <= 128)
1.52 dtucker 352: return 3072;
1.26 markus 353: if (bits <= 192)
1.52 dtucker 354: return 7680;
355: return 8192;
1.1 provos 356: }