There’s a new private key format for OpenSSH, thanks to markus and djm. It’s enabled automatically for keys using ed25519 signatures, or also for other algorithms by specifying -o to ssh-keygen. The new format allows for new functionality, the most notable of which may be the addition of support for better key derivation functions (KDF). (Also known as a PBKDF, as in password based.)

Old encrypted keys have a short header that identifies them and the encryption algorithm used. Here’s the start of an old RSA key using DES and a newer ECDSA key that uses AES.

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,...

base64 nonsense
-----BEGIN EC PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,...

base64 nonsense

In both cases, the passphrase is converted to a cipher key by running it through MD5. MD5 is very fast, which makes it possible for an attacker who gets hold of the private key file to make lots of guesses in a very short amount of time (think billions per second with the help of a few graphics cards). Hope you have a long passphrase.

What works better than hope is a KDF specifically designed to be slow. The new key format identifies both the name of the KDF used and its parameters. Currently the default (and only) KDF is the bcrypt pbkdf, which is very similar to the bcrypt password hash. It’s nice and slow. By default, it’s applied with 16 rounds, which takes my reasonably fast laptop half a second, and by specifying the -a option to ssh-keygen that can be increased to 1000 rounds, taking a full 30 seconds.

I mention these numbers so you don’t accidentally take a rounds parameter appropriate for PBKDF2 and use it here. For example, WPA uses 4096 rounds and still computes almost instantly. 4096 rounds of bcrypt would take approximately two minutes. That’s a long time to wait to login. (Technical note: PBKDF2, aka PKCS #5, supports pluggable hash functions, though in practice everybody uses HMAC-SHA1. The bcrypt pbkdf essentially is PBKDF2, but with bcrypt plugged into it instead.)

Keys in the old format can by upgraded to the new format by using ssh-keygen. For example:

ssh-keygen -o -p -f id_ecdsa -a 1000
Enter old passphrase:
Key has comment 'id_ecdsa'
Enter new passphrase (empty for no passphrase):
Enter same passphrase again:
[wait 30 seconds]
Your identification has been saved with the new passphrase.

Now the key file looks like this:

-----BEGIN OPENSSH PRIVATE KEY-----
base64 nonsense

It’s harder to peek inside, but running ssh-add confirms the change. Entering the wrong password requires 30 seconds of processing before it tells me “Bad passphrase”. Compare with the instantaneous result when entering the wrong password with the old key. 1000 rounds is extreme, however; the default of 16 is reasonable. If you’re feeling paranoid, maybe try 64, which will take about two seconds of processing time.

Note that the new key format is only supported starting with OpenSSH 6.5. This shouldn’t pose too much of a problem in upgrading, as it only affects the private key. You can still login to all the same servers, but if you copy key files between machines you’ll want to check for compatibility.