9

My server recently stopped offering me public key-based authentication. I tried to log in using my RSA public key and only got:

$ ssh -v <server>
OpenSSH_8.9p1 Ubuntu-3ubuntu0.1, OpenSSL 3.0.2 15 Mar 2022
debug1: Reading configuration data /home/user/.ssh/config
debug1: /home/user/.ssh/config line 33: Applying options for <server>
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug1: Connecting to <server> [<ip>] port 22.
debug1: Connection established.
debug1: identity file /home/user/.ssh/id_rsa type 0
debug1: identity file /home/user/.ssh/id_rsa-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_8.9p1 Ubuntu-3ubuntu0.1
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Debian-5+deb8u1
debug1: compat_banner: match: OpenSSH_6.7p1 Debian-5+deb8u1 pat OpenSSH* compat 0x04000000
debug1: Authenticating to <server>:22 as 'user'
debug1: load_hostkeys: fopen /home/user/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: [email protected]
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: [email protected] MAC: <implicit> compression: none
debug1: kex: client->server cipher: [email protected] MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: SSH2_MSG_KEX_ECDH_REPLY received
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:tKraF30I02/eujsuOeMD9Aihjxp/9CXl/lu3c3vGcGs
debug1: load_hostkeys: fopen /home/user/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: Host '[<server>]:22' is known and matches the ECDSA host key.
debug1: Found key in /home/user/.ssh/known_hosts:31
debug1: rekey out after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey in after 134217728 blocks
debug1: get_agent_identities: bound agent to hostkey
debug1: get_agent_identities: agent returned 1 keys
debug1: Will attempt key: /home/user/.ssh/other_key RSA SHA256:<fingerprint> agent
debug1: Will attempt key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering public key: /home/user/.ssh/other_key RSA SHA256:<fingerprint> agent
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Next authentication method: password
user@<server>'s password:

The crucial part seems to be the third-to-last line:

debug1: send_pubkey_test: no mutual signature algorithm

At first I thought it must have something to do with the fact that ssh-rsa has been deprecated and finally disabled by default. However, it turns out the server is quite old, running OpenSSH 6.7p1.

Maybe it is for this reason that the server doesn't tell me which algorithms it supports – modern OpenSSH versions seem to send an SSH2_MSG_EXT_INFO with kex_input_ext_info: server-sig-algs=….

So I had a look at the server's /etc/ssh/sshd_config but it looks fine and doesn't mention anything related to PubkeyAcceptedKeyTypes (= PubkeyAcceptedAlgorithms in more recent versions of OpenSSH):

…
KexAlgorithms [email protected],diffie-hellman-group-exchange-sha256
Ciphers [email protected],[email protected],[email protected],aes256-ctr,aes192-ctr,aes128-ctr
MACs [email protected],[email protected],[email protected],[email protected],hmac-sha2-512,hmac-sha2-256,hmac-ripemd160,[email protected]
…

I also tried using ssh -Q (sig|PubkeyAcceptedKeyTypes) <server> to query the supported signature algorithms but, contrary to what the man page suggests (ssh … [-Q query_option] … destination), it seems this queries the client(?), not the server as it is the same for every server I've tried.

Then I thought: Wait, but if the server hasn't seen an update in recent times, anyway, it must be my client!

And indeed: ssh -o "PubkeyAcceptedAlgorithms=+ssh-rsa" -v <server> works!

$ ssh -o "PubkeyAcceptedAlgorithms=ssh-rsa" -v <server>
OpenSSH_8.9p1 Ubuntu-3ubuntu0.1, OpenSSL 3.0.2 15 Mar 2022
debug1: Reading configuration data /home/user/.ssh/config
debug1: /home/user/.ssh/config line 33: Applying options for <server>
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug1: Connecting to <server> [<ip>] port 22.
debug1: Connection established.
debug1: identity file /home/user/.ssh/id_rsa type 0
debug1: identity file /home/user/.ssh/id_rsa-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_8.9p1 Ubuntu-3ubuntu0.1
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.7p1 Debian-5+deb8u1
debug1: compat_banner: match: OpenSSH_6.7p1 Debian-5+deb8u1 pat OpenSSH* compat 0x04000000
debug1: Authenticating to <server>:22 as 'user'
debug1: load_hostkeys: fopen /home/user/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: [email protected]
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: [email protected] MAC: <implicit> compression: none
debug1: kex: client->server cipher: [email protected] MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: SSH2_MSG_KEX_ECDH_REPLY received
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:tKraF30I02/eujsuOeMD9Aihjxp/9CXl/lu3c3vGcGs
debug1: load_hostkeys: fopen /home/user/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: Host '[<server>]:22' is known and matches the ECDSA host key.
debug1: Found key in /home/user/.ssh/known_hosts:31
debug1: rekey out after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey in after 134217728 blocks
debug1: get_agent_identities: bound agent to hostkey
debug1: get_agent_identities: agent returned 1 keys
debug1: Will attempt key: /home/user/.ssh/other_key RSA SHA256:<fingerprint> agent
debug1: Will attempt key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering public key: /home/user/.ssh/other_key RSA SHA256:<fingerprint> agent
debug1: Authentications that can continue: publickey,password
debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: Server accepts key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
Enter passphrase for key '/home/user/.ssh/id_rsa':

How is this possible? Even if my OpenSSH client (v8.9, see above) had deprecated/disabled usage of ssh-rsa with SHA1[0]: As one can see, server & client agree to use SHA256 – which should be perfectly fine?!

What's more, ssh -Q PubkeyAcceptedAlgorithms does list ssh-rsa:

$ ssh -Q PubkeyAcceptedAlgorithms
ssh-ed25519
[email protected]
[email protected]
[email protected]
ssh-rsa
rsa-sha2-256
rsa-sha2-512
ssh-dss
ecdsa-sha2-nistp256
ecdsa-sha2-nistp384
ecdsa-sha2-nistp521
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]

I also haven't been able to find a line disabling ssh-rsa (e.g. PubkeyAcceptedAlgorithms=-ssh-rsa) anywhere on my computer, whether in ~/.ssh/config, /etc/ssh or anywhere else.

Concluding: This is a real mystery to me. Why is ssh-rsa no longer working? (I should mention, ssh-ed25519 public keys work perfectly fine.)

For now I'll just configure PubkeyAcceptedAlgorithms=+ssh-rsa in my local ~/.ssh/config but this feels like a dirty workaround for a problem that I haven't understood.

--

Related posts of other people having the exact same problem: The server runs OpenSSH v6.7p1, the client is some OpenSSH version > 8 and ssh-rsa authentication fails:

Suddenly, my ssh requires a password--debug1: send_pubkey_test: no mutual signature algorithm

https://serverfault.com/questions/1064247/ssh-permission-denied-publickey

Improve this question
1
  • The man page says ssh -Q queries ssh which is the client program (not the server), but doesn't say it lists all implemented algos of a type not the subset enabled by default. And yes when the log says offering key ... RSA SHA256:fingerprint that means the fingerprint (computed locally only) used SHA256, not the signature (or probe) sent to the server (and rsa-sha2 signatures sent to versions below 7.2 do fail)
    – dave_thompson_085
    Commented Oct 16, 2023 at 4:57

1 Answer 1

Reset to default
8

I'm starting to think the reason is this one:

OpenSSH has supported RFC8332 RSA/SHA-256/512 signatures since release 7.2 and existing ssh-rsa keys will automatically use the stronger algorithm where possible.

So it seems OpenSSH v6.7p1 doesn't support SHA-256/512 yet and still wants to use SHA1 when confronted with an ssh-rsa key. In particular, the debug output (in the successful case)

debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: Server accepts key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit

was misleading and says nothing about which hashing algorithm was used in the client<>server communication.

Moreover, the RFC explains why my server didn't send server-sig-algs:

Servers that accept rsa-sha2-* signatures for client authentication
SHOULD implement the extension negotiation mechanism defined in
[RFC8308], including especially the "server-sig-algs" extension.

All in all, having successfully wasted an entire night on this, I'm flabbergasted by how it didn't occur to the OpenSSH developers that using ssh-rsa to mean "use RSA key", "use RSA + SHA1" or "use RSA + any SHA version" (depending on the situation) could be confusing. The RFC at least is very explicit.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .