SSH No Matching Host Key Type Found With Every Cause

After upgrading a laptop to a current OS, a connection to an older Linux server or appliance fails with Unable to negotiate with 192.0.2.5 port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss. The server proves its identity with a host key, and the only types it offers are ones the client no longer accepts. It is a sibling of no matching key exchange method. The commands assume an OpenSSH 9.x client.

What was disabled and why

ssh -Q key
ssh -Q HostKeyAlgorithms 2>/dev/null | head
ssh -V

ssh-ed25519
ecdsa-sha2-nistp256
rsa-sha2-256
rsa-sha2-512
[email protected]
OpenSSH_9.8p1, OpenSSL 3.0.15

The name ssh-rsa refers to RSA keys signed with SHA-1, a hash with practical collision attacks; OpenSSH 8.8 (2021) disabled it by default. The same RSA key can sign with SHA-2 (rsa-sha2-256 or -512), so a server with a recent OpenSSH needs no new key. DSA (ssh-dss) was removed earlier because the keys are weak and limited to 1024 bits. The example version numbers will differ on your machine.

Fix on the server

sudo ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ''
echo 'HostKey /etc/ssh/ssh_host_ed25519_key' | sudo tee -a /etc/ssh/sshd_config
sudo sshd -t && sudo systemctl reload ssh
ssh-keyscan -t ed25519 localhost

If the server runs OpenSSH 7.2 or newer, it already supports SHA-2 RSA signatures once the client asks for them, so the error means the offer shown is old. Upgrade OpenSSH if possible. Adding an Ed25519 host key gives modern clients something to accept. Clients that saved the old key will then see a new key, and need to update known_hosts after verifying the fingerprint (REMOTE HOST IDENTIFICATION HAS CHANGED). Generating keys is covered in generating SSH keys.

Stopgap on the client

Host legacy-nas
    HostName 192.0.2.5
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

ssh -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa [email protected]

The first option lets the client accept the server's SHA-1 host key; the second allows your own RSA key to authenticate with SHA-1 when the old server cannot verify SHA-2 signatures. Older releases call the second option PubkeyAcceptedKeyTypes. Both use + so the safe defaults stay. Keep it per host, and consider it a ticket to schedule the upgrade.

If the server offers only DSA

Their offer: ssh-dss

DSA is removed from OpenSSH clients and servers entirely in recent versions, so re-enabling it needs a build that still includes it. The only durable fix is generating a new host key on the server, which can be done on any distribution still receiving updates. For devices that cannot be updated, an alternative is reaching them through a modern jump host that is allowed to speak the old protocol, limiting exposure: see ProxyJump.

Client keys versus host keys

Do not confuse the two. The host key authenticates the server to you; your key authenticates you to the server. A related message, Permission denied (publickey) after you allowed ssh-rsa, can mean your own old RSA key is refused by a newer server; generate an Ed25519 key. The steps for that debugging are in the permission denied post.

What the host key is for

The host key is the server's long-term identity. The client stores it after the first trusted connection and compares it on every later one. The negotiation we are looking at happens before that comparison: the client says which signature algorithms it accepts for host keys, and the server must present a key that can sign with one of them. If the server's only keys are of types the client has disabled, the client refuses to continue, because accepting a key signed with a broken algorithm would defeat the purpose of the identity check.

That is why the error is about types and not about trust. The key might be the right one, and the machine might be the one you want. The problem is only the strength of the signature scheme used to prove it. An RSA key itself is acceptable; it is the SHA-1 signature that was retired, and servers with a recent enough OpenSSH can already sign RSA keys with SHA-2 when asked. In many cases the actual fix is an update to a server that has been running unchanged for years.

Which side to change first

Prefer changing the server when you control it, because fixing the server fixes every client at once, while loosening a client fixes one machine and weakens it. If the server is within reach, check its OpenSSH version, update the package and, if needed, generate an Ed25519 host key and list it in the daemon configuration. Keep the old keys until clients have learned the new one, so existing known-hosts entries continue to match for a while and the change causes a warning only for those who connected over the weaker type.

If the server is a device you cannot update, record that fact. A note in the inventory saying the device requires legacy SHA-1 signatures, with an owner and a replacement date, turns a surprise into a managed risk. Connect to it from a machine that is itself hardened, use a jump host in the same network segment, and keep your general-purpose workstation configuration free of weak settings.

Verifying you reach the right machine

Relaxing algorithms does not relax the need to verify the host. When the connection succeeds with the override, compare the fingerprint it presents with one you obtained through another channel, such as the device's console or its management interface. ssh-keygen -lf on a key file or ssh-keyscan output gives the fingerprint to compare. If you cannot verify it, treat the first connection as untrusted and do not send credentials you cannot afford to lose over it.

Cleaning up after the migration

When the server is updated, remove the client overrides and the old known-hosts entries for that address, reconnect and verify the new fingerprint. Check ssh -v to confirm the connection now uses a modern key type and key exchange. Search your configuration files for leftover +ssh-rsa lines with grep -rn 'ssh-rsa' ~/.ssh /etc/ssh, and delete them. A temporary exception that stays in place for years quietly turns into a standing policy.

A short decision guide

If the server is under your control and runs a current system, update OpenSSH and stop there. If it runs an old release that still receives updates from its vendor, apply the update and add an Ed25519 host key. If it is a device on a management network with no update path, scope a per-host client exception, verify the fingerprint through another channel and schedule its replacement. If it is exposed to the internet and cannot be updated, put it behind a VPN or bastion first and only then think about the exception. In every branch, the exception is the last step and not the first, and it always carries a date for removal.

Where this does not apply

Do not copy the override into a shared configuration file or a golden image; it silently weakens every future connection. Check the host key types a server really offers with ssh-keyscan host. Cloud-provider images are current and rarely hit this; the usual victims are old network gear, long-lived appliances and unmaintained servers. See the OpenSSH 8.8 release notes and the ssh_config HostKeyAlgorithms description.