What's Actually Happening

Your SSH connection fails immediately during the initial protocol handshake. The client and server cannot agree on a compatible SSH protocol version, preventing any further negotiation of encryption, authentication, or session parameters.

The Error You'll See

The error message typically appears as:

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

Or for protocol version issues:

bash
Protocol major versions differ: 2 vs. 1

Or a more generic:

bash
ssh_exchange_identification: Connection closed by remote host

Why This Happens

This error occurs when the SSH client and server have no overlap in their supported key exchange (KEX) algorithms. Modern SSH clients disable older, insecure algorithms like diffie-hellman-group1-sha1, while legacy servers may only offer these deprecated methods. Similar issues can occur with SSH protocol version 1, which is obsolete and disabled in modern clients.

Step 1: Identify the Server's Offered Algorithms

Use verbose mode to see what the server offers:

bash
ssh -vvv user@server 2>&1 | grep -i "offer"

Look for lines like:

bash
debug1: kex: algorithm: (no match)
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: diffie-hellman-group1-sha1,ssh-dss

Step 2: Check Client's Supported Algorithms

List your client's supported key exchange methods:

bash
ssh -Q kex

Compare this list with what the server offers to identify the gap.

Step 3: Enable Legacy Algorithms Temporarily

For a quick connection to a legacy server, specify a compatible key exchange method:

bash
ssh -o KexAlgorithms=+diffie-hellman-group1-sha1 user@legacy-server

The + prefix adds to the default list rather than replacing it.

Step 4: Configure Legacy Support in SSH Config

For repeated connections to legacy systems, add to ~/.ssh/config:

bash
Host legacy-server.example.com
    KexAlgorithms +diffie-hellman-group1-sha1
    HostKeyAlgorithms +ssh-dss

You may also need to add legacy host key algorithms if the server uses older keys.

If you have administrative access, update the server's /etc/ssh/sshd_config:

bash
KexAlgorithms curve25519-sha256,curve25519-sha256@libssh.org,diffie-hellman-group-exchange-sha256

For older systems, you may need to regenerate host keys:

bash
ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key
ssh-keygen -t rsa -b 4096 -f /etc/ssh/ssh_host_rsa_key

Then restart the SSH service:

bash
sudo systemctl restart sshd

Step 6: Handle Protocol Version 1 Issues

If the server only supports SSH protocol 1 (extremely rare now), you cannot connect with modern clients. The server must be updated:

bash
# Check the server's SSH version and protocol support
ssh -v user@server 2>&1 | head -5

If you see SSH-1.99, the server supports both protocols. If you see SSH-1.5 or similar, the server is obsolete and must be upgraded.

Verify the Fix

Connect with verbose output to confirm successful negotiation:

bash
ssh -v user@server 2>&1 | grep -E "(kex|KEX)"

You should see successful algorithm selection:

bash
debug1: kex: algorithm: curve25519-sha256
debug1: kex: host key algorithm: ssh-ed25519
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com

Test a simple command:

bash
ssh user@server "echo 'Protocol negotiation successful'"

If you must use legacy algorithms in production, document the security implications and create a plan to upgrade the affected systems.