When modern OpenSSH clients (v8.8+) connect to legacy servers (pre-v7.0), you'll often encounter:

Unable to negotiate with xxx.xxx.xxx.xxx port xxxxx: no matching host key found. Their offer: ssh-rsa,ssh-dss

OpenSSH 8.8+ disabled ssh-rsa and ssh-dss by default due to SHA-1 vulnerabilities. The server (OpenSSH 5.3) only offers these legacy key types, creating negotiation failure.

Create or modify ~/.ssh/config with these directives:

Host legacy_server
    HostName xxx.xxx.xxx.xxx
    Port xxxxx
    User your_username
    HostKeyAlgorithms ssh-rsa,ssh-dss
    PubkeyAcceptedKeyTypes ssh-rsa,ssh-dss
    KexAlgorithms diffie-hellman-group-exchange-sha256
    Ciphers aes256-ctr,aes192-ctr,aes128-ctr

For one-time connections:

ssh -o HostKeyAlgorithms=ssh-rsa -o PubkeyAcceptedKeyTypes=ssh-rsa user@host

While these solutions work, be aware that:

• SSH-RSA uses SHA-1 which has known vulnerabilities
• This should be temporary until server upgrade
• Consider tunneling through a bastion host

If you control the server, the proper fix is upgrading OpenSSH and generating new host keys:

# On the server:
sudo ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key
sudo ssh-keygen -t rsa -b 4096 -f /etc/ssh/ssh_host_rsa_key

For deeper investigation:

ssh -vvv -o HostKeyAlgorithms=ssh-rsa user@host

Look for "host key algorithms" in debug output to verify negotiation.

When your Windows machine running OpenSSH 8.8 (S1) tries to connect to a legacy Linux server with OpenSSH 5.3 (S2), the key exchange protocol negotiation fails because:

Modern OpenSSH (≥8.2) disables ssh-rsa SHA-1 by default
Legacy servers often only support older key types (ssh-rsa/ssh-dss)
The host key algorithms advertised by S2 (ssh-rsa,ssh-dss) are rejected by S1

Add these lines to ~/.ssh/config on your Windows machine:

Host legacy-server
    HostName xxx.xxx.xxx.xxx
    Port xxxxx
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedKeyTypes +ssh-rsa
    KexAlgorithms +diffie-hellman-group-exchange-sha256

When you only specify HostkeyAlgorithms, the server may fall back to password auth because:

• The client isn't advertising RSA keys as acceptable for authentication
• Try adding PubkeyAcceptedKeyTypes as shown above

If you have control over the client environment:

# Generate a new RSA key specifically for legacy connections
ssh-keygen -t rsa -b 4096 -f ~/.ssh/id_rsa_legacy

# Specify the key explicitly in your config
Host legacy-server
    IdentityFile ~/.ssh/id_rsa_legacy

While these workarounds enable connectivity:

• RSA/SHA1 is considered weak (CVE-2020-15778)
• Best practice: Upgrade the server or implement a jump host
• Monitor for unusual activity if forced to use weaker algorithms

Use this command to test with verbose output:

ssh -vvv -o HostKeyAlgorithms=+ssh-rsa \
    -o PubkeyAcceptedKeyTypes=+ssh-rsa \
    user@legacy-server

The -vvv flag will show the exact key exchange negotiation process.