How many KDF rounds for an SSH key?

Question

What is the best practice on choosing how many key derivation function (KDF) rounds/iterations when generating an SSH key pair with ssh-keygen?

Am I correct in saying that it is unnecessary if the passphrase is strong enough? Is there some kind of formula for how long it would take to crack a private key given the passphrase length and KDF rounds?

My guess is that the default value of 16 for when generating an Ed25519 key is small enough to be almost imperceptible for normal use (logging into a server from the command line), but adds significant expense to any brute-force attempts. I'm wondering if it's worth increasing it.

Answer 1

I did also tried to find a good value for the -a flag, in a MacBook Pro Mid14 (i7), trying to login in to a Debian 8.5, I had this results:

• -a 1000 Took about ~20s.
• -a 100 Varies between ~3.5s to ~6s.
• -a 64 (4x default value) ~3 to ~9s.
• -a 16 (default) ~2s ~2.5s.

In the end I just stick with the default since I'm not a paranoiac and I don't like to wait, however I did found in my research a value of 100 is not uncommon to choose.

Answer 2

Slower is better, as slow as you can tolerate. Timing for different -a values, each measured 20 times:

-a 16 takes on average 0.247 (seconds)
-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

The time is linear, so you can expect a doubling of the -a value to take twice as long. The default (16) takes about a quarter of a second on a reasonable i5 CPU in 2018 (and CPUs aren't doing anything close to doubling in operations per second per buck every 18 months anymore).

---

Measurement method

This is measured by changing the password on a key (because that doesn't wait for /dev/random):

time ssh-keygen -qa 16 -N newpassword -pP oldpassword -f keyfile

To create the overview, I used this code (running the command 20 times for each -a value):

$ for j in 16 32 64 100 150; do
>     echo -n "-a $j takes on average";
>     for i in {1..20}; do
>         ssh-keygen -qa $j -t ed25519 -f test -N test;
>         time ssh-keygen -qa $j -N tost -pP test -f test;
>         rm test{.pub,};
>     done |& grep real | awk -F m '{print $2}' | tr -d s | awk '{sum+=$1} END{print sum/NR}';
> done

The time is less stable than I would expect, probably due to CPU throttling (my laptop throttles ridiculously when it goes over 40°C, which is a bug). Still, these look a lot more stable and sensible than the numbers in ZzAntáres' answer. Here are raw values for 10 runs of each rounds setting:

16  0.243 0.243 0.242 0.242 0.242 0.242 0.244 0.263 0.250 0.257
32  0.482 0.482 0.483 0.486 0.537 0.481 0.481 0.481 0.481 0.991
64  1.064 0.962 0.959 0.996 0.959 0.959 0.959 1.548 0.959 0.976
100 1.798 1.514 2.109 1.609 1.496 1.496 1.498 1.496 1.497 1.496
150 2.659 3.373 3.373 2.726 2.301 2.473 3.373 3.374 2.893 2.242

Answer 3

The new format uses bcrypt_pbkdf() to derive the symmetric key. This behaves slightly differently from normal bcrypt when it comes to the work factor.

Per Ted Unangst, who wrote bcrypt_pbkdf():

The original difficulty parameter for bcrypt is the log2 number of times to rekey the cipher. bhash fixes this number at 64, and instead relies on the PBKDF2 rounds parameter to control difficulty.

source: http://www.tedunangst.com/flak/post/bcrypt-pbkdf

Since the cipher is rekeyed 64 times per iteration, the default of 16 rounds will perform 1024 rekeying operations in total, which is equal to original bcrypt with a work factor of 10.

You can read more about choosing the number of KDF rounds here.