How do I resolve the "Unable to negotiate: No matching host key type found" error when connecting to my EC2 Linux instance using SSH?

Short description

You might see one of the following errors when connecting to an EC2 Linux instance using SSH:

• No matching host key type found: This error occurs If SSH can't negotiate a common encryption algorithm or host key with the server that you're connecting to.
• No matching key exchange method found: This error indicates a problem with the key exchange algorithm negotiated between the SSH client and server during the SSH handshake. This error occurs when the SSH client and server have different or incompatible key exchange algorithms.

Resolution

Update the openssh-client

Older versions of the openssh-client might not support the key exchange algorithm negotiated by the server. Run one of the following commands to update the client to the latest version:

Ubuntu and Debian

sudo apt upgrade openssh-client

Amazon Linux, RHEL, and Fedora

sudo yum upgrade openssh-clients

Resolve the "no matching host key type found" error

Example error

Unable to negotiate with X.X.X.X port 22. no matching host key type found. Their offer: rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519.

To resolve this error, make sure that the server and client have at least a single matching host key algorithm. Run the following command on the server and the client to check the host key algorithm:

sudo ssh -Q key

To add additional algorithms in the client, append the following line in the ~/.ssh/config or /etc/ssh/ssh_config file:

vi ~/.ssh/config
HostkeyAlgorithms +ssh-ed25519

Resolve the "no matching key exchange method found" error

Example error

 Unable to negotiate with X.X.X.X port 22: no matching key exchange method found. Their offer: curve25519-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha25

To resolve this error, make sure that the server and client having at least a single matching key exchange algorithm. Run the following command on the server and the client to check the key exchange algorithm:

sudo ssh -Q kex

To add additional key exchange algorithm on the client, append the following line in the ~/.ssh/config or /etc/ssh/ssh_config file:

vi ~/.ssh/config
KexAlgorithms +diffie-hellman-group16-sha512

Related information

OpenSSH Legacy Options on openssh.com