SSH: agent key RSA SHA256:[hash] returned incorrect signature type

Question

I just upgraded two machines from Debian 9 to Debian 10 and now, when I'm connecting to them using SSH, I'm getting the following warning:

agent key RSA SHA256:[hash] returned incorrect signature type

I have been using the exact same setup before and nobody was complaining.

Even though it doesn't have any impact on the ability to successfully connect, I would like to understand what it exactly means and how to fix it.

This is the ssh -vvv output:

debug3: sign_and_send_pubkey: RSA SHA256:[hash]
debug3: sign_and_send_pubkey: signing using rsa-sha2-512
agent key RSA SHA256:[hash] returned incorrect signature type
debug3: sign_and_send_pubkey: signing using ssh-rsa

Do I understand it right that my SSH client is using a hashing algorithm to sign the key the SSH server doesn't like? Or is it SSH agent? How to configure it properly so the SSH server is not complaining, please?

I don't understand what's expected and what's actually used, confused by the SHA256: prefix vs. the message signing using rsa-sha2-512.

Answer 1

I have been using the exact same setup before and nobody was complaining.

You upgraded from Debian 9 to Debian 10. That is no longer "the exact same setup".

Do I understand it right that my SSH client is using a hashing algorithm to sign the key the SSH server doesn't like?

No; the SSH agent is using a hashing algorithm the client doesn't like.

Traditionally there was only one hash algorithm defined for each SSH key type, and ssh-rsa keys always used the SHA1 algorithm when making signatures. (Note that this is for signing data – authentication challenges – not keys themselves.)

Recently, as SHA1 is no longer state-of-the-art (or anywhere near), the combinations of RSA with SHA256 and SHA512 were specified and the ssh-agent protocol was extended with a flags field to request a different hash type than usual.

For this connection, your client and server have negotiated that a SHA512-based signature should be used instead. However, when the client asked ssh-agent to create the signature, ssh-agent ignored the new extension and just returned a SHA1-based signature instead. Usually this happens when the agent simply does not support the updated protocol.

The solution is to upgrade the SSH agent. Latest versions of OpenSSH and PuTTY both have agents compatible with the new protocol; GnuPG's gpg-agent should also support this as of v2.2.6.

confused by the SHA256: prefix vs. the message signing using rsa-sha2-512.

The SHA256: prefix has nothing whatsoever to do with the signatures being made. It indicates the method that the key's fingerprint was generated (the fingerprint is a direct hash of the public key; not a signature). Old clients used to use MD5 for this purpose.

The fingerprint is shown for your information only (to indicate which key is being used) and its appearance doesn't affect the actual SSH connection.