Adam Heins

December 20, 2020

SSH: agent key RSA returned incorrect signature type

I have a laptop running Ubuntu 16.04. The default version of SSH on Ubuntu 16.04 is OpenSSH 7.2. I recently decided to install a newer version, 8.2. However, when I did so, I started to see the warning

agent key RSA SHA256:lPA0is9m3uARV75WmNYVrxH1rTzP68w+Zvar5chXzhI returned incorrect signature type

whenever I connected to another machine using SSH public key authentication. It took me quite a while to understand why this message was appearing and what to do about it, so I thought it would be an interesting topic for a blog post.

SSH public key authentication

First, some background on SSH public key authentication. Public key authentication is based on asymmetric cryptography, in which each user has a key-pair consisting of a public key and a private key. The public key can be freely shared, while the private key must be kept secret.

Public key authentication is typically considered more secure than password-based authentication, for a couple of reasons. First, the private key is stored in a (possibly encrypted and password-protected) file on the user's local computer. In contrast, a password is typically either memorized and thus at risk of being forgotten, or written in an insecure location (like a sticky note on your monitor). Second, cryptographic keys are, by design, just way more difficult to break than even extremely complex passwords.

In general, cryptographic keys may be used for two mathematical operations: encryption and/or signing. Encryption refers to encoding a message so that it is unreadable until it is decrypted; signing refers to adding a digital signature to a message that proves the identity of the sender and proves that the data has not been altered. The private and public keys are both involved in each operation:

The public key can:

  • encrypt data;
  • verify that a signature was made by the private key.

The private key can:

  • decrypt data that has been encrypted using the public key;
  • sign data.

For public-key authentication, we are primarily concerned with cryptographic signing.

One of the oldest public-key schemes is known as RSA ("Rivest-Shamir-Adleman", after its inventors), which was first developed in 1977 and is based on the difficulty of factoring large prime numbers. RSA can be used for both encryption and signing, and is probably the most common cryptographic scheme used by SSH for authentication. Other common public-key schemes supported by SSH, such as DSA ("Digital Signature Algorithm"), are designed specifically for cryptographic signing, and cannot be used for encryption. All signature algorithms make use of hash functions, which map a variable-sized input to a fixed-size output, known as the hash or hash value.

Now let's go through a simplified example of the RSA signing process. First, the sender produces a signature by using their private key to sign the hash value of a message. The signature and message are then sent to the receiver. Next, the receiver uses the sender's public key to verify the signature and recover the hash value. If the recovered hash value matches the hash value of the received message, then the sender's identity is verified.

This example is essentially how SSH's public key authentication works. When initiating an SSH connection, the server needs a way to prove that you (the client) are who you say you are. Only owners of the public keys listed in the ~/.ssh/authorized_keys file on the server are allowed to authenticate. So, to verify your identity, you must prove to the server that you own the private key corresponding to one of those public keys. To do so, you sign a message using your private key, send it to the server, and the server verifies the signature using your public key. For the curious, more SSH-specific details can be found in the the relevant RFC and the OpenSSH source code.

It is important that the hash functions used for cryptography are one-way: the input message must not (realistically) be recoverable from the output hash value. To see why, suppose that the sender's signature and message from the example above are intercepted by a bad actor. The bad actor can use the sender's public key to recover the message's hash value from the sender's signature, just like the intended receiver.

The trouble arises if the hash function is not one-way: then the bad actor could conceivably create a new, different message with the same hash value as the original message. The bad actor then sends this new, malicious message to the receiver in place of the original message. When the receiver compares the real signature and the malicious message hash value, they will match and it will appear that the malicious message was actually sent by the original sender.

A popular cryptographic hash function was SHA-1 ("Secure Hash Algorithm 1"), introduced in 1995 after revision of an earlier version from 1993. SHA-1 was the hash function SSH originally used with RSA for cryptographic signing. However, SHA-1 is now considered insecure, because a message matching a given hash value can now be generated relatively easily. Consequently, the release notes of OpenSSH 8.2 state that original SHA-1-based signing algorithm ssh-rsa will be disabled in a near-future version.

SHA-1 has been superseded by the SHA-2 and SHA-3 families of hash functions. Signing algorithms for RSA based on SHA-2 have been included in OpenSSH since version 7.2 under the names rsa-sha2-256 and rsa-sha2-512 (the 256 and 512 refer the number of bits in the hash value).

Resolving the warning

Having discussed the basics of public key authentication, let's now return to the warning SSH was giving me. The issue becomes clearer by running SSH in triple-verbose mode (ssh -vvv) to see additional logging output:

...
debug3: sign_and_send_pubkey: signing using rsa-sha2-512 SHA256:lPA0is9m3uARV75WmNYVrxH1rTzP68w+Zvar5chXzhI
agent key RSA SHA256:lPA0is9m3uARV75WmNYVrxH1rTzP68w+Zvar5chXzhI returned incorrect signature type
debug3: sign_and_send_pubkey: signing using ssh-rsa SHA256:lPA0is9m3uARV75WmNYVrxH1rTzP68w+Zvar5chXzhI
...

The client and server agree to use the rsa-sha2-512 signing algorithm for authentication. The client then asks the agent to produce the signature, but it incorrectly uses the old ssh-rsa signing algorithm based on SHA-1 instead, prompting the warning. The agent is the SSH agent, which is a daemon that runs on the client machine and stores decrypted private keys to be used for authentication. Note that the SHA256 in the warning refers to the hash function used to generate the fingerprint lPA0is9m3uARV75WmNYVrxH1rTzP68w+Zvar5chXzhI of my public key, and is not related to the signing algorithm.

The warning message was added in OpenSSH 7.7, hence why I started to see it when I upgraded from version 7.2 to 8.2. However, since RSA SHA-2 algorithms are supported in OpenSSH 7.2, I was confused why the OpenSSH agent provided the wrong signature. Even if the older version 7.2 agent was running, it should still be fully capable of producing the desired signature.

Well, it turns out that I had not been using the OpenSSH agent at all. Ubuntu's Gnome desktop environment provides its own alternative to the SSH agent called Gnome Keyring, which does not support RSA SHA-2 signing algorithms. To prevent Gnome Keyring being used as a substitute SSH agent, copy the file /etc/xdg/autostart/gnome-keyring-ssh.desktop to ~/.config/autostart/gnome-keyring-ssh.desktop and add the line Hidden=true.

When Gnome Keyring is disabled, the OpenSSH agent executable /usr/bin/ssh-agent is automatically run by X11. This is the system's default version of the agent. In my case, since this version is recent enough to support RSA SHA-2 signing algorithms, I'm quite happy to use it. For convenience, I like to add the line AddKeysToAgent yes to ~/.ssh/config so that keys are automatically added to the running agent after I first use them.

Alternative agents

Suppose you want to use something besides /usr/bin/ssh-agent for SSH key management: perhaps a newer OpenSSH agent you've installed, a different key-management program, or no agent at all (see here for some alternatives). You can disable the agent started by X11 by changing use-ssh-agent to no-use-ssh-agent in /etc/X11/Xsession.options. Then no SSH agent will be started automatically, so you are free to set up your own preferred alternative.

I'll briefly mention two alternatives I tried before simply settling on the /usr/bin/ssh-agent run by X11. The first was to use the GPG agent as the SSH agent. This just requires adding the line enable-ssh-support to ~/.gnupg/gpg-agent.conf. However, I found that using the GPG agent for SSH has a couple of issues. The first issue is easily fixed but was quite frustrating before I knew how. Whenever I tried to add an key to the GPG agent using ssh-add, the agent would respond with the terse message agent refused operation. The solution is given in this StackExchange answer: the PIN entry program I was using was incompatible with the dual text entry window used by GPG. I had been using pinentry-curses, a simple command line PIN entry program, but I had to install and use pinentry-gtk-2 to make the agent work.

The second issue is more damning: GPG apparently does not properly support the RSA SHA-2 algorithms as of the version I use, 2.2.20. Once I was able to add keys, it still showed me the warning that motivated this blog post, which quickly made me decide against using it.

The other alternative I tried was keychain, which I actually quite like. It automatically starts and manages ssh-agent, and adds the specified keys. I would probably use it if I wanted to run a version of ssh-agent that wasn't /usr/bin/ssh-agent, since it uses whichever one is first in your $PATH.

Conclusion

It took me a while to figure out how to resolve this warning message, and even longer to understand why it was occurring. I wrote this article as an attempt to provide a fairly complete picture of the issue, and I hope it may be found useful or simply interesting.

Thanks to Galen Leir-Taha for reading a draft of this.