Fix SSH 'no matching key exchange method found'

What "no matching key exchange method found" means

The SSH error no matching key exchange method found means the client and the server have no key exchange method in common, so the connection stops before login. To fix it, read the Their offer: list and pick one name from it. Then add that name to the matching directive on the side that lacks it. Keep that change to one host or one port, because a global change weakens every connection.

On Ubuntu 26.04 the error usually has one of two causes. Your new client is talking to an old network device or server. Or an old client is talking to your new server. Both cases use the same algorithm lists, but the fix lives on a different side.

Which side is old? The two directions of this error

A new client talking to an old device. You run ssh on Ubuntu 26.04 and connect to an old switch or a server that nobody has updated. Your terminal prints the Unable to negotiate line. The fix belongs on your client, in one Host block in ~/.ssh/config.

An old client talking to a new server. A legacy Unix machine connects to your Ubuntu 26.04 server and fails. The old client prints its own error text, which may look nothing like OpenSSH's. Your server logs the real reason. Read it with:

sudo journalctl -u ssh --since "1 hour ago" | grep -i "unable to negotiate"

The fix for this case belongs on the server, and it is harder to scope there, as you will see below.

One rule decides how to read both cases: Their offer: is always the other side's list. In your terminal it is the server's list. In the server log it is the client's list.

What changed in Ubuntu 26.04 and OpenSSH 10

Ubuntu 26.04 LTS was released on 23 April 2026 and ships OpenSSH 10.2p1. Ubuntu 24.04 LTS ships OpenSSH 9.6p1. Ubuntu's own 26.04 release notes say this upgrade "includes major changes". Check what you run before you change anything:

ssh -V
apt-cache policy openssh-server

The changes behind this error came in several OpenSSH releases:

• OpenSSH 8.8 disabled RSA signatures that use SHA-1 by default. That is the ssh-rsa signature algorithm. Ubuntu 24.04 already has this change, so it is not new in 26.04.
• OpenSSH 10.0, released on 9 April 2025, removed DSA (ssh-dss) completely.
• OpenSSH 10.0 also turned off finite-field Diffie-Hellman key exchange in sshd by default. These are the diffie-hellman-group* methods, also called modp. The client still offers some of them.
• OpenSSH 10.0 made the hybrid post-quantum method mlkem768x25519-sha256 the default key agreement. OpenSSH 10.1 then added a client warning for connections that do not use post-quantum key exchange, controlled by a new WarnWeakCrypto option that is on by default.

The post-quantum part has its own explainer on what post-quantum SSH changed, and the warning has a separate guide to the non-post-quantum key exchange warning. If you are still planning the move, the guide to upgrading Ubuntu 24.04 to 26.04 covers the rest of the jump.

How to read the "Their offer" list

OpenSSH builds the error from three parts. It starts with Unable to negotiate with and the peer's address. Then comes one reason. Then comes Their offer: and the peer's list for that one class of algorithm. The address part differs between versions, so match on the reason, not on the whole line.

The reason tells you which directive to change. Each directive governs a different list:

• no matching key exchange method found means KexAlgorithms. Key exchange is how the two sides agree on session keys. Names look like curve25519-sha256, mlkem768x25519-sha256 or diffie-hellman-group14-sha1.
• no matching host key type found means HostKeyAlgorithms. This list holds the signature algorithms the server may use to prove its identity with its host key. Names look like ssh-ed25519, rsa-sha2-512, ssh-rsa or ssh-dss.
• no matching cipher found means Ciphers, the encryption algorithms for the session itself.
• no matching MAC found means MACs. A MAC (message authentication code) protects each packet against changes on the way.

One more list causes trouble, but it never prints Unable to negotiate. PubkeyAcceptedAlgorithms decides which signature algorithms the server accepts for a user's key at login. The server checks it after negotiation, so a mismatch shows up as a login failure. An old client whose RSA user key can only sign with ssh-rsa fails this way against a modern server. That failure looks like any other key problem, which the guide to fixing Permission denied (publickey) walks through.

The error reports one class at a time. Fix the key exchange, and the next attempt may stop at the host key type. The lab below shows exactly that.

Are the old KeyTypes option names still accepted?

Older guides use PubkeyAcceptedKeyTypes and HostbasedKeyTypes. OpenSSH 10.2 still accepts them. The 10.2 source maps them to PubkeyAcceptedAlgorithms and HostbasedAcceptedAlgorithms and marks them obsolete. The current man pages describe only the new names, apart from one note that HostbasedAcceptedAlgorithms was formerly named HostbasedAcceptedKeyTypes. Use the new names in anything you write today. After you edit an old file, run sudo sshd -t to check that it still parses.

Ask the binary what it can speak: ssh -Q and sshd -T

Before you add a name, check that your OpenSSH build supports it at all. ssh -Q lists what the binary can do. It also accepts any config keyword that takes an algorithm list, so you can ask with the directive's own name:

ssh -Q kex
ssh -Q key
ssh -Q KexAlgorithms
ssh -Q HostKeyAlgorithms
ssh -Q PubkeyAcceptedAlgorithms
ssh -Q cipher
ssh -Q mac

If a name from Their offer: is missing from this output, your build cannot speak it. No config line adds it back. Check DSA on your own machine with ssh -Q key | grep dss. No output means this client has no DSA support.

ssh -Q shows what is possible. To see what sshd will actually offer, after it reads every config file and drop-in, use the extended test mode:

sudo sshd -T | grep -E '^(kexalgorithms|hostkeyalgorithms|pubkeyacceptedalgorithms|ciphers|macs) '

On the client, ssh -G answers the same question for one destination. It prints the effective config and does not connect:

ssh -G old-switch | grep -E '^(kexalgorithms|hostkeyalgorithms|pubkeyacceptedalgorithms) '

Run both commands on 24.04 and on 26.04 and compare them. The modp methods that OpenSSH 10.0 turned off in sshd are the diffie-hellman-group names. Your own output is a better source than a default list copied from a web page, because package updates change it.

Why ssh-rsa can never go in KexAlgorithms

ssh-rsa is the most common name in these errors, and KexAlgorithms +ssh-rsa is the most common wrong fix. ssh-rsa is a key type and a signature algorithm. It never names a key exchange method. It belongs in HostKeyAlgorithms when the server proves its identity with it, or in PubkeyAcceptedAlgorithms when a user's key signs with it. Key exchange names are a different family, such as curve25519-sha256 or diffie-hellman-group14-sha1.

Compare the two lists and you will find ssh-rsa in only one of them:

ssh -Q kex | grep ssh-rsa
ssh -Q key | grep ssh-rsa

The first command prints nothing. So KexAlgorithms +ssh-rsa cannot work: ssh refuses the option before it connects, and sshd -t refuses it in a server file. When the reason is no matching host key type found and Their offer: says ssh-rsa, the fix is HostKeyAlgorithms +ssh-rsa.

Reproduce the failure safely on 127.0.0.1

Build a small lab first. A throwaway sshd on a high port, with a deliberately old algorithm list, reproduces both directions. It never touches your real SSH service. Every list in the lab is set explicitly, so the steps behave the same way on 24.04 and 26.04.

sshd needs its privilege-separation directory, /run/sshd. It must be owned by root and must not be writable by group or others. It already exists on any box where the ssh service has run. Create it if it is missing, then build the lab:

sudo mkdir -p /run/sshd
sudo install -d -m 700 /tmp/kexlab
sudo ssh-keygen -q -t rsa -b 3072 -N '' -f /tmp/kexlab/host_rsa
sudo tee /tmp/kexlab/sshd_config >/dev/null <<'EOF'
ListenAddress 127.0.0.1
HostKey /tmp/kexlab/host_rsa
PidFile /tmp/kexlab/sshd.pid
KexAlgorithms diffie-hellman-group14-sha256
HostKeyAlgorithms ssh-rsa
EOF
sudo /usr/sbin/sshd -t -f /tmp/kexlab/sshd_config && echo config ok

This file plays an old device. It offers only one classic Diffie-Hellman key exchange, and only SHA-1 RSA host key signatures. Start it in a first terminal. -d is debug mode: sshd stays in the foreground, prints its log to the terminal, and exits after one connection. -p 2222 overrides any Port line in the file. It does not override a port written into a ListenAddress line, such as 127.0.0.1:22, because sshd gives that port priority over the command line. The lab's ListenAddress names no port, so the server listens on 2222.

sudo /usr/sbin/sshd -d -f /tmp/kexlab/sshd_config -p 2222

In a second terminal, define a short helper. BatchMode=yes stops ssh from asking for a password. The two host key options keep the lab key out of your known_hosts file.

lab() { ssh -p 2222 -o BatchMode=yes -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null "$@" 127.0.0.1; }
lab -o KexAlgorithms=curve25519-sha256

The client offers only curve25519-sha256, so the attempt fails with no matching key exchange method found. In your terminal, Their offer: holds the server's list, which is the one method in the lab file. The first terminal shows the same failure from the server's side, and there Their offer: is the client's list. Start the server again after each attempt, because -d handles only one connection.

Now add the offered name and try again:

lab -o KexAlgorithms=curve25519-sha256,diffie-hellman-group14-sha256

Key exchange now succeeds, and the next class fails with no matching host key type found. Their offer: now holds ssh-rsa. Your client supports ssh-rsa, but the OpenSSH 8.8 change removed it from the default HostKeyAlgorithms. Add it back with the + prefix, which appends to the default list instead of replacing it:

lab -o KexAlgorithms=curve25519-sha256,diffie-hellman-group14-sha256 -o HostKeyAlgorithms=+ssh-rsa

Negotiation now completes and the attempt reaches login. You get a permission error, or a shell if your own key is in ~/.ssh/authorized_keys. Either result is the success signal here, because it means every algorithm list found a match. On 26.04 the client may also warn that the connection does not use post-quantum key exchange, because diffie-hellman-group14-sha256 is a classic method.

Now flip the lab to the other direction. Rewrite the file so the server offers only curve25519-sha256, and let the client play the old side:

sudo tee /tmp/kexlab/sshd_config >/dev/null <<'EOF'
ListenAddress 127.0.0.1
HostKey /tmp/kexlab/host_rsa
PidFile /tmp/kexlab/sshd.pid
KexAlgorithms curve25519-sha256
EOF
sudo /usr/sbin/sshd -t -f /tmp/kexlab/sshd_config && sudo /usr/sbin/sshd -d -f /tmp/kexlab/sshd_config -p 2222

In the second terminal, run lab -o KexAlgorithms=diffie-hellman-group14-sha256. This time, watch the server terminal. It names the client's offer, which is what a 26.04 server writes to its journal when a real old client fails. Change the server line to KexAlgorithms curve25519-sha256,diffie-hellman-group14-sha256, run sshd -t, start the server, and connect again. The attempt now reaches login.

Fix a new client talking to an old device

Put the change in one Host block in ~/.ssh/config. Never put it under Host *, because that weakens every connection you make. ssh uses the first value it finds for each option, so put specific blocks above any Host * block.

Host old-switch
    HostName 192.0.2.10
    User admin
    KexAlgorithms +diffie-hellman-group14-sha1
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

Use the names from your own Their offer: line, not the ones above. Add only the lines you need. If only the key exchange failed, add only KexAlgorithms. Add PubkeyAcceptedAlgorithms +ssh-rsa only when you log in with an RSA key and the device cannot check the newer rsa-sha2-256 or rsa-sha2-512 signatures. This is the stopgap that the OpenSSH 8.8 release notes give for legacy hosts.

Use + rather than a full list. The client picks the first algorithm in its own list that the server also supports. An appended legacy name sits at the end, so ssh uses it only when nothing stronger matches. Check the result, then connect:

ssh -Q kex | grep diffie-hellman-group14-sha1
ssh -G old-switch | grep -E '^(kexalgorithms|hostkeyalgorithms) '
ssh old-switch

Fix an old client talking to a new Ubuntu 26.04 server

On the server, the rule is simple: run sudo sshd -t after every edit and before every restart. Ubuntu's own OpenSSH server guide says the same thing, and warns that a bad directive may stop sshd from starting. Keep a second SSH session open while you work.

The quick fix is a global drop-in file. Take the name from the client's offer in the server log, and check that the server's build lists it in ssh -Q kex:

echo 'KexAlgorithms +diffie-hellman-group14-sha1' | sudo tee /etc/ssh/sshd_config.d/60-legacy-kex.conf
sudo sshd -t && sudo systemctl restart ssh
sudo sshd -T | grep '^kexalgorithms '

sshd also uses the first value it finds. If another drop-in sets KexAlgorithms earlier, yours is ignored, and sshd -T shows you which one won.

This works, but it changes the main sshd for every client on the internet. A modern client still picks its first choice, so your own sessions keep strong key exchange. The cost is that any client offering nothing better can now use the old method.

Can a Match block limit KexAlgorithms to one IP address?

The obvious next idea is to allow the old method only for the legacy machine's address. Test it in the lab before you try it on a real server. Append a Match block to the lab file and run the test mode:

printf 'Match Address 127.0.0.1\n    KexAlgorithms +diffie-hellman-group14-sha256\n' | sudo tee -a /tmp/kexlab/sshd_config
sudo /usr/sbin/sshd -t -f /tmp/kexlab/sshd_config; echo "exit code: $?"

sshd -t rejects the file and exits with a non-zero code. The reason is in the OpenSSH 10.2 source: KexAlgorithms and HostKeyAlgorithms are marked global-only. The sshd_config man page also leaves them out of the list of keywords allowed after Match, and Ciphers and MACs are missing from that list too. The same line in the real /etc/ssh/sshd_config would fail the same check, which is why you test before you restart.

One of these lists does work inside Match: PubkeyAcceptedAlgorithms. If the old client's only problem is an RSA user key that signs with ssh-rsa, you can scope that fix to its address:

Match Address 203.0.113.50
    PubkeyAcceptedAlgorithms +ssh-rsa

When you are done with the lab, remove it with sudo rm -rf /tmp/kexlab.

Run a second sshd for the one legacy client

For key exchange and host key types, the honest scoped fix is a second sshd. It gets its own config file and its own port, and only the legacy machine's IP address can reach it. The main sshd on port 22 keeps its modern defaults.

List the host keys you have with ls /etc/ssh/ssh_host_*_key, then write the second config:

# /etc/ssh/sshd_config_legacy
Port 2222
HostKey /etc/ssh/ssh_host_ed25519_key
HostKey /etc/ssh/ssh_host_rsa_key
PidFile /run/sshd-legacy.pid
KexAlgorithms +diffie-hellman-group14-sha1
AllowUsers legacyuser
UsePAM yes

This file stands alone. It does not read /etc/ssh/sshd_config or its drop-ins, so copy in any login settings you depend on. The separate PidFile stops the two instances from writing to one PID file. AllowUsers limits logins to the one account the legacy machine needs. Test the file, then run it once in debug mode and connect from the legacy machine:

sudo /usr/sbin/sshd -t -f /etc/ssh/sshd_config_legacy && echo config ok
sudo /usr/sbin/sshd -d -f /etc/ssh/sshd_config_legacy

When that connection works, run it under systemd. This unit is written for this guide, so read systemctl cat ssh to see how your release starts the main service:

sudo tee /etc/systemd/system/ssh-legacy.service >/dev/null <<'EOF'
[Unit]
Description=OpenSSH server for one legacy client on port 2222
After=network.target

[Service]
ExecStartPre=/usr/bin/mkdir -p /run/sshd
ExecStartPre=/usr/sbin/sshd -t -f /etc/ssh/sshd_config_legacy
ExecStart=/usr/sbin/sshd -D -f /etc/ssh/sshd_config_legacy
Restart=on-failure

[Install]
WantedBy=multi-user.target
EOF
sudo systemctl daemon-reload
sudo systemctl enable --now ssh-legacy
sudo ss -tlnp | grep ':2222'

-D keeps sshd in the foreground, so systemd can track it. The sshd -t line stops the unit from starting with a broken file. The mkdir line covers a boot where the main ssh service has not created /run/sshd yet.

Now limit the port to one address. On Ubuntu, ufw is disabled on a fresh install, so port 2222 is open to everyone until you turn it on. Allow port 22 before you enable it, or you lock yourself out:

sudo ufw allow 22/tcp
sudo ufw allow proto tcp from 203.0.113.50 to any port 2222
sudo ufw enable
sudo ufw status verbose

Your provider may also run a separate network firewall in its panel. If the legacy machine still cannot connect, the difference between SSH connection refused and connection timed out tells you which layer is blocking it, and checking whether a port is open on Linux confirms that sshd is listening. Keep the main instance on port 22 strict, as in the SSH hardening guide for a VPS.

A device that only offers ssh-dss cannot be reached from OpenSSH 10

OpenSSH 10.0 removed DSA, and Ubuntu's 26.04 release notes list the removal too. So a 10.x client cannot connect to a device whose only host key is DSA, whatever you add to the config. HostKeyAlgorithms +ssh-dss cannot bring back code that is no longer in the binary. Confirm it with ssh -Q key | grep dss. You have two ways out: a firmware update that adds a newer host key type, or a jump host whose client still lists ssh-dss in ssh -Q key.

What you give up when you re-enable old algorithms

• SHA-1 signatures (ssh-rsa). The OpenSSH 8.8 release notes say chosen-prefix collisions for SHA-1 cost under USD 50,000. With HostKeyAlgorithms +ssh-rsa, the proof that you reached the real device rests on SHA-1. With PubkeyAcceptedAlgorithms +ssh-rsa, the proof that the user holds the key rests on SHA-1. OpenSSH calls this a stopgap until the device is upgraded or moved to ECDSA or Ed25519 keys.
• Modp Diffie-Hellman. OpenSSH 10.0 turned it off in sshd by default. The -sha1 variants also hash the key exchange with SHA-1. No classic method, modp or elliptic curve, is post-quantum. The mlkem768x25519-sha256 default exists to protect sessions recorded today against a future quantum computer, and a legacy session does not get that protection.

The scope matters as much as the algorithm. A Host block weakens one destination. A global server drop-in weakens what the server accepts from every client. A second instance behind a one-address firewall rule weakens one port for one machine.

The durable fixes: new firmware or a jump host

The real fix is to update the device. Check the vendor's firmware for a release that supports Ed25519 or rsa-sha2-512 host keys and a modern key exchange. Then delete your legacy Host block or second sshd.

If no update exists, put a jump host on the same private network as the device. You connect to the jump host with modern algorithms. The legacy Host block lives only in the jump host's ~/.ssh/config. Then run the second hop from there:

ssh -t jump ssh old-switch

ProxyJump does not solve this error. It only forwards a TCP connection through the jump host, so your own client still negotiates directly with the device and gets the same Unable to negotiate line. The weak hop must start on the jump host itself.

FAQ

What does "no matching key exchange method found" mean in SSH?

The client and the server share no key exchange method, so they cannot agree on session keys and the connection stops before login. The Their offer: part of the error is the other side's list. Add one name from that list to KexAlgorithms on the side that lacks it. On a client, put it in one Host block in ~/.ssh/config with a + prefix. On a server, run sudo sshd -t before you restart.

Can I fix the error by adding ssh-rsa to KexAlgorithms?

No. ssh-rsa is a key type and a signature algorithm, not a key exchange method, so ssh and sshd -t both reject it in KexAlgorithms. Compare ssh -Q kex and ssh -Q key to see that it is only in the second list. If the error says no matching host key type found and offers ssh-rsa, use HostKeyAlgorithms +ssh-rsa in a Host block for that one device.

Why can I not connect to a device that only offers ssh-dss?

OpenSSH 10.0 removed DSA support, and Ubuntu 26.04 ships OpenSSH 10.2p1. A client without DSA code cannot verify a DSA host key, and no config option adds it back. ssh -Q key | grep dss printing nothing confirms it. Update the device's firmware to get a newer host key type, or connect through a jump host whose own client still supports ssh-dss.

Can I enable an old key exchange for one client IP on Ubuntu 26.04?

Not with Match Address. In OpenSSH 10.2, KexAlgorithms and HostKeyAlgorithms are global-only, so sshd -t rejects them inside a Match block. Run a second sshd with its own config file on its own port, and allow that port in ufw only from the legacy client's address. PubkeyAcceptedAlgorithms is the exception and does work inside Match.