automatically order the hostkeys requested by the client based on

which hostkeys are already recorded in known_hosts. This avoids
hostkey warnings when connecting to servers with new ECDSA keys
that are preferred by default; with markus@

8 files changed, 429 insertions, 287 deletions

diff --git a/usr.bin/ssh/auth.c b/usr.bin/ssh/auth.c
index 550bb4fc694..9330fd09de0 100644
--- a/usr.bin/ssh/auth.c
+++ b/usr.bin/ssh/auth.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth.c,v 1.90 2010/11/23 02:35:50 djm Exp $ */
+/* $OpenBSD: auth.c,v 1.91 2010/11/29 23:45:51 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  *
@@ -289,16 +289,15 @@ HostStatus
 check_key_in_hostfiles(struct passwd *pw, Key *key, const char *host,
     const char *sysfile, const char *userfile)
 {
-	Key *found;
 	char *user_hostfile;
 	struct stat st;
 	HostStatus host_status;
+	struct hostkeys *hostkeys;
+	const struct hostkey_entry *found;
 
-	/* Check if we know the host and its host key. */
-	found = key_new(key_is_cert(key) ? KEY_UNSPEC : key->type);
-	host_status = check_host_in_hostfile(sysfile, host, key, found, NULL);
-
-	if (host_status != HOST_OK && userfile != NULL) {
+	hostkeys = init_hostkeys();
+	load_hostkeys(hostkeys, host, sysfile);
+	if (userfile != NULL) {
 		user_hostfile = tilde_expand_filename(userfile, pw->pw_uid);
 		if (options.strict_modes &&
 		    (stat(user_hostfile, &st) == 0) &&
@@ -311,16 +310,23 @@ check_key_in_hostfiles(struct passwd *pw, Key *key, const char *host,
 			    user_hostfile);
 		} else {
 			temporarily_use_uid(pw);
-			host_status = check_host_in_hostfile(user_hostfile,
-			    host, key, found, NULL);
+			load_hostkeys(hostkeys, host, user_hostfile);
 			restore_uid();
 		}
 		xfree(user_hostfile);
 	}
-	key_free(found);
+	host_status = check_key_in_hostkeys(hostkeys, key, &found);
+	if (host_status == HOST_REVOKED)
+		error("WARNING: revoked key for %s attempted authentication",
+		    found->host);
+	else if (host_status == HOST_OK)
+		debug("%s: key for %s found at %s:%ld", __func__,
+		    found->host, found->file, found->line);
+	else
+		debug("%s: key for host %s not found", __func__, host);
+
+	free_hostkeys(hostkeys);
 
-	debug2("check_key_in_hostfiles: key %s for %s", host_status == HOST_OK ?
-	    "ok" : "not found", host);
 	return host_status;
 }
 
diff --git a/usr.bin/ssh/hostfile.c b/usr.bin/ssh/hostfile.c
index 4ad5557fede..06408e3f052 100644
--- a/usr.bin/ssh/hostfile.c
+++ b/usr.bin/ssh/hostfile.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: hostfile.c,v 1.48 2010/03/04 10:36:03 djm Exp $ */
+/* $OpenBSD: hostfile.c,v 1.49 2010/11/29 23:45:51 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -53,6 +53,12 @@
 #include "key.h"
 #include "hostfile.h"
 #include "log.h"
+#include "misc.h"
+
+struct hostkeys {
+	struct hostkey_entry *entries;
+	u_int num_entries;
+};
 
 static int
 extract_salt(const char *s, u_int l, char *salt, size_t salt_len)
@@ -161,26 +167,28 @@ hostfile_read_key(char **cpp, u_int *bitsp, Key *ret)
 
 	/* Return results. */
 	*cpp = cp;
-	*bitsp = key_size(ret);
+	if (bitsp != NULL)
+		*bitsp = key_size(ret);
 	return 1;
 }
 
 static int
-hostfile_check_key(int bits, const Key *key, const char *host, const char *filename, int linenum)
+hostfile_check_key(int bits, const Key *key, const char *host,
+    const char *filename, u_long linenum)
 {
 	if (key == NULL || key->type != KEY_RSA1 || key->rsa == NULL)
 		return 1;
 	if (bits != BN_num_bits(key->rsa->n)) {
-		logit("Warning: %s, line %d: keysize mismatch for host %s: "
+		logit("Warning: %s, line %lu: keysize mismatch for host %s: "
 		    "actual %d vs. announced %d.",
 		    filename, linenum, host, BN_num_bits(key->rsa->n), bits);
-		logit("Warning: replace %d with %d in %s, line %d.",
+		logit("Warning: replace %d with %d in %s, line %lu.",
 		    bits, BN_num_bits(key->rsa->n), filename, linenum);
 	}
 	return 1;
 }
 
-static enum { MRK_ERROR, MRK_NONE, MRK_REVOKE, MRK_CA }
+static HostkeyMarker
 check_markers(char **cpp)
 {
 	char marker[32], *sp, *cp = *cpp;
@@ -215,49 +223,32 @@ check_markers(char **cpp)
 	return ret;
 }
 
-/*
- * Checks whether the given host (which must be in all lowercase) is already
- * in the list of our known hosts. Returns HOST_OK if the host is known and
- * has the specified key, HOST_NEW if the host is not known, and HOST_CHANGED
- * if the host is known but used to have a different host key.
- *
- * If no 'key' has been specified and a key of type 'keytype' is known
- * for the specified host, then HOST_FOUND is returned.
- */
+struct hostkeys *
+init_hostkeys(void)
+{
+	struct hostkeys *ret = xcalloc(1, sizeof(*ret));
 
-static HostStatus
-check_host_in_hostfile_by_key_or_type(const char *filename,
-    const char *host, const Key *key, int keytype, Key *found,
-    int want_revocation, int *numret)
+	ret->entries = NULL;
+	return ret;
+}
+
+void
+load_hostkeys(struct hostkeys *hostkeys, const char *host, const char *path)
 {
 	FILE *f;
 	char line[8192];
-	int want, have, linenum = 0, want_cert = key_is_cert(key);
-	u_int kbits;
+	u_long linenum = 0, num_loaded = 0;
 	char *cp, *cp2, *hashed_host;
-	HostStatus end_return;
-
-	debug3("check_host_in_hostfile: host %s filename %s", host, filename);
-
-	if (want_revocation && (key == NULL || keytype != 0 || found != NULL))
-		fatal("%s: invalid arguments", __func__);
-
-	/* Open the file containing the list of known hosts. */
-	f = fopen(filename, "r");
-	if (!f)
-		return HOST_NEW;
-
-	/*
-	 * Return value when the loop terminates.  This is set to
-	 * HOST_CHANGED if we have seen a different key for the host and have
-	 * not found the proper one.
-	 */
-	end_return = HOST_NEW;
-
-	/* Go through the file. */
-	while (fgets(line, sizeof(line), f)) {
+	HostkeyMarker marker;
+	Key *key;
+	int kbits;
+
+	if ((f = fopen(path, "r")) == NULL)
+		return;
+	debug3("%s: loading entries for host \"%.100s\" from file \"%s\"",
+	    __func__, host, path);
+	while (read_keyfile_line(f, path, line, sizeof(line), &linenum) == 0) {
 		cp = line;
-		linenum++;
 
 		/* Skip any leading whitespace, comments and empty lines. */
 		for (; *cp == ' ' || *cp == '\t'; cp++)
@@ -265,19 +256,11 @@ check_host_in_hostfile_by_key_or_type(const char *filename,
 		if (!*cp || *cp == '#' || *cp == '\n')
 			continue;
 
-		if (want_revocation)
-			want = MRK_REVOKE;
-		else if (want_cert)
-			want = MRK_CA;
-		else
-			want = MRK_NONE;
-
-		if ((have = check_markers(&cp)) == MRK_ERROR) {
-			verbose("%s: invalid marker at %s:%d",
-			    __func__, filename, linenum);
-			continue;
-		} else if (want != have)
+		if ((marker = check_markers(&cp)) == MRK_ERROR) {
+			verbose("%s: invalid marker at %s:%lu",
+			    __func__, path, linenum);
 			continue;
+		}
 
 		/* Find the end of the host name portion. */
 		for (cp2 = cp; *cp2 && *cp2 != ' ' && *cp2 != '\t'; cp2++)
@@ -289,8 +272,8 @@ check_host_in_hostfile_by_key_or_type(const char *filename,
 				continue;
 			hashed_host = host_hash(host, cp, (u_int) (cp2 - cp));
 			if (hashed_host == NULL) {
-				debug("Invalid hashed host line %d of %s",
-				    linenum, filename);
+				debug("Invalid hashed host line %lu of %s",
+				    linenum, path);
 				continue;
 			}
 			if (strncmp(hashed_host, cp, (u_int) (cp2 - cp)) != 0)
@@ -300,98 +283,166 @@ check_host_in_hostfile_by_key_or_type(const char *filename,
 		/* Got a match.  Skip host name. */
 		cp = cp2;
 
-		if (want_revocation)
-			found = key_new(KEY_UNSPEC);
-
 		/*
 		 * Extract the key from the line.  This will skip any leading
 		 * whitespace.  Ignore badly formatted lines.
 		 */
-		if (!hostfile_read_key(&cp, &kbits, found))
+		key = key_new(KEY_UNSPEC);
+		if (!hostfile_read_key(&cp, &kbits, key)) {
+			key_free(key);
+			key = key_new(KEY_RSA1);
+			if (!hostfile_read_key(&cp, &kbits, key)) {
+				key_free(key);
+				continue;
+			}
+		}
+		if (!hostfile_check_key(kbits, key, host, path, linenum))
 			continue;
 
-		if (numret != NULL)
-			*numret = linenum;
+		debug3("%s: found %skey type %s in file %s:%lu", __func__,
+		    marker == MRK_NONE ? "" :
+		    (marker == MRK_CA ? "ca " : "revoked "),
+		    key_type(key), path, linenum);
+		hostkeys->entries = xrealloc(hostkeys->entries,
+		    hostkeys->num_entries + 1, sizeof(*hostkeys->entries));
+		hostkeys->entries[hostkeys->num_entries].host = xstrdup(host);
+		hostkeys->entries[hostkeys->num_entries].file = xstrdup(path);
+		hostkeys->entries[hostkeys->num_entries].line = linenum;
+		hostkeys->entries[hostkeys->num_entries].key = key;
+		hostkeys->entries[hostkeys->num_entries].marker = marker;
+		hostkeys->num_entries++;
+		num_loaded++;
+	}
+	debug3("%s: loaded %lu keys", __func__, num_loaded);
+	return;
+}	
 
-		if (key == NULL) {
-			/* we found a key of the requested type */
-			if (found->type == keytype) {
-				fclose(f);
-				return HOST_FOUND;
-			}
-			continue;
-		}
+void
+free_hostkeys(struct hostkeys *hostkeys)
+{
+	u_int i;
+
+	for (i = 0; i < hostkeys->num_entries; i++) {
+		xfree(hostkeys->entries[i].host);
+		xfree(hostkeys->entries[i].file);
+		key_free(hostkeys->entries[i].key);
+		bzero(hostkeys->entries + i, sizeof(*hostkeys->entries));
+	}
+	if (hostkeys->entries != NULL)
+		xfree(hostkeys->entries);
+	hostkeys->entries = NULL;
+	hostkeys->num_entries = 0;
+	xfree(hostkeys);
+}
 
-		if (!hostfile_check_key(kbits, found, host, filename, linenum))
+static int
+check_key_not_revoked(struct hostkeys *hostkeys, Key *k)
+{
+	int is_cert = key_is_cert(k);
+	u_int i;
+
+	for (i = 0; i < hostkeys->num_entries; i++) {
+		if (hostkeys->entries[i].marker != MRK_REVOKE)
 			continue;
+		if (key_equal_public(k, hostkeys->entries[i].key))
+			return -1;
+		if (is_cert &&
+		    key_equal_public(k->cert->signature_key,
+		    hostkeys->entries[i].key))
+			return -1;
+	}
+	return 0;
+}
 
-		if (want_revocation) {
-			if (key_is_cert(key) &&
-			    key_equal_public(key->cert->signature_key, found)) {
-				verbose("check_host_in_hostfile: revoked CA "
-				    "line %d", linenum);
-				key_free(found);
-				return HOST_REVOKED;
-			}
-			if (key_equal_public(key, found)) {
-				verbose("check_host_in_hostfile: revoked key "
-				    "line %d", linenum);
-				key_free(found);
-				return HOST_REVOKED;
-			}
-			key_free(found);
+/*
+ * Match keys against a specified key, or look one up by key type.
+ *
+ * If looking for a keytype (key == NULL) and one is found then return
+ * HOST_FOUND, otherwise HOST_NEW.
+ *
+ * If looking for a key (key != NULL):
+ *  1. If the key is a cert and a matching CA is found, return HOST_OK
+ *  2. If the key is not a cert and a matching key is found, return HOST_OK
+ *  3. If no key matches but a key with a different type is found, then
+ *     return HOST_CHANGED
+ *  4. If no matching keys are found, then return HOST_NEW.
+ *
+ * Finally, check any found key is not revoked.
+ */
+static HostStatus
+check_hostkeys_by_key_or_type(struct hostkeys *hostkeys,
+    Key *k, int keytype, const struct hostkey_entry **found)
+{
+	u_int i;
+	HostStatus end_return = HOST_NEW;
+	int want_cert = key_is_cert(k);
+	HostkeyMarker want_marker = want_cert ? MRK_CA : MRK_NONE;
+	int proto = (k ? k->type : keytype) == KEY_RSA1 ? 1 : 2;
+
+	if (found != NULL)
+		*found = NULL;
+
+	for (i = 0; i < hostkeys->num_entries; i++) {
+		if (proto == 1 && hostkeys->entries[i].key->type != KEY_RSA1)
+			continue;
+		if (proto == 2 && hostkeys->entries[i].key->type == KEY_RSA1)
 			continue;
+		if (hostkeys->entries[i].marker != want_marker)
+			continue;
+		if (k == NULL) {
+			if (hostkeys->entries[i].key->type != keytype)
+				continue;
+			end_return = HOST_FOUND;
+			if (found != NULL)
+				*found = hostkeys->entries + i;
+			k = hostkeys->entries[i].key;
+			break;
 		}
-
-		/* Check if the current key is the same as the given key. */
-		if (want_cert && key_equal(key->cert->signature_key, found)) {
-			/* Found CA cert for key */
-			debug3("check_host_in_hostfile: CA match line %d",
-			    linenum);
-			fclose(f);
-			return HOST_OK;
-		} else if (!want_cert && key_equal(key, found)) {
-			/* Found identical key */
-			debug3("check_host_in_hostfile: match line %d", linenum);
-			fclose(f);
-			return HOST_OK;
+		if (want_cert) {
+			if (key_equal_public(k->cert->signature_key,
+			    hostkeys->entries[i].key)) {
+				/* A matching CA exists */
+				end_return = HOST_OK;
+				if (found != NULL)
+					*found = hostkeys->entries + i;
+				break;
+			}
+		} else {
+			if (key_equal(k, hostkeys->entries[i].key)) {
+				end_return = HOST_OK;
+				if (found != NULL)
+					*found = hostkeys->entries + i;
+				break;
+			}
+			/* A non-maching key exists */
+			end_return = HOST_CHANGED;
+			if (found != NULL)
+				*found = hostkeys->entries + i;
 		}
-		/*
-		 * They do not match.  We will continue to go through the
-		 * file; however, we note that we will not return that it is
-		 * new.
-		 */
-		end_return = HOST_CHANGED;
 	}
-	/* Clear variables and close the file. */
-	fclose(f);
-
-	/*
-	 * Return either HOST_NEW or HOST_CHANGED, depending on whether we
-	 * saw a different key for the host.
-	 */
+	if (check_key_not_revoked(hostkeys, k) != 0) {
+		end_return = HOST_REVOKED;
+		if (found != NULL)
+			*found = NULL;
+	}
 	return end_return;
 }
-
+	
 HostStatus
-check_host_in_hostfile(const char *filename, const char *host, const Key *key,
-    Key *found, int *numret)
+check_key_in_hostkeys(struct hostkeys *hostkeys, Key *key,
+    const struct hostkey_entry **found)
 {
 	if (key == NULL)
 		fatal("no key to look up");
-	if (check_host_in_hostfile_by_key_or_type(filename, host,
-	    key, 0, NULL, 1, NULL) == HOST_REVOKED)
-		return HOST_REVOKED;
-	return check_host_in_hostfile_by_key_or_type(filename, host, key, 0,
-	    found, 0, numret);
+	return check_hostkeys_by_key_or_type(hostkeys, key, 0, found);
 }
 
 int
-lookup_key_in_hostfile_by_type(const char *filename, const char *host,
-    int keytype, Key *found, int *numret)
+lookup_key_in_hostkeys_by_type(struct hostkeys *hostkeys, int keytype,
+    const struct hostkey_entry **found)
 {
-	return (check_host_in_hostfile_by_key_or_type(filename, host, NULL,
-	    keytype, found, 0, numret) == HOST_FOUND);
+	return (check_hostkeys_by_key_or_type(hostkeys, NULL, keytype,
+	    found) == HOST_FOUND);
 }
 
 /*
diff --git a/usr.bin/ssh/hostfile.h b/usr.bin/ssh/hostfile.h
index 1d460c1a915..d84d422ff6e 100644
--- a/usr.bin/ssh/hostfile.h
+++ b/usr.bin/ssh/hostfile.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: hostfile.h,v 1.18 2010/03/04 10:36:03 djm Exp $ */
+/* $OpenBSD: hostfile.h,v 1.19 2010/11/29 23:45:51 djm Exp $ */
 
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
@@ -18,12 +18,30 @@ typedef enum {
 	HOST_OK, HOST_NEW, HOST_CHANGED, HOST_REVOKED, HOST_FOUND
 }       HostStatus;
 
+typedef enum {
+	MRK_ERROR, MRK_NONE, MRK_REVOKE, MRK_CA
+}	HostkeyMarker;
+
+struct hostkey_entry {
+	char *host;
+	char *file;
+	u_long line;
+	Key *key;
+	HostkeyMarker marker;
+};
+struct hostkeys;
+
+struct hostkeys *init_hostkeys(void);
+void	 load_hostkeys(struct hostkeys *, const char *, const char *);
+void	 free_hostkeys(struct hostkeys *);
+
+HostStatus check_key_in_hostkeys(struct hostkeys *, Key *,
+    const struct hostkey_entry **);
+int	 lookup_key_in_hostkeys_by_type(struct hostkeys *, int,
+    const struct hostkey_entry **);
+
 int	 hostfile_read_key(char **, u_int *, Key *);
-HostStatus check_host_in_hostfile(const char *, const char *,
-	    const Key *, Key *, int *);
-int	add_host_to_hostfile(const char *, const char *, const Key *, int);
-int	lookup_key_in_hostfile_by_type(const char *, const char *,
-	    int, Key *, int *);
+int	 add_host_to_hostfile(const char *, const char *, const Key *, int);
 
 #define HASH_MAGIC	"|1|"
 #define HASH_DELIM	'|'
diff --git a/usr.bin/ssh/ssh.c b/usr.bin/ssh/ssh.c
index 244ed4b5fe9..70f341da99c 100644
--- a/usr.bin/ssh/ssh.c
+++ b/usr.bin/ssh/ssh.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh.c,v 1.354 2010/11/13 23:27:50 djm Exp $ */
+/* $OpenBSD: ssh.c,v 1.355 2010/11/29 23:45:51 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -842,7 +842,7 @@ main(int ac, char **av)
 
 	/* Log into the remote system.  Never returns if the login fails. */
 	ssh_login(&sensitive_data, host, (struct sockaddr *)&hostaddr,
-	    pw, timeout_ms);
+	    options.port, pw, timeout_ms);
 
 	if (packet_connection_is_on_socket()) {
 		verbose("Authenticated to %s ([%s]:%d).", host,
diff --git a/usr.bin/ssh/ssh_config.5 b/usr.bin/ssh/ssh_config.5
index a51a37dded6..5c6673de36c 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.144 2010/11/15 07:40:14 jmc Exp $
-.Dd $Mdocdate: November 15 2010 $
+.\" $OpenBSD: ssh_config.5,v 1.145 2010/11/29 23:45:51 djm Exp $
+.Dd $Mdocdate: November 29 2010 $
 .Dt SSH_CONFIG 5
 .Os
 .Sh NAME
@@ -555,6 +555,9 @@ ssh-rsa-cert-v00@openssh.com,ssh-dss-cert-v00@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
 ssh-rsa,ssh-dss
 .Ed
+.Pp
+If hostkeys are known for the destination host then this default is modified
+to prefer their algorithms.
 .It Cm HostKeyAlias
 Specifies an alias that should be used instead of the
 real host name when looking up or saving the host key
diff --git a/usr.bin/ssh/sshconnect.c b/usr.bin/ssh/sshconnect.c
index c9dcbcf6f5a..d872e7d3c95 100644
--- a/usr.bin/ssh/sshconnect.c
+++ b/usr.bin/ssh/sshconnect.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect.c,v 1.228 2010/10/06 21:10:21 djm Exp $ */
+/* $OpenBSD: sshconnect.c,v 1.229 2010/11/29 23:45:51 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -65,7 +65,7 @@ extern char *__progname;
 extern uid_t original_real_uid;
 extern uid_t original_effective_uid;
 
-static int show_other_keys(const char *, Key *);
+static int show_other_keys(struct hostkeys *, Key *);
 static void warn_changed_key(Key *);
 
 /*
@@ -597,6 +597,63 @@ check_host_cert(const char *host, const Key *host_key)
 	return 1;
 }
 
+static int
+sockaddr_is_local(struct sockaddr *hostaddr)
+{
+	switch (hostaddr->sa_family) {
+	case AF_INET:
+		return (ntohl(((struct sockaddr_in *)hostaddr)->
+		    sin_addr.s_addr) >> 24) == IN_LOOPBACKNET;
+	case AF_INET6:
+		return IN6_IS_ADDR_LOOPBACK(
+		    &(((struct sockaddr_in6 *)hostaddr)->sin6_addr));
+	default:
+		return 0;
+	}
+}
+
+/*
+ * Prepare the hostname and ip address strings that are used to lookup
+ * host keys in known_hosts files. These may have a port number appended.
+ */
+void
+get_hostfile_hostname_ipaddr(char *hostname, struct sockaddr *hostaddr,
+    u_short port, char **hostfile_hostname, char **hostfile_ipaddr)
+{
+	char ntop[NI_MAXHOST];
+
+	/*
+	 * We don't have the remote ip-address for connections
+	 * using a proxy command
+	 */
+	if (hostfile_ipaddr != NULL) {
+		if (options.proxy_command == NULL) {
+			if (getnameinfo(hostaddr, hostaddr->sa_len,
+			    ntop, sizeof(ntop), NULL, 0, NI_NUMERICHOST) != 0)
+			fatal("check_host_key: getnameinfo failed");
+			*hostfile_ipaddr = put_host_port(ntop, port);
+		} else {
+			*hostfile_ipaddr = xstrdup("<no hostip for proxy "
+			    "command>");
+		}
+	}
+
+	/*
+	 * Allow the user to record the key under a different name or
+	 * differentiate a non-standard port.  This is useful for ssh
+	 * tunneling over forwarded connections or if you run multiple
+	 * sshd's on different ports on the same machine.
+	 */
+	if (hostfile_hostname != NULL) {
+		if (options.host_key_alias != NULL) {
+			*hostfile_hostname = xstrdup(options.host_key_alias);
+			debug("using hostkeyalias: %s", *hostfile_hostname);
+		} else {
+			*hostfile_hostname = put_host_port(hostname, port);
+		}
+	}
+}
+
 /*
  * check whether the supplied host key is valid, return -1 if the key
  * is not valid. the user_hostfile will not be updated if 'readonly' is true.
@@ -606,20 +663,21 @@ check_host_cert(const char *host, const Key *host_key)
 #define ROQUIET	2
 static int
 check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
-    Key *host_key, int readonly, const char *user_hostfile,
-    const char *system_hostfile)
+    Key *host_key, int readonly, char *user_hostfile,
+    char *system_hostfile)
 {
-	Key *file_key, *raw_key = NULL;
+	Key *raw_key = NULL;
 	const char *type;
 	char *ip = NULL, *host = NULL;
 	char hostline[1000], *hostp, *fp, *ra;
 	HostStatus host_status;
 	HostStatus ip_status;
-	int r, want_cert, local = 0, host_ip_differ = 0;
-	char ntop[NI_MAXHOST];
+	int r, want_cert = key_is_cert(host_key), host_ip_differ = 0;
+	int local = sockaddr_is_local(hostaddr);
 	char msg[1024];
-	int len, host_line, ip_line, cancelled_forwarding = 0;
-	const char *host_file = NULL, *ip_file = NULL;
+	int len, cancelled_forwarding = 0;
+	struct hostkeys *host_hostkeys, *ip_hostkeys;
+	const struct hostkey_entry *host_found, *ip_found;
 
 	/*
 	 * Force accepting of the host key for loopback/localhost. The
@@ -629,20 +687,6 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 	 * essentially disables host authentication for localhost; however,
 	 * this is probably not a real problem.
 	 */
-	/**  hostaddr == 0! */
-	switch (hostaddr->sa_family) {
-	case AF_INET:
-		local = (ntohl(((struct sockaddr_in *)hostaddr)->
-		    sin_addr.s_addr) >> 24) == IN_LOOPBACKNET;
-		break;
-	case AF_INET6:
-		local = IN6_IS_ADDR_LOOPBACK(
-		    &(((struct sockaddr_in6 *)hostaddr)->sin6_addr));
-		break;
-	default:
-		local = 0;
-		break;
-	}
 	if (options.no_host_authentication_for_localhost == 1 && local &&
 	    options.host_key_alias == NULL) {
 		debug("Forcing accepting of host key for "
@@ -651,17 +695,10 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 	}
 
 	/*
-	 * We don't have the remote ip-address for connections
-	 * using a proxy command
+	 * Prepare the hostname and address strings used for hostkey lookup.
+	 * In some cases, these will have a port number appended.
 	 */
-	if (options.proxy_command == NULL) {
-		if (getnameinfo(hostaddr, hostaddr->sa_len, ntop, sizeof(ntop),
-		    NULL, 0, NI_NUMERICHOST) != 0)
-			fatal("check_host_key: getnameinfo failed");
-		ip = put_host_port(ntop, port);
-	} else {
-		ip = xstrdup("<no hostip for proxy command>");
-	}
+	get_hostfile_hostname_ipaddr(hostname, hostaddr, port, &host, &ip);
 
 	/*
 	 * Turn off check_host_ip if the connection is to localhost, via proxy
@@ -671,74 +708,52 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 	    strcmp(hostname, ip) == 0 || options.proxy_command != NULL))
 		options.check_host_ip = 0;
 
-	/*
-	 * Allow the user to record the key under a different name or
-	 * differentiate a non-standard port.  This is useful for ssh
-	 * tunneling over forwarded connections or if you run multiple
-	 * sshd's on different ports on the same machine.
-	 */
-	if (options.host_key_alias != NULL) {
-		host = xstrdup(options.host_key_alias);
-		debug("using hostkeyalias: %s", host);
-	} else {
-		host = put_host_port(hostname, port);
+	host_hostkeys = init_hostkeys();
+	load_hostkeys(host_hostkeys, host, user_hostfile);
+	load_hostkeys(host_hostkeys, host, system_hostfile);
+
+	ip_hostkeys = NULL;
+	if (!want_cert && options.check_host_ip) {
+		ip_hostkeys = init_hostkeys();
+		load_hostkeys(ip_hostkeys, ip, user_hostfile);
+		load_hostkeys(ip_hostkeys, ip, system_hostfile);
 	}
 
  retry:
+	/* Reload these as they may have changed on cert->key downgrade */
 	want_cert = key_is_cert(host_key);
 	type = key_type(host_key);
 
 	/*
-	 * Store the host key from the known host file in here so that we can
-	 * compare it with the key for the IP address.
-	 */
-	file_key = key_new(key_is_cert(host_key) ? KEY_UNSPEC : host_key->type);
-
-	/*
 	 * Check if the host key is present in the user's list of known
 	 * hosts or in the systemwide list.
 	 */
-	host_file = user_hostfile;
-	host_status = check_host_in_hostfile(host_file, host, host_key,
-	    file_key, &host_line);
-	if (host_status == HOST_NEW) {
-		host_file = system_hostfile;
-		host_status = check_host_in_hostfile(host_file, host, host_key,
-		    file_key, &host_line);
-	}
+	host_status = check_key_in_hostkeys(host_hostkeys, host_key,
+	    &host_found);
+
 	/*
 	 * Also perform check for the ip address, skip the check if we are
 	 * localhost, looking for a certificate, or the hostname was an ip
 	 * address to begin with.
 	 */
-	if (!want_cert && options.check_host_ip) {
-		Key *ip_key = key_new(host_key->type);
-
-		ip_file = user_hostfile;
-		ip_status = check_host_in_hostfile(ip_file, ip, host_key,
-		    ip_key, &ip_line);
-		if (ip_status == HOST_NEW) {
-			ip_file = system_hostfile;
-			ip_status = check_host_in_hostfile(ip_file, ip,
-			    host_key, ip_key, &ip_line);
-		}
+	if (!want_cert && ip_hostkeys != NULL) {
+		ip_status = check_key_in_hostkeys(ip_hostkeys, host_key,
+		    &ip_found);
 		if (host_status == HOST_CHANGED &&
-		    (ip_status != HOST_CHANGED || !key_equal(ip_key, file_key)))
+		    (ip_status != HOST_CHANGED || 
+		    (ip_found != NULL &&
+		    !key_equal(ip_found->key, host_found->key))))
 			host_ip_differ = 1;
-
-		key_free(ip_key);
 	} else
 		ip_status = host_status;
 
-	key_free(file_key);
-
 	switch (host_status) {
 	case HOST_OK:
 		/* The host is known and the key matches. */
 		debug("Host '%.200s' is known and matches the %s host %s.",
 		    host, type, want_cert ? "certificate" : "key");
-		debug("Found %s in %s:%d",
-		    want_cert ? "CA key" : "key", host_file, host_line);
+		debug("Found %s in %s:%lu", want_cert ? "CA key" : "key",
+		    host_found->file, host_found->line);
 		if (want_cert && !check_host_cert(hostname, host_key))
 			goto fail;
 		if (options.check_host_ip && ip_status == HOST_NEW) {
@@ -789,7 +804,7 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 		} else if (options.strict_host_key_checking == 2) {
 			char msg1[1024], msg2[1024];
 
-			if (show_other_keys(host, host_key))
+			if (show_other_keys(host_hostkeys, host_key))
 				snprintf(msg1, sizeof(msg1),
 				    "\nbut keys of different type are already"
 				    " known for this host.");
@@ -830,8 +845,7 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 		 * local known_hosts file.
 		 */
 		if (options.check_host_ip && ip_status == HOST_NEW) {
-			snprintf(hostline, sizeof(hostline), "%s,%s",
-			    host, ip);
+			snprintf(hostline, sizeof(hostline), "%s,%s", host, ip);
 			hostp = hostline;
 			if (options.hash_known_hosts) {
 				/* Add hash of host and IP separately */
@@ -885,8 +899,8 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 			 * all hosts that one might visit.
 			 */
 			debug("Host certificate authority does not "
-			    "match %s in %s:%d", CA_MARKER,
-			    host_file, host_line);
+			    "match %s in %s:%lu", CA_MARKER,
+			    host_found->file, host_found->line);
 			goto fail;
 		}
 		if (readonly == ROQUIET)
@@ -908,13 +922,15 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 			error("DNS SPOOFING is happening or the IP address for the host");
 			error("and its host key have changed at the same time.");
 			if (ip_status != HOST_NEW)
-				error("Offending key for IP in %s:%d", ip_file, ip_line);
+				error("Offending key for IP in %s:%lu",
+				    ip_found->file, ip_found->line);
 		}
 		/* The host key has changed. */
 		warn_changed_key(host_key);
 		error("Add correct host key in %.100s to get rid of this message.",
 		    user_hostfile);
-		error("Offending key in %s:%d", host_file, host_line);
+		error("Offending %s key in %s:%lu", key_type(host_found->key),
+		    host_found->file, host_found->line);
 
 		/*
 		 * If strict host key checking is in use, the user will have
@@ -999,13 +1015,13 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 		snprintf(msg, sizeof(msg),
 		    "Warning: the %s host key for '%.200s' "
 		    "differs from the key for the IP address '%.128s'"
-		    "\nOffending key for IP in %s:%d",
-		    type, host, ip, ip_file, ip_line);
+		    "\nOffending key for IP in %s:%lu",
+		    type, host, ip, ip_found->file, ip_found->line);
 		if (host_status == HOST_OK) {
 			len = strlen(msg);
 			snprintf(msg + len, sizeof(msg) - len,
-			    "\nMatching host key in %s:%d",
-			    host_file, host_line);
+			    "\nMatching host key in %s:%lu",
+			    host_found->file, host_found->line);
 		}
 		if (options.strict_host_key_checking == 1) {
 			logit("%s", msg);
@@ -1023,6 +1039,10 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 
 	xfree(ip);
 	xfree(host);
+	if (host_hostkeys != NULL)
+		free_hostkeys(host_hostkeys);
+	if (ip_hostkeys != NULL)
+		free_hostkeys(ip_hostkeys);
 	return 0;
 
 fail:
@@ -1042,6 +1062,10 @@ fail:
 		key_free(raw_key);
 	xfree(ip);
 	xfree(host);
+	if (host_hostkeys != NULL)
+		free_hostkeys(host_hostkeys);
+	if (ip_hostkeys != NULL)
+		free_hostkeys(ip_hostkeys);
 	return -1;
 }
 
@@ -1051,6 +1075,11 @@ verify_host_key(char *host, struct sockaddr *hostaddr, Key *host_key)
 {
 	struct stat st;
 	int flags = 0;
+	char *fp;
+
+	fp = key_fingerprint(host_key, SSH_FP_MD5, SSH_FP_HEX);
+	debug("Server host key: %s %s", key_type(host_key), fp);
+	xfree(fp);
 
 	/* XXX certs are not yet supported for DNS */
 	if (!key_is_cert(host_key) && options.verify_host_key_dns &&
@@ -1094,7 +1123,7 @@ verify_host_key(char *host, struct sockaddr *hostaddr, Key *host_key)
  */
 void
 ssh_login(Sensitive *sensitive, const char *orighost,
-    struct sockaddr *hostaddr, struct passwd *pw, int timeout_ms)
+    struct sockaddr *hostaddr, u_short port, struct passwd *pw, int timeout_ms)
 {
 	char *host, *cp;
 	char *server_user, *local_user;
@@ -1117,7 +1146,7 @@ ssh_login(Sensitive *sensitive, const char *orighost,
 	/* key exchange */
 	/* authenticate user */
 	if (compat20) {
-		ssh_kex2(host, hostaddr);
+		ssh_kex2(host, hostaddr, port);
 		ssh_userauth2(local_user, server_user, host, sensitive);
 	} else {
 		ssh_kex(host, hostaddr);
@@ -1144,61 +1173,35 @@ ssh_put_password(char *password)
 	xfree(padded);
 }
 
-static int
-show_key_from_file(const char *file, const char *host, int keytype)
-{
-	Key *found;
-	char *fp, *ra;
-	int line, ret;
-
-	found = key_new(keytype);
-	if ((ret = lookup_key_in_hostfile_by_type(file, host,
-	    keytype, found, &line))) {
-		fp = key_fingerprint(found, SSH_FP_MD5, SSH_FP_HEX);
-		ra = key_fingerprint(found, SSH_FP_MD5, SSH_FP_RANDOMART);
-		logit("WARNING: %s key found for host %s\n"
-		    "in %s:%d\n"
-		    "%s key fingerprint %s.\n%s\n",
-		    key_type(found), host, file, line,
-		    key_type(found), fp, ra);
-		xfree(ra);
-		xfree(fp);
-	}
-	key_free(found);
-	return (ret);
-}
-
 /* print all known host keys for a given host, but skip keys of given type */
 static int
-show_other_keys(const char *host, Key *key)
+show_other_keys(struct hostkeys *hostkeys, Key *key)
 {
 	int type[] = { KEY_RSA1, KEY_RSA, KEY_DSA, KEY_ECDSA, -1};
-	int i, found = 0;
+	int i, ret = 0;
+	char *fp, *ra;
+	const struct hostkey_entry *found;
 
 	for (i = 0; type[i] != -1; i++) {
 		if (type[i] == key->type)
 			continue;
-		if (type[i] != KEY_RSA1 &&
-		    show_key_from_file(options.user_hostfile2, host, type[i])) {
-			found = 1;
-			continue;
-		}
-		if (type[i] != KEY_RSA1 &&
-		    show_key_from_file(options.system_hostfile2, host, type[i])) {
-			found = 1;
-			continue;
-		}
-		if (show_key_from_file(options.user_hostfile, host, type[i])) {
-			found = 1;
-			continue;
-		}
-		if (show_key_from_file(options.system_hostfile, host, type[i])) {
-			found = 1;
+		if (!lookup_key_in_hostkeys_by_type(hostkeys, type[i], &found))
 			continue;
-		}
-		debug2("no key of type %d for host %s", type[i], host);
+		fp = key_fingerprint(found->key, SSH_FP_MD5, SSH_FP_HEX);
+		ra = key_fingerprint(found->key, SSH_FP_MD5, SSH_FP_RANDOMART);
+		logit("WARNING: %s key found for host %s\n"
+		    "in %s:%lu\n"
+		    "%s key fingerprint %s.",
+		    key_type(found->key),
+		    found->host, found->file, found->line,
+		    key_type(found->key), fp);
+		if (options.visual_host_key)
+			logit("%s", ra);
+		xfree(ra);
+		xfree(fp);
+		ret = 1;
 	}
-	return (found);
+	return ret;
 }
 
 static void
diff --git a/usr.bin/ssh/sshconnect.h b/usr.bin/ssh/sshconnect.h
index 69163afbc86..fd7f7f7c614 100644
--- a/usr.bin/ssh/sshconnect.h
+++ b/usr.bin/ssh/sshconnect.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect.h,v 1.26 2010/10/06 06:39:28 djm Exp $ */
+/* $OpenBSD: sshconnect.h,v 1.27 2010/11/29 23:45:51 djm Exp $ */
 
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
@@ -36,15 +36,18 @@ ssh_connect(const char *, struct sockaddr_storage *, u_short, int, int,
     int *, int, int, const char *);
 void	 ssh_kill_proxy_command(void);
 
-void
-ssh_login(Sensitive *, const char *, struct sockaddr *, struct passwd *, int);
+void	 ssh_login(Sensitive *, const char *, struct sockaddr *, u_short,
+    struct passwd *, int);
 
 void	 ssh_exchange_identification(int);
 
 int	 verify_host_key(char *, struct sockaddr *, Key *);
 
+void	 get_hostfile_hostname_ipaddr(char *, struct sockaddr *, u_short,
+    char **, char **);
+
 void	 ssh_kex(char *, struct sockaddr *);
-void	 ssh_kex2(char *, struct sockaddr *);
+void	 ssh_kex2(char *, struct sockaddr *, u_short);
 
 void	 ssh_userauth1(const char *, const char *, char *, Sensitive *);
 void	 ssh_userauth2(const char *, const char *, char *, Sensitive *);
diff --git a/usr.bin/ssh/sshconnect2.c b/usr.bin/ssh/sshconnect2.c
index 8b7db3a17c6..c88a8ddd48c 100644
--- a/usr.bin/ssh/sshconnect2.c
+++ b/usr.bin/ssh/sshconnect2.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect2.c,v 1.185 2010/09/22 05:01:29 djm Exp $ */
+/* $OpenBSD: sshconnect2.c,v 1.186 2010/11/29 23:45:51 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  * Copyright (c) 2008 Damien Miller.  All rights reserved.
@@ -63,6 +63,7 @@
 #include "msg.h"
 #include "pathnames.h"
 #include "uidswap.h"
+#include "hostfile.h"
 #include "schnorr.h"
 #include "jpake.h"
 
@@ -95,8 +96,60 @@ verify_host_key_callback(Key *hostkey)
 	return 0;
 }
 
+static char *
+order_hostkeyalgs(char *host, struct sockaddr *hostaddr, u_short port)
+{
+	char *oavail, *avail, *first, *last, *alg, *hostname, *ret;
+	size_t maxlen;
+	struct hostkeys *hostkeys;
+	int ktype;
+
+	/* Find all hostkeys for this hostname */
+	get_hostfile_hostname_ipaddr(host, hostaddr, port, &hostname, NULL);
+	hostkeys = init_hostkeys();
+	load_hostkeys(hostkeys, hostname, options.user_hostfile2);
+	load_hostkeys(hostkeys, hostname, options.system_hostfile2);
+	load_hostkeys(hostkeys, hostname, options.user_hostfile);
+	load_hostkeys(hostkeys, hostname, options.system_hostfile);
+
+	oavail = avail = xstrdup(KEX_DEFAULT_PK_ALG);
+	maxlen = strlen(avail) + 1;
+	first = xmalloc(maxlen);
+	last = xmalloc(maxlen);
+	*first = *last = '\0';
+
+#define ALG_APPEND(to, from) \
+	do { \
+		if (*to != '\0') \
+			strlcat(to, ",", maxlen); \
+		strlcat(to, from, maxlen); \
+	} while (0)
+
+	while ((alg = strsep(&avail, ",")) && *alg != '\0') {
+		if ((ktype = key_type_from_name(alg)) == KEY_UNSPEC)
+			fatal("%s: unknown alg %s", __func__, alg);
+		if (lookup_key_in_hostkeys_by_type(hostkeys,
+		    key_type_plain(ktype), NULL))
+			ALG_APPEND(first, alg);
+		else
+			ALG_APPEND(last, alg);
+	}
+#undef ALG_APPEND
+	xasprintf(&ret, "%s%s%s", first, *first == '\0' ? "" : ",", last);
+	if (*first != '\0')
+		debug3("%s: prefer hostkeyalgs: %s", __func__, first);
+
+	xfree(first);
+	xfree(last);
+	xfree(hostname);
+	xfree(oavail);
+	free_hostkeys(hostkeys);
+
+	return ret;
+}
+
 void
-ssh_kex2(char *host, struct sockaddr *hostaddr)
+ssh_kex2(char *host, struct sockaddr *hostaddr, u_short port)
 {
 	Kex *kex;
 
@@ -129,6 +182,11 @@ ssh_kex2(char *host, struct sockaddr *hostaddr)
 	if (options.hostkeyalgorithms != NULL)
 		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] =
 		    options.hostkeyalgorithms;
+	else {
+		/* Prefer algorithms that we already have keys for */
+		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] =
+		    order_hostkeyalgs(host, hostaddr, port);
+	}
 	if (options.kex_algorithms != NULL)
 		myproposal[PROPOSAL_KEX_ALGS] = options.kex_algorithms;