Unable to negotiate: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1

no matching key exchange method found means the SSH client and server have no key exchange (KEX) algorithm in common, so they cannot even agree on how to set up encryption. Their offer: lists what the server supports; typically only diffie-hellman-group1-sha1 or diffie-hellman-group14-sha1, which modern OpenSSH clients no longer offer by default. Upgrade the server; for a device you cannot upgrade, enable the offered algorithm for that host only with KexAlgorithms +ALGORITHM.

Reproduce it

A test server (Python paramiko on 127.0.0.1) restricted to diffie-hellman-group1-sha1, and a current OpenSSH client:

ssh-keygen -q -t ed25519 -N "" -f hostkey
cat > legacy_kex.py <<'EOF'
import socket, paramiko
key = paramiko.Ed25519Key(filename="hostkey")
srv = socket.socket(); srv.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
srv.bind(("127.0.0.1", 4806)); srv.listen(1); srv.settimeout(30)
conn, _ = srv.accept()
t = paramiko.Transport(conn)
t._preferred_kex = ("diffie-hellman-group1-sha1",)
t.add_server_key(key)
try:
    t.start_server(server=paramiko.ServerInterface())
except Exception:
    pass
t.close()
EOF
uv run -q --no-project --python 3.13 --with paramiko==4.0.0 python legacy_kex.py 2>/dev/null &
sleep 5
ssh -p 4806 -o BatchMode=yes -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null 127.0.0.1 true
echo "ssh exit code: $?"
wait

Unable to negotiate with 127.0.0.1 port 4806: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,kex-strict-s-v00@openssh.com
ssh exit code: 255

kex-strict-s-v00@openssh.com in the offer is not a real algorithm: it is the marker for strict key exchange (the Terrapin countermeasure) that current servers add. A real legacy device usually shows only the old algorithms.

Enable the old algorithm for one host

Host old-router
    HostName 192.0.2.1
    KexAlgorithms +diffie-hellman-group14-sha1

Confirm what the client will offer, without connecting:

ssh -T -G -o KexAlgorithms=+diffie-hellman-group14-sha1 old-router | grep -i '^kexalgorithms' | tr ',' '\n' | grep -x 'diffie-hellman-group14-sha1'

diffie-hellman-group14-sha1

ssh -Q kex lists every algorithm the client binary supports, including disabled ones; if the algorithm in Their offer is not in that list, no client option can enable it and only a server upgrade (or an older client) helps. The same negotiation can fail on other algorithm lists with no matching cipher found (Ciphers +...), no matching MAC found (MACs +...) and no matching host key type found (HostKeyAlgorithms +...).