PuTTY Fatal error: Couldn't agree on host key algorithm

I'm trying to connect to a new system with PuTTY and am seeing the following:

Fatal error: Couldn't agree on host key algorithm (available: rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256)

Checking available algos on the server:

acoder@client ~ $ nmap --script ssh2-enum-algos -sV -p 22 server.name.here
Starting Nmap 7.01 ( ) at 2021-04-16 10:33 EDT
Nmap scan report for server.name.here (1.1.1.1)
Host is up (0.018s latency).
PORT STATE SERVICE VERSION
22/tcp open ssh OpenSSH 8.0 (protocol 2.0)
| ssh2-enum-algos:
| kex_algorithms: (7)
| ecdh-sha2-nistp256
| ecdh-sha2-nistp384
| ecdh-sha2-nistp521
| diffie-hellman-group-exchange-sha256
| diffie-hellman-group14-sha256
| diffie-hellman-group16-sha512
| diffie-hellman-group18-sha512
| server_host_key_algorithms: (3)
| rsa-sha2-512
| rsa-sha2-256
| ecdsa-sha2-nistp256
| encryption_algorithms: (6)
|
| aes256-ctr
| aes256-cbc
|
| aes128-ctr
| aes128-cbc
| mac_algorithms: (6)
|
|
|
| hmac-sha2-256
| hmac-sha1
| hmac-sha2-512
| compression_algorithms: (2)
| none
|_ 

Here's what's available on my client machine:

PubkeyAcceptedKeyTypes

acoder@client ~ $ ssh -Q key
ssh-ed25519
ssh-rsa
ssh-dss
ecdsa-sha2-nistp256
ecdsa-sha2-nistp384
ecdsa-sha2-nistp521

Ciphers

acoder@client ~ $ ssh -Q cipher
3des-cbc
blowfish-cbc
cast128-cbc
arcfour
arcfour128
arcfour256
aes128-cbc
aes192-cbc
aes256-cbc
aes128-ctr
aes192-ctr
aes256-ctr

MACs

acoder@client ~ $ ssh -Q mac
hmac-sha1
hmac-sha1-96
hmac-sha2-256
hmac-sha2-512
hmac-md5
hmac-md5-96
hmac-ripemd160

KexAlgorithms

acoder@client ~ $ ssh -Q kex
diffie-hellman-group1-sha1
diffie-hellman-group14-sha1
diffie-hellman-group-exchange-sha1
diffie-hellman-group-exchange-sha256
ecdh-sha2-nistp256
ecdh-sha2-nistp384
ecdh-sha2-nistp521

What am I overlooking here?

1 Answer

You're overlooking that PuTTY and ssh (OpenSSH) are two completely separate programs. They don't share any code; they don't use any common crypto library. The ssh -Q lists don't tell you anything about what PuTTY can support.

I think the problem is that your PuTTY version is too old. Out of the signature methods offered by the server, ECDSA signatures (ecdsa-sha2-nistp256) need at least PuTTY version 0.68, while the RSA-SHA2 methods (rsa-sha2-*) will only be available in the next PuTTY release (0.75).

The cause of this is that OpenSSH servers have disabled support for the old SHA1-based ssh-rsa signature algorithm very recently (they still use the same RSA keys, but only through SHA2-based signatures), while support for DSA keys has been removed several years ago.