Upgrade SSH Client Keys and Remote Servers after Fedora 33's New Crypto Policy

Public key authentication failing after a distro or OpenSSH upgrade? Yeah, me too.

The symptoms

After happily upgrading to Fedora 33, one of my remote servers insisted on prompting me for my password, even though I have a perfectly good id_rsa key and the appropriate public key in that server's authorized_keys file.

My key is 3072-bit RSA, and signed with SHA256. Sounds secure...

So, I passed the -v flag to ssh like so:

ssh -v my_beloved_server

I could tell that public key auth was tried, but failed, when I read these two lines:

debug1: Offering public key: /home/my_user/.ssh/id_rsa RSA SHA256:d2bs859ofWY430iBQTfczJd17NhvYTU80WHD3FwbYYk agent
debug1: send_pubkey_test: no mutual signature algorithm

Meanwhile, on my dropbear 2019.78 server (foreshadowing!) I see something like the following:

Pubkey auth attempt with unknown algo for 'my_user' from my_ip_address:port

The public key auth failed, because the client and server could not agree on (or even support) appropriate signature algorithms.

The problem

For good reason, there are new crypto policies in Fedora 33.

If you are interested in the details, take a look in /etc/crypto-policies/back-ends/openssh.config, at the PubkeyAcceptedKeyTypes line:

PubkeyAcceptedKeyTypes ecdsa-sha2-nistp256,ecdsa-sha2-nistp256-cert-v01@openssh.com,sk-ecdsa-sha2-nistp256@openssh.com,sk-ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-ed25519,ssh-ed25519-cert-v01@openssh.com,sk-ssh-ed25519@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,rsa-sha2-256,rsa-sha2-256-cert-v01@openssh.com,rsa-sha2-512,rsa-sha2-512-cert-v01@openssh.com

Now compare that with the same line in the LEGACY settings from /usr/share/crypto-policies/back-ends/LEGACY/openssh.config:

PubkeyAcceptedKeyTypes ecdsa-sha2-nistp256,ecdsa-sha2-nistp256-cert-v01@openssh.com,sk-ecdsa-sha2-nistp256@openssh.com,sk-ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-ed25519,ssh-ed25519-cert-v01@openssh.com,sk-ssh-ed25519@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,rsa-sha2-256,rsa-sha2-256-cert-v01@openssh.com,rsa-sha2-512,rsa-sha2-512-cert-v01@openssh.com,ssh-rsa,ssh-rsa-cert-v01@openssh.com,ssh-dss,ssh-dss-cert-v01@openssh.com

Much longer, yes? In other words, the legacy policy allows more public key algorithms. In this case, note the addition of ssh-rsa.

My out-of-date (foreshadowing!) dropbear server really wants that ssh-rsa algorithm, and the new policies on my client side (Fedora 33) forbid it.

I know! Reduce the security. All will be well.

Wait. Just wait. Yes, we can solve this be adding that algorithm into the allow list, and read below to find out how. But, really, there are better ways, if you have the permissions and time to do so.

Solution #1: Upgrade the server

As has been foreshadowed, the first and best choice may be to upgrade the legacy server. If the server is using an old version of openssh or dropbear, ask the sysadmin of that server to upgrade.

I happened to be the sysadmin for my server. The Linux distro on it is Alpine. Unfortunately, Alpine only has the most recent version of dropbear in their "edge" branch. So I had to pull from upstream:

sudo apk upgrade dropbear --repository=http://dl-cdn.alpinelinux.org/alpine/edge/main

In some cases, though, you may need to switch distributions, or run an openssh-server container with docker or podman.

Solution #1.5: generate new keys

If you can't upgrade the server, and even if you can, consider using ecdsa or, better yet, ed25519 keys. Really, the only reason to not use ed25519 is if your server doesn't support them.

Generate a new ed25519 key like so:

ssh-keygen -t ed25519 -a 64

(While doing 64 rounds on the key derivation isn't strictly necessary, it adds a little reassurance for only fractions of a second.)

If your server does not support ed25519 but does support ecdsa, then something like the following may be best:

ssh-keygen -t ecdsa -a 64 -b 384

The increase to 384 bits and the 64 kdf rounds are, again, not strictly necessary. Just some extra entropy.

To summarize:

• if I was unable to upgrade my legacy server (dropbear 2019.78), changing to an ecdsa key would be more secure and also in line with Fedora 33 crypto policies. Provided the legacy server supports ecdsa, of course.
• if I was able to upgrade my legacy server to a recent version that supports ed25519 keys, I would still leave my RSA key behind to have the assurance of security, even though the new server would be just fine with my old SHA256-signed 3072-bit RSA key. It's time to move up. Elliptic curve it is.

Be sure to add your new public keys to the authorized_keys file on the remote server, with something like this:

cat ~/.ssh/id_ed25519.pub | ssh the_server_name_or_ip "cat >> ~/.ssh/authorized_keys"

Solution #2: downgrade security system-wide

If and only if solution #1 and/or #1.5 do not work for you, you can downgrade the crypto security policies.

To do so globally (for all SSH connections):

update-crypto-policies --set LEGACY

You can always switch it back with

update-crypto-policies --set DEFAULT

If you want to live on the edge, try update-crypto-policies --set FUTURE just to see what breaks, if anything.

Solution #3: downgrade security per host

If you need to downgrade security, I like this solution better: for the legacy server(s) in question, circumvent the public key types per server, in your ~/.ssh/config file. This way you are accommodating only those servers that are problematic, and retaining upgraded security policies in relation to the others.

You can add the following to each host that needs it: PubkeyAcceptedKeyTypes +ssh-rsa

If you don't have an entry for that host yet, make one. If your server is "legacy_or_dropbear2019.com", and you want to give it the alias "legacy", try something like this:

Host legacy
  HostName legacy_or_dropbear2019.com
  User my_user
  Port 22
  PubkeyAcceptedKeyTypes +ssh-rsa

In the above, you don't need User or Port necessarily. I just left them there as examples of how you can configure a host in .ssh/config.

Please comment if you have advice, corrections, or experiences to share!

Credits

Thanks to this reddit discussion I had with myself and others. Really helped to clarify matters.

Blowfish image courtesy of JoyPixels and shared under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.