Revise hostkeys@openssh.com hostkey learning extension.

The client will not ask the server to prove ownership of the private
halves of any hitherto-unseen hostkeys it offers to the client.

Allow UpdateHostKeys option to take an 'ask' argument to let the
user manually review keys offered.

ok markus@

14 files changed, 537 insertions, 101 deletions

diff --git a/usr.bin/ssh/PROTOCOL b/usr.bin/ssh/PROTOCOL
index 8150c577b37..f9560839ec4 100644
--- a/usr.bin/ssh/PROTOCOL
+++ b/usr.bin/ssh/PROTOCOL
@@ -40,8 +40,8 @@ http://www.openssh.com/txt/draft-miller-secsh-compression-delayed-00.txt
      "ecdsa-sha2-nistp521-cert-v01@openssh.com"
 
 OpenSSH introduces new public key algorithms to support certificate
-authentication for users and hostkeys. These methods are documented in
-the file PROTOCOL.certkeys
+authentication for users and host keys. These methods are documented
+in the file PROTOCOL.certkeys
 
 1.4. transport: Elliptic Curve cryptography
 
@@ -283,26 +283,51 @@ by the client cancel the forwarding of a Unix domain socket.
 	string		socket path
 
 2.5. connection: hostkey update and rotation "hostkeys@openssh.com"
+and "hostkeys-prove@openssh.com"
 
 OpenSSH supports a protocol extension allowing a server to inform
-a client of all its protocol v.2 hostkeys after user-authentication
+a client of all its protocol v.2 host keys after user-authentication
 has completed.
 
 	byte		SSH_MSG_GLOBAL_REQUEST
 	string		"hostkeys@openssh.com"
 	string[]	hostkeys
 
-Upon receiving this message, a client may update its known_hosts
-file, adding keys that it has not seen before and deleting keys
-for the server host that are no longer offered.
+Upon receiving this message, a client should check which of the
+supplied host keys are present in known_hosts. For keys that are
+not present, it should send a "hostkeys-prove@openssh.com" message
+to request the server prove ownership of the private half of the
+key.
 
-This extension allows a client to learn key types that it had
-not previously encountered, thereby allowing it to potentially
-upgrade from weaker key algorithms to better ones. It also
-supports graceful key rotation: a server may offer multiple keys
-of the same type for a period (to give clients an opportunity to
-learn them using this extension) before removing the deprecated
-key from those offered.
+	byte		SSH_MSG_GLOBAL_REQUEST
+	string		"hostkeys-prove@openssh.com"
+	char		1 /* want-reply */
+	string[]	hostkeys
+
+When a server receives this message, it should generate a signature
+using each requested key over the following:
+
+	string		session identifier
+	string		"hostkeys-prove@openssh.com"
+	string		hostkey
+
+These signatures should be included in the reply, in the order matching
+the hostkeys in the request:
+
+	byte		SSH_MSG_REQUEST_SUCCESS
+	string[]	signatures
+
+When the client receives this reply (and not a failure), it should
+validate the signatures and may update its known_hosts file, adding keys
+that it has not seen before and deleting keys for the server host that
+are no longer offered.
+
+These extensions let a client learn key types that it had not previously
+encountered, thereby allowing it to potentially upgrade from weaker
+key algorithms to better ones. It also supports graceful key rotation:
+a server may offer multiple keys of the same type for a period (to
+give clients an opportunity to learn them using this extension) before
+removing the deprecated key from those offered.
 
 3. SFTP protocol changes
 
@@ -428,4 +453,4 @@ respond with a SSH_FXP_STATUS message.
 This extension is advertised in the SSH_FXP_VERSION hello with version
 "1".
 
-$OpenBSD: PROTOCOL,v 1.25 2015/01/26 03:04:45 djm Exp $
+$OpenBSD: PROTOCOL,v 1.26 2015/02/16 22:13:32 djm Exp $
diff --git a/usr.bin/ssh/auth.h b/usr.bin/ssh/auth.h
index 26250dc806d..a42cd013e41 100644
--- a/usr.bin/ssh/auth.h
+++ b/usr.bin/ssh/auth.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth.h,v 1.81 2015/01/26 06:10:03 djm Exp $ */
+/* $OpenBSD: auth.h,v 1.82 2015/02/16 22:13:32 djm Exp $ */
 
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
@@ -182,9 +182,10 @@ Key	*get_hostkey_by_index(int);
 Key	*get_hostkey_public_by_index(int, struct ssh *);
 Key	*get_hostkey_public_by_type(int, int, struct ssh *);
 Key	*get_hostkey_private_by_type(int, int, struct ssh *);
-int	 get_hostkey_index(Key *, struct ssh *);
+int	 get_hostkey_index(Key *, int, struct ssh *);
 int	 ssh1_session_key(BIGNUM *);
-int	 sshd_hostkey_sign(Key *, Key *, u_char **, size_t *, u_char *, size_t, u_int);
+int	 sshd_hostkey_sign(Key *, Key *, u_char **, size_t *,
+	     const u_char *, size_t, u_int);
 
 /* debug messages during authentication */
 void	 auth_debug_add(const char *fmt,...) __attribute__((format(printf, 1, 2)));
diff --git a/usr.bin/ssh/clientloop.c b/usr.bin/ssh/clientloop.c
index 54d72155917..ef0ecadd5d0 100644
--- a/usr.bin/ssh/clientloop.c
+++ b/usr.bin/ssh/clientloop.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: clientloop.c,v 1.268 2015/02/16 22:08:57 djm Exp $ */
+/* $OpenBSD: clientloop.c,v 1.269 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -2071,6 +2071,216 @@ client_input_channel_req(int type, u_int32_t seq, void *ctxt)
 	return 0;
 }
 
+struct hostkeys_update_ctx {
+	/* The hostname and (optionally) IP address string for the server */
+	char *host_str, *ip_str;
+
+	/*
+	 * Keys received from the server and a flag for each indicating
+	 * whether they already exist in known_hosts.
+	 * keys_seen is filled in by hostkeys_find() and later (for new
+	 * keys) by client_global_hostkeys_private_confirm().
+	 */
+	struct sshkey **keys;
+	int *keys_seen;
+	size_t nkeys;
+
+	size_t nnew;
+
+	/*
+	 * Keys that are in known_hosts, but were not present in the update
+	 * from the server (i.e. scheduled to be deleted).
+	 * Filled in by hostkeys_find().
+	 */
+	struct sshkey **old_keys;
+	size_t nold;
+};
+
+static void
+hostkeys_update_ctx_free(struct hostkeys_update_ctx *ctx)
+{
+	size_t i;
+
+	if (ctx == NULL)
+		return;
+	for (i = 0; i < ctx->nkeys; i++)
+		sshkey_free(ctx->keys[i]);
+	free(ctx->keys);
+	free(ctx->keys_seen);
+	for (i = 0; i < ctx->nold; i++)
+		sshkey_free(ctx->old_keys[i]);
+	free(ctx->old_keys);
+	free(ctx->host_str);
+	free(ctx->ip_str);
+	free(ctx);
+}
+
+static int
+hostkeys_find(struct hostkey_foreach_line *l, void *_ctx)
+{
+	struct hostkeys_update_ctx *ctx = (struct hostkeys_update_ctx *)_ctx;
+	size_t i;
+	struct sshkey **tmp;
+
+	if (l->status != HKF_STATUS_MATCHED || l->key == NULL ||
+	    l->key->type == KEY_RSA1)
+		return 0;
+
+	/* Mark off keys we've already seen for this host */
+	for (i = 0; i < ctx->nkeys; i++) {
+		if (sshkey_equal(l->key, ctx->keys[i])) {
+			debug3("%s: found %s key at %s:%ld", __func__,
+			    sshkey_ssh_name(ctx->keys[i]), l->path, l->linenum);
+			ctx->keys_seen[i] = 1;
+			return 0;
+		}
+	}
+	/* This line contained a key that not offered by the server */
+	debug3("%s: deprecated %s key at %s:%ld", __func__,
+	    sshkey_ssh_name(l->key), l->path, l->linenum);
+	if ((tmp = reallocarray(ctx->old_keys, ctx->nold + 1,
+	    sizeof(*ctx->old_keys))) == NULL)
+		fatal("%s: reallocarray failed nold = %zu",
+		    __func__, ctx->nold);
+	ctx->old_keys = tmp;
+	ctx->old_keys[ctx->nold++] = l->key;
+	l->key = NULL;
+
+	return 0;
+}
+
+static void
+update_known_hosts(struct hostkeys_update_ctx *ctx)
+{
+	int r, loglevel = options.update_hostkeys == SSH_UPDATE_HOSTKEYS_ASK ?
+	    SYSLOG_LEVEL_INFO : SYSLOG_LEVEL_VERBOSE;
+	char *fp, *response;
+	size_t i;
+
+	for (i = 0; i < ctx->nkeys; i++) {
+		if (ctx->keys_seen[i] != 2)
+			continue;
+		if ((fp = sshkey_fingerprint(ctx->keys[i],
+		    options.fingerprint_hash, SSH_FP_DEFAULT)) == NULL)
+			fatal("%s: sshkey_fingerprint failed", __func__);
+		do_log2(loglevel, "Learned new hostkey: %s %s",
+		    sshkey_type(ctx->keys[i]), fp);
+		free(fp);
+	}
+	for (i = 0; i < ctx->nold; i++) {
+		if ((fp = sshkey_fingerprint(ctx->old_keys[i],
+		    options.fingerprint_hash, SSH_FP_DEFAULT)) == NULL)
+			fatal("%s: sshkey_fingerprint failed", __func__);
+		do_log2(loglevel, "Deprecating obsolete hostkey: %s %s",
+		    sshkey_type(ctx->old_keys[i]), fp);
+		free(fp);
+	}
+	if (options.update_hostkeys == SSH_UPDATE_HOSTKEYS_ASK) {
+		leave_raw_mode(options.request_tty == REQUEST_TTY_FORCE);
+		response = NULL;
+		for (i = 0; !quit_pending && i < 3; i++) {
+			free(response);
+			response = read_passphrase("Accept updated hostkeys? "
+			    "(yes/no): ", RP_ECHO);
+			if (strcasecmp(response, "yes") == 0)
+				break;
+			else if (quit_pending || response == NULL ||
+			    strcasecmp(response, "no") == 0) {
+				options.update_hostkeys = 0;
+				break;
+			} else {
+				do_log2(loglevel, "Please enter "
+				    "\"yes\" or \"no\"");
+			}
+		}
+		if (quit_pending || i >= 3 || response == NULL)
+			options.update_hostkeys = 0;
+		free(response);
+		enter_raw_mode(options.request_tty == REQUEST_TTY_FORCE);
+	}
+
+	/*
+	 * Now that all the keys are verified, we can go ahead and replace
+	 * them in known_hosts (assuming SSH_UPDATE_HOSTKEYS_ASK didn't
+	 * cancel the operation).
+	 */
+	if (options.update_hostkeys != 0 &&
+	    (r = hostfile_replace_entries(options.user_hostfiles[0],
+	    ctx->host_str, ctx->ip_str, ctx->keys, ctx->nkeys,
+	    options.hash_known_hosts, 0,
+	    options.fingerprint_hash)) != 0)
+		error("%s: hostfile_replace_entries failed: %s",
+		    __func__, ssh_err(r));
+}
+
+static void
+client_global_hostkeys_private_confirm(int type, u_int32_t seq, void *_ctx)
+{
+	struct ssh *ssh = active_state; /* XXX */
+	struct hostkeys_update_ctx *ctx = (struct hostkeys_update_ctx *)_ctx;
+	size_t i, ndone;
+	struct sshbuf *signdata;
+	int r;
+	const u_char *sig;
+	size_t siglen;
+
+	if (ctx->nnew == 0)
+		fatal("%s: ctx->nnew == 0", __func__); /* sanity */
+	if (type != SSH2_MSG_REQUEST_SUCCESS) {
+		error("Server failed to confirm ownership of "
+		    "private host keys");
+		hostkeys_update_ctx_free(ctx);
+		return;
+	}
+	if ((signdata = sshbuf_new()) == NULL)
+		fatal("%s: sshbuf_new failed", __func__);
+	/* Don't want to accidentally accept an unbound signature */
+	if (ssh->kex->session_id_len == 0)
+		fatal("%s: ssh->kex->session_id_len == 0", __func__);
+	/*
+	 * Expect a signature for each of the ctx->nnew private keys we
+	 * haven't seen before. They will be in the same order as the
+	 * ctx->keys where the corresponding ctx->keys_seen[i] == 0.
+	 */
+	for (ndone = i = 0; i < ctx->nkeys; i++) {
+		if (ctx->keys_seen[i])
+			continue;
+		/* Prepare data to be signed: session ID, unique string, key */
+		sshbuf_reset(signdata);
+		if ((r = sshbuf_put_string(signdata, ssh->kex->session_id,
+		    ssh->kex->session_id_len)) != 0 ||
+		    (r = sshbuf_put_cstring(signdata,
+		    "hostkeys-prove@openssh.com")) != 0 ||
+		    (r = sshkey_puts(ctx->keys[i], signdata)) != 0)
+			fatal("%s: failed to prepare signature: %s",
+			    __func__, ssh_err(r));
+		/* Extract and verify signature */
+		if ((r = sshpkt_get_string_direct(ssh, &sig, &siglen)) != 0) {
+			error("%s: couldn't parse message: %s",
+			    __func__, ssh_err(r));
+			goto out;
+		}
+		if ((r = sshkey_verify(ctx->keys[i], sig, siglen,
+		    sshbuf_ptr(signdata), sshbuf_len(signdata), 0)) != 0) {
+			error("%s: server gave bad signature for %s key %zu",
+			    __func__, sshkey_type(ctx->keys[i]), i);
+			goto out;
+		}
+		/* Key is good. Mark it as 'seen' */
+		ctx->keys_seen[i] = 2;
+		ndone++;
+	}
+	if (ndone != ctx->nnew)
+		fatal("%s: ndone != ctx->nnew (%zu / %zu)", __func__,
+		    ndone, ctx->nnew);  /* Shouldn't happen */
+	ssh_packet_check_eom(ssh);
+
+	/* Make the edits to known_hosts */
+	update_known_hosts(ctx);
+ out:
+	hostkeys_update_ctx_free(ctx);
+}
+
 /*
  * Handle hostkeys@openssh.com global request to inform the client of all
  * the server's hostkeys. The keys are checked against the user's
@@ -2079,34 +2289,35 @@ client_input_channel_req(int type, u_int32_t seq, void *ctxt)
 static int
 client_input_hostkeys(void)
 {
+	struct ssh *ssh = active_state; /* XXX */
 	const u_char *blob = NULL;
-	u_int i, len = 0, nkeys = 0;
+	size_t i, len = 0;
 	struct sshbuf *buf = NULL;
-	struct sshkey *key = NULL, **tmp, **keys = NULL;
-	int r, success = 1;
-	char *fp, *host_str = NULL, *ip_str = NULL;
+	struct sshkey *key = NULL, **tmp;
+	int r;
+	char *fp;
 	static int hostkeys_seen = 0; /* XXX use struct ssh */
 	extern struct sockaddr_storage hostaddr; /* XXX from ssh.c */
+	struct hostkeys_update_ctx *ctx;
 
-	/*
-	 * NB. Return success for all cases other than protocol error. The
-	 * server doesn't need to know what the client does with its hosts
-	 * file.
-	 */
-
-	blob = packet_get_string_ptr(&len);
-	packet_check_eom();
+	ctx = xcalloc(1, sizeof(*ctx));
 
 	if (hostkeys_seen)
 		fatal("%s: server already sent hostkeys", __func__);
+	if (options.update_hostkeys == SSH_UPDATE_HOSTKEYS_ASK &&
+	    options.batch_mode)
+		return 1; /* won't ask in batchmode, so don't even try */
 	if (!options.update_hostkeys || options.num_user_hostfiles <= 0)
 		return 1;
-	if ((buf = sshbuf_from(blob, len)) == NULL)
-		fatal("%s: sshbuf_from failed", __func__);
-	while (sshbuf_len(buf) > 0) {
+	while (ssh_packet_remaining(ssh) > 0) {
 		sshkey_free(key);
 		key = NULL;
-		if ((r = sshkey_froms(buf, &key)) != 0)
+		if ((r = sshpkt_get_string_direct(ssh, &blob, &len)) != 0) {
+			error("%s: couldn't parse message: %s",
+			    __func__, ssh_err(r));
+			goto out;
+		}
+		if ((r = sshkey_from_blob(blob, len, &key)) != 0)
 			fatal("%s: parse key: %s", __func__, ssh_err(r));
 		fp = sshkey_fingerprint(key, options.fingerprint_hash,
 		    SSH_FP_DEFAULT);
@@ -2122,47 +2333,107 @@ client_input_hostkeys(void)
 			    __func__, sshkey_ssh_name(key));
 			continue;
 		}
-		if ((tmp = reallocarray(keys, nkeys + 1,
-		    sizeof(*keys))) == NULL)
-			fatal("%s: reallocarray failed nkeys = %u",
-			    __func__, nkeys);
-		keys = tmp;
-		keys[nkeys++] = key;
+		/* Skip certs */
+		if (sshkey_is_cert(key)) {
+			debug3("%s: %s key is a certificate; skipping",
+			    __func__, sshkey_ssh_name(key));
+			continue;
+		}
+		/* Ensure keys are unique */
+		for (i = 0; i < ctx->nkeys; i++) {
+			if (sshkey_equal(key, ctx->keys[i])) {
+				error("%s: received duplicated %s host key",
+				    __func__, sshkey_ssh_name(key));
+				goto out;
+			}
+		}
+		/* Key is good, record it */
+		if ((tmp = reallocarray(ctx->keys, ctx->nkeys + 1,
+		    sizeof(*ctx->keys))) == NULL)
+			fatal("%s: reallocarray failed nkeys = %zu",
+			    __func__, ctx->nkeys);
+		ctx->keys = tmp;
+		ctx->keys[ctx->nkeys++] = key;
 		key = NULL;
 	}
 
-	if (nkeys == 0) {
+	if (ctx->nkeys == 0) {
 		error("%s: server sent no hostkeys", __func__);
 		goto out;
 	}
+	if ((ctx->keys_seen = calloc(ctx->nkeys,
+	    sizeof(*ctx->keys_seen))) == NULL)
+		fatal("%s: calloc failed", __func__);
 
 	get_hostfile_hostname_ipaddr(host,
 	    options.check_host_ip ? (struct sockaddr *)&hostaddr : NULL,
-	    options.port, &host_str, options.check_host_ip ? &ip_str : NULL);
+	    options.port, &ctx->host_str,
+	    options.check_host_ip ? &ctx->ip_str : NULL);
+
+	/* Find which keys we already know about. */
+	if ((r = hostkeys_foreach(options.user_hostfiles[0], hostkeys_find,
+	    ctx, ctx->host_str, ctx->ip_str,
+	    HKF_WANT_PARSE_KEY|HKF_WANT_MATCH)) != 0) {
+		error("%s: hostkeys_foreach failed: %s", __func__, ssh_err(r));
+		goto out;
+	}
+
+	/* Figure out if we have any new keys to add */
+	ctx->nnew = 0;
+	for (i = 0; i < ctx->nkeys; i++) {
+		if (!ctx->keys_seen[i])
+			ctx->nnew++;
+	}
 
-	debug3("%s: update known hosts for %s%s%s with %u keys from server",
-	    __func__, host_str,
-	    options.check_host_ip ? " " : "",
-	    options.check_host_ip ? ip_str : "", nkeys);
+	debug3("%s: %zu keys from server: %zu new, %zu retained. %zu to remove",
+	    __func__, ctx->nkeys, ctx->nnew, ctx->nkeys - ctx->nnew, ctx->nold);
 
-	if ((r = hostfile_replace_entries(options.user_hostfiles[0],
-	    host_str, options.check_host_ip ? ip_str : NULL,
-	    keys, nkeys, options.hash_known_hosts, 0,
-	    options.fingerprint_hash)) != 0) {
-		error("%s: hostfile_replace_entries failed: %s",
-		    __func__, ssh_err(r));
-		goto out;
+	if (ctx->nnew == 0 && ctx->nold != 0) {
+		/* We have some keys to remove. Just do it. */
+		update_known_hosts(ctx);
+	} else if (ctx->nnew != 0) {
+		/*
+		 * We have received hitherto-unseen keys from the server.
+		 * Ask the server to confirm ownership of the private halves.
+		 */
+		debug3("%s: asking server to prove ownership for %zu keys",
+		    __func__, ctx->nnew);
+		if ((r = sshpkt_start(ssh, SSH2_MSG_GLOBAL_REQUEST)) != 0 ||
+		    (r = sshpkt_put_cstring(ssh,
+		    "hostkeys-prove@openssh.com")) != 0 ||
+		    (r = sshpkt_put_u8(ssh, 1)) != 0) /* bool: want reply */
+			fatal("%s: cannot prepare packet: %s",
+			    __func__, ssh_err(r));
+		if ((buf = sshbuf_new()) == NULL)
+			fatal("%s: sshbuf_new", __func__);
+		for (i = 0; i < ctx->nkeys; i++) {
+			if (ctx->keys_seen[i])
+				continue;
+			sshbuf_reset(buf);
+			if ((r = sshkey_putb(ctx->keys[i], buf)) != 0)
+				fatal("%s: sshkey_putb: %s",
+				    __func__, ssh_err(r));
+			if ((r = sshpkt_put_stringb(ssh, buf)) != 0)
+				fatal("%s: sshpkt_put_string: %s",
+				    __func__, ssh_err(r));
+		}
+		if ((r = sshpkt_send(ssh)) != 0)
+			fatal("%s: sshpkt_send: %s", __func__, ssh_err(r));
+		client_register_global_confirm(
+		    client_global_hostkeys_private_confirm, ctx);
+		ctx = NULL;  /* will be freed in callback */
 	}
 
 	/* Success */
  out:
-	free(host_str);
-	free(ip_str);
+	hostkeys_update_ctx_free(ctx);
 	sshkey_free(key);
-	for (i = 0; i < nkeys; i++)
-		sshkey_free(keys[i]);
 	sshbuf_free(buf);
-	return success;
+	/*
+	 * NB. Return success for all cases. The server doesn't need to know
+	 * what the client does with its hosts file.
+	 */
+	return 1;
 }
 
 static int
diff --git a/usr.bin/ssh/kex.h b/usr.bin/ssh/kex.h
index 45d35773c03..99a7d55bf83 100644
--- a/usr.bin/ssh/kex.h
+++ b/usr.bin/ssh/kex.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: kex.h,v 1.70 2015/01/26 06:10:03 djm Exp $ */
+/* $OpenBSD: kex.h,v 1.71 2015/02/16 22:13:32 djm Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -130,9 +130,9 @@ struct kex {
 	int	(*verify_host_key)(struct sshkey *, struct ssh *);
 	struct sshkey *(*load_host_public_key)(int, int, struct ssh *);
 	struct sshkey *(*load_host_private_key)(int, int, struct ssh *);
-	int	(*host_key_index)(struct sshkey *, struct ssh *);
+	int	(*host_key_index)(struct sshkey *, int, struct ssh *);
 	int	(*sign)(struct sshkey *, struct sshkey *,
-	    u_char **, size_t *, u_char *, size_t, u_int);
+	    u_char **, size_t *, const u_char *, size_t, u_int);
 	int	(*kex[KEX_MAX])(struct ssh *);
 	/* kex specific state */
 	DH	*dh;			/* DH */
diff --git a/usr.bin/ssh/monitor.c b/usr.bin/ssh/monitor.c
index e6012451bed..13b75a62e48 100644
--- a/usr.bin/ssh/monitor.c
+++ b/usr.bin/ssh/monitor.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: monitor.c,v 1.143 2015/02/13 18:57:00 markus Exp $ */
+/* $OpenBSD: monitor.c,v 1.144 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * Copyright 2002 Markus Friedl <markus@openbsd.org>
@@ -591,12 +591,15 @@ mm_answer_moduli(int sock, Buffer *m)
 int
 mm_answer_sign(int sock, Buffer *m)
 {
+	struct ssh *ssh = active_state; 	/* XXX */
 	extern int auth_sock;			/* XXX move to state struct? */
 	struct sshkey *key;
+	struct sshbuf *sigbuf;
 	u_char *p;
 	u_char *signature;
 	size_t datlen, siglen;
-	int r, keyid;
+	int r, keyid, is_proof = 0;
+	const char proof_req[] = "hostkeys-prove@openssh.com";
 
 	debug3("%s", __func__);
 
@@ -607,9 +610,38 @@ mm_answer_sign(int sock, Buffer *m)
 	/*
 	 * Supported KEX types use SHA1 (20 bytes), SHA256 (32 bytes),
 	 * SHA384 (48 bytes) and SHA512 (64 bytes).
+	 *
+	 * Otherwise, verify the signature request is for a hostkey
+	 * proof.
+	 *
+	 * XXX perform similar check for KEX signature requests too?
+	 * it's not trivial, since what is signed is the hash, rather
+	 * than the full kex structure...
 	 */
-	if (datlen != 20 && datlen != 32 && datlen != 48 && datlen != 64)
-		fatal("%s: data length incorrect: %zu", __func__, datlen);
+	if (datlen != 20 && datlen != 32 && datlen != 48 && datlen != 64) {
+		/*
+		 * Construct expected hostkey proof and compare it to what
+		 * the client sent us.
+		 */
+		if (session_id2_len == 0) /* hostkeys is never first */
+			fatal("%s: bad data length: %zu", __func__, datlen);
+		if ((key = get_hostkey_public_by_index(keyid, ssh)) == NULL)
+			fatal("%s: no hostkey for index %d", __func__, keyid);
+		if ((sigbuf = sshbuf_new()) == NULL)
+			fatal("%s: sshbuf_new", __func__);
+		if ((r = sshbuf_put_string(sigbuf, session_id2,
+		    session_id2_len) != 0) ||
+		    (r = sshbuf_put_cstring(sigbuf, proof_req)) != 0 ||
+		    (r = sshkey_puts(key, sigbuf)) != 0)
+			fatal("%s: couldn't prepare private key "
+			    "proof buffer: %s", __func__, ssh_err(r));
+		if (datlen != sshbuf_len(sigbuf) ||
+		    memcmp(p, sshbuf_ptr(sigbuf), sshbuf_len(sigbuf)) != 0)
+			fatal("%s: bad data length: %zu, hostkey proof len %zu",
+			    __func__, datlen, sshbuf_len(sigbuf));
+		sshbuf_free(sigbuf);
+		is_proof = 1;
+	}
 
 	/* save session id, it will be passed on the first call */
 	if (session_id2_len == 0) {
@@ -623,7 +655,7 @@ mm_answer_sign(int sock, Buffer *m)
 		    datafellows)) != 0)
 			fatal("%s: sshkey_sign failed: %s",
 			    __func__, ssh_err(r));
-	} else if ((key = get_hostkey_public_by_index(keyid, active_state)) != NULL &&
+	} else if ((key = get_hostkey_public_by_index(keyid, ssh)) != NULL &&
 	    auth_sock > 0) {
 		if ((r = ssh_agent_sign(auth_sock, key, &signature, &siglen,
 		    p, datlen, datafellows)) != 0) {
@@ -633,7 +665,8 @@ mm_answer_sign(int sock, Buffer *m)
 	} else
 		fatal("%s: no hostkey from index %d", __func__, keyid);
 
-	debug3("%s: signature %p(%zu)", __func__, signature, siglen);
+	debug3("%s: %s signature %p(%zu)", __func__,
+	    is_proof ? "KEX" : "hostkey proof", signature, siglen);
 
 	sshbuf_reset(m);
 	if ((r = sshbuf_put_string(m, signature, siglen)) != 0)
diff --git a/usr.bin/ssh/monitor_wrap.c b/usr.bin/ssh/monitor_wrap.c
index 30716a63256..bf5ae17ea92 100644
--- a/usr.bin/ssh/monitor_wrap.c
+++ b/usr.bin/ssh/monitor_wrap.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: monitor_wrap.c,v 1.83 2015/01/19 20:16:15 markus Exp $ */
+/* $OpenBSD: monitor_wrap.c,v 1.84 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * Copyright 2002 Markus Friedl <markus@openbsd.org>
@@ -207,7 +207,8 @@ mm_choose_dh(int min, int nbits, int max)
 #endif
 
 int
-mm_key_sign(Key *key, u_char **sigp, u_int *lenp, u_char *data, u_int datalen)
+mm_key_sign(Key *key, u_char **sigp, u_int *lenp,
+    const u_char *data, u_int datalen)
 {
 	struct kex *kex = *pmonitor->m_pkex;
 	Buffer m;
@@ -215,7 +216,7 @@ mm_key_sign(Key *key, u_char **sigp, u_int *lenp, u_char *data, u_int datalen)
 	debug3("%s entering", __func__);
 
 	buffer_init(&m);
-	buffer_put_int(&m, kex->host_key_index(key, active_state));
+	buffer_put_int(&m, kex->host_key_index(key, 0, active_state));
 	buffer_put_string(&m, data, datalen);
 
 	mm_request_send(pmonitor->m_recvfd, MONITOR_REQ_SIGN, &m);
diff --git a/usr.bin/ssh/monitor_wrap.h b/usr.bin/ssh/monitor_wrap.h
index fdec0baaf56..8ced84140cf 100644
--- a/usr.bin/ssh/monitor_wrap.h
+++ b/usr.bin/ssh/monitor_wrap.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: monitor_wrap.h,v 1.25 2015/01/19 19:52:16 markus Exp $ */
+/* $OpenBSD: monitor_wrap.h,v 1.26 2015/02/16 22:13:32 djm Exp $ */
 
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
@@ -40,7 +40,7 @@ struct Authctxt;
 void mm_log_handler(LogLevel, const char *, void *);
 int mm_is_monitor(void);
 DH *mm_choose_dh(int, int, int);
-int mm_key_sign(Key *, u_char **, u_int *, u_char *, u_int);
+int mm_key_sign(Key *, u_char **, u_int *, const u_char *, u_int);
 void mm_inform_authserv(char *, char *);
 struct passwd *mm_getpwnamallow(const char *);
 char *mm_auth2_read_banner(void);
diff --git a/usr.bin/ssh/readconf.c b/usr.bin/ssh/readconf.c
index 89eff0c0074..c24a369765b 100644
--- a/usr.bin/ssh/readconf.c
+++ b/usr.bin/ssh/readconf.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: readconf.c,v 1.231 2015/02/02 07:41:40 djm Exp $ */
+/* $OpenBSD: readconf.c,v 1.232 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -1468,7 +1468,8 @@ parse_int:
 
 	case oUpdateHostkeys:
 		intptr = &options->update_hostkeys;
-		goto parse_flag;
+		multistate_ptr = multistate_yesnoask;
+		goto parse_multistate;
 
 	case oHostbasedKeyTypes:
 		charptr = &options->hostbased_key_types;
@@ -2093,6 +2094,7 @@ fmt_intarg(OpCodes code, int val)
 		return fmt_multistate_int(val, multistate_addressfamily);
 	case oVerifyHostKeyDNS:
 	case oStrictHostKeyChecking:
+	case oUpdateHostkeys:
 		return fmt_multistate_int(val, multistate_yesnoask);
 	case oControlMaster:
 		return fmt_multistate_int(val, multistate_controlmaster);
diff --git a/usr.bin/ssh/readconf.h b/usr.bin/ssh/readconf.h
index 701b9c6965e..576b9e352d8 100644
--- a/usr.bin/ssh/readconf.h
+++ b/usr.bin/ssh/readconf.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: readconf.h,v 1.108 2015/01/30 11:43:14 djm Exp $ */
+/* $OpenBSD: readconf.h,v 1.109 2015/02/16 22:13:32 djm Exp $ */
 
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
@@ -148,7 +148,7 @@ typedef struct {
 
 	int	 fingerprint_hash;
 
-	int	 update_hostkeys;
+	int	 update_hostkeys; /* one of SSH_UPDATE_HOSTKEYS_* */
 
 	char	*hostbased_key_types;
 
@@ -174,6 +174,10 @@ typedef struct {
 #define SSHCONF_USERCONF	2  /* user provided config file not system */
 #define SSHCONF_POSTCANON	4  /* After hostname canonicalisation */
 
+#define SSH_UPDATE_HOSTKEYS_NO	0
+#define SSH_UPDATE_HOSTKEYS_YES	1
+#define SSH_UPDATE_HOSTKEYS_ASK	2
+
 void     initialize_options(Options *);
 void     fill_default_options(Options *);
 void	 fill_default_options_for_canonicalization(Options *);
diff --git a/usr.bin/ssh/serverloop.c b/usr.bin/ssh/serverloop.c
index d46459d4309..6b09fbde2f5 100644
--- a/usr.bin/ssh/serverloop.c
+++ b/usr.bin/ssh/serverloop.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: serverloop.c,v 1.176 2015/01/20 23:14:00 deraadt Exp $ */
+/* $OpenBSD: serverloop.c,v 1.177 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -75,6 +75,7 @@
 #include "auth-options.h"
 #include "serverloop.h"
 #include "roaming.h"
+#include "ssherr.h"
 
 extern ServerOptions options;
 
@@ -1113,11 +1114,82 @@ server_input_channel_open(int type, u_int32_t seq, void *ctxt)
 }
 
 static int
+server_input_hostkeys_prove(struct sshbuf **respp)
+{
+	struct ssh *ssh = active_state; /* XXX */
+	struct sshbuf *resp = NULL;
+	struct sshbuf *sigbuf = NULL;
+	struct sshkey *key = NULL, *key_pub = NULL, *key_prv = NULL;
+	int r, ndx, success = 0;
+	const u_char *blob;
+	u_char *sig = 0;
+	size_t blen, slen;
+
+	if ((resp = sshbuf_new()) == NULL || (sigbuf = sshbuf_new()) == NULL)
+		fatal("%s: sshbuf_new", __func__);
+
+	while (ssh_packet_remaining(ssh) > 0) {
+		sshkey_free(key);
+		key = NULL;
+		if ((r = sshpkt_get_string_direct(ssh, &blob, &blen)) != 0 ||
+		    (r = sshkey_from_blob(blob, blen, &key)) != 0) {
+			error("%s: couldn't parse key: %s",
+			    __func__, ssh_err(r));
+			goto out;
+		}
+		/*
+		 * Better check that this is actually one of our hostkeys
+		 * before attempting to sign anything with it.
+		 */
+		if ((ndx = ssh->kex->host_key_index(key, 1, ssh)) == -1) {
+			error("%s: unknown host %s key",
+			    __func__, sshkey_type(key));
+			goto out;
+		}
+		/*
+		 * XXX refactor: make kex->sign just use an index rather
+		 * than passing in public and private keys
+		 */
+		if ((key_prv = get_hostkey_by_index(ndx)) == NULL &&
+		    (key_pub = get_hostkey_public_by_index(ndx, ssh)) == NULL) {
+			error("%s: can't retrieve hostkey %d", __func__, ndx);
+			goto out;
+		}
+		sshbuf_reset(sigbuf);
+		free(sig);
+		sig = NULL;
+		if ((r = sshbuf_put_string(sigbuf,
+		    ssh->kex->session_id, ssh->kex->session_id_len)) != 0 ||
+		    (r = sshbuf_put_cstring(sigbuf,
+		    "hostkeys-prove@openssh.com")) != 0 ||
+		    (r = sshkey_puts(key, sigbuf)) != 0 ||
+		    (r = ssh->kex->sign(key_prv, key_pub, &sig, &slen,
+		    sshbuf_ptr(sigbuf), sshbuf_len(sigbuf), 0)) != 0 ||
+		    (r = sshbuf_put_string(resp, sig, slen)) != 0) {
+			error("%s: couldn't prepare signature: %s",
+			    __func__, ssh_err(r));
+			goto out;
+		}
+	}
+	/* Success */
+	*respp = resp;
+	resp = NULL; /* don't free it */
+	success = 1;
+ out:
+	free(sig);
+	sshbuf_free(resp);
+	sshbuf_free(sigbuf);
+	sshkey_free(key);
+	return success;
+}
+
+static int
 server_input_global_request(int type, u_int32_t seq, void *ctxt)
 {
 	char *rtype;
 	int want_reply;
-	int success = 0, allocated_listen_port = 0;
+	int r, success = 0, allocated_listen_port = 0;
+	struct sshbuf *resp = NULL;
 
 	rtype = packet_get_string(NULL);
 	want_reply = packet_get_char();
@@ -1151,6 +1223,10 @@ server_input_global_request(int type, u_int32_t seq, void *ctxt)
 			    &allocated_listen_port, &options.fwd_opts);
 		}
 		free(fwd.listen_host);
+		if ((resp = sshbuf_new()) == NULL)
+			fatal("%s: sshbuf_new", __func__);
+		if ((r = sshbuf_put_u32(resp, allocated_listen_port)) != 0)
+			fatal("%s: sshbuf_put_u32: %s", __func__, ssh_err(r));
 	} else if (strcmp(rtype, "cancel-tcpip-forward") == 0) {
 		struct Forward fwd;
 
@@ -1194,16 +1270,20 @@ server_input_global_request(int type, u_int32_t seq, void *ctxt)
 	} else if (strcmp(rtype, "no-more-sessions@openssh.com") == 0) {
 		no_more_sessions = 1;
 		success = 1;
+	} else if (strcmp(rtype, "hostkeys-prove@openssh.com") == 0) {
+		success = server_input_hostkeys_prove(&resp);
 	}
 	if (want_reply) {
 		packet_start(success ?
 		    SSH2_MSG_REQUEST_SUCCESS : SSH2_MSG_REQUEST_FAILURE);
-		if (success && allocated_listen_port > 0)
-			packet_put_int(allocated_listen_port);
+		if (success && resp != NULL)
+			ssh_packet_put_raw(active_state, sshbuf_ptr(resp),
+			    sshbuf_len(resp));
 		packet_send();
 		packet_write_wait();
 	}
 	free(rtype);
+	sshbuf_free(resp);
 	return 0;
 }
 
diff --git a/usr.bin/ssh/ssh_api.c b/usr.bin/ssh/ssh_api.c
index 27511eb69b3..8d48021e5e7 100644
--- a/usr.bin/ssh/ssh_api.c
+++ b/usr.bin/ssh/ssh_api.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh_api.c,v 1.3 2015/01/30 01:13:33 djm Exp $ */
+/* $OpenBSD: ssh_api.c,v 1.4 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Copyright (c) 2012 Markus Friedl.  All rights reserved.
  *
@@ -39,7 +39,7 @@ int	_ssh_verify_host_key(struct sshkey *, struct ssh *);
 struct sshkey *_ssh_host_public_key(int, int, struct ssh *);
 struct sshkey *_ssh_host_private_key(int, int, struct ssh *);
 int	_ssh_host_key_sign(struct sshkey *, struct sshkey *, u_char **,
-    size_t *, u_char *, size_t, u_int);
+    size_t *, const u_char *, size_t, u_int);
 
 /*
  * stubs for the server side implementation of kex.
@@ -522,7 +522,8 @@ _ssh_order_hostkeyalgs(struct ssh *ssh)
 
 int
 _ssh_host_key_sign(struct sshkey *privkey, struct sshkey *pubkey,
-    u_char **signature, size_t *slen, u_char *data, size_t dlen, u_int compat)
+    u_char **signature, size_t *slen,
+    const u_char *data, size_t dlen, u_int compat)
 {
 	return sshkey_sign(privkey, signature, slen, data, dlen, compat);
 }
diff --git a/usr.bin/ssh/ssh_config.5 b/usr.bin/ssh/ssh_config.5
index ce79fe03fbf..fa59c518e87 100644
--- a/usr.bin/ssh/ssh_config.5
+++ b/usr.bin/ssh/ssh_config.5
@@ -33,8 +33,8 @@
 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.\" $OpenBSD: ssh_config.5,v 1.203 2015/02/02 07:41:40 djm Exp $
-.Dd $Mdocdate: February 2 2015 $
+.\" $OpenBSD: ssh_config.5,v 1.204 2015/02/16 22:13:32 djm Exp $
+.Dd $Mdocdate: February 16 2015 $
 .Dt SSH_CONFIG 5
 .Os
 .Sh NAME
@@ -1510,15 +1510,20 @@ should accept notifications of additional hostkeys from the server sent
 after authentication has completed and add them to
 .Cm UserKnownHostsFile .
 The argument must be
-.Dq yes
-or
+.Dq yes ,
 .Dq no
-(the default).
+(the default) or
+.Dq ask .
 Enabling this option allows learning alternate hostkeys for a server
 and supports graceful key rotation by allowing a server to send replacement
 public keys before old ones are removed.
 Additional hostkeys are only accepted if the key used to authenticate the
 host was already trusted or explicity accepted by the user.
+If
+.Cm UpdateHostKeys
+is set to
+.Dq ask ,
+then the user is asked to confirm the modifications to the known_hosts file.
 .Pp
 Presently, only
 .Xr sshd 8
diff --git a/usr.bin/ssh/sshd.c b/usr.bin/ssh/sshd.c
index 85359925600..bad5d4ee1bc 100644
--- a/usr.bin/ssh/sshd.c
+++ b/usr.bin/ssh/sshd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshd.c,v 1.441 2015/01/31 20:30:05 djm Exp $ */
+/* $OpenBSD: sshd.c,v 1.442 2015/02/16 22:13:32 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -857,18 +857,25 @@ get_hostkey_public_by_index(int ind, struct ssh *ssh)
 }
 
 int
-get_hostkey_index(Key *key, struct ssh *ssh)
+get_hostkey_index(Key *key, int compare, struct ssh *ssh)
 {
 	int i;
 
 	for (i = 0; i < options.num_host_key_files; i++) {
 		if (key_is_cert(key)) {
-			if (key == sensitive_data.host_certificates[i])
+			if (key == sensitive_data.host_certificates[i] ||
+			    (compare && sensitive_data.host_certificates[i] &&
+			    sshkey_equal(key,
+			    sensitive_data.host_certificates[i])))
 				return (i);
 		} else {
-			if (key == sensitive_data.host_keys[i])
+			if (key == sensitive_data.host_keys[i] ||
+			    (compare && sensitive_data.host_keys[i] &&
+			    sshkey_equal(key, sensitive_data.host_keys[i])))
 				return (i);
-			if (key == sensitive_data.host_pubkeys[i])
+			if (key == sensitive_data.host_pubkeys[i] ||
+			    (compare && sensitive_data.host_pubkeys[i] &&
+			    sshkey_equal(key, sensitive_data.host_pubkeys[i])))
 				return (i);
 		}
 	}
@@ -896,19 +903,23 @@ notify_hostkeys(struct ssh *ssh)
 		debug3("%s: key %d: %s %s", __func__, i,
 		    sshkey_ssh_name(key), fp);
 		free(fp);
-		if ((r = sshkey_puts(key, buf)) != 0)
+		if (nkeys == 0) {
+			packet_start(SSH2_MSG_GLOBAL_REQUEST);
+			packet_put_cstring("hostkeys@openssh.com");
+			packet_put_char(0); /* want-reply */
+		}
+		sshbuf_reset(buf);
+		if ((r = sshkey_putb(key, buf)) != 0)
 			fatal("%s: couldn't put hostkey %d: %s",
 			    __func__, i, ssh_err(r));
+		packet_put_string(sshbuf_ptr(buf), sshbuf_len(buf));
 		nkeys++;
 	}
+	debug3("%s: sent %d hostkeys", __func__, nkeys);
 	if (nkeys == 0)
 		fatal("%s: no hostkeys", __func__);
-	debug3("%s: send %d hostkeys", __func__, nkeys);
-	packet_start(SSH2_MSG_GLOBAL_REQUEST);
-	packet_put_cstring("hostkeys@openssh.com");
-	packet_put_char(0); /* want-reply */
-	packet_put_string(sshbuf_ptr(buf), sshbuf_len(buf));
 	packet_send();
+	sshbuf_free(buf);
 }
 
 /*
@@ -2310,7 +2321,7 @@ do_ssh1_kex(void)
 
 int
 sshd_hostkey_sign(Key *privkey, Key *pubkey, u_char **signature, size_t *slen,
-    u_char *data, size_t dlen, u_int flag)
+    const u_char *data, size_t dlen, u_int flag)
 {
 	int r;
 	u_int xxx_slen, xxx_dlen = dlen;
diff --git a/usr.bin/ssh/ssherr.c b/usr.bin/ssh/ssherr.c
index 5c29c467c0d..4ca7939926c 100644
--- a/usr.bin/ssh/ssherr.c
+++ b/usr.bin/ssh/ssherr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ssherr.c,v 1.3 2015/01/30 01:13:33 djm Exp $	*/
+/*	$OpenBSD: ssherr.c,v 1.4 2015/02/16 22:13:32 djm Exp $	*/
 /*
  * Copyright (c) 2011 Damien Miller
  *
@@ -121,6 +121,8 @@ ssh_err(int n)
 		return "agent not present";
 	case SSH_ERR_AGENT_NO_IDENTITIES:
 		return "agent contains no identities";
+	case SSH_ERR_BUFFER_READ_ONLY:
+		return "internal error: buffer is read-only";
 	case SSH_ERR_KRL_BAD_MAGIC:
 		return "KRL file has invalid magic number";
 	case SSH_ERR_KEY_REVOKED: