-a is for rounds

tl;dr ssh-keygen -o -a 100 is more than enough.

If you look closely at (a recent) ssh-keygen —help (or even man ssh-keygen), you’ll see that ssh-keygen provide a way to strengthen your private key against brute-force attacks.

When saving a new-format private key (i.e. an ed25519 key or any SSH protocol 2 key when the -o flag is set), this option specifies the number of KDF (key derivation function) rounds used. Higher numbers result in slower passphrase verification and increased resistance to brute-force password cracking (should the keys be stolen).

and about the -o option:

-o Causes ssh-keygen to save private keys using the new OpenSSH format rather than the more compatible PEM format. The new format has increased resistance to brute-force password cracking but is not supported by versions of OpenSSH prior to 6.5. Ed25519 keys always use the new private key format.

What is this? Witchcraft?! Let’s have a look! Upon reading ssh-keygen.c, you’ll see that it uses extensively the functions located in sshkey.c

The rounds variable is set in ssh-keygen.c and read from argv

		case 'a':
			rounds = (int)strtonum(optarg, 1, INT_MAX, &errstr);
			if (errstr)
				fatal("Invalid number: %s (%s)",
					optarg, errstr);
			break;

In sshkey.c we have a few insight on this « mysterious » Key Derivation Function (KDF):

#define KDFNAME "bcrypt"
#define DEFAULT_ROUNDS 16

The function is int bcrypt_pbkdf(const char *pass, size_t passlen, const u_int8_t *salt, size_t saltlen, u_int8_t *key, size_t keylen, unsigned int rounds)

And if you go deeper, this is where the rounds variable is used

for (i = 1; i < rounds; i++) {
			/* subsequent rounds, salt is previous output */
			crypto_hash_sha512(sha2salt, tmpout, sizeof(tmpout));
			bcrypt_hash(sha2pass, sha2salt, tmpout);
			for (j = 0; j < sizeof(out); j++)
				out[j] ^= tmpout[j];
		}

Even if the name (bcrypt) gave the answer, we now know that the workload is linear.

If we want to verify this with a more empirical technique, we can just generate lots of ssh key and trace the time for each generation depending on the rounds values.

note: -a = 0 is not a correct value but I’m lazy so…

#!/bin/bash

 mytime() {
 python -c 'import time; print time.time()'
 }

 for i in `seq 0 50 2000`
	 do
		 timer1=$(mytime)
		 ssh-keygen -o -a $i -t ed25519 -P "toto" -f $i.ssh
		 timer2=$(mytime)
		 runtime=$(echo "$timer2 - $timer1" | bc)
		 echo "$i, $runtime" >> data.txt
	 done

But why should all this matters? After all, security is all fun and play until someone loses a private key… And adding more rounds will only buy you time… but only (and if only) your ssh key password is strong enough. And if it’s strong enough then you don’t really need to set a high number of rounds…

I see several reasons to fix a reasonable of rounds…:

1. Schadenfreude: the attacker will have crappy c/s and they don’t like this…
2. It’s buying you time… That is if you set a good enough password and realise that you lost your private key…
3. Because some people will blame you if you don’t.

However, the KDF function also applies to you so you have to chose wisely the number of rounds… I personnaly settled for 100 as it only adds 1 second to my ssh login delay.

Of course, we can check if 100 is enough to make John unhappy…

~/P/ssh ❯❯❯ john -format=ssh-ng -test
Benchmarking: SSH-ng [RSA/DSA 32/64]... DONE
Raw:	493117 c/s real, 493117 c/s virtual

~/P/ssh ❯❯❯ /usr/local//Cellar/john-jumbo/1.8.0/share/john/sshng2john.py 100.rsa.ssh > test.john

~/P/ssh ❯❯❯ john -format=ssh-ng test.john
Loaded 1 password hash (SSH-ng [RSA/DSA 32/64])
Note: This format may emit false positives, so it will keep trying even after
finding a possible candidate.
Press 'q' or Ctrl-C to abort, almost any other key for status
Ssh100           (100.rsa.ssh)
1g 0:00:00:15 1.39% 1/3 (ETA: 17:52:23) 0.06459g/s 6.589p/s 6.589c/s 6.589C/s rsas
Session aborted