SSH Error “No Matching Host Key Type Found”

I just wanted to share a fix for the annoying SSH error you get on older versions of Linux. I got this error when connecting to a Centos 6.9 x64 vanilla installation.

Step 1 – Validate the Error

When you attempt to SSH to the server you will get this error:

ssh [email protected]

Unable to negotiate with 69.28.67.189 port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss

# Note: This IP address no longer exists

This error means there’s a mismatch in the cryptographic keys the SSH client (OpenSSH) is willing to use and the keys the server (CentOS 6.9) is offering.

• Host Keys:
  Connecting to a server via SSH presents a unique “host key.” My local laptop stores this key and verifies it on subsequent connections to ensure you’re talking to the same server (and not a malicious imposter—man-in-the-middle attack).
  
• Algorithms:
  There are different cryptographic algorithms for generating host keys. Older versions of SSH (like the one used in the CentOS 6.9 server) offer outdated or less secure algorithms, like ssh-rsa and ssh-dss. Newer clients prioritize stronger algorithms and may refuse connections if only weaker options are available.

Step 2 – How to Fix Error

This command temporarily overrides your client’s default behavior:

 ssh -oHostKeyAlgorithms=+ssh-dss [email protected]
 
 #Example Output
 #The authenticity of host '69.28.67.189 (69.28.67.189)' can't be established.
 #DSA key fingerprint is SHA256:TBH5kXiO1PwljvFLAduE1+ddrCRjtxESeRo8O2K+FCs.
 #This key is not known by any other names
 #Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
 #Warning: Permanently added '69.28.67.189' (DSA) to the list of known hosts.
 [email protected]'s password:
 [root@CentosEOLDEMO ~]#

-oHostKeyAlgorithms=+ssh-dss: Tells your SSH client to explicitly include ssh-dss in the list of acceptable host key algorithms. This lets it successfully negotiate with the older CentOS server.

Step 3 – Need a permanent Fix?

If you need this fix to be permanent, you can update your ssh config files to always allow ssh-dss. While not always the best security practice, some users may have no other choice but to so this.

Client-Side Configuration (Less Secure):

You can modify your SSH client configuration (~/.ssh/config) to permanently accept ssh-dss. This is the simplest solution, but it’s important to be aware that it lowers your security slightly.

• Edit Config: Open your SSH config file (~/.ssh/config) in a text editor. If it doesn’t exist, create it.
• Add Lines: Add the following lines to the file:

Host 69.28.67.189   # Replace with your server's IP or hostname
    HostKeyAlgorithms +ssh-dss

• Save: Save the file and exit. Now, your client will always use ssh-dss when connecting to that specific server.

Server-Side Configuration (Recommended):

This involves updating the SSH configuration on your CentOS 6.9 server.

• SSH Configuration: Edit the SSH daemon configuration file, usually located at /etc/ssh/sshd_config.
• HostKey Line: Look for a line starting with HostKey. Comment out any lines using ssh-dss or ssh-rsa and add a line for a more secure algorithm, like:

HostKey /etc/ssh/ssh_host_ecdsa_key  # ECDSA key
# Or
HostKey /etc/ssh/ssh_host_ed25519_key  # Ed25519 key

• Generate Keys: If the specified keys don’t exist, generate them with these commands:

ssh-keygen -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key
# Or
ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key

4. Restart SSHD: Restart the SSH daemon to apply the changes:

service sshd restart

3. Upgrading CentOS (Best Long-Term Solution):

If possible, upgrading your CentOS server to a newer version (CentOS 7 or 8) is the best long-term solution. This would provide:

• Security:
  Newer OpenSSH versions with stronger default algorithms.
  
• Maintenance:
  Continued updates and support for your operating system.

Why It Happens

This issue arises due to a combination of factors:

1. Older Server:
   CentOS 6.9 is an older distribution, and its SSH configuration has outdated defaults.
   
2. Security Updates:
   Your SSH client (and modern OpenSSH in general) has been updated over time to prioritize stronger security. It may disable or deprecate older algorithms, like ssh-rsa and ssh-dss due to potential vulnerabilities.

Important Considerations:

• Temporary Solution:
  The command you used is a workaround. It’s not ideal for long-term use because ssh-dss is considered less secure.
  
• Upgrading:
  If possible, consider upgrading your CentOS server to a newer version. This would likely allow it to use more modern and secure host key algorithms.
  
• Alternative:
  If upgrading isn’t an option, you can configure your client to accept permanently ssh-dss. However, do so with caution, as it might weaken the security of your SSH connections.

Q&A on SSH Errors with Older Linux Versions

Q1: What is the fundamental reason behind the “Unable to negotiate with [host] port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss” error when SSHing into older Linux systems like CentOS 6.9?

A1: This error stems from a mismatch in supported key exchange algorithms between the SSH client and server. Older SSH servers like those in CentOS 6.9 rely on outdated algorithms like ssh-rsa and ssh-dss, which are often disabled or deprecated in modern SSH clients due to known vulnerabilities. Newer clients prioritize stronger, more secure algorithms like ecdsa or ed25519.

Q2: Why do newer SSH clients disable older key exchange algorithms like ssh-rsa and ssh-dss?

A2: ssh-rsa and ssh-dss have been found to have vulnerabilities that could potentially be exploited by attackers. For instance, ssh-rsa is susceptible to attacks if weak keys are generated, and ssh-dss has inherent weaknesses in its design. Disabling these algorithms enhances the security of SSH connections.

Q3: The article mentions a temporary fix using -oHostKeyAlgorithms=+ssh-dss. Explain how this command works and why it’s considered a temporary solution.

A3: This command forces the SSH client to accept ssh-dss as a valid key exchange algorithm, even if it’s disabled by default. It’s a workaround, not a solution, as it lowers the security of the connection. ssh-dss is less secure and shouldn’t be relied upon for long-term use.

Q4: What are the security implications of modifying the client-side SSH configuration (~/.ssh/config) to permanently accept ssh-dss?

A4: While convenient, permanently accepting ssh-dss on the client-side weakens the security posture of your SSH connections. It makes the client susceptible to attacks exploiting the vulnerabilities of ssh-dss. This approach should be used cautiously and only as a last resort if upgrading the server is not feasible.

Q5: Describe the recommended server-side fix for this issue and explain why it’s preferable to client-side workarounds.

A5: The recommended fix involves updating the SSH server’s configuration (/etc/ssh/sshd_config) to use more secure key exchange algorithms like ecdsa or ed25519. This involves:

1. Commenting out lines using ssh-dss or ssh-rsa in the HostKey directive.
2. Adding a line for HostKey /etc/ssh/ssh_host_ecdsa_key or HostKey /etc/ssh/ssh_host_ed25519_key.
3. Generating the necessary keys using ssh-keygen if they don’t exist.
4. Restarting the SSH daemon (service sshd restart).

This approach is preferable because it addresses the root cause of the issue by upgrading the server’s security, rather than simply working around it on the client-side.

Q6: Why is upgrading CentOS to a newer version considered the best long-term solution?

A6: Upgrading CentOS provides multiple benefits:

• Enhanced Security: Newer OpenSSH versions in updated CentOS distributions have stronger default algorithms, improving the overall security of SSH connections.
• Continued Maintenance: Upgrading ensures continued access to security updates and bug fixes, essential for maintaining a secure and stable system.
• Compatibility: Newer CentOS versions are compatible with modern SSH clients, eliminating the need for workarounds or compromises on security.

Q7: Can you explain the concept of “host keys” in the context of SSH and their role in preventing man-in-the-middle attacks?

A7: When an SSH client connects to a server for the first time, the server presents a unique cryptographic key called the “host key.” The client stores this key and verifies it on subsequent connections. This process ensures that the client is always communicating with the same server and not an imposter trying to intercept the connection. This mechanism is crucial in preventing man-in-the-middle attacks, where an attacker could potentially eavesdrop on or manipulate the communication between the client and the server.