After upgrading your OpenSSH client or your OS distribution, you may encounter this error when connecting to your SSH servers.
What does “no matching host key type found” mean?
When establishing an SSH connection, the client uses the host key of the SSH server to verify the information the server has provided, which it does by verifying the data’s signature with the server’s known public key.
Many different types of host keys are supported, and this error indicates that the client and server could not agree on a host key to use. More specifically, in this case, the server could not provide a signature in any of the algorithms that the client supports.
But this used to work?
Your older software worked because it supported using SHA1-hashed RSA signatures. When you upgraded your OpenSSH client or OS distribution, it upgraded to a version of OpenSSH that has disabled SHA1 signatures.
Why have OpenSSH disabled SHA1 signatures on RSA keys?
Security experts no longer consider RSA signatures that use SHA1 hashes to be secure for communication because SHA1 hash algorithms are vulnerable to collision attacks, which can potentially allow an attacker to create two different messages with the same SHA1 hash. Collisions lead to a situation in which the authenticity of any given message is uncertain, as someone else can construct a message with the same SHA1 hash, thus bypassing the security measures in place.
SHA1 is no longer suitable for use where secure communications are required, including SSH (Secure Shell) connections, and should not be used in any circumstances.
Users should use more recent and reliable hashing algorithms like SHA-256 or SHA-512 to maximize their security. Modern SSH implementations, including the OpenSSH version you upgraded to, will still allow you to use your old SSH RSA keys and will automatically upgrade any signature they use from SHA1 to a SHA2-based hash.
The problem is that if you connect to a server that does not support the new SHA-2 signatures, you will be unable to connect.
How do I fix this?
First, this is not a problem with your upgraded software, but rather that the SSH server you are connecting to uses an outdated set of algorithms and should be upgraded immediately to support the new SHA-2 hashes.
OpenSSH has supported these new algorithms since version 7.2, released in 2016, and a server that does not support these algorithms is a serious security concern.
If you don’t control that server or there is no upgrade path, it’s time to consider if you should continue using that service or product.
If you must connect to this server, you can re-enable the old SHA-1 signatures, but make sure you do this for this host only and not every host. Create or edit ~/.ssh/config and ensure the following entries are present, placing the host’s name after the Host directive. This name must match the value you use when you connect with ssh.
Host `hostname`
HostkeyAlgorithms +ssh-rsa
PubkeyAcceptedAlgorithms +ssh-rsa