Cadey is coffee
<Cadey> Hello! Thank you for visiting my website. You seem to be using an ad-blocker. I understand why you do this, but I'd really appreciate if it you would turn it off for my website. These ads help pay for running the website and are done by Ethical Ads. I do not receive detailed analytics on the ads and from what I understand neither does Ethical Ads. If you don't want to disable your ad blocker, please consider donating on Patreon or sending some extra cash to xeiaso.eth or 0xeA223Ca8968Ca59e0Bc79Ba331c2F6f636A3fB82. It helps fund the website's hosting bills and pay for the expensive technical editor that I use for my longer articles. Thanks and be well!

How to move away from RSA for SSH keys

Read time in minutes: 7

hero image volcano-bliss
Image generated by Stable Diffusion v1.5 -- a rolling green landscape by makoto shinkai, breath of the wild, active volcano, windows xp bliss, manga style, ((thick outlines))

RSA is one of the most widely deployed encryption algorithms in the world. Notably, when you generate an SSH key without any extra flags, ssh-keygen will default to using RSA:

root@hiro:~# ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa):

For a while cryptographers have feared that RSA is vulnerable to a quantum computing algorithm known as Shor's Algorithm. I won't pretend to understand it in this article, but the main reason why it's not deployed is that the hardware required to attack RSA keys in the wild literally doesn't exist yet (think literally tens of generations more advanced than current quantum computers).

A group of researchers have just published a paper that posits that it's likely you can break 2048-bit RSA (the most widely deployed keysize) with a quantum computer that only uses 372 qubits of computational power. The IBM Osprey has 433 qubits.

Cadey is coffee
<Cadey> Note that quantum computers are effectively unobtainable (unless you're a research institution or you have a few small loans of billions of dollars laying around), require a team of highly specialized experts to monitor them 24/7, and aren't really usable to the general public. I highly doubt that quantum computers are going to be rolling into store shelves any time soon. I also have no idea what I'm talking about with quantum computers. Please temper your interpretations of my statements appropriately.

It may be a good time to move away from RSA keys when and where you can. Today I'm going to cover how to make SSH keys using ed25519 keys instead of RSA.

Mara is hacker
<Mara> It's worth noting that RSA has not been broken yet, the paper in question describes a theoretical attack. Quantum computers are nowhere near good enough for this yet.

Generating new keys

To generate a new keypair, use the ssh-keygen command:

ssh-keygen -t ed25519

Make sure to set a password on that key and then you can add it to your SSH agent with ssh-add. Copy the public key to your clipboard (print it to the screen with cat ~/.ssh/ and then you can add it to GitHub or other services you use.

Mara is hacker
<Mara> Pro tip: you can get a list of machines you've SSHed into by reading your ~/.ssh/known_hosts file. You could use a command like this:

cat ~/.ssh/known_hosts | cut -d' ' -f1 | sort | uniq

Mara is happy
<Mara> This will get you a list of machines that you may need to update your SSH key in! Remember that your new key should go to the end of ~/.ssh/authorized_keys!

Disabling RSA host keys

The OpenSSH server will create a keypair for each machine it runs on. By default this creates an RSA key as well as an ed25519 key. You can disable this by adding the following line to /etc/ssh/sshd_config:

HostKey /etc/ssh/ssh_host_ed25519_key

Mara is hacker
<Mara> In my testing, this was the case for both NixOS and Ubuntu. If you want to be sure you're setting the right key, check the file for commented-out HostKey instructions. Uncomment whichever one contains ed25519 in it.

If your SSH configuration file has a Ciphers, HostKeyAlgorithms, PubkeyAcceptedAlgorithms, or CASignatureAlgorithms setting in it, you may want to make sure that any rsa cipher or algorithm isn't present in any of them. If your distro has an option to change this system wide (such as in Red Hat and derivatives), you may want to use that.

Mara is happy
<Mara> You may want to have some kind of transition period for shared machines before you start rejecting RSA keys willy-nilly. This can break people's workflows and SSH-key-in-GPG setups. Talk with your users and work on compromises. Something something shill for the company supplying the author of this post with the money needed for food something something.

If you want to do this on NixOS, add the following configuration to either your configuration.nix or something that is imported by your configuration.nix:

services.openssh.hostKeys = [{
  path = "/etc/ssh/ssh_host_ed25519_key";
  type = "ed25519";

Mara is hacker
<Mara> This tells SSH to use only an ed25519 host key. By default it will also create an RSA key.

I hope this helps! Systems administration is full of annyoing migrations and compromises like this. Good luck out there!

Mara is hacker
<Mara> Also check out this article on how you can store an SSH key on a Yubikey or any other compliant FIDO2 key!

This article was posted on M01 04 2023. Facts and circumstances may have changed since publication. Please contact me before jumping to conclusions if something seems wrong or unclear.

Tags: OpenSSH RSA ed25519 security sre NixOS

The art for Mara was drawn by Selicre.

The art for Cadey was drawn by ArtZora Studios.

Some of the art for Aoi was drawn by @Sandra_Thomas01.