kex.c - security/openssh-library - Rivoreo Source Code Repositories

 /* $OpenBSD: kex.c,v 1.103 2015/01/20 23:14:00 deraadt Exp $ */
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #include "includes.h"

 #include <sys/param.h>	/* MAX roundup */

 #include <signal.h>
 #include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

 #ifdef WITH_OPENSSL
 #include <openssl/crypto.h>
 #endif

 #include "ssh2.h"
 #include "packet.h"
 #include "compat.h"
 #include "cipher.h"
 #include "sshkey.h"
 #include "kex.h"
 #include "log.h"
 #include "mac.h"
 #include "match.h"
 #include "misc.h"
 #include "dispatch.h"
 #include "monitor.h"
 #include "roaming.h"

 #include "ssherr.h"
 #include "sshbuf.h"
 #include "digest.h"

 #if OPENSSL_VERSION_NUMBER >= 0x00907000L
 # if defined(HAVE_EVP_SHA256)
 # define evp_ssh_sha256 EVP_sha256
 # else
 extern const EVP_MD *evp_ssh_sha256(void);
 # endif
 #endif

 /* prototype */
 static int kex_choose_conf(struct ssh *);
 static int kex_input_newkeys(int, u_int32_t, void *);

 struct kexalg {
 	char *name;
 	u_int type;
 	int ec_nid;
 	int hash_alg;
 };
 static const struct kexalg kexalgs[] = {
 #ifdef WITH_OPENSSL
 	{ KEX_DH1, KEX_DH_GRP1_SHA1, 0, SSH_DIGEST_SHA1 },
 	{ KEX_DH14, KEX_DH_GRP14_SHA1, 0, SSH_DIGEST_SHA1 },
 	{ KEX_DHGEX_SHA1, KEX_DH_GEX_SHA1, 0, SSH_DIGEST_SHA1 },
 #ifdef HAVE_EVP_SHA256
 	{ KEX_DHGEX_SHA256, KEX_DH_GEX_SHA256, 0, SSH_DIGEST_SHA256 },
 #endif /* HAVE_EVP_SHA256 */
 #ifdef OPENSSL_HAS_ECC
 	{ KEX_ECDH_SHA2_NISTP256, KEX_ECDH_SHA2,
 	    NID_X9_62_prime256v1, SSH_DIGEST_SHA256 },
 	{ KEX_ECDH_SHA2_NISTP384, KEX_ECDH_SHA2, NID_secp384r1,
 	    SSH_DIGEST_SHA384 },
 # ifdef OPENSSL_HAS_NISTP521
 	{ KEX_ECDH_SHA2_NISTP521, KEX_ECDH_SHA2, NID_secp521r1,
 	    SSH_DIGEST_SHA512 },
 # endif /* OPENSSL_HAS_NISTP521 */
 #endif /* OPENSSL_HAS_ECC */
 #endif /* WITH_OPENSSL */
 #if defined(HAVE_EVP_SHA256) || !defined(WITH_OPENSSL)
 	{ KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
 #endif /* HAVE_EVP_SHA256 || !WITH_OPENSSL */
 	{ NULL, -1, -1, -1},
 };

 char *
 kex_alg_list(char sep)
 {
 	char *ret = NULL, *tmp;
 	size_t nlen, rlen = 0;
 	const struct kexalg *k;

 	for (k = kexalgs; k->name != NULL; k++) {
 		if (ret != NULL)
 			ret[rlen++] = sep;
 		nlen = strlen(k->name);
 		if ((tmp = realloc(ret, rlen + nlen + 2)) == NULL) {
 			free(ret);
 			return NULL;
 		}
 		ret = tmp;
 		memcpy(ret + rlen, k->name, nlen + 1);
 		rlen += nlen;
 	}
 	return ret;
 }

 static const struct kexalg *
 kex_alg_by_name(const char *name)
 {
 	const struct kexalg *k;

 	for (k = kexalgs; k->name != NULL; k++) {
 		if (strcmp(k->name, name) == 0)
 			return k;
 	}
 	return NULL;
 }

 /* Validate KEX method name list */
 int
 kex_names_valid(const char *names)
 {
 	char *s, *cp, *p;

 	if (names == NULL || strcmp(names, "") == 0)
 		return 0;
 	if ((s = cp = strdup(names)) == NULL)
 		return 0;
 	for ((p = strsep(&cp, ",")); p && *p != '\0';
 	    (p = strsep(&cp, ","))) {
 		if (kex_alg_by_name(p) == NULL) {
 			error("Unsupported KEX algorithm \"%.100s\"", p);
 			free(s);
 			return 0;
 		}
 	}
 	debug3("kex names ok: [%s]", names);
 	free(s);
 	return 1;
 }

 /* put algorithm proposal into buffer */
 int
 kex_prop2buf(struct sshbuf *b, char *proposal[PROPOSAL_MAX])
 {
 	u_int i;
 	int r;

 	sshbuf_reset(b);

 	/*
 	 * add a dummy cookie, the cookie will be overwritten by
 	 * kex_send_kexinit(), each time a kexinit is set
 	 */
 	for (i = 0; i < KEX_COOKIE_LEN; i++) {
 		if ((r = sshbuf_put_u8(b, 0)) != 0)
 			return r;
 	}
 	for (i = 0; i < PROPOSAL_MAX; i++) {
 		if ((r = sshbuf_put_cstring(b, proposal[i])) != 0)
 			return r;
 	}
 	if ((r = sshbuf_put_u8(b, 0)) != 0 ||	/* first_kex_packet_follows */
 	    (r = sshbuf_put_u32(b, 0)) != 0)	/* uint32 reserved */
 		return r;
 	return 0;
 }

 /* parse buffer and return algorithm proposal */
 int
 kex_buf2prop(struct sshbuf *raw, int *first_kex_follows, char ***propp)
 {
 	struct sshbuf *b = NULL;
 	u_char v;
 	u_int i;
 	char **proposal = NULL;
 	int r;

 	*propp = NULL;
 	if ((proposal = calloc(PROPOSAL_MAX, sizeof(char *))) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
 	if ((b = sshbuf_fromb(raw)) == NULL) {
 		r = SSH_ERR_ALLOC_FAIL;
 		goto out;
 	}
 	if ((r = sshbuf_consume(b, KEX_COOKIE_LEN)) != 0) /* skip cookie */
 		goto out;
 	/* extract kex init proposal strings */
 	for (i = 0; i < PROPOSAL_MAX; i++) {
 		if ((r = sshbuf_get_cstring(b, &(proposal[i]), NULL)) != 0)
 			goto out;
 		debug2("kex_parse_kexinit: %s", proposal[i]);
 	}
 	/* first kex follows / reserved */
 	if ((r = sshbuf_get_u8(b, &v)) != 0 ||
 	    (r = sshbuf_get_u32(b, &i)) != 0)
 		goto out;
 	if (first_kex_follows != NULL)
 		*first_kex_follows = i;
 	debug2("kex_parse_kexinit: first_kex_follows %d ", v);
 	debug2("kex_parse_kexinit: reserved %u ", i);
 	r = 0;
 	*propp = proposal;
  out:
 	if (r != 0 && proposal != NULL)
 		kex_prop_free(proposal);
 	sshbuf_free(b);
 	return r;
 }

 void
 kex_prop_free(char **proposal)
 {
 	u_int i;

 	for (i = 0; i < PROPOSAL_MAX; i++)
 		free(proposal[i]);
 	free(proposal);
 }

 /* ARGSUSED */
 static int
 kex_protocol_error(int type, u_int32_t seq, void *ctxt)
 {
 	error("Hm, kex protocol error: type %d seq %u", type, seq);
 	return 0;
 }

 static void
 kex_reset_dispatch(struct ssh *ssh)
 {
 	ssh_dispatch_range(ssh, SSH2_MSG_TRANSPORT_MIN,
 	    SSH2_MSG_TRANSPORT_MAX, &kex_protocol_error);
 	ssh_dispatch_set(ssh, SSH2_MSG_KEXINIT, &kex_input_kexinit);
 }

 int
 kex_send_newkeys(struct ssh *ssh)
 {
 	int r;

 	kex_reset_dispatch(ssh);
 	if ((r = sshpkt_start(ssh, SSH2_MSG_NEWKEYS)) != 0 ||
 	    (r = sshpkt_send(ssh)) != 0)
 		return r;
 	debug("SSH2_MSG_NEWKEYS sent");
 	debug("expecting SSH2_MSG_NEWKEYS");
 	ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_input_newkeys);
 	return 0;
 }

 static int
 kex_input_newkeys(int type, u_int32_t seq, void *ctxt)
 {
 	struct ssh *ssh = ctxt;
 	struct kex *kex = ssh->kex;
 	int r;

 	debug("SSH2_MSG_NEWKEYS received");
 	ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_protocol_error);
 	if ((r = sshpkt_get_end(ssh)) != 0)
 		return r;
 	kex->done = 1;
 	sshbuf_reset(kex->peer);
 	/* sshbuf_reset(kex->my); */
 	kex->flags &= ~KEX_INIT_SENT;
 	free(kex->name);
 	kex->name = NULL;
 	return 0;
 }

 int
 kex_send_kexinit(struct ssh *ssh)
 {
 	u_char *cookie;
 	struct kex *kex = ssh->kex;
 	int r;

 	if (kex == NULL)
 		return SSH_ERR_INTERNAL_ERROR;
 	if (kex->flags & KEX_INIT_SENT)
 		return 0;
 	kex->done = 0;

 	/* generate a random cookie */
 	if (sshbuf_len(kex->my) < KEX_COOKIE_LEN)
 		return SSH_ERR_INVALID_FORMAT;
 	if ((cookie = sshbuf_mutable_ptr(kex->my)) == NULL)
 		return SSH_ERR_INTERNAL_ERROR;
 	arc4random_buf(cookie, KEX_COOKIE_LEN);

 	if ((r = sshpkt_start(ssh, SSH2_MSG_KEXINIT)) != 0 ||
 	    (r = sshpkt_putb(ssh, kex->my)) != 0 ||
 	    (r = sshpkt_send(ssh)) != 0)
 		return r;
 	debug("SSH2_MSG_KEXINIT sent");
 	kex->flags |= KEX_INIT_SENT;
 	return 0;
 }

 /* ARGSUSED */
 int
 kex_input_kexinit(int type, u_int32_t seq, void *ctxt)
 {
 	struct ssh *ssh = ctxt;
 	struct kex *kex = ssh->kex;
 	const u_char *ptr;
 	u_int i;
 	size_t dlen;
 	int r;

 	debug("SSH2_MSG_KEXINIT received");
 	if (kex == NULL)
 		return SSH_ERR_INVALID_ARGUMENT;

 	ptr = sshpkt_ptr(ssh, &dlen);
 	if ((r = sshbuf_put(kex->peer, ptr, dlen)) != 0)
 		return r;

 	/* discard packet */
 	for (i = 0; i < KEX_COOKIE_LEN; i++)
 		if ((r = sshpkt_get_u8(ssh, NULL)) != 0)
 			return r;
 	for (i = 0; i < PROPOSAL_MAX; i++)
 		if ((r = sshpkt_get_string(ssh, NULL, NULL)) != 0)
 			return r;
 	/*
 	 * XXX RFC4253 sec 7: "each side MAY guess" - currently no supported
 	 * KEX method has the server move first, but a server might be using
 	 * a custom method or one that we otherwise don't support. We should
 	 * be prepared to remember first_kex_follows here so we can eat a
 	 * packet later.
 	 * XXX2 - RFC4253 is kind of ambiguous on what first_kex_follows means
 	 * for cases where the server *doesn't* go first. I guess we should
 	 * ignore it when it is set for these cases, which is what we do now.
 	 */
 	if ((r = sshpkt_get_u8(ssh, NULL)) != 0 ||	/* first_kex_follows */
 	    (r = sshpkt_get_u32(ssh, NULL)) != 0 ||	/* reserved */
 	    (r = sshpkt_get_end(ssh)) != 0)
 			return r;

 	if (!(kex->flags & KEX_INIT_SENT))
 		if ((r = kex_send_kexinit(ssh)) != 0)
 			return r;
 	if ((r = kex_choose_conf(ssh)) != 0)
 		return r;

 	if (kex->kex_type < KEX_MAX && kex->kex[kex->kex_type] != NULL)
 		return (kex->kex[kex->kex_type])(ssh);

 	return SSH_ERR_INTERNAL_ERROR;
 }

 int
 kex_new(struct ssh *ssh, char *proposal[PROPOSAL_MAX], struct kex **kexp)
 {
 	struct kex *kex;
 	int r;

 	*kexp = NULL;
 	if ((kex = calloc(1, sizeof(*kex))) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
 	if ((kex->peer = sshbuf_new()) == NULL ||
 	    (kex->my = sshbuf_new()) == NULL) {
 		r = SSH_ERR_ALLOC_FAIL;
 		goto out;
 	}
 	if ((r = kex_prop2buf(kex->my, proposal)) != 0)
 		goto out;
 	kex->done = 0;
 	kex_reset_dispatch(ssh);
 	r = 0;
 	*kexp = kex;
  out:
 	if (r != 0)
 		kex_free(kex);
 	return r;
 }

 void
 kex_free_newkeys(struct newkeys *newkeys)
 {
 	if (newkeys == NULL)
 		return;
 	if (newkeys->enc.key) {
 		explicit_bzero(newkeys->enc.key, newkeys->enc.key_len);
 		free(newkeys->enc.key);
 		newkeys->enc.key = NULL;
 	}
 	if (newkeys->enc.iv) {
 		explicit_bzero(newkeys->enc.iv, newkeys->enc.block_size);
 		free(newkeys->enc.iv);
 		newkeys->enc.iv = NULL;
 	}
 	free(newkeys->enc.name);
 	explicit_bzero(&newkeys->enc, sizeof(newkeys->enc));
 	free(newkeys->comp.name);
 	explicit_bzero(&newkeys->comp, sizeof(newkeys->comp));
 	mac_clear(&newkeys->mac);
 	if (newkeys->mac.key) {
 		explicit_bzero(newkeys->mac.key, newkeys->mac.key_len);
 		free(newkeys->mac.key);
 		newkeys->mac.key = NULL;
 	}
 	free(newkeys->mac.name);
 	explicit_bzero(&newkeys->mac, sizeof(newkeys->mac));
 	explicit_bzero(newkeys, sizeof(*newkeys));
 	free(newkeys);
 }

 void
 kex_free(struct kex *kex)
 {
 	u_int mode;

 #ifdef WITH_OPENSSL
 	if (kex->dh)
 		DH_free(kex->dh);
 	if (kex->ec_client_key)
 		EC_KEY_free(kex->ec_client_key);
 #endif
 	for (mode = 0; mode < MODE_MAX; mode++) {
 		kex_free_newkeys(kex->newkeys[mode]);
 		kex->newkeys[mode] = NULL;
 	}
 	sshbuf_free(kex->peer);
 	sshbuf_free(kex->my);
 	free(kex->session_id);
 	free(kex->client_version_string);
 	free(kex->server_version_string);
 	free(kex);
 }

 int
 kex_setup(struct ssh *ssh, char *proposal[PROPOSAL_MAX])
 {
 	int r;

 	if ((r = kex_new(ssh, proposal, &ssh->kex)) != 0)
 		return r;
 	if ((r = kex_send_kexinit(ssh)) != 0) {		/* we start */
 		kex_free(ssh->kex);
 		ssh->kex = NULL;
 		return r;
 	}
 	return 0;
 }

 static int
 choose_enc(struct sshenc *enc, char *client, char *server)
 {
 	char *name = match_list(client, server, NULL);

 	if (name == NULL)
 		return SSH_ERR_NO_CIPHER_ALG_MATCH;
 	if ((enc->cipher = cipher_by_name(name)) == NULL)
 		return SSH_ERR_INTERNAL_ERROR;
 	enc->name = name;
 	enc->enabled = 0;
 	enc->iv = NULL;
 	enc->iv_len = cipher_ivlen(enc->cipher);
 	enc->key = NULL;
 	enc->key_len = cipher_keylen(enc->cipher);
 	enc->block_size = cipher_blocksize(enc->cipher);
 	return 0;
 }

 static int
 choose_mac(struct ssh *ssh, struct sshmac *mac, char *client, char *server)
 {
 	char *name = match_list(client, server, NULL);

 	if (name == NULL)
 		return SSH_ERR_NO_MAC_ALG_MATCH;
 	if (mac_setup(mac, name) < 0)
 		return SSH_ERR_INTERNAL_ERROR;
 	/* truncate the key */
 	if (ssh->compat & SSH_BUG_HMAC)
 		mac->key_len = 16;
 	mac->name = name;
 	mac->key = NULL;
 	mac->enabled = 0;
 	return 0;
 }

 static int
 choose_comp(struct sshcomp *comp, char *client, char *server)
 {
 	char *name = match_list(client, server, NULL);

 	if (name == NULL)
 		return SSH_ERR_NO_COMPRESS_ALG_MATCH;
 	if (strcmp(name, "zlib@openssh.com") == 0) {
 		comp->type = COMP_DELAYED;
 	} else if (strcmp(name, "zlib") == 0) {
 		comp->type = COMP_ZLIB;
 	} else if (strcmp(name, "none") == 0) {
 		comp->type = COMP_NONE;
 	} else {
 		return SSH_ERR_INTERNAL_ERROR;
 	}
 	comp->name = name;
 	return 0;
 }

 static int
 choose_kex(struct kex *k, char *client, char *server)
 {
 	const struct kexalg *kexalg;

 	k->name = match_list(client, server, NULL);

 	if (k->name == NULL)
 		return SSH_ERR_NO_KEX_ALG_MATCH;
 	if ((kexalg = kex_alg_by_name(k->name)) == NULL)
 		return SSH_ERR_INTERNAL_ERROR;
 	k->kex_type = kexalg->type;
 	k->hash_alg = kexalg->hash_alg;
 	k->ec_nid = kexalg->ec_nid;
 	return 0;
 }

 static int
 choose_hostkeyalg(struct kex *k, char *client, char *server)
 {
 	char *hostkeyalg = match_list(client, server, NULL);

 	if (hostkeyalg == NULL)
 		return SSH_ERR_NO_HOSTKEY_ALG_MATCH;
 	k->hostkey_type = sshkey_type_from_name(hostkeyalg);
 	if (k->hostkey_type == KEY_UNSPEC)
 		return SSH_ERR_INTERNAL_ERROR;
 	free(hostkeyalg);
 	return 0;
 }

 static int
 proposals_match(char *my[PROPOSAL_MAX], char *peer[PROPOSAL_MAX])
 {
 	static int check[] = {
 		PROPOSAL_KEX_ALGS, PROPOSAL_SERVER_HOST_KEY_ALGS, -1
 	};
 	int *idx;
 	char *p;

 	for (idx = &check[0]; *idx != -1; idx++) {
 		if ((p = strchr(my[*idx], ',')) != NULL)
 			*p = '\0';
 		if ((p = strchr(peer[*idx], ',')) != NULL)
 			*p = '\0';
 		if (strcmp(my[*idx], peer[*idx]) != 0) {
 			debug2("proposal mismatch: my %s peer %s",
 			    my[*idx], peer[*idx]);
 			return (0);
 		}
 	}
 	debug2("proposals match");
 	return (1);
 }

 static int
 kex_choose_conf(struct ssh *ssh)
 {
 	struct kex *kex = ssh->kex;
 	struct newkeys *newkeys;
 	char **my = NULL, **peer = NULL;
 	char **cprop, **sprop;
 	int nenc, nmac, ncomp;
 	u_int mode, ctos, need, dh_need, authlen;
 	int r, first_kex_follows;

 	if ((r = kex_buf2prop(kex->my, NULL, &my)) != 0 ||
 	    (r = kex_buf2prop(kex->peer, &first_kex_follows, &peer)) != 0)
 		goto out;

 	if (kex->server) {
 		cprop=peer;
 		sprop=my;
 	} else {
 		cprop=my;
 		sprop=peer;
 	}

 	/* Check whether server offers roaming */
 	if (!kex->server) {
 		char *roaming = match_list(KEX_RESUME,
 		    peer[PROPOSAL_KEX_ALGS], NULL);

 		if (roaming) {
 			kex->roaming = 1;
 			free(roaming);
 		}
 	}

 	/* Algorithm Negotiation */
 	for (mode = 0; mode < MODE_MAX; mode++) {
 		if ((newkeys = calloc(1, sizeof(*newkeys))) == NULL) {
 			r = SSH_ERR_ALLOC_FAIL;
 			goto out;
 		}
 		kex->newkeys[mode] = newkeys;
 		ctos = (!kex->server && mode == MODE_OUT) ||
 		    (kex->server && mode == MODE_IN);
 		nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
 		nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
 		ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
 		if ((r = choose_enc(&newkeys->enc, cprop[nenc],
 		    sprop[nenc])) != 0)
 			goto out;
 		authlen = cipher_authlen(newkeys->enc.cipher);
 		/* ignore mac for authenticated encryption */
 		if (authlen == 0 &&
 		    (r = choose_mac(ssh, &newkeys->mac, cprop[nmac],
 		    sprop[nmac])) != 0)
 			goto out;
 		if ((r = choose_comp(&newkeys->comp, cprop[ncomp],
 		    sprop[ncomp])) != 0)
 			goto out;
 		debug("kex: %s %s %s %s",
 		    ctos ? "client->server" : "server->client",
 		    newkeys->enc.name,
 		    authlen == 0 ? newkeys->mac.name : "<implicit>",
 		    newkeys->comp.name);
 	}
 	if ((r = choose_kex(kex, cprop[PROPOSAL_KEX_ALGS],
 	    sprop[PROPOSAL_KEX_ALGS])) != 0 ||
 	    (r = choose_hostkeyalg(kex, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
 	    sprop[PROPOSAL_SERVER_HOST_KEY_ALGS])) != 0)
 		goto out;
 	need = dh_need = 0;
 	for (mode = 0; mode < MODE_MAX; mode++) {
 		newkeys = kex->newkeys[mode];
 		need = MAX(need, newkeys->enc.key_len);
 		need = MAX(need, newkeys->enc.block_size);
 		need = MAX(need, newkeys->enc.iv_len);
 		need = MAX(need, newkeys->mac.key_len);
 		dh_need = MAX(dh_need, cipher_seclen(newkeys->enc.cipher));
 		dh_need = MAX(dh_need, newkeys->enc.block_size);
 		dh_need = MAX(dh_need, newkeys->enc.iv_len);
 		dh_need = MAX(dh_need, newkeys->mac.key_len);
 	}
 	/* XXX need runden? */
 	kex->we_need = need;
 	kex->dh_need = dh_need;

 	/* ignore the next message if the proposals do not match */
 	if (first_kex_follows && !proposals_match(my, peer) &&
 	    !(ssh->compat & SSH_BUG_FIRSTKEX))
 		ssh->dispatch_skip_packets = 1;
 	r = 0;
  out:
 	kex_prop_free(my);
 	kex_prop_free(peer);
 	return r;
 }

 static int
 derive_key(struct ssh *ssh, int id, u_int need, u_char *hash, u_int hashlen,
     const struct sshbuf *shared_secret, u_char **keyp)
 {
 	struct kex *kex = ssh->kex;
 	struct ssh_digest_ctx *hashctx = NULL;
 	char c = id;
 	u_int have;
 	size_t mdsz;
 	u_char *digest;
 	int r;

 	if ((mdsz = ssh_digest_bytes(kex->hash_alg)) == 0)
 		return SSH_ERR_INVALID_ARGUMENT;
 	if ((digest = calloc(1, roundup(need, mdsz))) == NULL) {
 		r = SSH_ERR_ALLOC_FAIL;
 		goto out;
 	}

 	/* K1 = HASH(K || H || "A" || session_id) */
 	if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL ||
 	    ssh_digest_update_buffer(hashctx, shared_secret) != 0 ||
 	    ssh_digest_update(hashctx, hash, hashlen) != 0 ||
 	    ssh_digest_update(hashctx, &c, 1) != 0 ||
 	    ssh_digest_update(hashctx, kex->session_id,
 	    kex->session_id_len) != 0 ||
 	    ssh_digest_final(hashctx, digest, mdsz) != 0) {
 		r = SSH_ERR_LIBCRYPTO_ERROR;
 		goto out;
 	}
 	ssh_digest_free(hashctx);
 	hashctx = NULL;

 	/*
 	 * expand key:
 	 * Kn = HASH(K || H || K1 || K2 || ... || Kn-1)
 	 * Key = K1 || K2 || ... || Kn
 	 */
 	for (have = mdsz; need > have; have += mdsz) {
 		if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL ||
 		    ssh_digest_update_buffer(hashctx, shared_secret) != 0 ||
 		    ssh_digest_update(hashctx, hash, hashlen) != 0 ||
 		    ssh_digest_update(hashctx, digest, have) != 0 ||
 		    ssh_digest_final(hashctx, digest + have, mdsz) != 0) {
 			r = SSH_ERR_LIBCRYPTO_ERROR;
 			goto out;
 		}
 		ssh_digest_free(hashctx);
 		hashctx = NULL;
 	}
 #ifdef DEBUG_KEX
 	fprintf(stderr, "key '%c'== ", c);
 	dump_digest("key", digest, need);
 #endif
 	*keyp = digest;
 	digest = NULL;
 	r = 0;
  out:
 	if (digest)
 		free(digest);
 	ssh_digest_free(hashctx);
 	return r;
 }

 #define NKEYS	6
 int
 kex_derive_keys(struct ssh *ssh, u_char *hash, u_int hashlen,
     const struct sshbuf *shared_secret)
 {
 	struct kex *kex = ssh->kex;
 	u_char *keys[NKEYS];
 	u_int i, j, mode, ctos;
 	int r;

 	for (i = 0; i < NKEYS; i++) {
 		if ((r = derive_key(ssh, 'A'+i, kex->we_need, hash, hashlen,
 		    shared_secret, &keys[i])) != 0) {
 			for (j = 0; j < i; j++)
 				free(keys[j]);
 			return r;
 		}
 	}
 	for (mode = 0; mode < MODE_MAX; mode++) {
 		ctos = (!kex->server && mode == MODE_OUT) ||
 		    (kex->server && mode == MODE_IN);
 		kex->newkeys[mode]->enc.iv  = keys[ctos ? 0 : 1];
 		kex->newkeys[mode]->enc.key = keys[ctos ? 2 : 3];
 		kex->newkeys[mode]->mac.key = keys[ctos ? 4 : 5];
 	}
 	return 0;
 }

 #ifdef WITH_OPENSSL
 int
 kex_derive_keys_bn(struct ssh *ssh, u_char *hash, u_int hashlen,
     const BIGNUM *secret)
 {
 	struct sshbuf *shared_secret;
 	int r;

 	if ((shared_secret = sshbuf_new()) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
 	if ((r = sshbuf_put_bignum2(shared_secret, secret)) == 0)
 		r = kex_derive_keys(ssh, hash, hashlen, shared_secret);
 	sshbuf_free(shared_secret);
 	return r;
 }
 #endif

 #ifdef WITH_SSH1
 int
 derive_ssh1_session_id(BIGNUM *host_modulus, BIGNUM *server_modulus,
     u_int8_t cookie[8], u_int8_t id[16])
 {
 	u_int8_t nbuf[2048], obuf[SSH_DIGEST_MAX_LENGTH];
 	struct ssh_digest_ctx *hashctx = NULL;
 	size_t len;
 	int r;

 	len = BN_num_bytes(host_modulus);
 	if (len < (512 / 8) || (u_int)len > sizeof(nbuf))
 		return SSH_ERR_KEY_BITS_MISMATCH;
 	if (BN_bn2bin(host_modulus, nbuf) <= 0 ||
 	    (hashctx = ssh_digest_start(SSH_DIGEST_MD5)) == NULL ||
 	    ssh_digest_update(hashctx, nbuf, len) != 0 ||
 	    ssh_digest_update(hashctx, cookie, 8) != 0 ||
 	    ssh_digest_final(hashctx, obuf, sizeof(obuf)) != 0) {
 		r = SSH_ERR_LIBCRYPTO_ERROR;
 		goto out;
 	}
 	memcpy(id, obuf, ssh_digest_bytes(SSH_DIGEST_MD5));
 	r = 0;
  out:
 	ssh_digest_free(hashctx);
 	explicit_bzero(nbuf, sizeof(nbuf));
 	explicit_bzero(obuf, sizeof(obuf));
 	return r;
 }
 #endif

 #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH)
 void
 dump_digest(char *msg, u_char *digest, int len)
 {
 	fprintf(stderr, "%s\n", msg);
 	sshbuf_dump_data(digest, len, stderr);
 }
 #endif
	/* $OpenBSD: kex.c,v 1.103 2015/01/20 23:14:00 deraadt Exp $ */
	/*
	* Copyright (c) 2000, 2001 Markus Friedl. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "includes.h"

	#include <sys/param.h> /* MAX roundup */

	#include <signal.h>
	#include <stdarg.h>
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>

	#ifdef WITH_OPENSSL
	#include <openssl/crypto.h>
	#endif

	#include "ssh2.h"
	#include "packet.h"
	#include "compat.h"
	#include "cipher.h"
	#include "sshkey.h"
	#include "kex.h"
	#include "log.h"
	#include "mac.h"
	#include "match.h"
	#include "misc.h"
	#include "dispatch.h"
	#include "monitor.h"
	#include "roaming.h"

	#include "ssherr.h"
	#include "sshbuf.h"
	#include "digest.h"

	#if OPENSSL_VERSION_NUMBER >= 0x00907000L
	# if defined(HAVE_EVP_SHA256)
	# define evp_ssh_sha256 EVP_sha256
	# else
	extern const EVP_MD *evp_ssh_sha256(void);
	# endif
	#endif

	/* prototype */
	static int kex_choose_conf(struct ssh *);
	static int kex_input_newkeys(int, u_int32_t, void *);

	struct kexalg {
	char *name;
	u_int type;
	int ec_nid;
	int hash_alg;
	};
	static const struct kexalg kexalgs[] = {
	#ifdef WITH_OPENSSL
	{ KEX_DH1, KEX_DH_GRP1_SHA1, 0, SSH_DIGEST_SHA1 },
	{ KEX_DH14, KEX_DH_GRP14_SHA1, 0, SSH_DIGEST_SHA1 },
	{ KEX_DHGEX_SHA1, KEX_DH_GEX_SHA1, 0, SSH_DIGEST_SHA1 },
	#ifdef HAVE_EVP_SHA256
	{ KEX_DHGEX_SHA256, KEX_DH_GEX_SHA256, 0, SSH_DIGEST_SHA256 },
	#endif /* HAVE_EVP_SHA256 */
	#ifdef OPENSSL_HAS_ECC
	{ KEX_ECDH_SHA2_NISTP256, KEX_ECDH_SHA2,
	NID_X9_62_prime256v1, SSH_DIGEST_SHA256 },
	{ KEX_ECDH_SHA2_NISTP384, KEX_ECDH_SHA2, NID_secp384r1,
	SSH_DIGEST_SHA384 },
	# ifdef OPENSSL_HAS_NISTP521
	{ KEX_ECDH_SHA2_NISTP521, KEX_ECDH_SHA2, NID_secp521r1,
	SSH_DIGEST_SHA512 },
	# endif /* OPENSSL_HAS_NISTP521 */
	#endif /* OPENSSL_HAS_ECC */
	#endif /* WITH_OPENSSL */
	#if defined(HAVE_EVP_SHA256) \|\| !defined(WITH_OPENSSL)
	{ KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
	#endif /* HAVE_EVP_SHA256 \|\| !WITH_OPENSSL */
	{ NULL, -1, -1, -1},
	};

	char *
	kex_alg_list(char sep)
	{
	char ret = NULL, tmp;
	size_t nlen, rlen = 0;
	const struct kexalg *k;

	for (k = kexalgs; k->name != NULL; k++) {
	if (ret != NULL)
	ret[rlen++] = sep;
	nlen = strlen(k->name);
	if ((tmp = realloc(ret, rlen + nlen + 2)) == NULL) {
	free(ret);
	return NULL;
	}
	ret = tmp;
	memcpy(ret + rlen, k->name, nlen + 1);
	rlen += nlen;
	}
	return ret;
	}

	static const struct kexalg *
	kex_alg_by_name(const char *name)
	{
	const struct kexalg *k;

	for (k = kexalgs; k->name != NULL; k++) {
	if (strcmp(k->name, name) == 0)
	return k;
	}
	return NULL;
	}

	/* Validate KEX method name list */
	int
	kex_names_valid(const char *names)
	{
	char s, cp, *p;

	if (names == NULL \|\| strcmp(names, "") == 0)
	return 0;
	if ((s = cp = strdup(names)) == NULL)
	return 0;
	for ((p = strsep(&cp, ",")); p && *p != '\0';
	(p = strsep(&cp, ","))) {
	if (kex_alg_by_name(p) == NULL) {
	error("Unsupported KEX algorithm \"%.100s\"", p);
	free(s);
	return 0;
	}
	}
	debug3("kex names ok: [%s]", names);
	free(s);
	return 1;
	}

	/* put algorithm proposal into buffer */
	int
	kex_prop2buf(struct sshbuf b, char proposal[PROPOSAL_MAX])
	{
	u_int i;
	int r;

	sshbuf_reset(b);

	/*
	* add a dummy cookie, the cookie will be overwritten by
	* kex_send_kexinit(), each time a kexinit is set
	*/
	for (i = 0; i < KEX_COOKIE_LEN; i++) {
	if ((r = sshbuf_put_u8(b, 0)) != 0)
	return r;
	}
	for (i = 0; i < PROPOSAL_MAX; i++) {
	if ((r = sshbuf_put_cstring(b, proposal[i])) != 0)
	return r;
	}
	if ((r = sshbuf_put_u8(b, 0)) != 0 \|\| /* first_kex_packet_follows */
	(r = sshbuf_put_u32(b, 0)) != 0) /* uint32 reserved */
	return r;
	return 0;
	}

	/* parse buffer and return algorithm proposal */
	int
	kex_buf2prop(struct sshbuf raw, int first_kex_follows, char ***propp)
	{
	struct sshbuf *b = NULL;
	u_char v;
	u_int i;
	char **proposal = NULL;
	int r;

	*propp = NULL;
	if ((proposal = calloc(PROPOSAL_MAX, sizeof(char *))) == NULL)
	return SSH_ERR_ALLOC_FAIL;
	if ((b = sshbuf_fromb(raw)) == NULL) {
	r = SSH_ERR_ALLOC_FAIL;
	goto out;
	}
	if ((r = sshbuf_consume(b, KEX_COOKIE_LEN)) != 0) /* skip cookie */
	goto out;
	/* extract kex init proposal strings */
	for (i = 0; i < PROPOSAL_MAX; i++) {
	if ((r = sshbuf_get_cstring(b, &(proposal[i]), NULL)) != 0)
	goto out;
	debug2("kex_parse_kexinit: %s", proposal[i]);
	}
	/* first kex follows / reserved */
	if ((r = sshbuf_get_u8(b, &v)) != 0 \|\|
	(r = sshbuf_get_u32(b, &i)) != 0)
	goto out;
	if (first_kex_follows != NULL)
	*first_kex_follows = i;
	debug2("kex_parse_kexinit: first_kex_follows %d ", v);
	debug2("kex_parse_kexinit: reserved %u ", i);
	r = 0;
	*propp = proposal;
	out:
	if (r != 0 && proposal != NULL)
	kex_prop_free(proposal);
	sshbuf_free(b);
	return r;
	}

	void
	kex_prop_free(char **proposal)
	{
	u_int i;

	for (i = 0; i < PROPOSAL_MAX; i++)
	free(proposal[i]);
	free(proposal);
	}

	/* ARGSUSED */
	static int
	kex_protocol_error(int type, u_int32_t seq, void *ctxt)
	{
	error("Hm, kex protocol error: type %d seq %u", type, seq);
	return 0;
	}

	static void
	kex_reset_dispatch(struct ssh *ssh)
	{
	ssh_dispatch_range(ssh, SSH2_MSG_TRANSPORT_MIN,
	SSH2_MSG_TRANSPORT_MAX, &kex_protocol_error);
	ssh_dispatch_set(ssh, SSH2_MSG_KEXINIT, &kex_input_kexinit);
	}

	int
	kex_send_newkeys(struct ssh *ssh)
	{
	int r;

	kex_reset_dispatch(ssh);
	if ((r = sshpkt_start(ssh, SSH2_MSG_NEWKEYS)) != 0 \|\|
	(r = sshpkt_send(ssh)) != 0)
	return r;
	debug("SSH2_MSG_NEWKEYS sent");
	debug("expecting SSH2_MSG_NEWKEYS");
	ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_input_newkeys);
	return 0;
	}

	static int
	kex_input_newkeys(int type, u_int32_t seq, void *ctxt)
	{
	struct ssh *ssh = ctxt;
	struct kex *kex = ssh->kex;
	int r;

	debug("SSH2_MSG_NEWKEYS received");
	ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_protocol_error);
	if ((r = sshpkt_get_end(ssh)) != 0)
	return r;
	kex->done = 1;
	sshbuf_reset(kex->peer);
	/* sshbuf_reset(kex->my); */
	kex->flags &= ~KEX_INIT_SENT;
	free(kex->name);
	kex->name = NULL;
	return 0;
	}

	int
	kex_send_kexinit(struct ssh *ssh)
	{
	u_char *cookie;
	struct kex *kex = ssh->kex;
	int r;

	if (kex == NULL)
	return SSH_ERR_INTERNAL_ERROR;
	if (kex->flags & KEX_INIT_SENT)
	return 0;
	kex->done = 0;

	/* generate a random cookie */
	if (sshbuf_len(kex->my) < KEX_COOKIE_LEN)
	return SSH_ERR_INVALID_FORMAT;
	if ((cookie = sshbuf_mutable_ptr(kex->my)) == NULL)
	return SSH_ERR_INTERNAL_ERROR;
	arc4random_buf(cookie, KEX_COOKIE_LEN);

	if ((r = sshpkt_start(ssh, SSH2_MSG_KEXINIT)) != 0 \|\|
	(r = sshpkt_putb(ssh, kex->my)) != 0 \|\|
	(r = sshpkt_send(ssh)) != 0)
	return r;
	debug("SSH2_MSG_KEXINIT sent");
	kex->flags \|= KEX_INIT_SENT;
	return 0;
	}

	/* ARGSUSED */
	int
	kex_input_kexinit(int type, u_int32_t seq, void *ctxt)
	{
	struct ssh *ssh = ctxt;
	struct kex *kex = ssh->kex;
	const u_char *ptr;
	u_int i;
	size_t dlen;
	int r;

	debug("SSH2_MSG_KEXINIT received");
	if (kex == NULL)
	return SSH_ERR_INVALID_ARGUMENT;

	ptr = sshpkt_ptr(ssh, &dlen);
	if ((r = sshbuf_put(kex->peer, ptr, dlen)) != 0)
	return r;

	/* discard packet */
	for (i = 0; i < KEX_COOKIE_LEN; i++)
	if ((r = sshpkt_get_u8(ssh, NULL)) != 0)
	return r;
	for (i = 0; i < PROPOSAL_MAX; i++)
	if ((r = sshpkt_get_string(ssh, NULL, NULL)) != 0)
	return r;
	/*
	* XXX RFC4253 sec 7: "each side MAY guess" - currently no supported
	* KEX method has the server move first, but a server might be using
	* a custom method or one that we otherwise don't support. We should
	* be prepared to remember first_kex_follows here so we can eat a
	* packet later.
	* XXX2 - RFC4253 is kind of ambiguous on what first_kex_follows means
	* for cases where the server doesn't go first. I guess we should
	* ignore it when it is set for these cases, which is what we do now.
	*/
	if ((r = sshpkt_get_u8(ssh, NULL)) != 0 \|\| /* first_kex_follows */
	(r = sshpkt_get_u32(ssh, NULL)) != 0 \|\| /* reserved */
	(r = sshpkt_get_end(ssh)) != 0)
	return r;

	if (!(kex->flags & KEX_INIT_SENT))
	if ((r = kex_send_kexinit(ssh)) != 0)
	return r;
	if ((r = kex_choose_conf(ssh)) != 0)
	return r;

	if (kex->kex_type < KEX_MAX && kex->kex[kex->kex_type] != NULL)
	return (kex->kex[kex->kex_type])(ssh);

	return SSH_ERR_INTERNAL_ERROR;
	}

	int
	kex_new(struct ssh ssh, char proposal[PROPOSAL_MAX], struct kex **kexp)
	{
	struct kex *kex;
	int r;

	*kexp = NULL;
	if ((kex = calloc(1, sizeof(*kex))) == NULL)
	return SSH_ERR_ALLOC_FAIL;
	if ((kex->peer = sshbuf_new()) == NULL \|\|
	(kex->my = sshbuf_new()) == NULL) {
	r = SSH_ERR_ALLOC_FAIL;
	goto out;
	}
	if ((r = kex_prop2buf(kex->my, proposal)) != 0)
	goto out;
	kex->done = 0;
	kex_reset_dispatch(ssh);
	r = 0;
	*kexp = kex;
	out:
	if (r != 0)
	kex_free(kex);
	return r;
	}

	void
	kex_free_newkeys(struct newkeys *newkeys)
	{
	if (newkeys == NULL)
	return;
	if (newkeys->enc.key) {
	explicit_bzero(newkeys->enc.key, newkeys->enc.key_len);
	free(newkeys->enc.key);
	newkeys->enc.key = NULL;
	}
	if (newkeys->enc.iv) {
	explicit_bzero(newkeys->enc.iv, newkeys->enc.block_size);
	free(newkeys->enc.iv);
	newkeys->enc.iv = NULL;
	}
	free(newkeys->enc.name);
	explicit_bzero(&newkeys->enc, sizeof(newkeys->enc));
	free(newkeys->comp.name);
	explicit_bzero(&newkeys->comp, sizeof(newkeys->comp));
	mac_clear(&newkeys->mac);
	if (newkeys->mac.key) {
	explicit_bzero(newkeys->mac.key, newkeys->mac.key_len);
	free(newkeys->mac.key);
	newkeys->mac.key = NULL;
	}
	free(newkeys->mac.name);
	explicit_bzero(&newkeys->mac, sizeof(newkeys->mac));
	explicit_bzero(newkeys, sizeof(*newkeys));
	free(newkeys);
	}

	void
	kex_free(struct kex *kex)
	{
	u_int mode;

	#ifdef WITH_OPENSSL
	if (kex->dh)
	DH_free(kex->dh);
	if (kex->ec_client_key)
	EC_KEY_free(kex->ec_client_key);
	#endif
	for (mode = 0; mode < MODE_MAX; mode++) {
	kex_free_newkeys(kex->newkeys[mode]);
	kex->newkeys[mode] = NULL;
	}
	sshbuf_free(kex->peer);
	sshbuf_free(kex->my);
	free(kex->session_id);
	free(kex->client_version_string);
	free(kex->server_version_string);
	free(kex);
	}

	int
	kex_setup(struct ssh ssh, char proposal[PROPOSAL_MAX])
	{
	int r;

	if ((r = kex_new(ssh, proposal, &ssh->kex)) != 0)
	return r;
	if ((r = kex_send_kexinit(ssh)) != 0) { /* we start */
	kex_free(ssh->kex);
	ssh->kex = NULL;
	return r;
	}
	return 0;
	}

	static int
	choose_enc(struct sshenc enc, char client, char *server)
	{
	char *name = match_list(client, server, NULL);

	if (name == NULL)
	return SSH_ERR_NO_CIPHER_ALG_MATCH;
	if ((enc->cipher = cipher_by_name(name)) == NULL)
	return SSH_ERR_INTERNAL_ERROR;
	enc->name = name;
	enc->enabled = 0;
	enc->iv = NULL;
	enc->iv_len = cipher_ivlen(enc->cipher);
	enc->key = NULL;
	enc->key_len = cipher_keylen(enc->cipher);
	enc->block_size = cipher_blocksize(enc->cipher);
	return 0;
	}

	static int
	choose_mac(struct ssh ssh, struct sshmac mac, char client, char server)
	{
	char *name = match_list(client, server, NULL);

	if (name == NULL)
	return SSH_ERR_NO_MAC_ALG_MATCH;
	if (mac_setup(mac, name) < 0)
	return SSH_ERR_INTERNAL_ERROR;
	/* truncate the key */
	if (ssh->compat & SSH_BUG_HMAC)
	mac->key_len = 16;
	mac->name = name;
	mac->key = NULL;
	mac->enabled = 0;
	return 0;
	}

	static int
	choose_comp(struct sshcomp comp, char client, char *server)
	{
	char *name = match_list(client, server, NULL);

	if (name == NULL)
	return SSH_ERR_NO_COMPRESS_ALG_MATCH;
	if (strcmp(name, "zlib@openssh.com") == 0) {
	comp->type = COMP_DELAYED;
	} else if (strcmp(name, "zlib") == 0) {
	comp->type = COMP_ZLIB;
	} else if (strcmp(name, "none") == 0) {
	comp->type = COMP_NONE;
	} else {
	return SSH_ERR_INTERNAL_ERROR;
	}
	comp->name = name;
	return 0;
	}

	static int
	choose_kex(struct kex k, char client, char *server)
	{
	const struct kexalg *kexalg;

	k->name = match_list(client, server, NULL);

	if (k->name == NULL)
	return SSH_ERR_NO_KEX_ALG_MATCH;
	if ((kexalg = kex_alg_by_name(k->name)) == NULL)
	return SSH_ERR_INTERNAL_ERROR;
	k->kex_type = kexalg->type;
	k->hash_alg = kexalg->hash_alg;
	k->ec_nid = kexalg->ec_nid;
	return 0;
	}

	static int
	choose_hostkeyalg(struct kex k, char client, char *server)
	{
	char *hostkeyalg = match_list(client, server, NULL);

	if (hostkeyalg == NULL)
	return SSH_ERR_NO_HOSTKEY_ALG_MATCH;
	k->hostkey_type = sshkey_type_from_name(hostkeyalg);
	if (k->hostkey_type == KEY_UNSPEC)
	return SSH_ERR_INTERNAL_ERROR;
	free(hostkeyalg);
	return 0;
	}

	static int
	proposals_match(char my[PROPOSAL_MAX], char peer[PROPOSAL_MAX])
	{
	static int check[] = {
	PROPOSAL_KEX_ALGS, PROPOSAL_SERVER_HOST_KEY_ALGS, -1
	};
	int *idx;
	char *p;

	for (idx = &check[0]; *idx != -1; idx++) {
	if ((p = strchr(my[*idx], ',')) != NULL)
	*p = '\0';
	if ((p = strchr(peer[*idx], ',')) != NULL)
	*p = '\0';
	if (strcmp(my[idx], peer[idx]) != 0) {
	debug2("proposal mismatch: my %s peer %s",
	my[idx], peer[idx]);
	return (0);
	}
	}
	debug2("proposals match");
	return (1);
	}

	static int
	kex_choose_conf(struct ssh *ssh)
	{
	struct kex *kex = ssh->kex;
	struct newkeys *newkeys;
	char my = NULL, peer = NULL;
	char cprop, sprop;
	int nenc, nmac, ncomp;
	u_int mode, ctos, need, dh_need, authlen;
	int r, first_kex_follows;

	if ((r = kex_buf2prop(kex->my, NULL, &my)) != 0 \|\|
	(r = kex_buf2prop(kex->peer, &first_kex_follows, &peer)) != 0)
	goto out;

	if (kex->server) {
	cprop=peer;
	sprop=my;
	} else {
	cprop=my;
	sprop=peer;
	}

	/* Check whether server offers roaming */
	if (!kex->server) {
	char *roaming = match_list(KEX_RESUME,
	peer[PROPOSAL_KEX_ALGS], NULL);

	if (roaming) {
	kex->roaming = 1;
	free(roaming);
	}
	}

	/* Algorithm Negotiation */
	for (mode = 0; mode < MODE_MAX; mode++) {
	if ((newkeys = calloc(1, sizeof(*newkeys))) == NULL) {
	r = SSH_ERR_ALLOC_FAIL;
	goto out;
	}
	kex->newkeys[mode] = newkeys;
	ctos = (!kex->server && mode == MODE_OUT) \|\|
	(kex->server && mode == MODE_IN);
	nenc = ctos ? PROPOSAL_ENC_ALGS_CTOS : PROPOSAL_ENC_ALGS_STOC;
	nmac = ctos ? PROPOSAL_MAC_ALGS_CTOS : PROPOSAL_MAC_ALGS_STOC;
	ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
	if ((r = choose_enc(&newkeys->enc, cprop[nenc],
	sprop[nenc])) != 0)
	goto out;
	authlen = cipher_authlen(newkeys->enc.cipher);
	/* ignore mac for authenticated encryption */
	if (authlen == 0 &&
	(r = choose_mac(ssh, &newkeys->mac, cprop[nmac],
	sprop[nmac])) != 0)
	goto out;
	if ((r = choose_comp(&newkeys->comp, cprop[ncomp],
	sprop[ncomp])) != 0)
	goto out;
	debug("kex: %s %s %s %s",
	ctos ? "client->server" : "server->client",
	newkeys->enc.name,
	authlen == 0 ? newkeys->mac.name : "<implicit>",
	newkeys->comp.name);
	}
	if ((r = choose_kex(kex, cprop[PROPOSAL_KEX_ALGS],
	sprop[PROPOSAL_KEX_ALGS])) != 0 \|\|
	(r = choose_hostkeyalg(kex, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
	sprop[PROPOSAL_SERVER_HOST_KEY_ALGS])) != 0)
	goto out;
	need = dh_need = 0;
	for (mode = 0; mode < MODE_MAX; mode++) {
	newkeys = kex->newkeys[mode];
	need = MAX(need, newkeys->enc.key_len);
	need = MAX(need, newkeys->enc.block_size);
	need = MAX(need, newkeys->enc.iv_len);
	need = MAX(need, newkeys->mac.key_len);
	dh_need = MAX(dh_need, cipher_seclen(newkeys->enc.cipher));
	dh_need = MAX(dh_need, newkeys->enc.block_size);
	dh_need = MAX(dh_need, newkeys->enc.iv_len);
	dh_need = MAX(dh_need, newkeys->mac.key_len);
	}
	/* XXX need runden? */
	kex->we_need = need;
	kex->dh_need = dh_need;

	/* ignore the next message if the proposals do not match */
	if (first_kex_follows && !proposals_match(my, peer) &&
	!(ssh->compat & SSH_BUG_FIRSTKEX))
	ssh->dispatch_skip_packets = 1;
	r = 0;
	out:
	kex_prop_free(my);
	kex_prop_free(peer);
	return r;
	}

	static int
	derive_key(struct ssh ssh, int id, u_int need, u_char hash, u_int hashlen,
	const struct sshbuf shared_secret, u_char *keyp)
	{
	struct kex *kex = ssh->kex;
	struct ssh_digest_ctx *hashctx = NULL;
	char c = id;
	u_int have;
	size_t mdsz;
	u_char *digest;
	int r;

	if ((mdsz = ssh_digest_bytes(kex->hash_alg)) == 0)
	return SSH_ERR_INVALID_ARGUMENT;
	if ((digest = calloc(1, roundup(need, mdsz))) == NULL) {
	r = SSH_ERR_ALLOC_FAIL;
	goto out;
	}

	/* K1 = HASH(K \|\| H \|\| "A" \|\| session_id) */
	if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL \|\|
	ssh_digest_update_buffer(hashctx, shared_secret) != 0 \|\|
	ssh_digest_update(hashctx, hash, hashlen) != 0 \|\|
	ssh_digest_update(hashctx, &c, 1) != 0 \|\|
	ssh_digest_update(hashctx, kex->session_id,
	kex->session_id_len) != 0 \|\|
	ssh_digest_final(hashctx, digest, mdsz) != 0) {
	r = SSH_ERR_LIBCRYPTO_ERROR;
	goto out;
	}
	ssh_digest_free(hashctx);
	hashctx = NULL;

	/*
	* expand key:
	* Kn = HASH(K \|\| H \|\| K1 \|\| K2 \|\| ... \|\| Kn-1)
	* Key = K1 \|\| K2 \|\| ... \|\| Kn
	*/
	for (have = mdsz; need > have; have += mdsz) {
	if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL \|\|
	ssh_digest_update_buffer(hashctx, shared_secret) != 0 \|\|
	ssh_digest_update(hashctx, hash, hashlen) != 0 \|\|
	ssh_digest_update(hashctx, digest, have) != 0 \|\|
	ssh_digest_final(hashctx, digest + have, mdsz) != 0) {
	r = SSH_ERR_LIBCRYPTO_ERROR;
	goto out;
	}
	ssh_digest_free(hashctx);
	hashctx = NULL;
	}
	#ifdef DEBUG_KEX
	fprintf(stderr, "key '%c'== ", c);
	dump_digest("key", digest, need);
	#endif
	*keyp = digest;
	digest = NULL;
	r = 0;
	out:
	if (digest)
	free(digest);
	ssh_digest_free(hashctx);
	return r;
	}

	#define NKEYS 6
	int
	kex_derive_keys(struct ssh ssh, u_char hash, u_int hashlen,
	const struct sshbuf *shared_secret)
	{
	struct kex *kex = ssh->kex;
	u_char *keys[NKEYS];
	u_int i, j, mode, ctos;
	int r;

	for (i = 0; i < NKEYS; i++) {
	if ((r = derive_key(ssh, 'A'+i, kex->we_need, hash, hashlen,
	shared_secret, &keys[i])) != 0) {
	for (j = 0; j < i; j++)
	free(keys[j]);
	return r;
	}
	}
	for (mode = 0; mode < MODE_MAX; mode++) {
	ctos = (!kex->server && mode == MODE_OUT) \|\|
	(kex->server && mode == MODE_IN);
	kex->newkeys[mode]->enc.iv = keys[ctos ? 0 : 1];
	kex->newkeys[mode]->enc.key = keys[ctos ? 2 : 3];
	kex->newkeys[mode]->mac.key = keys[ctos ? 4 : 5];
	}
	return 0;
	}

	#ifdef WITH_OPENSSL
	int
	kex_derive_keys_bn(struct ssh ssh, u_char hash, u_int hashlen,
	const BIGNUM *secret)
	{
	struct sshbuf *shared_secret;
	int r;

	if ((shared_secret = sshbuf_new()) == NULL)
	return SSH_ERR_ALLOC_FAIL;
	if ((r = sshbuf_put_bignum2(shared_secret, secret)) == 0)
	r = kex_derive_keys(ssh, hash, hashlen, shared_secret);
	sshbuf_free(shared_secret);
	return r;
	}
	#endif

	#ifdef WITH_SSH1
	int
	derive_ssh1_session_id(BIGNUM host_modulus, BIGNUM server_modulus,
	u_int8_t cookie[8], u_int8_t id[16])
	{
	u_int8_t nbuf[2048], obuf[SSH_DIGEST_MAX_LENGTH];
	struct ssh_digest_ctx *hashctx = NULL;
	size_t len;
	int r;

	len = BN_num_bytes(host_modulus);
	if (len < (512 / 8) \|\| (u_int)len > sizeof(nbuf))
	return SSH_ERR_KEY_BITS_MISMATCH;
	if (BN_bn2bin(host_modulus, nbuf) <= 0 \|\|
	(hashctx = ssh_digest_start(SSH_DIGEST_MD5)) == NULL \|\|
	ssh_digest_update(hashctx, nbuf, len) != 0 \|\|
	ssh_digest_update(hashctx, cookie, 8) != 0 \|\|
	ssh_digest_final(hashctx, obuf, sizeof(obuf)) != 0) {
	r = SSH_ERR_LIBCRYPTO_ERROR;
	goto out;
	}
	memcpy(id, obuf, ssh_digest_bytes(SSH_DIGEST_MD5));
	r = 0;
	out:
	ssh_digest_free(hashctx);
	explicit_bzero(nbuf, sizeof(nbuf));
	explicit_bzero(obuf, sizeof(obuf));
	return r;
	}
	#endif

	#if defined(DEBUG_KEX) \|\| defined(DEBUG_KEXDH) \|\| defined(DEBUG_KEXECDH)
	void
	dump_digest(char msg, u_char digest, int len)
	{
	fprintf(stderr, "%s\n", msg);
	sshbuf_dump_data(digest, len, stderr);
	}
	#endif