Ever heard someone saying that using ssh-keys is a perfect way to have “passwordless” logins to servers? Probably you have. There is a big problem with this approach (I will ignore ssh-agents and stuff like this in this article). If you really want a completley passwordless login, you will need to store the private key unencrypted. The key can be stolen without you knowing it and the attacker could use it “as is”.

The first countermeasure is to encrypt the key and protect it with a passphrase. But since the key is just a file without any brute force protection it could (if the passphrase is weak or semiweak) be very easy to crack the key open. The encryption key used is just a md5 hash of your passphrase and md5 is… fast. Since OpenSSH 6.5 there is a bettery way to protect your ssh-keys. A new private key format is used where you can apply KDF (key deviation function) to slow down the decryption of your private key.

To create a key in the new format with KDF applied you use -o for the new key format and -a specify how many rounds of KDF to use. (more rounds is slower to decrypt)

> ssh-keygen -a 256 -o -t rsa -b 4096 -f test
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in test.
Your public key has been saved in test.pub.
The key fingerprint is:
45:20:9e:50:d2:6e:c9:11:bb:3a:fe:1c:a3:c6:93:48 peter
The key's randomart image is:
+--[ RSA 4096]----+
|    oo+....      |
|     +o+ .       |
|     o+o  .      |
|      =. .       |
|     .. S        |
|  E  .           |
| . oo.o          |
|  ..=+ o         |
|   .ooo          |
+-----------------+

How many rounds to use depends on your environment and how concerned you are about losing your private keys. 256 rounds on a reasonable modern computer takes me ~4s to decrypt. This is a infinite amount of time compared md5 brute force.