🚨 Security Error Guide: 'no matching host key type found' After SSH Hardening

Exact Error Message

After tightening the SSH server’s allowed algorithms, a previously working client can no longer connect:

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

A closely related key-exchange variant appears when KexAlgorithms no longer overlap:

Unable to negotiate with 10.0.4.22 port 22: no matching key exchange method found.
Their offer: diffie-hellman-group14-sha1

What the Error Means

SSH negotiates a host key type, a key-exchange (KEX) algorithm, and a cipher during the handshake. Both sides advertise a list, and they must share at least one entry. “no matching host key type found” means the server’s HostKeyAlgorithms (or PubkeyAcceptedAlgorithms) and the client’s accepted set have an empty intersection — typically because hardening removed ssh-rsa (SHA-1) and the peer only offers that.

This is a defensive-hardening side effect. Disabling SHA-1 host keys and legacy KEX methods is correct, but an older client, a network appliance, or a jump host that was never updated still only speaks the removed algorithm. The fix is to confirm the overlap gap, update the lagging peer where possible, and only narrowly re-enable a legacy algorithm as a temporary bridge.

Common Causes

• ssh-rsa removed from the server. Modern OpenSSH deprecated the SHA-1 ssh-rsa signature; a hardened sshd_config drops it, but legacy clients offer nothing else.
• KexAlgorithms pruned too far. Removing diffie-hellman-group14-sha1 and group-exchange-sha1 leaves no common KEX with an old client.
• Old client OpenSSH version. A client from a long-term-support image predates the modern rsa-sha2-256/512 signatures and cannot use the server’s RSA key safely.
• Network appliance or device. Switches, load balancers, or SFTP appliances often support only the legacy algorithms now disabled.
• Client config also restricted. A hardened client ~/.ssh/config or system ssh_config narrowed its own algorithm list, so the gap is on the client side.
• Host key type not generated. The server offers only an Ed25519 key, but the client’s policy excludes Ed25519.

How to Reproduce the Error

On a test server, restrict host key algorithms to exclude ssh-rsa, then connect from a client that forces only ssh-rsa:

# Client forces the now-disallowed type to simulate a legacy peer
ssh -o HostKeyAlgorithms=ssh-rsa deploy@10.0.4.22

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

Force a legacy KEX to reproduce the key-exchange variant:

ssh -o KexAlgorithms=diffie-hellman-group14-sha1 deploy@10.0.4.22

Diagnostic Commands

These read-only checks reveal exactly what each side offers, without weakening the server.

# What host key types and algorithms does the server actually offer?
ssh -vv deploy@10.0.4.22 2>&1 | grep -iE 'host key algorithms|kex|peer server'

# Probe the server's effective sshd config (read-only dump)
sudo sshd -T | grep -iE 'hostkeyalgorithms|kexalgorithms|pubkeyacceptedalgorithms|ciphers'

# List the server's actual host keys and their types
ls -l /etc/ssh/ssh_host_*_key.pub
for k in /etc/ssh/ssh_host_*_key.pub; do ssh-keygen -lf "$k"; done

# Use openssl/ssh to see the negotiated/offered set from the client side
ssh -Q HostKeyAlgorithms
ssh -Q kex

# Confirm the daemon is listening and which port
ss -tlnp | grep ':22'

# Read the server-side negotiation failure
sudo journalctl -u sshd --since '10 min ago' | grep -iE 'no matching|kex|userauth'

sudo sshd -T prints the fully resolved configuration, which is the authoritative source for what the server will negotiate.

Step-by-Step Resolution

1. Capture both offers. Run ssh -vv from the failing client and read the “host key algorithms” lines. The error’s “Their offer” tells you what the peer supports; sshd -T tells you what the server accepts. The gap is the root cause.

2. Prefer fixing the lagging peer. If the client is an old OpenSSH, upgrade it so it supports rsa-sha2-256/rsa-sha2-512 or Ed25519. This closes the gap without re-enabling SHA-1.

3. Ensure the server has a modern host key. If it only has an RSA key, generate an Ed25519 key and let sshd offer it:

   sudo ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ''

   Ensure HostKey /etc/ssh/ssh_host_ed25519_key is present, then reload sshd.

4. Re-enable a legacy algorithm only as a temporary, scoped bridge for a peer you cannot upgrade. Append (do not replace) to the existing set, and plan to remove it:

   # In a drop-in like /etc/ssh/sshd_config.d/legacy-bridge.conf
   HostKeyAlgorithms +ssh-rsa
   PubkeyAcceptedAlgorithms +ssh-rsa

5. Validate the config before reloading so a typo does not lock you out:

   sudo sshd -t && sudo systemctl reload sshd

6. Re-test from the affected client and confirm via ssh -vv that a modern algorithm is negotiated where possible.

Prevention and Best Practices

• Inventory clients and appliances before pruning algorithms; identify anything stuck on SHA-1 or legacy KEX first.
• Roll out host-key and algorithm changes through a drop-in under /etc/ssh/sshd_config.d/ so they are easy to review and revert.
• Always generate an Ed25519 host key alongside RSA so modern clients have a strong option.
• Use the +/- syntax to adjust algorithm lists relative to the defaults rather than hardcoding a full list that drifts over time.
• Track any temporary legacy re-enablement with an expiry date and an owner.

Related Errors

• Host key verification failed — a changed/stale known_hosts entry, a different failure mode covered in the security hardening guides.
• no matching cipher found — the cipher list, not the host key, has no overlap.
• no matching MAC found — the MAC algorithm intersection is empty after hardening.
• Permission denied (publickey) — a separate authentication failure, not negotiation.

Frequently Asked Questions

Is ssh-rsa the same as an RSA key being banned? No. ssh-rsa is the SHA-1 signature algorithm. The same RSA key can still be used with rsa-sha2-256/rsa-sha2-512. Only the SHA-1 signing is deprecated.

The client is an appliance I cannot upgrade. What now? Add a scoped HostKeyAlgorithms +ssh-rsa drop-in as a temporary bridge, restrict that exposure, and pressure the vendor for a firmware update.

Why did it break only for one client? Other clients already supported the modern algorithms the server still offers; only the lagging peer relied on the removed one.

How do I see exactly what my server offers? sudo sshd -T prints the resolved config, and ssh -vv from a client shows the negotiated lists in real time.

Will adding Ed25519 break existing clients? No. Adding a host key type expands what the server offers; existing clients keep negotiating whatever they already used.