Improve strictness and control over RSA-SHA2 signature types:

In ssh, when an agent fails to return a RSA-SHA2 signature when
requested and falls back to RSA-SHA1 instead, retry the signature to
ensure that the public key algorithm sent in the SSH_MSG_USERAUTH
matches the one in the signature itself.

In sshd, strictly enforce that the public key algorithm sent in the
SSH_MSG_USERAUTH message matches what appears in the signature.

Make the sshd_config PubkeyAcceptedKeyTypes and
HostbasedAcceptedKeyTypes options control accepted signature algorithms
(previously they selected supported key types). This allows these
options to ban RSA-SHA1 in favour of RSA-SHA2.

Add new signature algorithms "rsa-sha2-256-cert-v01@openssh.com" and
"rsa-sha2-512-cert-v01@openssh.com" to force use of RSA-SHA2 signatures
with certificate keys.

feedback and ok markus@

18 files changed, 461 insertions, 256 deletions

diff --git a/usr.bin/ssh/PROTOCOL.certkeys b/usr.bin/ssh/PROTOCOL.certkeys
index 65f11f5384e..11363fdc370 100644
--- a/usr.bin/ssh/PROTOCOL.certkeys
+++ b/usr.bin/ssh/PROTOCOL.certkeys
@@ -25,6 +25,10 @@ raw user keys. The ssh client will support automatic verification of
 acceptance of certified host keys, by adding a similar ability to
 specify CA keys in ~/.ssh/known_hosts.
 
+All certificate types include certification information along with the
+public key that is used to sign challenges. In OpenSSH, ssh-keygen
+performs the CA signing operation.
+
 Certified keys are represented using new key types:
 
     ssh-rsa-cert-v01@openssh.com
@@ -33,9 +37,17 @@ Certified keys are represented using new key types:
     ecdsa-sha2-nistp384-cert-v01@openssh.com
     ecdsa-sha2-nistp521-cert-v01@openssh.com
 
-These include certification information along with the public key
-that is used to sign challenges. ssh-keygen performs the CA signing
-operation.
+Two additional types exist for RSA certificates to force use of
+SHA-2 signatures (SHA-256 and SHA-512 respectively):
+
+    rsa-sha2-256-cert-v01@openssh.com
+    rsa-sha2-512-cert-v01@openssh.com
+
+These RSA/SHA-2 types should not appear in keys at rest or transmitted
+on their wire, but do appear in a SSH_MSG_KEXINIT's host-key algorithms
+field or in the "public key algorithm name" field of a "publickey"
+SSH_USERAUTH_REQUEST to indicate that the signature will use the
+specified algorithm.
 
 Protocol extensions
 -------------------
@@ -291,4 +303,4 @@ permit-user-rc          empty         Flag indicating that execution of
                                       of this script will not be permitted if
                                       this option is not present.
 
-$OpenBSD: PROTOCOL.certkeys,v 1.14 2018/04/10 00:10:49 djm Exp $
+$OpenBSD: PROTOCOL.certkeys,v 1.15 2018/07/03 11:39:54 djm Exp $
diff --git a/usr.bin/ssh/auth2-hostbased.c b/usr.bin/ssh/auth2-hostbased.c
index d6431296781..b843d4ee337 100644
--- a/usr.bin/ssh/auth2-hostbased.c
+++ b/usr.bin/ssh/auth2-hostbased.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth2-hostbased.c,v 1.33 2018/01/23 05:27:21 djm Exp $ */
+/* $OpenBSD: auth2-hostbased.c,v 1.34 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  *
@@ -110,8 +110,7 @@ userauth_hostbased(struct ssh *ssh)
 		    "signature format");
 		goto done;
 	}
-	if (match_pattern_list(sshkey_ssh_name(key),
-	    options.hostbased_key_types, 0) != 1) {
+	if (match_pattern_list(pkalg, options.hostbased_key_types, 0) != 1) {
 		logit("%s: key type %s not in HostbasedAcceptedKeyTypes",
 		    __func__, sshkey_type(key));
 		goto done;
diff --git a/usr.bin/ssh/auth2-pubkey.c b/usr.bin/ssh/auth2-pubkey.c
index 7422ba8b9b8..490cef11407 100644
--- a/usr.bin/ssh/auth2-pubkey.c
+++ b/usr.bin/ssh/auth2-pubkey.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth2-pubkey.c,v 1.79 2018/06/06 18:29:18 markus Exp $ */
+/* $OpenBSD: auth2-pubkey.c,v 1.80 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  *
@@ -106,7 +106,7 @@ userauth_pubkey(struct ssh *ssh)
 	pktype = sshkey_type_from_name(pkalg);
 	if (pktype == KEY_UNSPEC) {
 		/* this is perfectly legal */
-		logit("%s: unsupported public key algorithm: %s",
+		verbose("%s: unsupported public key algorithm: %s",
 		    __func__, pkalg);
 		goto done;
 	}
@@ -133,8 +133,7 @@ userauth_pubkey(struct ssh *ssh)
 		logit("refusing previously-used %s key", sshkey_type(key));
 		goto done;
 	}
-	if (match_pattern_list(sshkey_ssh_name(key),
-	    options.pubkey_key_types, 0) != 1) {
+	if (match_pattern_list(pkalg, options.pubkey_key_types, 0) != 1) {
 		logit("%s: key type %s not in PubkeyAcceptedKeyTypes",
 		    __func__, sshkey_ssh_name(key));
 		goto done;
@@ -185,8 +184,10 @@ userauth_pubkey(struct ssh *ssh)
 		/* test for correct signature */
 		authenticated = 0;
 		if (PRIVSEP(user_key_allowed(ssh, pw, key, 1, &authopts)) &&
-		    PRIVSEP(sshkey_verify(key, sig, slen, sshbuf_ptr(b),
-		    sshbuf_len(b), NULL, ssh->compat)) == 0) {
+		    PRIVSEP(sshkey_verify(key, sig, slen,
+		    sshbuf_ptr(b), sshbuf_len(b),
+		    (ssh->compat & SSH_BUG_SIGTYPE) == 0 ? pkalg : NULL,
+		    ssh->compat)) == 0) {
 			authenticated = 1;
 		}
 		sshbuf_free(b);
diff --git a/usr.bin/ssh/authfd.c b/usr.bin/ssh/authfd.c
index 45fdd78985b..c1a4f0bcd68 100644
--- a/usr.bin/ssh/authfd.c
+++ b/usr.bin/ssh/authfd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: authfd.c,v 1.109 2018/04/10 00:10:49 djm Exp $ */
+/* $OpenBSD: authfd.c,v 1.110 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -341,8 +341,8 @@ ssh_agent_sign(int sock, const struct sshkey *key,
     const u_char *data, size_t datalen, const char *alg, u_int compat)
 {
 	struct sshbuf *msg;
-	u_char *blob = NULL, type;
-	size_t blen = 0, len = 0;
+	u_char *sig = NULL, type = 0;
+	size_t len = 0;
 	u_int flags = 0;
 	int r = SSH_ERR_INTERNAL_ERROR;
 
@@ -353,11 +353,9 @@ ssh_agent_sign(int sock, const struct sshkey *key,
 		return SSH_ERR_INVALID_ARGUMENT;
 	if ((msg = sshbuf_new()) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
-	if ((r = sshkey_to_blob(key, &blob, &blen)) != 0)
-		goto out;
 	flags |= agent_encode_alg(key, alg);
 	if ((r = sshbuf_put_u8(msg, SSH2_AGENTC_SIGN_REQUEST)) != 0 ||
-	    (r = sshbuf_put_string(msg, blob, blen)) != 0 ||
+	    (r = sshkey_puts(key, msg)) != 0 ||
 	    (r = sshbuf_put_string(msg, data, datalen)) != 0 ||
 	    (r = sshbuf_put_u32(msg, flags)) != 0)
 		goto out;
@@ -372,15 +370,19 @@ ssh_agent_sign(int sock, const struct sshkey *key,
 		r = SSH_ERR_INVALID_FORMAT;
 		goto out;
 	}
-	if ((r = sshbuf_get_string(msg, sigp, &len)) != 0)
+	if ((r = sshbuf_get_string(msg, &sig, &len)) != 0)
+		goto out;
+	/* Check what we actually got back from the agent. */
+	if ((r = sshkey_check_sigtype(sig, len, alg)) != 0)
 		goto out;
+	/* success */
+	*sigp = sig;
 	*lenp = len;
+	sig = NULL;
+	len = 0;
 	r = 0;
  out:
-	if (blob != NULL) {
-		explicit_bzero(blob, blen);
-		free(blob);
-	}
+	freezero(sig, len);
 	sshbuf_free(msg);
 	return r;
 }
diff --git a/usr.bin/ssh/compat.c b/usr.bin/ssh/compat.c
index 44970b3cacd..f8d2fb21171 100644
--- a/usr.bin/ssh/compat.c
+++ b/usr.bin/ssh/compat.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: compat.c,v 1.107 2018/04/16 22:50:44 djm Exp $ */
+/* $OpenBSD: compat.c,v 1.108 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 1999, 2000, 2001, 2002 Markus Friedl.  All rights reserved.
  *
@@ -50,16 +50,27 @@ compat_datafellows(const char *version)
 	} check[] = {
 		{ "OpenSSH_2.*,"
 		  "OpenSSH_3.0*,"
-		  "OpenSSH_3.1*",	SSH_BUG_EXTEOF|SSH_OLD_FORWARD_ADDR},
-		{ "OpenSSH_3.*",	SSH_OLD_FORWARD_ADDR },
-		{ "Sun_SSH_1.0*",	SSH_BUG_NOREKEY|SSH_BUG_EXTEOF},
+		  "OpenSSH_3.1*",	SSH_BUG_EXTEOF|SSH_OLD_FORWARD_ADDR|
+					SSH_BUG_SIGTYPE},
+		{ "OpenSSH_3.*",	SSH_OLD_FORWARD_ADDR|SSH_BUG_SIGTYPE },
+		{ "Sun_SSH_1.0*",	SSH_BUG_NOREKEY|SSH_BUG_EXTEOF|
+					SSH_BUG_SIGTYPE},
 		{ "OpenSSH_2*,"
 		  "OpenSSH_3*,"
-		  "OpenSSH_4*",		0 },
-		{ "OpenSSH_5*",		SSH_NEW_OPENSSH|SSH_BUG_DYNAMIC_RPORT},
-		{ "OpenSSH_6.6.1*",	SSH_NEW_OPENSSH},
+		  "OpenSSH_4*",		SSH_BUG_SIGTYPE },
+		{ "OpenSSH_5*",		SSH_NEW_OPENSSH|SSH_BUG_DYNAMIC_RPORT|
+					SSH_BUG_SIGTYPE},
+		{ "OpenSSH_6.6.1*",	SSH_NEW_OPENSSH|SSH_BUG_SIGTYPE},
 		{ "OpenSSH_6.5*,"
-		  "OpenSSH_6.6*",	SSH_NEW_OPENSSH|SSH_BUG_CURVE25519PAD},
+		  "OpenSSH_6.6*",	SSH_NEW_OPENSSH|SSH_BUG_CURVE25519PAD|
+					SSH_BUG_SIGTYPE},
+		{ "OpenSSH_7.0*,"
+		  "OpenSSH_7.1*,"
+		  "OpenSSH_7.2*,"
+		  "OpenSSH_7.3*,"
+		  "OpenSSH_7.4*,"
+		  "OpenSSH_7.5*,"
+		  "OpenSSH_7.6*",	SSH_NEW_OPENSSH|SSH_BUG_SIGTYPE},
 		{ "OpenSSH*",		SSH_NEW_OPENSSH },
 		{ "*MindTerm*",		0 },
 		{ "3.0.*",		SSH_BUG_DEBUG },
diff --git a/usr.bin/ssh/compat.h b/usr.bin/ssh/compat.h
index 4fee3495a5a..28d2c81354e 100644
--- a/usr.bin/ssh/compat.h
+++ b/usr.bin/ssh/compat.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: compat.h,v 1.51 2018/02/16 04:43:11 dtucker Exp $ */
+/* $OpenBSD: compat.h,v 1.52 2018/07/03 11:39:54 djm Exp $ */
 
 /*
  * Copyright (c) 1999, 2000, 2001 Markus Friedl.  All rights reserved.
@@ -33,7 +33,7 @@
 #define	SSH_PROTO_2		0x04
 
 #define SSH_BUG_UTF8TTYMODE	0x00000001
-/* #define unused		0x00000002 */
+#define SSH_BUG_SIGTYPE		0x00000002
 /* #define unused		0x00000004 */
 /* #define unused		0x00000008 */
 #define SSH_OLD_SESSIONID	0x00000010
diff --git a/usr.bin/ssh/kex.c b/usr.bin/ssh/kex.c
index 44723db11e4..edaf7c2c353 100644
--- a/usr.bin/ssh/kex.c
+++ b/usr.bin/ssh/kex.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: kex.c,v 1.136 2018/02/07 02:06:50 jsing Exp $ */
+/* $OpenBSD: kex.c,v 1.137 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
  *
@@ -330,6 +330,7 @@ kex_send_ext_info(struct ssh *ssh)
 
 	if ((algs = sshkey_alg_list(0, 1, 1, ',')) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
+	/* XXX filter algs list by allowed pubkey/hostbased types */
 	if ((r = sshpkt_start(ssh, SSH2_MSG_EXT_INFO)) != 0 ||
 	    (r = sshpkt_put_u32(ssh, 1)) != 0 ||
 	    (r = sshpkt_put_cstring(ssh, "server-sig-algs")) != 0 ||
@@ -366,7 +367,7 @@ kex_input_ext_info(int type, u_int32_t seq, struct ssh *ssh)
 {
 	struct kex *kex = ssh->kex;
 	u_int32_t i, ninfo;
-	char *name, *found;
+	char *name;
 	u_char *val;
 	size_t vlen;
 	int r;
@@ -389,16 +390,8 @@ kex_input_ext_info(int type, u_int32_t seq, struct ssh *ssh)
 				return SSH_ERR_INVALID_FORMAT;
 			}
 			debug("%s: %s=<%s>", __func__, name, val);
-			found = match_list("rsa-sha2-256", val, NULL);
-			if (found) {
-				kex->rsa_sha2 = 256;
-				free(found);
-			}
-			found = match_list("rsa-sha2-512", val, NULL);
-			if (found) {
-				kex->rsa_sha2 = 512;
-				free(found);
-			}
+			kex->server_sig_algs = val;
+			val = NULL;
 		} else
 			debug("%s: %s (unrecognised)", __func__, name);
 		free(name);
diff --git a/usr.bin/ssh/kex.h b/usr.bin/ssh/kex.h
index 76f7328da16..575213e6694 100644
--- a/usr.bin/ssh/kex.h
+++ b/usr.bin/ssh/kex.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: kex.h,v 1.83 2017/05/30 14:23:52 markus Exp $ */
+/* $OpenBSD: kex.h,v 1.84 2018/07/03 11:39:54 djm Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -125,7 +125,7 @@ struct kex {
 	int	hostkey_type;
 	int	hostkey_nid;
 	u_int	kex_type;
-	int	rsa_sha2;
+	char	*server_sig_algs;
 	int	ext_info_c;
 	struct sshbuf *my;
 	struct sshbuf *peer;
diff --git a/usr.bin/ssh/myproposal.h b/usr.bin/ssh/myproposal.h
index 242c26ffd25..5ba525aa3d3 100644
--- a/usr.bin/ssh/myproposal.h
+++ b/usr.bin/ssh/myproposal.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: myproposal.h,v 1.55 2017/05/07 23:13:42 djm Exp $ */
+/* $OpenBSD: myproposal.h,v 1.56 2018/07/03 11:39:54 djm Exp $ */
 
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
@@ -50,6 +50,8 @@
 	"ecdsa-sha2-nistp384-cert-v01@openssh.com," \
 	"ecdsa-sha2-nistp521-cert-v01@openssh.com," \
 	"ssh-ed25519-cert-v01@openssh.com," \
+	"rsa-sha2-512-cert-v01@openssh.com," \
+	"rsa-sha2-256-cert-v01@openssh.com," \
 	"ssh-rsa-cert-v01@openssh.com," \
 	"ecdsa-sha2-nistp256," \
 	"ecdsa-sha2-nistp384," \
diff --git a/usr.bin/ssh/ssh-rsa.c b/usr.bin/ssh/ssh-rsa.c
index 006c8bdca40..053da818339 100644
--- a/usr.bin/ssh/ssh-rsa.c
+++ b/usr.bin/ssh/ssh-rsa.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-rsa.c,v 1.66 2018/02/14 16:27:24 jsing Exp $ */
+/* $OpenBSD: ssh-rsa.c,v 1.67 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 2000, 2003 Markus Friedl <markus@openbsd.org>
  *
@@ -46,11 +46,14 @@ rsa_hash_alg_ident(int hash_alg)
 	return NULL;
 }
 
+/*
+ * Returns the hash algorithm ID for a given algorithm identifier as used
+ * inside the signature blob,
+ */
 static int
-rsa_hash_alg_from_ident(const char *ident)
+rsa_hash_id_from_ident(const char *ident)
 {
-	if (strcmp(ident, "ssh-rsa") == 0 ||
-	    strcmp(ident, "ssh-rsa-cert-v01@openssh.com") == 0)
+	if (strcmp(ident, "ssh-rsa") == 0)
 		return SSH_DIGEST_SHA1;
 	if (strcmp(ident, "rsa-sha2-256") == 0)
 		return SSH_DIGEST_SHA256;
@@ -59,6 +62,27 @@ rsa_hash_alg_from_ident(const char *ident)
 	return -1;
 }
 
+/*
+ * Return the hash algorithm ID for the specified key name. This includes
+ * all the cases of rsa_hash_id_from_ident() but also the certificate key
+ * types.
+ */
+static int
+rsa_hash_id_from_keyname(const char *alg)
+{
+	int r;
+
+	if ((r = rsa_hash_id_from_ident(alg)) != -1)
+		return r;
+	if (strcmp(alg, "ssh-rsa-cert-v01@openssh.com") == 0)
+		return SSH_DIGEST_SHA1;
+	if (strcmp(alg, "rsa-sha2-256-cert-v01@openssh.com") == 0)
+		return SSH_DIGEST_SHA256;
+	if (strcmp(alg, "rsa-sha2-512-cert-v01@openssh.com") == 0)
+		return SSH_DIGEST_SHA512;
+	return -1;
+}
+
 static int
 rsa_hash_alg_nid(int type)
 {
@@ -130,7 +154,7 @@ ssh_rsa_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
 	if (alg_ident == NULL || strlen(alg_ident) == 0)
 		hash_alg = SSH_DIGEST_SHA1;
 	else
-		hash_alg = rsa_hash_alg_from_ident(alg_ident);
+		hash_alg = rsa_hash_id_from_keyname(alg_ident);
 	if (key == NULL || key->rsa == NULL || hash_alg == -1 ||
 	    sshkey_type_plain(key->type) != KEY_RSA)
 		return SSH_ERR_INVALID_ARGUMENT;
@@ -197,7 +221,7 @@ ssh_rsa_verify(const struct sshkey *key,
     const char *alg)
 {
 	char *sigtype = NULL;
-	int hash_alg, ret = SSH_ERR_INTERNAL_ERROR;
+	int hash_alg, want_alg, ret = SSH_ERR_INTERNAL_ERROR;
 	size_t len = 0, diff, modlen, dlen;
 	struct sshbuf *b = NULL;
 	u_char digest[SSH_DIGEST_MAX_LENGTH], *osigblob, *sigblob = NULL;
@@ -215,18 +239,24 @@ ssh_rsa_verify(const struct sshkey *key,
 		ret = SSH_ERR_INVALID_FORMAT;
 		goto out;
 	}
-	/* XXX djm: need cert types that reliably yield SHA-2 signatures */
-	if (alg != NULL && strcmp(alg, sigtype) != 0 &&
-	    strcmp(alg, "ssh-rsa-cert-v01@openssh.com") != 0) {
-		error("%s: RSA signature type mismatch: "
-		    "expected %s received %s", __func__, alg, sigtype);
-		ret = SSH_ERR_SIGNATURE_INVALID;
-		goto out;
-	}
-	if ((hash_alg = rsa_hash_alg_from_ident(sigtype)) == -1) {
+	if ((hash_alg = rsa_hash_id_from_ident(sigtype)) == -1) {
 		ret = SSH_ERR_KEY_TYPE_MISMATCH;
 		goto out;
 	}
+	/*
+	 * Allow ssh-rsa-cert-v01 certs to generate SHA2 signatures for
+	 * legacy reasons, but otherwise the signature type should match.
+	 */
+	if (alg != NULL && strcmp(alg, "ssh-rsa-cert-v01@openssh.com") != 0) {
+		if ((want_alg = rsa_hash_id_from_keyname(alg)) == -1) {
+			ret = SSH_ERR_INVALID_ARGUMENT;
+			goto out;
+		}
+		if (hash_alg != want_alg) {
+			ret = SSH_ERR_SIGNATURE_INVALID;
+			goto out;
+		}
+	}
 	if (sshbuf_get_string(b, &sigblob, &len) != 0) {
 		ret = SSH_ERR_INVALID_FORMAT;
 		goto out;
diff --git a/usr.bin/ssh/ssh_config.5 b/usr.bin/ssh/ssh_config.5
index e5eadcaaf73..eff9c5e61aa 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.277 2018/06/09 06:36:31 jmc Exp $
-.Dd $Mdocdate: June 9 2018 $
+.\" $OpenBSD: ssh_config.5,v 1.278 2018/07/03 11:39:54 djm Exp $
+.Dd $Mdocdate: July 3 2018 $
 .Dt SSH_CONFIG 5
 .Os
 .Sh NAME
@@ -772,9 +772,10 @@ ecdsa-sha2-nistp256-cert-v01@openssh.com,
 ecdsa-sha2-nistp384-cert-v01@openssh.com,
 ecdsa-sha2-nistp521-cert-v01@openssh.com,
 ssh-ed25519-cert-v01@openssh.com,
+rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
 ssh-rsa-cert-v01@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
-ssh-ed25519,ssh-rsa
+ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
 .Ed
 .Pp
 The
@@ -799,9 +800,10 @@ ecdsa-sha2-nistp256-cert-v01@openssh.com,
 ecdsa-sha2-nistp384-cert-v01@openssh.com,
 ecdsa-sha2-nistp521-cert-v01@openssh.com,
 ssh-ed25519-cert-v01@openssh.com,
+rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
 ssh-rsa-cert-v01@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
-ssh-ed25519,ssh-rsa
+ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
 .Ed
 .Pp
 If hostkeys are known for the destination host then this default is modified
@@ -1255,9 +1257,10 @@ ecdsa-sha2-nistp256-cert-v01@openssh.com,
 ecdsa-sha2-nistp384-cert-v01@openssh.com,
 ecdsa-sha2-nistp521-cert-v01@openssh.com,
 ssh-ed25519-cert-v01@openssh.com,
+rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
 ssh-rsa-cert-v01@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
-ssh-ed25519,ssh-rsa
+ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
 .Ed
 .Pp
 The list of available key types may also be obtained using
diff --git a/usr.bin/ssh/sshconnect2.c b/usr.bin/ssh/sshconnect2.c
index 54b202fd9d1..da326ea8e0b 100644
--- a/usr.bin/ssh/sshconnect2.c
+++ b/usr.bin/ssh/sshconnect2.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect2.c,v 1.271 2018/06/26 02:02:36 djm Exp $ */
+/* $OpenBSD: sshconnect2.c,v 1.272 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  * Copyright (c) 2008 Damien Miller.  All rights reserved.
@@ -307,7 +307,7 @@ int	input_gssapi_errtok(int, u_int32_t, struct ssh *);
 
 void	userauth(Authctxt *, char *);
 
-static int sign_and_send_pubkey(Authctxt *, Identity *);
+static int sign_and_send_pubkey(struct ssh *ssh, Authctxt *, Identity *);
 static void pubkey_prepare(Authctxt *);
 static void pubkey_cleanup(Authctxt *);
 static void pubkey_reset(Authctxt *);
@@ -611,7 +611,7 @@ input_userauth_pk_ok(int type, u_int32_t seq, struct ssh *ssh)
 	 */
 	TAILQ_FOREACH_REVERSE(id, &authctxt->keys, idlist, next) {
 		if (key_equal(key, id->key)) {
-			sent = sign_and_send_pubkey(authctxt, id);
+			sent = sign_and_send_pubkey(ssh, authctxt, id);
 			break;
 		}
 	}
@@ -978,73 +978,80 @@ input_userauth_passwd_changereq(int type, u_int32_t seqnr, struct ssh *ssh)
 	return 0;
 }
 
-static const char *
-key_sign_encode(const struct sshkey *key)
-{
-	struct ssh *ssh = active_state;
-
-	if (key->type == KEY_RSA) {
-		switch (ssh->kex->rsa_sha2) {
-		case 256:
-			return "rsa-sha2-256";
-		case 512:
-			return "rsa-sha2-512";
-		}
-	}
-	return key_ssh_name(key);
-}
-
 /*
- * Some agents will return ssh-rsa signatures when asked to make a
- * rsa-sha2-* signature. Check what they actually gave back and warn the
- * user if the agent has returned an unexpected type.
+ * Select an algorithm for publickey signatures.
+ * Returns algorithm (caller must free) or NULL if no mutual algorithm found.
+ *
+ * Call with ssh==NULL to ignore server-sig-algs extension list and
+ * only attempt with the key's base signature type.
  */
-static int
-check_sigtype(const struct sshkey *key, const u_char *sig, size_t len)
+static char *
+key_sig_algorithm(struct ssh *ssh, const struct sshkey *key)
 {
-	int r;
-	char *sigtype = NULL;
-	const char *alg = key_sign_encode(key);
+	char *allowed, *oallowed, *cp, *alg = NULL;
 
-	if (sshkey_is_cert(key))
-		return 0;
-	if ((r = sshkey_sigtype(sig, len, &sigtype)) != 0)
-		return r;
-	if (strcmp(sigtype, alg) != 0) {
-		logit("warning: agent returned different signature type %s "
-		    "(expected %s)", sigtype, alg);
-	}
-	free(sigtype);
-	/* Incorrect signature types aren't an error ... yet */
-	return 0;
+	/*
+	 * The signature algorithm will only differ from the key algorithm
+	 * for RSA keys/certs and when the server advertises support for
+	 * newer (SHA2) algorithms.
+	 */
+	if (ssh == NULL || ssh->kex->server_sig_algs == NULL ||
+	    (key->type != KEY_RSA && key->type != KEY_RSA_CERT)) {
+		/* Filter base key signature alg against our configuration */
+		return match_list(key_ssh_name(key),
+		    options.pubkey_key_types, NULL);
+	}
+
+	/*
+	 * For RSA keys/certs, since these might have a different sig type:
+	 * find the first entry in PubkeyAcceptedKeyTypes of the right type
+	 * that also appears in the supported signature algorithms list from
+	 * the server.
+	 */
+	oallowed = allowed = xstrdup(options.pubkey_key_types);
+	while ((cp = strsep(&allowed, ",")) != NULL) {
+		if (sshkey_type_from_name(cp) != key->type)
+			continue;
+		alg = match_list(cp, ssh->kex->server_sig_algs, NULL);
+		if (alg != NULL)
+			break;
+	}
+	free(oallowed);
+	return alg;
 }
 
 static int
 identity_sign(struct identity *id, u_char **sigp, size_t *lenp,
-    const u_char *data, size_t datalen, u_int compat)
+    const u_char *data, size_t datalen, u_int compat, const char *alg)
 {
 	struct sshkey *prv;
 	int r;
 
-	/* the agent supports this key */
+	/* The agent supports this key. */
 	if (id->key != NULL && id->agent_fd != -1) {
-		if ((r = ssh_agent_sign(id->agent_fd, id->key, sigp, lenp,
-		    data, datalen, key_sign_encode(id->key), compat)) != 0 ||
-		    (r = check_sigtype(id->key, *sigp, *lenp)) != 0)
-			return r;
-		return 0;
+		return ssh_agent_sign(id->agent_fd, id->key, sigp, lenp,
+		    data, datalen, alg, compat);
 	}
 
 	/*
-	 * we have already loaded the private key or
-	 * the private key is stored in external hardware
+	 * We have already loaded the private key or the private key is
+	 * stored in external hardware.
 	 */
 	if (id->key != NULL &&
-	    (id->isprivate || (id->key->flags & SSHKEY_FLAG_EXT)))
-		return (sshkey_sign(id->key, sigp, lenp, data, datalen,
-		    key_sign_encode(id->key), compat));
+	    (id->isprivate || (id->key->flags & SSHKEY_FLAG_EXT))) {
+		if ((r = sshkey_sign(id->key, sigp, lenp, data, datalen,
+		    alg, compat)) != 0)
+			return r;
+		/*
+		 * PKCS#11 tokens may not support all signature algorithms,
+		 * so check what we get back.
+		 */
+		if ((r = sshkey_check_sigtype(*sigp, *lenp, alg)) != 0)
+			return r;
+		return 0;
+	}
 
-	/* load the private key from the file */
+	/* Load the private key from the file. */
 	if ((prv = load_identity_file(id)) == NULL)
 		return SSH_ERR_KEY_NOT_FOUND;
 	if (id->key != NULL && !sshkey_equal_public(prv, id->key)) {
@@ -1052,8 +1059,7 @@ identity_sign(struct identity *id, u_char **sigp, size_t *lenp,
 		   __func__, id->filename);
 		return SSH_ERR_KEY_NOT_FOUND;
 	}
-	r = sshkey_sign(prv, sigp, lenp, data, datalen,
-	    key_sign_encode(prv), compat);
+	r = sshkey_sign(prv, sigp, lenp, data, datalen, alg, compat);
 	sshkey_free(prv);
 	return r;
 }
@@ -1078,57 +1084,35 @@ id_filename_matches(Identity *id, Identity *private_id)
 }
 
 static int
-sign_and_send_pubkey(Authctxt *authctxt, Identity *id)
+sign_and_send_pubkey(struct ssh *ssh, Authctxt *authctxt, Identity *id)
 {
-	Buffer b;
-	Identity *private_id;
-	u_char *blob, *signature;
-	size_t slen;
-	u_int bloblen, skip = 0;
-	int matched, ret = -1, have_sig = 1;
-	char *fp;
+	struct sshbuf *b = NULL;
+	Identity *private_id, *sign_id = NULL;
+	u_char *signature = NULL;
+	size_t slen = 0, skip = 0;
+	int r, fallback_sigtype, sent = 0;
+	char *alg = NULL, *fp = NULL;
+	const char *loc = "";
 
 	if ((fp = sshkey_fingerprint(id->key, options.fingerprint_hash,
 	    SSH_FP_DEFAULT)) == NULL)
 		return 0;
-	debug3("%s: %s %s", __func__, key_type(id->key), fp);
-	free(fp);
 
-	if (key_to_blob(id->key, &blob, &bloblen) == 0) {
-		/* we cannot handle this key */
-		debug3("sign_and_send_pubkey: cannot handle key");
-		return 0;
-	}
-	/* data to be signed */
-	buffer_init(&b);
-	if (datafellows & SSH_OLD_SESSIONID) {
-		buffer_append(&b, session_id2, session_id2_len);
-		skip = session_id2_len;
-	} else {
-		buffer_put_string(&b, session_id2, session_id2_len);
-		skip = buffer_len(&b);
-	}
-	buffer_put_char(&b, SSH2_MSG_USERAUTH_REQUEST);
-	buffer_put_cstring(&b, authctxt->server_user);
-	buffer_put_cstring(&b, authctxt->service);
-	buffer_put_cstring(&b, authctxt->method->name);
-	buffer_put_char(&b, have_sig);
-	buffer_put_cstring(&b, key_sign_encode(id->key));
-	buffer_put_string(&b, blob, bloblen);
+	debug3("%s: %s %s", __func__, sshkey_type(id->key), fp);
 
 	/*
 	 * If the key is an certificate, try to find a matching private key
 	 * and use it to complete the signature.
 	 * If no such private key exists, fall back to trying the certificate
 	 * key itself in case it has a private half already loaded.
+	 * This will try to set sign_id to the private key that will perform
+	 * the signature.
 	 */
-	if (key_is_cert(id->key)) {
-		matched = 0;
+	if (sshkey_is_cert(id->key)) {
 		TAILQ_FOREACH(private_id, &authctxt->keys, next) {
 			if (sshkey_equal_public(id->key, private_id->key) &&
 			    id->key->type != private_id->key->type) {
-				id = private_id;
-				matched = 1;
+				sign_id = private_id;
 				break;
 			}
 		}
@@ -1139,18 +1123,18 @@ sign_and_send_pubkey(Authctxt *authctxt, Identity *id)
 		 * of keeping just a private key file and public
 		 * certificate on disk.
 		 */
-		if (!matched && !id->isprivate && id->agent_fd == -1 &&
+		if (sign_id == NULL &&
+		    !id->isprivate && id->agent_fd == -1 &&
 		    (id->key->flags & SSHKEY_FLAG_EXT) == 0) {
 			TAILQ_FOREACH(private_id, &authctxt->keys, next) {
 				if (private_id->key == NULL &&
 				    id_filename_matches(id, private_id)) {
-					id = private_id;
-					matched = 1;
+					sign_id = private_id;
 					break;
 				}
 			}
 		}
-		if (matched) {
+		if (sign_id != NULL) {
 			debug2("%s: using private key \"%s\"%s for "
 			    "certificate", __func__, id->filename,
 			    id->agent_fd != -1 ? " from agent" : "");
@@ -1160,51 +1144,121 @@ sign_and_send_pubkey(Authctxt *authctxt, Identity *id)
 		}
 	}
 
-	/* generate signature */
-	ret = identity_sign(id, &signature, &slen,
-	    buffer_ptr(&b), buffer_len(&b), datafellows);
-	if (ret != 0) {
-		if (ret != SSH_ERR_KEY_NOT_FOUND)
-			error("%s: signing failed: %s", __func__, ssh_err(ret));
-		free(blob);
-		buffer_free(&b);
-		return 0;
+	/*
+	 * If the above didn't select another identity to do the signing
+	 * then default to the one we started with.
+	 */
+	if (sign_id == NULL)
+		sign_id = id;
+
+	/* assemble and sign data */
+	for (fallback_sigtype = 0; fallback_sigtype <= 1; fallback_sigtype++) {
+		free(alg);
+		slen = 0;
+		signature = NULL;
+		if ((alg = key_sig_algorithm(fallback_sigtype ? NULL : ssh,
+		    id->key)) == NULL) {
+			error("%s: no mutual signature supported", __func__);
+			goto out;
+		}
+		debug3("%s: signing using %s", __func__, alg);
+
+		sshbuf_free(b);
+		if ((b = sshbuf_new()) == NULL)
+			fatal("%s: sshbuf_new failed", __func__);
+		if (datafellows & SSH_OLD_SESSIONID) {
+			if ((r = sshbuf_put(b, session_id2,
+			    session_id2_len)) != 0) {
+				fatal("%s: sshbuf_put: %s",
+				    __func__, ssh_err(r));
+			}
+		} else {
+			if ((r = sshbuf_put_string(b, session_id2,
+			    session_id2_len)) != 0) {
+				fatal("%s: sshbuf_put_string: %s",
+				    __func__, ssh_err(r));
+			}
+		}
+		skip = buffer_len(b);
+		if ((r = sshbuf_put_u8(b, SSH2_MSG_USERAUTH_REQUEST)) != 0 ||
+		    (r = sshbuf_put_cstring(b, authctxt->server_user)) != 0 ||
+		    (r = sshbuf_put_cstring(b, authctxt->service)) != 0 ||
+		    (r = sshbuf_put_cstring(b, authctxt->method->name)) != 0 ||
+		    (r = sshbuf_put_u8(b, 1)) != 0 ||
+		    (r = sshbuf_put_cstring(b, alg)) != 0 ||
+		    (r = sshkey_puts(id->key, b)) != 0) {
+			fatal("%s: assemble signed data: %s",
+			    __func__, ssh_err(r));
+		}
+
+		/* generate signature */
+		r = identity_sign(sign_id, &signature, &slen,
+		    sshbuf_ptr(b), sshbuf_len(b), datafellows, alg);
+		if (r == 0)
+			break;
+		else if (r == SSH_ERR_KEY_NOT_FOUND)
+			goto out; /* soft failure */
+		else if (r == SSH_ERR_SIGN_ALG_UNSUPPORTED &&
+		    !fallback_sigtype) {
+			if (sign_id->agent_fd != -1)
+				loc = "agent ";
+			else if ((sign_id->key->flags & SSHKEY_FLAG_EXT) != 0)
+				loc = "token ";
+			logit("%skey %s %s returned incorrect signature type",
+			    loc, sshkey_type(id->key), fp);
+			continue;
+		}
+		error("%s: signing failed: %s", __func__, ssh_err(r));
+		goto out;
 	}
-#ifdef DEBUG_PK
-	buffer_dump(&b);
-#endif
-	free(blob);
+	if (slen == 0 || signature == NULL) /* shouldn't happen */
+		fatal("%s: no signature", __func__);
 
 	/* append signature */
-	buffer_put_string(&b, signature, slen);
-	free(signature);
+	if ((r = sshbuf_put_string(b, signature, slen)) != 0)
+		fatal("%s: append signature: %s", __func__, ssh_err(r));
 
+#ifdef DEBUG_PK
+	sshbuf_dump(b, stderr);
+#endif
 	/* skip session id and packet type */
-	if (buffer_len(&b) < skip + 1)
-		fatal("userauth_pubkey: internal error");
-	buffer_consume(&b, skip + 1);
+	if ((r = sshbuf_consume(b, skip + 1)) != 0)
+		fatal("%s: consume: %s", __func__, ssh_err(r));
 
 	/* put remaining data from buffer into packet */
-	packet_start(SSH2_MSG_USERAUTH_REQUEST);
-	packet_put_raw(buffer_ptr(&b), buffer_len(&b));
-	buffer_free(&b);
-	packet_send();
+	if ((r = sshpkt_start(ssh, SSH2_MSG_USERAUTH_REQUEST)) != 0 ||
+	    (r = sshpkt_putb(ssh, b)) != 0 ||
+	    (r = sshpkt_send(ssh)) != 0)
+		fatal("%s: enqueue request: %s", __func__, ssh_err(r));
 
-	return 1;
+	/* success */
+	sent = 1;
+
+ out:
+	free(fp);
+	free(alg);
+	sshbuf_free(b);
+	freezero(signature, slen);
+	return sent;
 }
 
 static int
-send_pubkey_test(Authctxt *authctxt, Identity *id)
+send_pubkey_test(struct ssh *ssh, Authctxt *authctxt, Identity *id)
 {
-	u_char *blob;
+	u_char *blob = NULL;
 	u_int bloblen, have_sig = 0;
+	char *alg = NULL;
+	int sent = 0;
 
-	debug3("send_pubkey_test");
+	if ((alg = key_sig_algorithm(ssh, id->key)) == NULL) {
+		debug("%s: no mutual signature algorithm", __func__);
+		goto out;
+	}
 
 	if (key_to_blob(id->key, &blob, &bloblen) == 0) {
 		/* we cannot handle this key */
-		debug3("send_pubkey_test: cannot handle key");
-		return 0;
+		debug3("%s: cannot handle key", __func__);
+		goto out;
 	}
 	/* register callback for USERAUTH_PK_OK message */
 	dispatch_set(SSH2_MSG_USERAUTH_PK_OK, &input_userauth_pk_ok);
@@ -1214,11 +1268,15 @@ send_pubkey_test(Authctxt *authctxt, Identity *id)
 	packet_put_cstring(authctxt->service);
 	packet_put_cstring(authctxt->method->name);
 	packet_put_char(have_sig);
-	packet_put_cstring(key_sign_encode(id->key));
+	packet_put_cstring(alg);
 	packet_put_string(blob, bloblen);
-	free(blob);
 	packet_send();
-	return 1;
+	/* success */
+	sent = 1;
+out:
+	free(alg);
+	free(blob);
+	return sent;
 }
 
 static struct sshkey *
@@ -1287,6 +1345,36 @@ load_identity_file(Identity *id)
 	return private;
 }
 
+static int
+key_type_allowed_by_config(struct sshkey *key)
+{
+	if (match_pattern_list(sshkey_ssh_name(key),
+	    options.pubkey_key_types, 0) == 1)
+		return 1;
+
+	/* RSA keys/certs might be allowed by alternate signature types */
+	switch (key->type) {
+	case KEY_RSA:
+		if (match_pattern_list("rsa-sha2-512",
+		    options.pubkey_key_types, 0) == 1)
+			return 1;
+		if (match_pattern_list("rsa-sha2-256",
+		    options.pubkey_key_types, 0) == 1)
+			return 1;
+		break;
+	case KEY_RSA_CERT:
+		if (match_pattern_list("rsa-sha2-512-cert-v01@openssh.com",
+		    options.pubkey_key_types, 0) == 1)
+			return 1;
+		if (match_pattern_list("rsa-sha2-256-cert-v01@openssh.com",
+		    options.pubkey_key_types, 0) == 1)
+			return 1;
+		break;
+	}
+	return 0;
+}
+
+
 /*
  * try keys in the following order:
  * 	1. certificates listed in the config file
@@ -1411,9 +1499,7 @@ pubkey_prepare(Authctxt *authctxt)
 	}
 	/* finally, filter by PubkeyAcceptedKeyTypes */
 	TAILQ_FOREACH_SAFE(id, preferred, next, id2) {
-		if (id->key != NULL &&
-		    match_pattern_list(sshkey_ssh_name(id->key),
-		    options.pubkey_key_types, 0) != 1) {
+		if (id->key != NULL && !key_type_allowed_by_config(key)) {
 			debug("Skipping %s key %s - "
 			    "not in PubkeyAcceptedKeyTypes",
 			    sshkey_ssh_name(id->key), id->filename);
@@ -1471,6 +1557,7 @@ try_identity(Identity *id)
 int
 userauth_pubkey(Authctxt *authctxt)
 {
+	struct ssh *ssh = active_state; /* XXX */
 	Identity *id;
 	int sent = 0;
 	char *fp;
@@ -1498,7 +1585,7 @@ userauth_pubkey(Authctxt *authctxt)
 				debug("Offering public key: %s %s %s",
 				    sshkey_type(id->key), fp, id->filename);
 				free(fp);
-				sent = send_pubkey_test(authctxt, id);
+				sent = send_pubkey_test(ssh, authctxt, id);
 			}
 		} else {
 			debug("Trying private key: %s", id->filename);
@@ -1506,7 +1593,7 @@ userauth_pubkey(Authctxt *authctxt)
 			if (id->key != NULL) {
 				if (try_identity(id)) {
 					id->isprivate = 1;
-					sent = sign_and_send_pubkey(
+					sent = sign_and_send_pubkey(ssh,
 					    authctxt, id);
 				}
 				key_free(id->key);
@@ -1727,7 +1814,7 @@ ssh_keysign(struct sshkey *key, u_char **sigp, size_t *lenp,
 int
 userauth_hostbased(Authctxt *authctxt)
 {
-	struct ssh *ssh = active_state;
+	struct ssh *ssh = active_state; /* XXX */
 	struct sshkey *private = NULL;
 	struct sshbuf *b = NULL;
 	u_char *sig = NULL, *keyblob = NULL;
diff --git a/usr.bin/ssh/sshd.c b/usr.bin/ssh/sshd.c
index e0b894eed61..c5ca132897c 100644
--- a/usr.bin/ssh/sshd.c
+++ b/usr.bin/ssh/sshd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshd.c,v 1.508 2018/04/13 03:57:26 dtucker Exp $ */
+/* $OpenBSD: sshd.c,v 1.509 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -639,45 +639,47 @@ privsep_postauth(Authctxt *authctxt)
 	packet_set_authenticated();
 }
 
+static void
+append_hostkey_type(struct sshbuf *b, const char *s)
+{
+	int r;
+
+	if (match_pattern_list(s, options.hostkeyalgorithms, 0) != 1) {
+		debug3("%s: %s key not permitted by HostkeyAlgorithms",
+		    __func__, s);
+		return;
+	}
+	if ((r = sshbuf_putf(b, "%s%s", sshbuf_len(b) > 0 ? "," : "", s)) != 0)
+		fatal("%s: sshbuf_putf: %s", __func__, ssh_err(r));
+}
+
 static char *
 list_hostkey_types(void)
 {
-	Buffer b;
-	const char *p;
+	struct sshbuf *b;
+	struct sshkey *key;
 	char *ret;
 	u_int i;
-	struct sshkey *key;
 
-	buffer_init(&b);
+	if ((b = sshbuf_new()) == NULL)
+		fatal("%s: sshbuf_new failed", __func__);
 	for (i = 0; i < options.num_host_key_files; i++) {
 		key = sensitive_data.host_keys[i];
 		if (key == NULL)
 			key = sensitive_data.host_pubkeys[i];
 		if (key == NULL)
 			continue;
-		/* Check that the key is accepted in HostkeyAlgorithms */
-		if (match_pattern_list(sshkey_ssh_name(key),
-		    options.hostkeyalgorithms, 0) != 1) {
-			debug3("%s: %s key not permitted by HostkeyAlgorithms",
-			    __func__, sshkey_ssh_name(key));
-			continue;
-		}
 		switch (key->type) {
 		case KEY_RSA:
+			/* for RSA we also support SHA2 signatures */
+			append_hostkey_type(b, "rsa-sha2-512");
+			append_hostkey_type(b, "rsa-sha2-256");
+			/* FALLTHROUGH */
 		case KEY_DSA:
 		case KEY_ECDSA:
 		case KEY_ED25519:
 		case KEY_XMSS:
-			if (buffer_len(&b) > 0)
-				buffer_append(&b, ",", 1);
-			p = key_ssh_name(key);
-			buffer_append(&b, p, strlen(p));
-
-			/* for RSA we also support SHA2 signatures */
-			if (key->type == KEY_RSA) {
-				p = ",rsa-sha2-512,rsa-sha2-256";
-				buffer_append(&b, p, strlen(p));
-			}
+			append_hostkey_type(b, sshkey_ssh_name(key));
 			break;
 		}
 		/* If the private key has a cert peer, then list that too */
@@ -686,21 +688,24 @@ list_hostkey_types(void)
 			continue;
 		switch (key->type) {
 		case KEY_RSA_CERT:
+			/* for RSA we also support SHA2 signatures */
+			append_hostkey_type(b,
+			    "rsa-sha2-512-cert-v01@openssh.com");
+			append_hostkey_type(b,
+			    "rsa-sha2-256-cert-v01@openssh.com");
+			/* FALLTHROUGH */
 		case KEY_DSA_CERT:
 		case KEY_ECDSA_CERT:
 		case KEY_ED25519_CERT:
 		case KEY_XMSS_CERT:
-			if (buffer_len(&b) > 0)
-				buffer_append(&b, ",", 1);
-			p = key_ssh_name(key);
-			buffer_append(&b, p, strlen(p));
+			append_hostkey_type(b, sshkey_ssh_name(key));
 			break;
 		}
 	}
-	if ((ret = sshbuf_dup_string(&b)) == NULL)
+	if ((ret = sshbuf_dup_string(b)) == NULL)
 		fatal("%s: sshbuf_dup_string failed", __func__);
-	buffer_free(&b);
-	debug("list_hostkey_types: %s", ret);
+	sshbuf_free(b);
+	debug("%s: %s", __func__, ret);
 	return ret;
 }
 
diff --git a/usr.bin/ssh/sshd_config.5 b/usr.bin/ssh/sshd_config.5
index 4b5cd188179..1fccceff77f 100644
--- a/usr.bin/ssh/sshd_config.5
+++ b/usr.bin/ssh/sshd_config.5
@@ -33,7 +33,7 @@
 .\" (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: sshd_config.5,v 1.278 2018/07/03 10:59:35 djm Exp $
+.\" $OpenBSD: sshd_config.5,v 1.279 2018/07/03 11:39:54 djm Exp $
 .Dd $Mdocdate: July 3 2018 $
 .Dt SSHD_CONFIG 5
 .Os
@@ -675,9 +675,10 @@ ecdsa-sha2-nistp256-cert-v01@openssh.com,
 ecdsa-sha2-nistp384-cert-v01@openssh.com,
 ecdsa-sha2-nistp521-cert-v01@openssh.com,
 ssh-ed25519-cert-v01@openssh.com,
+rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
 ssh-rsa-cert-v01@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
-ssh-ed25519,ssh-rsa
+ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
 .Ed
 .Pp
 The list of available key types may also be obtained using
@@ -752,9 +753,10 @@ ecdsa-sha2-nistp256-cert-v01@openssh.com,
 ecdsa-sha2-nistp384-cert-v01@openssh.com,
 ecdsa-sha2-nistp521-cert-v01@openssh.com,
 ssh-ed25519-cert-v01@openssh.com,
+rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
 ssh-rsa-cert-v01@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
-ssh-ed25519,ssh-rsa
+ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
 .Ed
 .Pp
 The list of available key types may also be obtained using
@@ -1400,9 +1402,10 @@ ecdsa-sha2-nistp256-cert-v01@openssh.com,
 ecdsa-sha2-nistp384-cert-v01@openssh.com,
 ecdsa-sha2-nistp521-cert-v01@openssh.com,
 ssh-ed25519-cert-v01@openssh.com,
+rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
 ssh-rsa-cert-v01@openssh.com,
 ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
-ssh-ed25519,ssh-rsa
+ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
 .Ed
 .Pp
 The list of available key types may also be obtained using
diff --git a/usr.bin/ssh/ssherr.c b/usr.bin/ssh/ssherr.c
index 3c0009d69d8..8ad3d575019 100644
--- a/usr.bin/ssh/ssherr.c
+++ b/usr.bin/ssh/ssherr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ssherr.c,v 1.7 2017/09/12 06:32:08 djm Exp $	*/
+/*	$OpenBSD: ssherr.c,v 1.8 2018/07/03 11:39:54 djm Exp $	*/
 /*
  * Copyright (c) 2011 Damien Miller
  *
@@ -139,6 +139,8 @@ ssh_err(int n)
 		return "Invalid key length";
 	case SSH_ERR_NUMBER_TOO_LARGE:
 		return "number is too large";
+	case SSH_ERR_SIGN_ALG_UNSUPPORTED:
+		return "signature algorithm not supported";
 	default:
 		return "unknown error";
 	}
diff --git a/usr.bin/ssh/ssherr.h b/usr.bin/ssh/ssherr.h
index c0b59211e83..348da5a2086 100644
--- a/usr.bin/ssh/ssherr.h
+++ b/usr.bin/ssh/ssherr.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ssherr.h,v 1.5 2017/09/12 06:32:08 djm Exp $	*/
+/*	$OpenBSD: ssherr.h,v 1.6 2018/07/03 11:39:54 djm Exp $	*/
 /*
  * Copyright (c) 2011 Damien Miller
  *
@@ -79,6 +79,7 @@
 #define SSH_ERR_PROTOCOL_ERROR			-55
 #define SSH_ERR_KEY_LENGTH			-56
 #define SSH_ERR_NUMBER_TOO_LARGE		-57
+#define SSH_ERR_SIGN_ALG_UNSUPPORTED		-58
 
 /* Translate a numeric error code to a human-readable error string */
 const char *ssh_err(int n);
diff --git a/usr.bin/ssh/sshkey.c b/usr.bin/ssh/sshkey.c
index f41b0a1d0a1..e9c641ad3f7 100644
--- a/usr.bin/ssh/sshkey.c
+++ b/usr.bin/ssh/sshkey.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshkey.c,v 1.64 2018/03/22 07:05:48 markus Exp $ */
+/* $OpenBSD: sshkey.c,v 1.65 2018/07/03 11:39:54 djm Exp $ */
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
  * Copyright (c) 2008 Alexander von Gernler.  All rights reserved.
@@ -79,38 +79,48 @@ static int sshkey_from_blob_internal(struct sshbuf *buf,
 struct keytype {
 	const char *name;
 	const char *shortname;
+	const char *sigalg;
 	int type;
 	int nid;
 	int cert;
 	int sigonly;
 };
 static const struct keytype keytypes[] = {
-	{ "ssh-ed25519", "ED25519", KEY_ED25519, 0, 0, 0 },
-	{ "ssh-ed25519-cert-v01@openssh.com", "ED25519-CERT",
+	{ "ssh-ed25519", "ED25519", NULL, KEY_ED25519, 0, 0, 0 },
+	{ "ssh-ed25519-cert-v01@openssh.com", "ED25519-CERT", NULL,
 	    KEY_ED25519_CERT, 0, 1, 0 },
 #ifdef WITH_XMSS
-	{ "ssh-xmss@openssh.com", "XMSS", KEY_XMSS, 0, 0, 0 },
-	{ "ssh-xmss-cert-v01@openssh.com", "XMSS-CERT",
+	{ "ssh-xmss@openssh.com", "XMSS", NULL, KEY_XMSS, 0, 0, 0 },
+	{ "ssh-xmss-cert-v01@openssh.com", "XMSS-CERT", NULL,
 	    KEY_XMSS_CERT, 0, 1, 0 },
 #endif /* WITH_XMSS */
 #ifdef WITH_OPENSSL
-	{ "ssh-rsa", "RSA", KEY_RSA, 0, 0, 0 },
-	{ "rsa-sha2-256", "RSA", KEY_RSA, 0, 0, 1 },
-	{ "rsa-sha2-512", "RSA", KEY_RSA, 0, 0, 1 },
-	{ "ssh-dss", "DSA", KEY_DSA, 0, 0, 0 },
-	{ "ecdsa-sha2-nistp256", "ECDSA", KEY_ECDSA, NID_X9_62_prime256v1, 0, 0 },
-	{ "ecdsa-sha2-nistp384", "ECDSA", KEY_ECDSA, NID_secp384r1, 0, 0 },
-	{ "ecdsa-sha2-nistp521", "ECDSA", KEY_ECDSA, NID_secp521r1, 0, 0 },
-	{ "ssh-rsa-cert-v01@openssh.com", "RSA-CERT", KEY_RSA_CERT, 0, 1, 0 },
-	{ "ssh-dss-cert-v01@openssh.com", "DSA-CERT", KEY_DSA_CERT, 0, 1, 0 },
-	{ "ecdsa-sha2-nistp256-cert-v01@openssh.com", "ECDSA-CERT",
+	{ "ssh-rsa", "RSA", NULL, KEY_RSA, 0, 0, 0 },
+	{ "rsa-sha2-256", "RSA", NULL, KEY_RSA, 0, 0, 1 },
+	{ "rsa-sha2-512", "RSA", NULL, KEY_RSA, 0, 0, 1 },
+	{ "ssh-dss", "DSA", NULL, KEY_DSA, 0, 0, 0 },
+	{ "ecdsa-sha2-nistp256", "ECDSA", NULL,
+	    KEY_ECDSA, NID_X9_62_prime256v1, 0, 0 },
+	{ "ecdsa-sha2-nistp384", "ECDSA", NULL,
+	    KEY_ECDSA, NID_secp384r1, 0, 0 },
+	{ "ecdsa-sha2-nistp521", "ECDSA", NULL,
+	    KEY_ECDSA, NID_secp521r1, 0, 0 },
+	{ "ssh-rsa-cert-v01@openssh.com", "RSA-CERT", NULL,
+	    KEY_RSA_CERT, 0, 1, 0 },
+	{ "rsa-sha2-256-cert-v01@openssh.com", "RSA-CERT",
+	    "ssh-rsa-sha2-256", KEY_RSA_CERT, 0, 1, 1 },
+	{ "rsa-sha2-512-cert-v01@openssh.com", "RSA-CERT",
+	    "ssh-rsa-sha2-512", KEY_RSA_CERT, 0, 1, 1 },
+	{ "ssh-dss-cert-v01@openssh.com", "DSA-CERT", NULL,
+	    KEY_DSA_CERT, 0, 1, 0 },
+	{ "ecdsa-sha2-nistp256-cert-v01@openssh.com", "ECDSA-CERT", NULL,
 	    KEY_ECDSA_CERT, NID_X9_62_prime256v1, 1, 0 },
-	{ "ecdsa-sha2-nistp384-cert-v01@openssh.com", "ECDSA-CERT",
+	{ "ecdsa-sha2-nistp384-cert-v01@openssh.com", "ECDSA-CERT", NULL,
 	    KEY_ECDSA_CERT, NID_secp384r1, 1, 0 },
-	{ "ecdsa-sha2-nistp521-cert-v01@openssh.com", "ECDSA-CERT",
-	    KEY_ECDSA_CERT, NID_secp521r1, 1, 0 },
+	{ "ecdsa-sha2-nistp521-cert-v01@openssh.com", "ECDSA-CERT", NULL,
+	   KEY_ECDSA_CERT, NID_secp521r1, 1, 0 },
 #endif /* WITH_OPENSSL */
-	{ NULL, NULL, -1, -1, 0, 0 }
+	{ NULL, NULL, NULL, -1, -1, 0, 0 }
 };
 
 const char *
@@ -2160,8 +2170,8 @@ sshkey_froms(struct sshbuf *buf, struct sshkey **keyp)
 	return r;
 }
 
-int
-sshkey_sigtype(const u_char *sig, size_t siglen, char **sigtypep)
+static int
+get_sigtype(const u_char *sig, size_t siglen, char **sigtypep)
 {
 	int r;
 	struct sshbuf *b = NULL;
@@ -2185,6 +2195,50 @@ sshkey_sigtype(const u_char *sig, size_t siglen, char **sigtypep)
 	return r;
 }
 
+/*
+ * Returns the expected signature algorithm for a given public key algorithm.
+ */
+static const char *
+sigalg_by_name(const char *name)
+{
+	const struct keytype *kt;
+
+	for (kt = keytypes; kt->type != -1; kt++) {
+		if (strcmp(kt->name, name) != 0)
+			continue;
+		if (kt->sigalg != NULL)
+			return kt->sigalg;
+		if (!kt->cert)
+			return kt->name;
+		return sshkey_ssh_name_from_type_nid(
+		    sshkey_type_plain(kt->type), kt->nid);
+	}
+	return NULL;
+}
+
+/*
+ * Verifies that the signature algorithm appearing inside the signature blob
+ * matches that which was requested.
+ */
+int
+sshkey_check_sigtype(const u_char *sig, size_t siglen,
+    const char *requested_alg)
+{
+	const char *expected_alg;
+	char *sigtype = NULL;
+	int r;
+
+	if (requested_alg == NULL)
+		return 0;
+	if ((expected_alg = sigalg_by_name(requested_alg)) == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = get_sigtype(sig, siglen, &sigtype)) != 0)
+		return r;
+	r = strcmp(expected_alg, sigtype) == 0;
+	free(sigtype);
+	return r ? 0 : SSH_ERR_SIGN_ALG_UNSUPPORTED;
+}
+
 int
 sshkey_sign(const struct sshkey *key,
     u_char **sigp, size_t *lenp,
diff --git a/usr.bin/ssh/sshkey.h b/usr.bin/ssh/sshkey.h
index b2fdc1037e2..023cc431437 100644
--- a/usr.bin/ssh/sshkey.h
+++ b/usr.bin/ssh/sshkey.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshkey.h,v 1.24 2018/02/23 15:58:38 markus Exp $ */
+/* $OpenBSD: sshkey.h,v 1.25 2018/07/03 11:39:54 djm Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -185,11 +185,11 @@ int	 sshkey_puts_opts(const struct sshkey *, struct sshbuf *,
 int	 sshkey_plain_to_blob(const struct sshkey *, u_char **, size_t *);
 int	 sshkey_putb_plain(const struct sshkey *, struct sshbuf *);
 
-int	 sshkey_sigtype(const u_char *, size_t, char **);
 int	 sshkey_sign(const struct sshkey *, u_char **, size_t *,
     const u_char *, size_t, const char *, u_int);
 int	 sshkey_verify(const struct sshkey *, const u_char *, size_t,
     const u_char *, size_t, const char *, u_int);
+int	 sshkey_check_sigtype(const u_char *, size_t, const char *);
 
 /* for debug */
 void	sshkey_dump_ec_point(const EC_GROUP *, const EC_POINT *);