xref: /freebsd/crypto/openssh/kex.c (revision 3fc36ee018bb836bd1796067cf4ef8683f166ebc)
1 /* $OpenBSD: kex.c,v 1.117 2016/02/08 10:57:07 djm Exp $ */
2 /*
3  * Copyright (c) 2000, 2001 Markus Friedl.  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"
27 
28 #include <sys/param.h>	/* MAX roundup */
29 
30 #include <signal.h>
31 #include <stdarg.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 
36 #ifdef WITH_OPENSSL
37 #include <openssl/crypto.h>
38 #endif
39 
40 #include "ssh2.h"
41 #include "packet.h"
42 #include "compat.h"
43 #include "cipher.h"
44 #include "sshkey.h"
45 #include "kex.h"
46 #include "log.h"
47 #include "mac.h"
48 #include "match.h"
49 #include "misc.h"
50 #include "dispatch.h"
51 #include "monitor.h"
52 
53 #include "ssherr.h"
54 #include "sshbuf.h"
55 #include "digest.h"
56 
57 #if OPENSSL_VERSION_NUMBER >= 0x00907000L
58 # if defined(HAVE_EVP_SHA256)
59 # define evp_ssh_sha256 EVP_sha256
60 # else
61 extern const EVP_MD *evp_ssh_sha256(void);
62 # endif
63 #endif
64 
65 /* prototype */
66 static int kex_choose_conf(struct ssh *);
67 static int kex_input_newkeys(int, u_int32_t, void *);
68 
69 static const char *proposal_names[PROPOSAL_MAX] = {
70 	"KEX algorithms",
71 	"host key algorithms",
72 	"ciphers ctos",
73 	"ciphers stoc",
74 	"MACs ctos",
75 	"MACs stoc",
76 	"compression ctos",
77 	"compression stoc",
78 	"languages ctos",
79 	"languages stoc",
80 };
81 
82 struct kexalg {
83 	char *name;
84 	u_int type;
85 	int ec_nid;
86 	int hash_alg;
87 };
88 static const struct kexalg kexalgs[] = {
89 #ifdef WITH_OPENSSL
90 	{ KEX_DH1, KEX_DH_GRP1_SHA1, 0, SSH_DIGEST_SHA1 },
91 	{ KEX_DH14, KEX_DH_GRP14_SHA1, 0, SSH_DIGEST_SHA1 },
92 	{ KEX_DHGEX_SHA1, KEX_DH_GEX_SHA1, 0, SSH_DIGEST_SHA1 },
93 #ifdef HAVE_EVP_SHA256
94 	{ KEX_DHGEX_SHA256, KEX_DH_GEX_SHA256, 0, SSH_DIGEST_SHA256 },
95 #endif /* HAVE_EVP_SHA256 */
96 #ifdef OPENSSL_HAS_ECC
97 	{ KEX_ECDH_SHA2_NISTP256, KEX_ECDH_SHA2,
98 	    NID_X9_62_prime256v1, SSH_DIGEST_SHA256 },
99 	{ KEX_ECDH_SHA2_NISTP384, KEX_ECDH_SHA2, NID_secp384r1,
100 	    SSH_DIGEST_SHA384 },
101 # ifdef OPENSSL_HAS_NISTP521
102 	{ KEX_ECDH_SHA2_NISTP521, KEX_ECDH_SHA2, NID_secp521r1,
103 	    SSH_DIGEST_SHA512 },
104 # endif /* OPENSSL_HAS_NISTP521 */
105 #endif /* OPENSSL_HAS_ECC */
106 #endif /* WITH_OPENSSL */
107 #if defined(HAVE_EVP_SHA256) || !defined(WITH_OPENSSL)
108 	{ KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
109 #endif /* HAVE_EVP_SHA256 || !WITH_OPENSSL */
110 	{ NULL, -1, -1, -1},
111 };
112 
113 char *
114 kex_alg_list(char sep)
115 {
116 	char *ret = NULL, *tmp;
117 	size_t nlen, rlen = 0;
118 	const struct kexalg *k;
119 
120 	for (k = kexalgs; k->name != NULL; k++) {
121 		if (ret != NULL)
122 			ret[rlen++] = sep;
123 		nlen = strlen(k->name);
124 		if ((tmp = realloc(ret, rlen + nlen + 2)) == NULL) {
125 			free(ret);
126 			return NULL;
127 		}
128 		ret = tmp;
129 		memcpy(ret + rlen, k->name, nlen + 1);
130 		rlen += nlen;
131 	}
132 	return ret;
133 }
134 
135 static const struct kexalg *
136 kex_alg_by_name(const char *name)
137 {
138 	const struct kexalg *k;
139 
140 	for (k = kexalgs; k->name != NULL; k++) {
141 		if (strcmp(k->name, name) == 0)
142 			return k;
143 	}
144 	return NULL;
145 }
146 
147 /* Validate KEX method name list */
148 int
149 kex_names_valid(const char *names)
150 {
151 	char *s, *cp, *p;
152 
153 	if (names == NULL || strcmp(names, "") == 0)
154 		return 0;
155 	if ((s = cp = strdup(names)) == NULL)
156 		return 0;
157 	for ((p = strsep(&cp, ",")); p && *p != '\0';
158 	    (p = strsep(&cp, ","))) {
159 		if (kex_alg_by_name(p) == NULL) {
160 			error("Unsupported KEX algorithm \"%.100s\"", p);
161 			free(s);
162 			return 0;
163 		}
164 	}
165 	debug3("kex names ok: [%s]", names);
166 	free(s);
167 	return 1;
168 }
169 
170 /*
171  * Concatenate algorithm names, avoiding duplicates in the process.
172  * Caller must free returned string.
173  */
174 char *
175 kex_names_cat(const char *a, const char *b)
176 {
177 	char *ret = NULL, *tmp = NULL, *cp, *p;
178 	size_t len;
179 
180 	if (a == NULL || *a == '\0')
181 		return NULL;
182 	if (b == NULL || *b == '\0')
183 		return strdup(a);
184 	if (strlen(b) > 1024*1024)
185 		return NULL;
186 	len = strlen(a) + strlen(b) + 2;
187 	if ((tmp = cp = strdup(b)) == NULL ||
188 	    (ret = calloc(1, len)) == NULL) {
189 		free(tmp);
190 		return NULL;
191 	}
192 	strlcpy(ret, a, len);
193 	for ((p = strsep(&cp, ",")); p && *p != '\0'; (p = strsep(&cp, ","))) {
194 		if (match_list(ret, p, NULL) != NULL)
195 			continue; /* Algorithm already present */
196 		if (strlcat(ret, ",", len) >= len ||
197 		    strlcat(ret, p, len) >= len) {
198 			free(tmp);
199 			free(ret);
200 			return NULL; /* Shouldn't happen */
201 		}
202 	}
203 	free(tmp);
204 	return ret;
205 }
206 
207 /*
208  * Assemble a list of algorithms from a default list and a string from a
209  * configuration file. The user-provided string may begin with '+' to
210  * indicate that it should be appended to the default.
211  */
212 int
213 kex_assemble_names(const char *def, char **list)
214 {
215 	char *ret;
216 
217 	if (list == NULL || *list == NULL || **list == '\0') {
218 		*list = strdup(def);
219 		return 0;
220 	}
221 	if (**list != '+') {
222 		return 0;
223 	}
224 
225 	if ((ret = kex_names_cat(def, *list + 1)) == NULL)
226 		return SSH_ERR_ALLOC_FAIL;
227 	free(*list);
228 	*list = ret;
229 	return 0;
230 }
231 
232 /* put algorithm proposal into buffer */
233 int
234 kex_prop2buf(struct sshbuf *b, char *proposal[PROPOSAL_MAX])
235 {
236 	u_int i;
237 	int r;
238 
239 	sshbuf_reset(b);
240 
241 	/*
242 	 * add a dummy cookie, the cookie will be overwritten by
243 	 * kex_send_kexinit(), each time a kexinit is set
244 	 */
245 	for (i = 0; i < KEX_COOKIE_LEN; i++) {
246 		if ((r = sshbuf_put_u8(b, 0)) != 0)
247 			return r;
248 	}
249 	for (i = 0; i < PROPOSAL_MAX; i++) {
250 		if ((r = sshbuf_put_cstring(b, proposal[i])) != 0)
251 			return r;
252 	}
253 	if ((r = sshbuf_put_u8(b, 0)) != 0 ||	/* first_kex_packet_follows */
254 	    (r = sshbuf_put_u32(b, 0)) != 0)	/* uint32 reserved */
255 		return r;
256 	return 0;
257 }
258 
259 /* parse buffer and return algorithm proposal */
260 int
261 kex_buf2prop(struct sshbuf *raw, int *first_kex_follows, char ***propp)
262 {
263 	struct sshbuf *b = NULL;
264 	u_char v;
265 	u_int i;
266 	char **proposal = NULL;
267 	int r;
268 
269 	*propp = NULL;
270 	if ((proposal = calloc(PROPOSAL_MAX, sizeof(char *))) == NULL)
271 		return SSH_ERR_ALLOC_FAIL;
272 	if ((b = sshbuf_fromb(raw)) == NULL) {
273 		r = SSH_ERR_ALLOC_FAIL;
274 		goto out;
275 	}
276 	if ((r = sshbuf_consume(b, KEX_COOKIE_LEN)) != 0) /* skip cookie */
277 		goto out;
278 	/* extract kex init proposal strings */
279 	for (i = 0; i < PROPOSAL_MAX; i++) {
280 		if ((r = sshbuf_get_cstring(b, &(proposal[i]), NULL)) != 0)
281 			goto out;
282 		debug2("%s: %s", proposal_names[i], proposal[i]);
283 	}
284 	/* first kex follows / reserved */
285 	if ((r = sshbuf_get_u8(b, &v)) != 0 ||	/* first_kex_follows */
286 	    (r = sshbuf_get_u32(b, &i)) != 0)	/* reserved */
287 		goto out;
288 	if (first_kex_follows != NULL)
289 		*first_kex_follows = v;
290 	debug2("first_kex_follows %d ", v);
291 	debug2("reserved %u ", i);
292 	r = 0;
293 	*propp = proposal;
294  out:
295 	if (r != 0 && proposal != NULL)
296 		kex_prop_free(proposal);
297 	sshbuf_free(b);
298 	return r;
299 }
300 
301 void
302 kex_prop_free(char **proposal)
303 {
304 	u_int i;
305 
306 	if (proposal == NULL)
307 		return;
308 	for (i = 0; i < PROPOSAL_MAX; i++)
309 		free(proposal[i]);
310 	free(proposal);
311 }
312 
313 /* ARGSUSED */
314 static int
315 kex_protocol_error(int type, u_int32_t seq, void *ctxt)
316 {
317 	struct ssh *ssh = active_state; /* XXX */
318 	int r;
319 
320 	error("kex protocol error: type %d seq %u", type, seq);
321 	if ((r = sshpkt_start(ssh, SSH2_MSG_UNIMPLEMENTED)) != 0 ||
322 	    (r = sshpkt_put_u32(ssh, seq)) != 0 ||
323 	    (r = sshpkt_send(ssh)) != 0)
324 		return r;
325 	return 0;
326 }
327 
328 static void
329 kex_reset_dispatch(struct ssh *ssh)
330 {
331 	ssh_dispatch_range(ssh, SSH2_MSG_TRANSPORT_MIN,
332 	    SSH2_MSG_TRANSPORT_MAX, &kex_protocol_error);
333 	ssh_dispatch_set(ssh, SSH2_MSG_KEXINIT, &kex_input_kexinit);
334 }
335 
336 static int
337 kex_send_ext_info(struct ssh *ssh)
338 {
339 	int r;
340 
341 	if ((r = sshpkt_start(ssh, SSH2_MSG_EXT_INFO)) != 0 ||
342 	    (r = sshpkt_put_u32(ssh, 1)) != 0 ||
343 	    (r = sshpkt_put_cstring(ssh, "server-sig-algs")) != 0 ||
344 	    (r = sshpkt_put_cstring(ssh, "rsa-sha2-256,rsa-sha2-512")) != 0 ||
345 	    (r = sshpkt_send(ssh)) != 0)
346 		return r;
347 	return 0;
348 }
349 
350 int
351 kex_send_newkeys(struct ssh *ssh)
352 {
353 	int r;
354 
355 	kex_reset_dispatch(ssh);
356 	if ((r = sshpkt_start(ssh, SSH2_MSG_NEWKEYS)) != 0 ||
357 	    (r = sshpkt_send(ssh)) != 0)
358 		return r;
359 	debug("SSH2_MSG_NEWKEYS sent");
360 	debug("expecting SSH2_MSG_NEWKEYS");
361 	ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_input_newkeys);
362 	if (ssh->kex->ext_info_c)
363 		if ((r = kex_send_ext_info(ssh)) != 0)
364 			return r;
365 	return 0;
366 }
367 
368 int
369 kex_input_ext_info(int type, u_int32_t seq, void *ctxt)
370 {
371 	struct ssh *ssh = ctxt;
372 	struct kex *kex = ssh->kex;
373 	u_int32_t i, ninfo;
374 	char *name, *val, *found;
375 	int r;
376 
377 	debug("SSH2_MSG_EXT_INFO received");
378 	ssh_dispatch_set(ssh, SSH2_MSG_EXT_INFO, &kex_protocol_error);
379 	if ((r = sshpkt_get_u32(ssh, &ninfo)) != 0)
380 		return r;
381 	for (i = 0; i < ninfo; i++) {
382 		if ((r = sshpkt_get_cstring(ssh, &name, NULL)) != 0)
383 			return r;
384 		if ((r = sshpkt_get_cstring(ssh, &val, NULL)) != 0) {
385 			free(name);
386 			return r;
387 		}
388 		debug("%s: %s=<%s>", __func__, name, val);
389 		if (strcmp(name, "server-sig-algs") == 0) {
390 			found = match_list("rsa-sha2-256", val, NULL);
391 			if (found) {
392 				kex->rsa_sha2 = 256;
393 				free(found);
394 			}
395 			found = match_list("rsa-sha2-512", val, NULL);
396 			if (found) {
397 				kex->rsa_sha2 = 512;
398 				free(found);
399 			}
400 		}
401 		free(name);
402 		free(val);
403 	}
404 	return sshpkt_get_end(ssh);
405 }
406 
407 static int
408 kex_input_newkeys(int type, u_int32_t seq, void *ctxt)
409 {
410 	struct ssh *ssh = ctxt;
411 	struct kex *kex = ssh->kex;
412 	int r;
413 
414 	debug("SSH2_MSG_NEWKEYS received");
415 	ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_protocol_error);
416 	if ((r = sshpkt_get_end(ssh)) != 0)
417 		return r;
418 	kex->done = 1;
419 	sshbuf_reset(kex->peer);
420 	/* sshbuf_reset(kex->my); */
421 	kex->flags &= ~KEX_INIT_SENT;
422 	free(kex->name);
423 	kex->name = NULL;
424 	return 0;
425 }
426 
427 int
428 kex_send_kexinit(struct ssh *ssh)
429 {
430 	u_char *cookie;
431 	struct kex *kex = ssh->kex;
432 	int r;
433 
434 	if (kex == NULL)
435 		return SSH_ERR_INTERNAL_ERROR;
436 	if (kex->flags & KEX_INIT_SENT)
437 		return 0;
438 	kex->done = 0;
439 
440 	/* generate a random cookie */
441 	if (sshbuf_len(kex->my) < KEX_COOKIE_LEN)
442 		return SSH_ERR_INVALID_FORMAT;
443 	if ((cookie = sshbuf_mutable_ptr(kex->my)) == NULL)
444 		return SSH_ERR_INTERNAL_ERROR;
445 	arc4random_buf(cookie, KEX_COOKIE_LEN);
446 
447 	if ((r = sshpkt_start(ssh, SSH2_MSG_KEXINIT)) != 0 ||
448 	    (r = sshpkt_putb(ssh, kex->my)) != 0 ||
449 	    (r = sshpkt_send(ssh)) != 0)
450 		return r;
451 	debug("SSH2_MSG_KEXINIT sent");
452 	kex->flags |= KEX_INIT_SENT;
453 	return 0;
454 }
455 
456 /* ARGSUSED */
457 int
458 kex_input_kexinit(int type, u_int32_t seq, void *ctxt)
459 {
460 	struct ssh *ssh = ctxt;
461 	struct kex *kex = ssh->kex;
462 	const u_char *ptr;
463 	u_int i;
464 	size_t dlen;
465 	int r;
466 
467 	debug("SSH2_MSG_KEXINIT received");
468 	if (kex == NULL)
469 		return SSH_ERR_INVALID_ARGUMENT;
470 
471 	ptr = sshpkt_ptr(ssh, &dlen);
472 	if ((r = sshbuf_put(kex->peer, ptr, dlen)) != 0)
473 		return r;
474 
475 	/* discard packet */
476 	for (i = 0; i < KEX_COOKIE_LEN; i++)
477 		if ((r = sshpkt_get_u8(ssh, NULL)) != 0)
478 			return r;
479 	for (i = 0; i < PROPOSAL_MAX; i++)
480 		if ((r = sshpkt_get_string(ssh, NULL, NULL)) != 0)
481 			return r;
482 	/*
483 	 * XXX RFC4253 sec 7: "each side MAY guess" - currently no supported
484 	 * KEX method has the server move first, but a server might be using
485 	 * a custom method or one that we otherwise don't support. We should
486 	 * be prepared to remember first_kex_follows here so we can eat a
487 	 * packet later.
488 	 * XXX2 - RFC4253 is kind of ambiguous on what first_kex_follows means
489 	 * for cases where the server *doesn't* go first. I guess we should
490 	 * ignore it when it is set for these cases, which is what we do now.
491 	 */
492 	if ((r = sshpkt_get_u8(ssh, NULL)) != 0 ||	/* first_kex_follows */
493 	    (r = sshpkt_get_u32(ssh, NULL)) != 0 ||	/* reserved */
494 	    (r = sshpkt_get_end(ssh)) != 0)
495 			return r;
496 
497 	if (!(kex->flags & KEX_INIT_SENT))
498 		if ((r = kex_send_kexinit(ssh)) != 0)
499 			return r;
500 	if ((r = kex_choose_conf(ssh)) != 0)
501 		return r;
502 
503 	if (kex->kex_type < KEX_MAX && kex->kex[kex->kex_type] != NULL)
504 		return (kex->kex[kex->kex_type])(ssh);
505 
506 	return SSH_ERR_INTERNAL_ERROR;
507 }
508 
509 int
510 kex_new(struct ssh *ssh, char *proposal[PROPOSAL_MAX], struct kex **kexp)
511 {
512 	struct kex *kex;
513 	int r;
514 
515 	*kexp = NULL;
516 	if ((kex = calloc(1, sizeof(*kex))) == NULL)
517 		return SSH_ERR_ALLOC_FAIL;
518 	if ((kex->peer = sshbuf_new()) == NULL ||
519 	    (kex->my = sshbuf_new()) == NULL) {
520 		r = SSH_ERR_ALLOC_FAIL;
521 		goto out;
522 	}
523 	if ((r = kex_prop2buf(kex->my, proposal)) != 0)
524 		goto out;
525 	kex->done = 0;
526 	kex_reset_dispatch(ssh);
527 	r = 0;
528 	*kexp = kex;
529  out:
530 	if (r != 0)
531 		kex_free(kex);
532 	return r;
533 }
534 
535 void
536 kex_free_newkeys(struct newkeys *newkeys)
537 {
538 	if (newkeys == NULL)
539 		return;
540 	if (newkeys->enc.key) {
541 		explicit_bzero(newkeys->enc.key, newkeys->enc.key_len);
542 		free(newkeys->enc.key);
543 		newkeys->enc.key = NULL;
544 	}
545 	if (newkeys->enc.iv) {
546 		explicit_bzero(newkeys->enc.iv, newkeys->enc.iv_len);
547 		free(newkeys->enc.iv);
548 		newkeys->enc.iv = NULL;
549 	}
550 	free(newkeys->enc.name);
551 	explicit_bzero(&newkeys->enc, sizeof(newkeys->enc));
552 	free(newkeys->comp.name);
553 	explicit_bzero(&newkeys->comp, sizeof(newkeys->comp));
554 	mac_clear(&newkeys->mac);
555 	if (newkeys->mac.key) {
556 		explicit_bzero(newkeys->mac.key, newkeys->mac.key_len);
557 		free(newkeys->mac.key);
558 		newkeys->mac.key = NULL;
559 	}
560 	free(newkeys->mac.name);
561 	explicit_bzero(&newkeys->mac, sizeof(newkeys->mac));
562 	explicit_bzero(newkeys, sizeof(*newkeys));
563 	free(newkeys);
564 }
565 
566 void
567 kex_free(struct kex *kex)
568 {
569 	u_int mode;
570 
571 #ifdef WITH_OPENSSL
572 	if (kex->dh)
573 		DH_free(kex->dh);
574 #ifdef OPENSSL_HAS_ECC
575 	if (kex->ec_client_key)
576 		EC_KEY_free(kex->ec_client_key);
577 #endif /* OPENSSL_HAS_ECC */
578 #endif /* WITH_OPENSSL */
579 	for (mode = 0; mode < MODE_MAX; mode++) {
580 		kex_free_newkeys(kex->newkeys[mode]);
581 		kex->newkeys[mode] = NULL;
582 	}
583 	sshbuf_free(kex->peer);
584 	sshbuf_free(kex->my);
585 	free(kex->session_id);
586 	free(kex->client_version_string);
587 	free(kex->server_version_string);
588 	free(kex->failed_choice);
589 	free(kex->hostkey_alg);
590 	free(kex->name);
591 	free(kex);
592 }
593 
594 int
595 kex_setup(struct ssh *ssh, char *proposal[PROPOSAL_MAX])
596 {
597 	int r;
598 
599 	if ((r = kex_new(ssh, proposal, &ssh->kex)) != 0)
600 		return r;
601 	if ((r = kex_send_kexinit(ssh)) != 0) {		/* we start */
602 		kex_free(ssh->kex);
603 		ssh->kex = NULL;
604 		return r;
605 	}
606 	return 0;
607 }
608 
609 /*
610  * Request key re-exchange, returns 0 on success or a ssherr.h error
611  * code otherwise. Must not be called if KEX is incomplete or in-progress.
612  */
613 int
614 kex_start_rekex(struct ssh *ssh)
615 {
616 	if (ssh->kex == NULL) {
617 		error("%s: no kex", __func__);
618 		return SSH_ERR_INTERNAL_ERROR;
619 	}
620 	if (ssh->kex->done == 0) {
621 		error("%s: requested twice", __func__);
622 		return SSH_ERR_INTERNAL_ERROR;
623 	}
624 	ssh->kex->done = 0;
625 	return kex_send_kexinit(ssh);
626 }
627 
628 static int
629 choose_enc(struct sshenc *enc, char *client, char *server)
630 {
631 	char *name = match_list(client, server, NULL);
632 
633 	if (name == NULL)
634 		return SSH_ERR_NO_CIPHER_ALG_MATCH;
635 	if ((enc->cipher = cipher_by_name(name)) == NULL)
636 		return SSH_ERR_INTERNAL_ERROR;
637 	enc->name = name;
638 	enc->enabled = 0;
639 	enc->iv = NULL;
640 	enc->iv_len = cipher_ivlen(enc->cipher);
641 	enc->key = NULL;
642 	enc->key_len = cipher_keylen(enc->cipher);
643 	enc->block_size = cipher_blocksize(enc->cipher);
644 	return 0;
645 }
646 
647 static int
648 choose_mac(struct ssh *ssh, struct sshmac *mac, char *client, char *server)
649 {
650 	char *name = match_list(client, server, NULL);
651 
652 	if (name == NULL)
653 		return SSH_ERR_NO_MAC_ALG_MATCH;
654 	if (mac_setup(mac, name) < 0)
655 		return SSH_ERR_INTERNAL_ERROR;
656 	/* truncate the key */
657 	if (ssh->compat & SSH_BUG_HMAC)
658 		mac->key_len = 16;
659 	mac->name = name;
660 	mac->key = NULL;
661 	mac->enabled = 0;
662 	return 0;
663 }
664 
665 static int
666 choose_comp(struct sshcomp *comp, char *client, char *server)
667 {
668 	char *name = match_list(client, server, NULL);
669 
670 	if (name == NULL)
671 		return SSH_ERR_NO_COMPRESS_ALG_MATCH;
672 	if (strcmp(name, "zlib@openssh.com") == 0) {
673 		comp->type = COMP_DELAYED;
674 	} else if (strcmp(name, "zlib") == 0) {
675 		comp->type = COMP_ZLIB;
676 	} else if (strcmp(name, "none") == 0) {
677 		comp->type = COMP_NONE;
678 	} else {
679 		return SSH_ERR_INTERNAL_ERROR;
680 	}
681 	comp->name = name;
682 	return 0;
683 }
684 
685 static int
686 choose_kex(struct kex *k, char *client, char *server)
687 {
688 	const struct kexalg *kexalg;
689 
690 	k->name = match_list(client, server, NULL);
691 
692 	debug("kex: algorithm: %s", k->name ? k->name : "(no match)");
693 	if (k->name == NULL)
694 		return SSH_ERR_NO_KEX_ALG_MATCH;
695 	if ((kexalg = kex_alg_by_name(k->name)) == NULL)
696 		return SSH_ERR_INTERNAL_ERROR;
697 	k->kex_type = kexalg->type;
698 	k->hash_alg = kexalg->hash_alg;
699 	k->ec_nid = kexalg->ec_nid;
700 	return 0;
701 }
702 
703 static int
704 choose_hostkeyalg(struct kex *k, char *client, char *server)
705 {
706 	k->hostkey_alg = match_list(client, server, NULL);
707 
708 	debug("kex: host key algorithm: %s",
709 	    k->hostkey_alg ? k->hostkey_alg : "(no match)");
710 	if (k->hostkey_alg == NULL)
711 		return SSH_ERR_NO_HOSTKEY_ALG_MATCH;
712 	k->hostkey_type = sshkey_type_from_name(k->hostkey_alg);
713 	if (k->hostkey_type == KEY_UNSPEC)
714 		return SSH_ERR_INTERNAL_ERROR;
715 	k->hostkey_nid = sshkey_ecdsa_nid_from_name(k->hostkey_alg);
716 	return 0;
717 }
718 
719 static int
720 proposals_match(char *my[PROPOSAL_MAX], char *peer[PROPOSAL_MAX])
721 {
722 	static int check[] = {
723 		PROPOSAL_KEX_ALGS, PROPOSAL_SERVER_HOST_KEY_ALGS, -1
724 	};
725 	int *idx;
726 	char *p;
727 
728 	for (idx = &check[0]; *idx != -1; idx++) {
729 		if ((p = strchr(my[*idx], ',')) != NULL)
730 			*p = '\0';
731 		if ((p = strchr(peer[*idx], ',')) != NULL)
732 			*p = '\0';
733 		if (strcmp(my[*idx], peer[*idx]) != 0) {
734 			debug2("proposal mismatch: my %s peer %s",
735 			    my[*idx], peer[*idx]);
736 			return (0);
737 		}
738 	}
739 	debug2("proposals match");
740 	return (1);
741 }
742 
743 static int
744 kex_choose_conf(struct ssh *ssh)
745 {
746 	struct kex *kex = ssh->kex;
747 	struct newkeys *newkeys;
748 	char **my = NULL, **peer = NULL;
749 	char **cprop, **sprop;
750 	int nenc, nmac, ncomp;
751 	u_int mode, ctos, need, dh_need, authlen;
752 	int r, first_kex_follows;
753 
754 	debug2("local %s KEXINIT proposal", kex->server ? "server" : "client");
755 	if ((r = kex_buf2prop(kex->my, NULL, &my)) != 0)
756 		goto out;
757 	debug2("peer %s KEXINIT proposal", kex->server ? "client" : "server");
758 	if ((r = kex_buf2prop(kex->peer, &first_kex_follows, &peer)) != 0)
759 		goto out;
760 
761 	if (kex->server) {
762 		cprop=peer;
763 		sprop=my;
764 	} else {
765 		cprop=my;
766 		sprop=peer;
767 	}
768 
769 	/* Check whether client supports ext_info_c */
770 	if (kex->server) {
771 		char *ext;
772 
773 		ext = match_list("ext-info-c", peer[PROPOSAL_KEX_ALGS], NULL);
774 		if (ext) {
775 			kex->ext_info_c = 1;
776 			free(ext);
777 		}
778 	}
779 
780 	/* Algorithm Negotiation */
781 	if ((r = choose_kex(kex, cprop[PROPOSAL_KEX_ALGS],
782 	    sprop[PROPOSAL_KEX_ALGS])) != 0) {
783 		kex->failed_choice = peer[PROPOSAL_KEX_ALGS];
784 		peer[PROPOSAL_KEX_ALGS] = NULL;
785 		goto out;
786 	}
787 	if ((r = choose_hostkeyalg(kex, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
788 	    sprop[PROPOSAL_SERVER_HOST_KEY_ALGS])) != 0) {
789 		kex->failed_choice = peer[PROPOSAL_SERVER_HOST_KEY_ALGS];
790 		peer[PROPOSAL_SERVER_HOST_KEY_ALGS] = NULL;
791 		goto out;
792 	}
793 	for (mode = 0; mode < MODE_MAX; mode++) {
794 		if ((newkeys = calloc(1, sizeof(*newkeys))) == NULL) {
795 			r = SSH_ERR_ALLOC_FAIL;
796 			goto out;
797 		}
798 		kex->newkeys[mode] = newkeys;
799 		ctos = (!kex->server && mode == MODE_OUT) ||
800 		    (kex->server && mode == MODE_IN);
801 		nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
802 		nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
803 		ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
804 		if ((r = choose_enc(&newkeys->enc, cprop[nenc],
805 		    sprop[nenc])) != 0) {
806 			kex->failed_choice = peer[nenc];
807 			peer[nenc] = NULL;
808 			goto out;
809 		}
810 		authlen = cipher_authlen(newkeys->enc.cipher);
811 		/* ignore mac for authenticated encryption */
812 		if (authlen == 0 &&
813 		    (r = choose_mac(ssh, &newkeys->mac, cprop[nmac],
814 		    sprop[nmac])) != 0) {
815 			kex->failed_choice = peer[nmac];
816 			peer[nmac] = NULL;
817 			goto out;
818 		}
819 		if ((r = choose_comp(&newkeys->comp, cprop[ncomp],
820 		    sprop[ncomp])) != 0) {
821 			kex->failed_choice = peer[ncomp];
822 			peer[ncomp] = NULL;
823 			goto out;
824 		}
825 		debug("kex: %s cipher: %s MAC: %s compression: %s",
826 		    ctos ? "client->server" : "server->client",
827 		    newkeys->enc.name,
828 		    authlen == 0 ? newkeys->mac.name : "<implicit>",
829 		    newkeys->comp.name);
830 	}
831 	need = dh_need = 0;
832 	for (mode = 0; mode < MODE_MAX; mode++) {
833 		newkeys = kex->newkeys[mode];
834 		need = MAX(need, newkeys->enc.key_len);
835 		need = MAX(need, newkeys->enc.block_size);
836 		need = MAX(need, newkeys->enc.iv_len);
837 		need = MAX(need, newkeys->mac.key_len);
838 		dh_need = MAX(dh_need, cipher_seclen(newkeys->enc.cipher));
839 		dh_need = MAX(dh_need, newkeys->enc.block_size);
840 		dh_need = MAX(dh_need, newkeys->enc.iv_len);
841 		dh_need = MAX(dh_need, newkeys->mac.key_len);
842 	}
843 	/* XXX need runden? */
844 	kex->we_need = need;
845 	kex->dh_need = dh_need;
846 
847 	/* ignore the next message if the proposals do not match */
848 	if (first_kex_follows && !proposals_match(my, peer) &&
849 	    !(ssh->compat & SSH_BUG_FIRSTKEX))
850 		ssh->dispatch_skip_packets = 1;
851 	r = 0;
852  out:
853 	kex_prop_free(my);
854 	kex_prop_free(peer);
855 	return r;
856 }
857 
858 static int
859 derive_key(struct ssh *ssh, int id, u_int need, u_char *hash, u_int hashlen,
860     const struct sshbuf *shared_secret, u_char **keyp)
861 {
862 	struct kex *kex = ssh->kex;
863 	struct ssh_digest_ctx *hashctx = NULL;
864 	char c = id;
865 	u_int have;
866 	size_t mdsz;
867 	u_char *digest;
868 	int r;
869 
870 	if ((mdsz = ssh_digest_bytes(kex->hash_alg)) == 0)
871 		return SSH_ERR_INVALID_ARGUMENT;
872 	if ((digest = calloc(1, roundup(need, mdsz))) == NULL) {
873 		r = SSH_ERR_ALLOC_FAIL;
874 		goto out;
875 	}
876 
877 	/* K1 = HASH(K || H || "A" || session_id) */
878 	if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL ||
879 	    ssh_digest_update_buffer(hashctx, shared_secret) != 0 ||
880 	    ssh_digest_update(hashctx, hash, hashlen) != 0 ||
881 	    ssh_digest_update(hashctx, &c, 1) != 0 ||
882 	    ssh_digest_update(hashctx, kex->session_id,
883 	    kex->session_id_len) != 0 ||
884 	    ssh_digest_final(hashctx, digest, mdsz) != 0) {
885 		r = SSH_ERR_LIBCRYPTO_ERROR;
886 		goto out;
887 	}
888 	ssh_digest_free(hashctx);
889 	hashctx = NULL;
890 
891 	/*
892 	 * expand key:
893 	 * Kn = HASH(K || H || K1 || K2 || ... || Kn-1)
894 	 * Key = K1 || K2 || ... || Kn
895 	 */
896 	for (have = mdsz; need > have; have += mdsz) {
897 		if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL ||
898 		    ssh_digest_update_buffer(hashctx, shared_secret) != 0 ||
899 		    ssh_digest_update(hashctx, hash, hashlen) != 0 ||
900 		    ssh_digest_update(hashctx, digest, have) != 0 ||
901 		    ssh_digest_final(hashctx, digest + have, mdsz) != 0) {
902 			r = SSH_ERR_LIBCRYPTO_ERROR;
903 			goto out;
904 		}
905 		ssh_digest_free(hashctx);
906 		hashctx = NULL;
907 	}
908 #ifdef DEBUG_KEX
909 	fprintf(stderr, "key '%c'== ", c);
910 	dump_digest("key", digest, need);
911 #endif
912 	*keyp = digest;
913 	digest = NULL;
914 	r = 0;
915  out:
916 	free(digest);
917 	ssh_digest_free(hashctx);
918 	return r;
919 }
920 
921 #define NKEYS	6
922 int
923 kex_derive_keys(struct ssh *ssh, u_char *hash, u_int hashlen,
924     const struct sshbuf *shared_secret)
925 {
926 	struct kex *kex = ssh->kex;
927 	u_char *keys[NKEYS];
928 	u_int i, j, mode, ctos;
929 	int r;
930 
931 	for (i = 0; i < NKEYS; i++) {
932 		if ((r = derive_key(ssh, 'A'+i, kex->we_need, hash, hashlen,
933 		    shared_secret, &keys[i])) != 0) {
934 			for (j = 0; j < i; j++)
935 				free(keys[j]);
936 			return r;
937 		}
938 	}
939 	for (mode = 0; mode < MODE_MAX; mode++) {
940 		ctos = (!kex->server && mode == MODE_OUT) ||
941 		    (kex->server && mode == MODE_IN);
942 		kex->newkeys[mode]->enc.iv  = keys[ctos ? 0 : 1];
943 		kex->newkeys[mode]->enc.key = keys[ctos ? 2 : 3];
944 		kex->newkeys[mode]->mac.key = keys[ctos ? 4 : 5];
945 	}
946 	return 0;
947 }
948 
949 #ifdef WITH_OPENSSL
950 int
951 kex_derive_keys_bn(struct ssh *ssh, u_char *hash, u_int hashlen,
952     const BIGNUM *secret)
953 {
954 	struct sshbuf *shared_secret;
955 	int r;
956 
957 	if ((shared_secret = sshbuf_new()) == NULL)
958 		return SSH_ERR_ALLOC_FAIL;
959 	if ((r = sshbuf_put_bignum2(shared_secret, secret)) == 0)
960 		r = kex_derive_keys(ssh, hash, hashlen, shared_secret);
961 	sshbuf_free(shared_secret);
962 	return r;
963 }
964 #endif
965 
966 #ifdef WITH_SSH1
967 int
968 derive_ssh1_session_id(BIGNUM *host_modulus, BIGNUM *server_modulus,
969     u_int8_t cookie[8], u_int8_t id[16])
970 {
971 	u_int8_t hbuf[2048], sbuf[2048], obuf[SSH_DIGEST_MAX_LENGTH];
972 	struct ssh_digest_ctx *hashctx = NULL;
973 	size_t hlen, slen;
974 	int r;
975 
976 	hlen = BN_num_bytes(host_modulus);
977 	slen = BN_num_bytes(server_modulus);
978 	if (hlen < (512 / 8) || (u_int)hlen > sizeof(hbuf) ||
979 	    slen < (512 / 8) || (u_int)slen > sizeof(sbuf))
980 		return SSH_ERR_KEY_BITS_MISMATCH;
981 	if (BN_bn2bin(host_modulus, hbuf) <= 0 ||
982 	    BN_bn2bin(server_modulus, sbuf) <= 0) {
983 		r = SSH_ERR_LIBCRYPTO_ERROR;
984 		goto out;
985 	}
986 	if ((hashctx = ssh_digest_start(SSH_DIGEST_MD5)) == NULL) {
987 		r = SSH_ERR_ALLOC_FAIL;
988 		goto out;
989 	}
990 	if (ssh_digest_update(hashctx, hbuf, hlen) != 0 ||
991 	    ssh_digest_update(hashctx, sbuf, slen) != 0 ||
992 	    ssh_digest_update(hashctx, cookie, 8) != 0 ||
993 	    ssh_digest_final(hashctx, obuf, sizeof(obuf)) != 0) {
994 		r = SSH_ERR_LIBCRYPTO_ERROR;
995 		goto out;
996 	}
997 	memcpy(id, obuf, ssh_digest_bytes(SSH_DIGEST_MD5));
998 	r = 0;
999  out:
1000 	ssh_digest_free(hashctx);
1001 	explicit_bzero(hbuf, sizeof(hbuf));
1002 	explicit_bzero(sbuf, sizeof(sbuf));
1003 	explicit_bzero(obuf, sizeof(obuf));
1004 	return r;
1005 }
1006 #endif
1007 
1008 #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH)
1009 void
1010 dump_digest(char *msg, u_char *digest, int len)
1011 {
1012 	fprintf(stderr, "%s\n", msg);
1013 	sshbuf_dump_data(digest, len, stderr);
1014 }
1015 #endif
1016