Upgrade your SSH security with RSA and Ed25519 keys

As a DevOps engineer, you're probably already familiar with SSH keys and how to use them. I've written about SSH before; you'll find those posts in the references. This time, I want to take a closer look at SSH key strength and the algorithms you can choose.

Why should you care about this?

Passwords are becoming more and more of a security risk. At the time of writing, GitHub will soon stop supporting password authentication for clone, push and pull actions, just as it did for its APIs. SSH keys also offer a more secure way to access your servers. That's why it's worth knowing how to set up your SSH keys securely and use them safely.

This is how I've been generating my SSH keys for years.

ssh-keygen -t rsa -b 4096 -C marco.franssen@domain.tld

So is this still the recommended approach? Let's find that out.

Algorithms for SSH keys

Based on the table above, I'm still safe with the keys I'm using, but there are a few small improvements I can make. Let's take a closer look at the algorithms and how to generate keys.

DSA

This algorithm is deprecated due to very poor randomness. OpenSSH version 7.0 and newer even refuse DSA keys smaller than 1024 bits. DSA key pairs should no longer be used.

RSA

This non-elliptic cryptographic algorithm is based on prime numbers. It's probably the most widely used algorithm at the time of writing. Keys shorter than 2048 bits are considered insecure. RSA's source of entropy is its weakest link. This is probably the first algorithm to fall as quantum computing matures. From the perspective of this 2021 post, a 3072-bit key should be safe for the next two years, while a 4096-bit key should probably be safe for at least the next five years.

ECDSA

The elliptic-curve (EC)DSA algorithm is supposed to help us combat these quantum computing attacks, while generating significantly smaller keys without compromising security. The size of the elliptic curve determines how difficult it is to break the algorithm. Secure implementations of the ECDSA curves are theoretically possible, but very hard in practice. Furthermore, a weakness in the random number generator (RNG) was publicly identified but still incorporated by NIST. We later learned from Snowden that the NSA had worked on the standardization process to become the sole editor of the Dual_EC_DRBG standard, and concluded that this NIST standard did indeed contain a backdoor for the NSA. Why trust NIST curves when there's a more transparent way of doing cryptography?

Ed25519

Ed25519 was introduced in OpenSSH 6.5 (January 2014). It's an EdDSA implementation using the Twisted Edwards curve. It uses elliptic-curve cryptography to offer better security and faster performance compared to DSA or ECDSA.

At the time of writing, RSA is the most widely used public-key algorithm for SSH keys. Compared to Ed25519, though, it's slower and is considered unsafe if the key is shorter than 2048 bits.

The Ed25519 public key is compact. It contains only 68 characters, compared to 544 for RSA 3072. Generating the key is also almost as fast as signing. Ed25519 is fast at batch signature verification, too. It's built to be collision-resistant: a hash-function collision won't break the system.

Long story short: it is not NIST and it is not NSA. The longer story is that, while NIST curves are advertised as being chosen verifiably at random, there's no explanation for the seeds used to generate them. The process used to pick Ed25519 curves is fully documented and can be verified independently. This prevents a malicious party from manipulating the parameters. Furthermore, the Ed25519 algorithm is supposed to be resistant to side-channel attacks.

What to do with this information

As we've already concluded, my key is still on the safe side, but I can improve a few things. When generating the RSA key, I'm still saving the private key in PEM format. I could store it in the newer, more secure OpenSSH format by providing another command-line option (for ed25519, this is the default). Let's do that.

Generate a strong RSA key

$ ssh-keygen -o -t rsa -b 4096 -C marco.franssen@macbook-pro
Generating public/private rsa key pair.
Enter file in which to save the key (/Users/marco/.ssh/id_rsa): /Users/marco/.ssh/id_rsa_new
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /Users/marco/.ssh/id_rsa_new.
Your public key has been saved in /Users/marco/.ssh/id_rsa_new.pub.
The key fingerprint is:
SHA256:t8yF1u3ahe/BfVtqHz6XO+2L11P9oW6WKw3ojdKZxsY marco.franssen@macbook-pro
The key's randomart image is:
+---[RSA 4096]----+
|                 |
|    E  .@        |
|                 |
|         o .     |
|        S = o . .|
|         * + ..o+|
|        = O o =+%|
|       . E o O+X@|
|        +   *==O%|
+----[SHA256]-----+

⚠️ Please note that we're using a passphrase to protect our private key. I'm also storing the key in a new file so I can gradually migrate the keys on my servers. (More on that later…)

What command-line options did we use?

• -o: Save the private key using the new OpenSSH format rather than PEM.
• -t: Specify the type of key to create; in our case, RSA.
• -b: Specify the key length; in our case, 4096 bits. Use at least 3072 bits.
• -C: Specify an informational comment. I usually use <login>@<hostname> to identify the key.

Without the -o option, we would have stored a private key that begins with:

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,7A720C77B76E72BD9BCE0ADD9EB80961
 
v+j4P…………………

With the -o option, our key is now stored in the new OpenSSH format.

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAACmFlczI1Ni1jdHIAAAAGYmNyeXB0AAAAGAAAABDkGszUTi
xCI0MMO………………

Now I also want a key using the Ed25519 algorithm, as it's considered more future-proof and uses smaller keys, which should improve the performance of my SSH connections. Let's have a look at that.

Generate an Ed25519 key

$ ssh-keygen -t ed25519 -a 64 -C marco.franssen@macbook-pro
Generating public/private ed25519 key pair.
Enter file in which to save the key (/Users/marco/.ssh/id_ed25519):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /Users/marco/.ssh/id_ed25519.
Your public key has been saved in /Users/marco/.ssh/id_ed25519.pub.
The key fingerprint is:
SHA256:Mc/2w2DifqTIvLd214aawJtFVl8pv//ZzEXiq8/JwPo marco.franssen@macbook-pro
The key's randomart image is:
+--[ED25519 256]--+
|   @ .. ..       |
|                .|
|        o   .. . |
|         = . .o. |
|        S O   o..|
|       o *.= . o.|
|     o .+O. *o...|
|      +.+=o o=o==|
|      .+=+++E+*.B|
+----[SHA256]-----+

⚠️ Please note that we're using a passphrase to protect our private key. I've used 64 KDF rounds, which seems to be a good trade-off between waiting time and brute-force attacks.

• -a 16 takes on average 0.247 (seconds) *default*
• -a 32 takes on average 0.586
• -a 64 takes on average 1.206
• -a 100 takes on average 1.962
• -a 150 takes on average 2.664

What command-line options did we use?

• -o: Save the private key using the new OpenSSH format rather than PEM. This is implicit when using ed25519.
• -t: Specify the type of key to create; in our case, RSA.
• -a: Specify the number of KDF (key derivation function) rounds. Higher numbers result in slower passphrase verification, increasing resistance to brute-force password cracking if the private key is stolen.
• -C: Specify an informational comment. I usually use <login>@<hostname> to identify the key.

Looking at the generated keys, we can see that the ed25519 keys are indeed much smaller than our RSA keys.

$ for k in ~/.ssh/id_* ; do wc -m $k ; done
     464 /Users/marco/.ssh/id_ed25519
     108 /Users/marco/.ssh/id_ed25519.pub
    3326 /Users/marco/.ssh/id_rsa
     752 /Users/marco/.ssh/id_rsa.pub
    3434 /Users/marco/.ssh/id_rsa_new
     752 /Users/marco/.ssh/id_rsa_new.pub

Using the newly created SSH keys

To use your SSH keys, you'll need to load them into your ssh-agent. We can also define which key to use for each server connection. This lets us migrate gradually.

Host github.com
  IdentityFile ~/.ssh/id_ed25519
 
Host my.legacy.server.com
  IdentityFile ~/.ssh/id_rsa_new
 
Host *
  IdentityFile ~/.ssh/id_ed25519
  IdentityFile ~/.ssh/id_rsa_new
  IdentityFile ~/.ssh/id_rsa

Once you've migrated all your keys, you can clean up the old id_rsa key. If all the servers you connect to support the ed25519 algorithm, you can eventually use just the id_ed25519 key.

Host *
  IdentityFile ~/.ssh/id_ed25519

For more details on configuring SSH, have a look at my other blog posts on SSH. There, I go into more detail on configuring your SSH client, including agent forwarding.

References

• Put your SSH experience in Windows on steroids
• How to use Secure Shell easily from the terminal
• Security keys are now supported for SSH Git operations
• Twisted Edwards Curve
• ECDSA contains a backdoor for the NSA
• Ed25519 documentation
• Side-channel attacks
• How many KDF rounds should I use for an SSH Key?

See you next time. Please consider sharing this with your peers so we can make our work more secure.