Updated on December 20th, 2022 in #linux

Switching from an RSA SSH Key to Ed25519 on Ubuntu 22.04

On Ubuntu 22.04 you'll get an SSH error of no mutual signature algorithm unless you change keys or modify PubkeyAcceptedKeyTypes.

Quick Jump: A Few Options to Solve This | Generating an Ed25519 SSH Key | Demo Video

Let’s say you just updated your dev box to Ubuntu 22.04 and carefully moved over your ~/.ssh directory from your backups and fixed all of the file permissions.

Then you tried to SSH into one of your servers and you got this error:

$ ssh you@example.com
you@example.com: Permission denied (publickey)

You’re absolutely sure your key works because if you use another device with Ubuntu 20.04 it works. The file permissions are identical too.

This happened to me recently when I updated my WSL 2 instance to Ubuntu 22.04.

If you run ssh you@example.com -v you’ll get a lot of great information in the output. Near the bottom you’ll likely see something similar to:

debug1: Next authentication method: publickey
debug1: Offering public key: /home/nick/.ssh/id_rsa RSA SHA256:...
debug1: send_pubkey_test: no mutual signature algorithm

If you see this chances are you have an older RSA SHA-1 or RSA SHA-256 based SSH key. I know I did because I created mine like 8 years ago.

You can check which RSA key you have by running:

$ ssh-keygen -lf ~/.ssh/id_rsa
2048 SHA256:gOSWbGlO4Z1S2mV2k7BI05QHuTZIZ0OcEaSrVmWI+ZE nick@nick-vb (RSA)

I know my key is super old because that nick-vb hostname is back when I used Virtual Box as my dev environment way before WSL 1 and WSL 2 existed.

This is the root cause of the problem.

At some point OpenSSH dropped support for this algorithm and the version of OpenSSH on Ubuntu 22.04 doesn’t support RSA keys by default.

A Few Options to Solve This

We have 2 options to address this:

• Configure our OpenSSH client to support RSA
• Create a new Ed25519 or ECDSA based key and slowly migrate everything to it

I’d suggest a combination of both options because the first option is purely client side, you don’t need to change anything on your servers or whatever devices require your specific SSH key. It’s a great temporary solution.

You can do that by modifying your dev box’s SSH config by adding this to the top of the file. This is taken straight from the OpenSSH changelog that introduced the deprecation:

# After adding this you'll be able to connect with your old RSA key.
Host *
  HostkeyAlgorithms +ssh-rsa
  PubkeyAcceptedAlgorithms +ssh-rsa

The first bullet is appealing because it gives you a way to create a new SSH key and add it to your servers while supporting the old RSA key at the same time. Basically you won’t ever lock yourself out of your server by mistake – in case you do a number of popular hosting providers let you open a VNC connection through a browser without depending on SSH.

Then you can add your new key to your servers’ ~/.ssh/authorized_keys while keeping your old RSA key there at the same time. When you’re confident and 100% happy that everything is working with your new key you can go back and remove the RSA key entry in that file.

You can continue to keep your old id_rsa key on your dev box even well after all of your servers were modified to only support the new SSH key. This gives you some type of peace of mind in case you forgot to update something. There’s no real harm keeping the unused RSA key idling on your dev box.

Ed25519 vs ECDSA: Which One Should You Pick?

I haven’t read the white papers and I’m not well versed in low level cryptography.

I did research this a bit and Ed25519 seems to have a number of practical advantages around not just speed but having protection against certain types of attacks.

Feel free to do further research. I mean, if you’re reading this article you’re likely using RSA which is less secure than either option so you’re probably in the same shoes as me which is wanting to have a well supported SSH key that adheres to specifications that very smart people have vetted against the test of time.

Also, GitHub, GitLab and Bitbucket’s official documentation suggests using Ed25519. I don’t like blindly doing something because “everyone else” is doing it but given the nature of how important it is to pick a secure SSH algorithm I’m OK following the majority this time.

By the way, Ed25519 works with OpenSSH 6.5+. That means even if you have extremely old and unsupported servers running Debian Jessie it’ll work because Jessie has 6.7. You can check which version you have on your server by running ssh -V.

Generating an Ed25519 SSH Key

It’s a one liner as seen below:

$ ssh-keygen -t ed25519 -C "you@example.com"

Generating public/private ed25519 key pair.
Enter file in which to save the key (/home/nick/.ssh/id_ed25519):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in id_ed25519
Your public key has been saved in id_ed25519.pub
The key fingerprint is:
SHA256:smLpHrmd/3cJhjhWGgxv1IrbOtt8HdPJFyS/TTjlbtg you@example.com
The key's randomart image is:
+--[ED25519 256]--+
|         .       |
|      . . .  . ..|
|       * .    ++ |
|      . * .   ooo|
|      .+S= . o B+|
|     o.o* . = =.E|
|    * .o . o + + |
|   o =o+  . o o  |
|   .+ +++o.. .   |
+----[SHA256]-----+

Now you can copy ~/.ssh/id_ed25519.pub and add it to the bottom of your servers’ ~/.ssh/authorized_keys file on its own line and you’ll be able to SSH in.

If you changed your OpenSSH client config earlier to support RSA you can confirm your new Ed25519 key works by commenting out those lines and trying to SSH in again. It should work.

You can also SSH in with the -v flag and see which key was used. You should see output similar to this near the bottom:

debug1: Offering public key: /home/nick/.ssh/id_ed25519 ED25519 SHA256: ...
debug1: Server accepts key: /home/nick/.ssh/id_ed25519 ED25519 SHA256: ...
Authenticated to example.com ([127.0.0.1]:22) using "publickey".

Yay, you’re all set.

Demo Video

Timestamps

• 0:35 – Ubuntu 22.04 doesn’t support RSA based SSH keys out of the box
• 1:04 – What is Ed25519?
• 2:04 – Encountering and debugging the permission denied SSH error
• 3:41 – Seeing what type of RSA key you have with ssh-keygen
• 4:35 – We have a couple of options and they can be used together
• 6:29 – Updating your keys without locking yourself out
• 7:32 – Ed25519 vs ECDSA
• 8:34 – Ed25519 works with OpenSSH 6.5+
• 9:35 – Generating a new Ed25519 SSH key
• 11:47 – Copying your new key to your server’s authorized_keys file

References

• https://en.wikipedia.org/wiki/Curve25519

Were you still using an older RSA SSH key too? Let me know below.