I already generated a new 2048-bit RSA key pair for SSH this year, on January 3rd, to replace the 1024-bit DSA key pair that I had been using since October 23, 2010. I’ve been putting off generating a new key pair for use on my laptop because I didn’t want to have to go through the effort of figuring out exactly which hosts I need to copy the new public key to.

Since the NSA has been trying very hard to scare us recently, I’m not entirely certain that my existing 2048-bit key is strong enough. I read an article telling me that the NSA may have the magical ability to crack 1024-bit RSA keys in a matter of hours. I’m not so sure I believe this, but what’s the harm in going overboard and generating some fresh, new 4096-bit keys? I have to update a few dozen authorized_keys files with the new public key on my laptop, and it doesn’t require much more work to add a new key for my desktop at the same time.

Is authentication slower when using a 4096-bit key?

I was a little worried about this, so I did some testing. Connecting to my web server with SSH using my new 4096-bit key usually takes between 0.35 and 0.39 seconds. That’s only two or three hundredths of a second slower than when using my old 2048-bit key.

1
2
3
4
5
6
7
8
9
10
11
12

wonko@zaphod:~$ for x in {1..5};do /usr/bin/time ssh patshead.com exit;done
0.00user 0.00system 0:00.38elapsed 2%CPU (0avgtext+0avgdata 3264maxresident)k
0inputs+0outputs (0major+998minor)pagefaults 0swaps
0.00user 0.00system 0:00.39elapsed 2%CPU (0avgtext+0avgdata 3268maxresident)k
0inputs+0outputs (0major+999minor)pagefaults 0swaps
0.00user 0.00system 0:00.37elapsed 1%CPU (0avgtext+0avgdata 3268maxresident)k
0inputs+0outputs (0major+999minor)pagefaults 0swaps
0.00user 0.00system 0:00.37elapsed 1%CPU (0avgtext+0avgdata 3264maxresident)k
0inputs+0outputs (0major+998minor)pagefaults 0swaps
0.00user 0.00system 0:00.35elapsed 1%CPU (0avgtext+0avgdata 3264maxresident)k
0inputs+0outputs (0major+998minor)pagefaults 0swaps
wonko@zaphod:~$

Using PKCS#8 for more secure SSH private key files (Ubuntu 13.10 and older)

Earlier this year, I saw Martin Kleppmann’s article about improving the security of your SSH private keys. Martin points out that brute forcing the passphrase on a private key created by ssh-keygen isn’t a very difficult task. You won’t have much time to remove your key from your servers if someone manages to get their hands on your private key.

Martin’s excellent write-up also explains how to convert your ssh-keygen generated PEM key file into a more secure PKCS#8 key file. I’m not exactly sure of just how much more security this is really buying me, but anything is better than using MD5, and I’ll take every bit of extra security I can get.

This is probably just about the as safe as you’re going to get if you have an older version of OpenSSH that doesn’t support the new key format. You should definitely skip this part iff your installed version of OpenSSH supports the new key format and PBKDF.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

wonko@zaphod:~$ ssh-keygen -b 4096 -f .ssh/id_rsa4096_2013 -C wonko@zaphod_4096_2013
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in .ssh/id_rsa4096_2013.
Your public key has been saved in .ssh/id_rsa4096_2013.pub.
The key fingerprint is:
ba:dc:39:af:d3:e5:d8:85:d6:f0:77:f0:cb:62:05:66 wonko@zaphod_4096_2013
The key's randomart image is:
+--[ RSA 4096]----+
|                 |
|                 |
|                 |
|            .E.  |
|        S   o=.o |
|       .    + +.+|
|      .  . * .o.o|
|     . oo.o oo o |
|      o +=. . .  |
+-----------------+
wonko@zaphod:~$ umask 0077
wonko@zaphod:~$ openssl pkcs8 -topk8 -v2 des3 -in ~/.ssh/id_rsa4096_2013 -out ~/.ssh/id_rsa.new && mv ~/.ssh/id_rsa.new ~/.ssh/id_rsa4096_2013
Enter pass phrase for /home/wonko/.ssh/id_rsa4096_2013:
Enter Encryption Password:
Verifying - Enter Encryption Password:
mv: overwrite ‘/home/wonko/.ssh/id_rsa4096_2013’? y
wonko@zaphod:~$ head -1 .ssh/id_rsa_2013
-----BEGIN RSA PRIVATE KEY-----
wonko@zaphod:~$ head -1 .ssh/id_rsa4096_2013
-----BEGIN ENCRYPTED PRIVATE KEY-----
wonko@zaphod:~$

Using PBKDF for extremely secure SSH private key files (Ubuntu 14.04 and newer)

I’ve been waiting patiently for Ubuntu 14.04 to ship. It includes the latest release of OpenSSH, and this version supports a new key encryption method. This encryption method, called PBKDF, is much more secure, since it is designed to run slowly. This means it takes much, much longer to brute force a stolen key.

Immediately after upgrading my laptop, I found an excellent blog explaining the new key format and how to make use of it. I stole his command line, and his idea to use 1000 rounds. The more rounds you use, the longer it takes to decrypt your key. Increasing the number of rounds makes it take longer to brute force your key.

I think 1000 rounds is a bit excessive. It takes a solid seven or eight seconds to decrypt on my laptop, and that just feels like an eternity. I decided to cut that in half. That is still several orders of magnitude more secure than my old keys!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

wonko@zaphod:~$ ssh-keygen -b 4096 -f .ssh/id_rsa4096_test -C wonko@zaphod_test -o -a 500
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in .ssh/id_rsa4096_test.
Your public key has been saved in .ssh/id_rsa4096_test.pub.
The key fingerprint is:
3c:f1:43:62:b6:c8:fc:d0:86:67:65:29:93:14:7b:d9 wonko@zaphod_test
The key's randomart image is:
+--[ RSA 4096]----+
|        o.       |
|       . o +     |
|        X B E    |
|     o B %       |
|      * S o      |
|       * . .     |
|        .        |
|                 |
|                 |
+-----------------+
wonko@zaphod:~$

Updating a few dozen authorized_keys files

I needed to add my new public keys to a few dozen hosts, and I also needed to remove the keys. Lucky for me, I’m not sharing a login on any of these hosts, so I was able to do this the easy way.

All I had to do was remove the old keys from my local .ssh/authorized_keys files and add the two new public keys. Then I just used scp to push that out to all the other machines.

1

wonko@zaphod:~$ for host in patshead.com laptop tf2.patshead.com; do scp ~/.ssh/authorized_keys $host:.ssh/; done

There were a few hosts that I was a little more careful with, though. I didn’t want to lock myself out of any virtual server host machines.

More than just my SSH keys need updating

My personal GnuPG key is embarrassingly old and weak. I’m looking at it right now, and I don’t even want to say how old it is. My corporate GnuPG key is much less embarrassing. It isn’t even two years old yet, and it is a 4096-bit RSA key.

I’m going to have to correct this oversight in the near future. Once I get that taken care of, I can print QR codes of all my new private keys and lock them safely away in case of an emergency.