No matching host key type found. Their offer: ssh-rsa (how to fix it)

Your SSH client and the server could not agree on a host key algorithm, so the connection ends before you get a login prompt. Almost always the client is OpenSSH 8.8 or newer and the server is old enough that it can only sign with ssh-rsa (RSA with SHA-1), which modern clients refuse by default:

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

Why OpenSSH 8.8 and later refuse ssh-rsa

OpenSSH 8.8, released on 26 September 2021, disabled RSA signatures that use the SHA-1 hash by default. SHA-1 is broken: the release notes cite a chosen-prefix collision that costs less than USD 50,000. In the SSH protocol, that signature scheme is called ssh-rsa, which is also the name of the RSA key type. This is the source of most of the confusion.

Your RSA keys are fine. One RSA key can sign three ways: rsa-sha2-512, rsa-sha2-256 and the old ssh-rsa. OpenSSH has supported the two SHA-2 variants since version 7.2 (February 2016), and Dropbear since 2020.79 (June 2020), with no change to the key itself. A server from before those releases can only produce the SHA-1 signature, so its offer is literally ssh-rsa, and a client from 8.8 on has nothing it is willing to accept.

“Their offer” is the list the other side sent. When you connect to an old box, it is the server’s host key list. Your own client’s list is printed by ssh -Q HostKeyAlgorithms (everything it can do) and ssh -G host (the list configured for that host). With a + value, ssh still moves the algorithms of a key already in known_hosts to the front when it connects, so the algorithm it really agreed on is the kex: host key algorithm line in ssh -v output.

Which servers trigger it? An SSH server that predates RSA/SHA-2 support and has no ECDSA or Ed25519 host key to offer instead. If it has one, your client simply picks that key, and the old server bites later, at login with an RSA user key. The OpenSSH versions below are the ones those releases shipped, read from the distribution archives and packaging:

The rest are mostly network switches, routers, old NAS boxes, out-of-band management controllers and embedded devices running an old OpenSSH, an old Dropbear or a vendor’s own SSH stack. They often offer ssh-rsa,ssh-dss and nothing else.

Temporary fix for one host: HostKeyAlgorithms +ssh-rsa

Test it on a single command first. This is the run from our test, before and after:

$ ssh user@192.0.2.20
Unable to negotiate with 192.0.2.20 port 22: no matching host key type found. Their offer: ssh-rsa

$ ssh -o HostKeyAlgorithms=+ssh-rsa user@192.0.2.20
Warning: Permanently added '192.0.2.20' (RSA) to the list of known hosts.
user@192.0.2.20: Permission denied (publickey).

The negotiation passes and you reach authentication. Our test server accepted no logins at all, hence the refusal; against a real server, this is where you get your password prompt or your key is checked. scp and sftp take the same -o option, for example scp -o HostKeyAlgorithms=+ssh-rsa file user@192.0.2.20:/tmp/.

Why the plus sign matters

Without the +, the value replaces the whole list, so this host can only ever use SHA-1 signatures, even after the server learns something better. With it, ssh-rsa is appended as the last resort. ssh -G prints the result without connecting:

$ ssh -G -o HostKeyAlgorithms=ssh-rsa oldbox | grep -i ^hostkeyalgorithms
hostkeyalgorithms ssh-rsa

$ ssh -G -o HostKeyAlgorithms=+ssh-rsa oldbox | grep -i ^hostkeyalgorithms
hostkeyalgorithms ssh-ed25519-cert-v01@openssh.com,...,ssh-ed25519,ecdsa-sha2-nistp256,...,rsa-sha2-512,rsa-sha2-256,ssh-rsa

Make it permanent for that host in ~/.ssh/config

Put the override in a block that matches only the old machine, in your SSH config file (~/.ssh/config, on Windows %USERPROFILE%\.ssh\config):

Host oldbox
    HostName 192.0.2.20
    User admin
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

Now ssh oldbox works, and so do scp, sftp, rsync and git, because they all run the same ssh client and read the same file. Keep a few things in mind:

• Host matches the name you type. If you sometimes connect by IP address, list both: Host oldbox 192.0.2.20.
• For a whole management network, use a wildcard: Host 10.10.0.*. CIDR notation does not work here. In our test, a Host 192.168.0.0/24 block did not apply to 192.168.0.5 at all.
• Never put it under Host *. That quietly weakens every connection you make, including the ones to servers that would happily use SHA-2.
• Spelling counts. A typo such as KeyAlgorithms stops ssh with Bad configuration option: keyalgorithms, and a name your client does not know gives Bad key types.

Check the configured lists with ssh -G oldbox | grep -i algorithms: the hostkeyalgorithms and pubkeyacceptedalgorithms lines should end in ssh-rsa, and for any other host they should not.

GIT_SSH_COMMAND='ssh -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa' \
  git clone ssh://git@192.0.2.20/srv/repo.git

Permission denied (publickey) with an RSA key

Fixing the host key only gets you to authentication. If you log in with an RSA key, the same rule applies a second time: the client will not sign with SHA-1 for the old server, and ssh -v shows a line containing no mutual signature algorithm before it falls back to a password or gives up with Permission denied (publickey). That is what the second line of the config block above is for:

    PubkeyAcceptedAlgorithms +ssh-rsa

Clients older than OpenSSH 8.5 do not know that keyword and stop with “Bad configuration option”. They know it as PubkeyAcceptedKeyTypes, which newer clients still accept as an alias, so use the old name in a config file that several machines share. An Ed25519 user key does not help on a server that cannot verify Ed25519; on one that can, it removes this half of the problem. If the RSA key still fails after this, the cause is something else, and Permission denied (publickey) goes through the other checks.

no matching key exchange method found

This is the twin error, one step earlier in the handshake. Before host keys are compared, both sides agree on a key exchange (KEX) method, and old servers often offer only SHA-1 Diffie-Hellman variants that modern clients no longer propose. Our test server, limited to diffie-hellman-group14-sha1:

$ ssh user@192.0.2.20
Unable to negotiate with 192.0.2.20 port 22: no matching key exchange method found. Their offer: diffie-hellman-group14-sha1,kex-strict-s-v00@openssh.com

$ ssh -o KexAlgorithms=+diffie-hellman-group14-sha1 user@192.0.2.20
user@192.0.2.20: Permission denied (publickey).    # past the handshake; the test server allows no logins

Copy the method from “Their offer” into KexAlgorithms, with the plus sign. Ignore a kex-strict-s-v00@openssh.com entry if you see one: it is a marker for the strict key exchange OpenSSH 9.6 added against the Terrapin attack, not a method you can choose, and a truly old server does not send it. The methods you meet on old devices:

The keyword is KexAlgorithms. Putting a key exchange method into HostKeyAlgorithms is a common mistake, and ssh answers it with Bad key types. Fix one error, connect again, and read the next one: very old gear can need a host key, a KEX and a cipher override at the same time. The same pattern covers no matching cipher found (add the offered name to Ciphers, for example Ciphers +aes128-cbc) and no matching MAC found (MACs).

RHEL 9, Rocky, Alma: error in libcrypto after +ssh-rsa

On RHEL 9 and its rebuilds (Rocky Linux 9, AlmaLinux 9, Oracle Linux 9), the override often just swaps one error for another. Your ssh now allows ssh-rsa, but the system-wide crypto policy DEFAULT also forbids SHA-1 signatures inside OpenSSL, so the check fails one layer lower:

$ ssh -o HostKeyAlgorithms=+ssh-rsa user@192.0.2.20
ssh_dispatch_run_fatal: Connection to 192.0.2.20 port 22: error in libcrypto

Check the active policy and allow SHA-1 again. Keep the +ssh-rsa lines in ~/.ssh/config as well; the policy change alone does not bring ssh-rsa back.

update-crypto-policies --show
# DEFAULT
sudo update-crypto-policies --set DEFAULT:SHA1
# back to normal once the old server is fixed:
# sudo update-crypto-policies --set DEFAULT

DEFAULT:SHA1 adds only SHA-1 back; LEGACY works too but loosens much more. Either way the change is system-wide, for every program that uses the system crypto libraries, not only for ssh. New ssh commands pick it up at once; Red Hat’s documentation asks for a reboot so that running services follow as well. Fedora uses the same update-crypto-policies tool, so if the same libcrypto error shows up there, the same commands apply. If you would rather not loosen the whole machine, reach the old device from another system instead.

When the offer is ssh-dss only

ssh-dss is DSA, disabled by default since OpenSSH 7.0. Up to OpenSSH 9.7, HostKeyAlgorithms +ssh-dss works the same way as the RSA override. From 9.8, DSA is off at compile time unless the build enables it, and OpenSSH 10.0 removed it completely, so there is nothing left to switch on. Check your client:

ssh -Q HostKeyAlgorithms | grep dss
# ssh-dss
# ssh-dss-cert-v01@openssh.com     <- still there, +ssh-dss will work
# (no output)                      <- gone, no option brings it back

With no output, the device has to change: a firmware update, or an RSA or newer key generated in its admin interface. Until then, you can reach it from an older system that still has DSA, such as a management host you keep for that gear.

Permanent fix on the old server: an Ed25519 host key

If you administer the old machine, stop weakening clients and give it a host key every modern client accepts. OpenSSH supports Ed25519 from version 6.5 and ECDSA from 5.7. Check the version with ssh -V on the server (or read the “remote software version” line in ssh -v output), then, from a session you keep open:

ls /etc/ssh/ssh_host_*_key        # an ed25519 or ecdsa file may already exist: then skip to HostKey
ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ''
# "unknown key type ed25519"? The server predates 6.5; use ECDSA instead:
# ssh-keygen -t ecdsa -b 256 -f /etc/ssh/ssh_host_ecdsa_key -N ''

grep -i '^HostKey' /etc/ssh/sshd_config
# If HostKey lines are listed, add the new one:
#   HostKey /etc/ssh/ssh_host_ed25519_key

sshd -t && service ssh restart     # the service is called sshd on CentOS

If ssh-keygen rejects ecdsa as well, the server predates OpenSSH 5.7 (unless the vendor backported ECDSA, as Red Hat did in later RHEL 6 updates). Then no new host key type helps, and only an upgrade or the client override remains.

Now log in once with the override still in place. Because +ssh-rsa only appends, ssh moves the algorithms for the RSA key already in your known_hosts to the front, so it keeps using ssh-rsa and shows no warning. With a client from OpenSSH 8.5 on and a server from 6.8 on, the server also announces its new Ed25519 key after login, and your client stores it by itself (UpdateHostKeys, on by default when you use the standard known_hosts file).

ssh oldbox                                  # override still in ~/.ssh/config; log out again
ssh-keygen -F 192.0.2.20 | grep -c ed25519  # 1 = the Ed25519 key is stored

Then delete the HostKeyAlgorithms +ssh-rsa line for that host and check that ssh picks the new key:

ssh -v oldbox exit 2>&1 | grep 'host key algorithm'
# debug1: kex: host key algorithm: ssh-ed25519

If your client is older than 8.5, UpdateHostKeys is off, or you removed the override first, ssh meets the Ed25519 key without knowing it. Your known_hosts holds only the old RSA key, and OpenSSH reports a changed host:

@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
...
The fingerprint for the ED25519 key sent by the remote host is
SHA256:6/sfI2LuUUAiT9GDBYwuHDdHCG/6fPGWKmMGeXOeTaE.
...
Offending RSA key in /home/you/.ssh/known_hosts:1
Host key verification failed.

Here you caused it yourself, but still compare the fingerprint with ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub on the server before you trust it. Then remove the old entry and reconnect, as described in Host key verification failed:

ssh-keygen -R 192.0.2.20
ssh oldbox      # compare the fingerprint shown, then answer yes

On Dropbear, the same idea works with dropbearkey. Ed25519 host keys arrived in 2020.79, the same release that added RSA/SHA-2, so on an older Dropbear generate ECDSA (supported since 2013.62) and pass the file to dropbear -r:

dropbearkey -t ecdsa -f /etc/dropbear/dropbear_ecdsa_host_key

A new host key is a patch, not a cure. A server that cannot sign with SHA-2 runs an SSH version that stopped getting fixes years ago; moving the service to a current release is the fix that lasts.

When you run the server and the client is the old one

The error also appears the other way round. A modern sshd rejects an old client (an ancient SSH library in a backup tool, a script on an old box), and the server log shows the client’s list as “their offer”:

Unable to negotiate with 198.51.100.7 port 51522: no matching host key type found. Their offer: ssh-rsa,ssh-dss [preauth]

Update the client first. If you cannot, the stopgap goes in the server’s /etc/ssh/sshd_config. HostKeyAlgorithms cannot go inside a Match block (sshd -t stops with “Directive 'HostKeyAlgorithms' is not allowed within a Match block”), so it has to be global; with the +, modern clients still pick a SHA-2 or Ed25519 signature. PubkeyAcceptedAlgorithms is allowed in Match, so limit that one to the old client:

HostKeyAlgorithms +ssh-rsa

# at the end of the file
Match Address 198.51.100.7
    PubkeyAcceptedAlgorithms +ssh-rsa

Then run sudo sshd -t && sudo systemctl restart ssh (the unit is sshd on Rocky, Alma and RHEL).

Switches, routers and old NAS boxes

Often the old side is not a Linux server at all but a switch, router or NAS, and the error appears after your laptop updated OpenSSH. In that case:

• Look for a firmware update first. Newer firmware often adds RSA/SHA-2 or a newer key type and makes every override unnecessary.
• Give the devices one Host block with a wildcard that only matches them, holding every override they need, and nothing else.
• Behind a jump host, the override belongs in the device’s block, not the jump host’s. With ProxyJump, your own client negotiates with the device through the tunnel; see the jump host section of our tunneling guide.

Host 10.10.0.*
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa
    KexAlgorithms +diffie-hellman-group14-sha1

Every negotiation error at a glance

If the old machine is a server you still depend on, the cleanest way out is a fresh system with a current SSH, and moving the service across. A Standard KVM VPS comes with a current distribution and a VNC console in the panel, so you can still get in through the console when sshd does not come back after an SSH change.

Frequently asked