Without support for rsa-sha2-* a connection is not possible anymore

[dkocher]

We have updated to the latest version of sshj in Cyberduck and now there are reports that pubkey auth with RSA keys does not work anymore, e.g. iterate-ch/cyberduck#12733.

This is caused by the removed heuristic based on the host key algorithms sent by the server. For older servers without support for rsa-sha2-* a connection is not possible anymore as in SSH_MSG_USERAUTH_REQUEST the pubkey algorithm rsa-sha2-512 is chosen due to its position in the config list. To invoke #prioritizeSshRsaKeyAlgorithm would resolve the issue but is not an option as we don't know in advance what kind and version of server the user connects to. This would break the client for new server without ssh-rsa support. A workaround could be to try with and without #prioritizeSshRsaKeyAlgorithm but IMO this should be handled by the library.

As we cannot rely on the SSH extension SSH2_MSG_EXT_INFO/server-sig-algs I would suggest to repeat the SSH_MSG_USERAUTH_REQUEST request with all possible pubkey algorithms for a specific key type, e.g. ssh-rsa, rsa-sha2-256, rsa-sha2-512 for RSA keys. That's the way it's done in the MINA client btw. Refer to https://issues.apache.org/jira/browse/SSHD-1105.

Originally posted by @ylangisc in #740 (comment)