sshd "Unable to negotiate with …: no matching … found": What It Means

Oct 18 03:51:11 web1 sshd-session[48211]: Unable to negotiate with 203.0.113.7 port 54321: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1 [preauth]
Oct 18 04:02:19 web1 sshd-session[48344]: Unable to negotiate with 198.51.100.22 port 40118: no matching host key type found. Their offer: ssh-rsa,ssh-dss [preauth]
Oct 18 04:19:50 web1 sshd-session[48502]: Unable to negotiate with 192.0.2.44 port 51902: no matching cipher found. Their offer: aes128-cbc,3des-cbc,blowfish-cbc [preauth]
Oct 18 05:03:27 web1 sshd-session[48711]: Unable to negotiate with 198.51.100.9 port 33110: no matching MAC found. Their offer: hmac-md5,hmac-sha1-96 [preauth]

What it means

sshd writes this line from the error handler in its packet layer, through logdie(): it logs the message and the connection ends there. Three values are filled in:

• The remote identifier — the client’s IP address and source port, the same identifier that other pre-authentication lines for that connection use. The [preauth] tag marks the message as coming from the pre-authentication process, before any account exists.
• The error text, from ssh_err(). For this message it is one of no matching key exchange method found, no matching host key type found, no matching cipher found or no matching MAC found; the same table also has no matching compression method found for the compression case. That text is the only part that tells you which component failed.
• The client’s offer — the proposal list for the component that failed. It is the client’s list, never the server’s.

SSH negotiates each of these components separately during the KEXINIT exchange: both sides send a list, and the connection can only continue if the lists intersect for key exchange, host key signature algorithm, cipher and MAC. If any one has no overlap, sshd stops. On the server the four lists come from KexAlgorithms, HostKeyAlgorithms, Ciphers and MACs.

The gap that produces most of these lines is between supported and default. sshd_config(5) lists 3des-cbc, aes128-cbc and friends as supported ciphers, and hmac-md5, hmac-sha1 as supported MACs, but the default Ciphers set is [email protected], [email protected],[email protected], aes128-ctr,aes192-ctr,aes256-ctr, and the default KexAlgorithms set contains only the ML-KEM/sntrup hybrids, curve25519 and the three ECDH methods — no diffie-hellman-* at all. Likewise ssh-rsa and ssh-dss are absent from the default HostKeyAlgorithms, which starts at rsa-sha2-512,rsa-sha2-256 for RSA.

Is it an attack?

Almost never on its own, but the shape matters.

Pattern	Reading
Many single connections, many sources, ancient offers such as diffie-hellman-group1-sha1	Internet-wide scanners and old bot clients — noise
One source, several connections in seconds, a different offer each time	Algorithm enumeration — a scanner mapping what your server accepts
One source, repeating on a schedule, same offer every time	Your own monitoring, backup or CI client that was never updated
A burst from internal addresses right after a change	A hardening change broke legitimate clients — an availability problem
The same source later produces Accepted	Investigate the session; the negotiation failure itself is irrelevant

Nothing in this line indicates stolen or guessed credentials: the connection never reached authentication, which is also why these keep appearing on a key-only server where PasswordAuthentication is off.

How to investigate

Split the lines by failing component first, then by source and offer.

# Last 24 hours (Debian/Ubuntu unit is ssh; RHEL/Fedora use -u sshd)
sudo journalctl -u ssh --since "24 hours ago" | grep "Unable to negotiate"

# Which component failed, and how often (/var/log/auth.log; RHEL/Fedora /var/log/secure)
sudo grep -oP 'Unable to negotiate with \S+ port \d+: \Kno matching .+ found' \
  /var/log/auth.log | sort | uniq -c | sort -rn

# Busiest sources
sudo grep -oP 'Unable to negotiate with \K\S+' /var/log/auth.log \
  | sort | uniq -c | sort -rn | head -20

# What those clients actually offered
sudo grep -oP 'Their offer: \K[^ ]+' /var/log/auth.log | sort | uniq -c | sort -rn | head -20

# The whole connection, by PID
sudo grep 'sshd-session\[48211\]' /var/log/auth.log

# What this server will accept right now
sudo sshd -T | grep -E '^(kexalgorithms|hostkeyalgorithms|ciphers|macs) '

# Everything this build of OpenSSH can do, per sshd_config(5)
ssh -Q KexAlgorithms; ssh -Q HostKeyAlgorithms; ssh -Q cipher; ssh -Q mac

Compare the offer column with the effective list: the intersection is empty, and the missing entry tells you whether the client is behind on key exchange, host keys, cipher or MAC. Private-address sources belong to you and need fixing; public ones are usually scanners. For an exported auth.log, the browser log analyzer groups the lines by source, and connections that die even earlier show up as kex_exchange_identification or Connection closed lines instead.

How to stop it

• Decide whose connections these are. If every source is external and each appears once, there is nothing to fix — the modern defaults are doing their job and the clients are obsolete.
• Fix the client, not the server. Upgrading the SSH client, library or appliance firmware removes the cause permanently.
• Only widen the server’s lists as a last resort. The manual describes prefixing a list with + to append to the default set, - to remove from it and ^ to move entries to the head; appending a legacy cipher or host key algorithm applies to every client that connects, so treat it as a temporary, documented exception.
• Cut the scanner volume at the network edge by restricting port 22 to known ranges or putting it behind a VPN or bastion. That removes these lines faster than any sshd setting.
• Do not expect penalties to suppress them. PerSourcePenalties is enabled by default, but the documented categories cover crashes, unsuccessful authentication attempts, administratively refused connections, clients that disconnect without attempting authentication and clients that exceed LoginGraceTime — a failed algorithm negotiation is not one of the listed conditions.
• Keep LogLevel at the default INFO. These lines are cheap evidence that a legitimate client broke, and raising the bar on logging hides that.

sudo sshd -t && sudo systemctl reload ssh

Validate the configuration before reloading, and keep a working session open while you test a new one.