11
$\begingroup$

What is the best practice on choosing how many key derivation function (KDF) rounds/iterations when generating an SSH key pair? 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.

$\endgroup$
  • 1
    $\begingroup$ Just to be sure, we're talking about the iteration count of password based key derivation functions (aka iterated hash functions) here? If so, 16 rounds is usually considered waaaaaaay too low. 100k and upwards is normal these days for sensitive data (and still takes less than a second on most systems). $\endgroup$ – SEJPM Sep 29 '16 at 12:22
  • $\begingroup$ I'm talking about the -o option in ssh-keygen, e.g. ssh-keygen -o -a 100 -t ed25519 (see blog.g3rt.nl/upgrade-your-ssh-keys.html). 100k would take forever, so I guess it's something different than what you're thinking? $\endgroup$ – Peter Tseng Sep 29 '16 at 21:04
  • $\begingroup$ -o just specifies that the "new OpenSSH" format should be used for the private keys. -a specifies the number of rounds for bcrypt. What that means concretely probably needs to be looked up in the OpenSSH source. $\endgroup$ – SEJPM Oct 22 '16 at 19:11
  • 1
    $\begingroup$ Instead of making things trickier with KDF, you can have the attacker's workload increase choosing a much harder key to crack. See this answer for more. Choose your inconvenience: waiting or typing a long passphrase. :) $\endgroup$ – Tom Hale Dec 12 '16 at 0:34
  • 1
    $\begingroup$ @zeroconf+Peter: but not if you have the key in ssh-agent or similar (as some Linux distros or GUIs do for convenience) and of course not if you didn't set a passphrase in the first place. $\endgroup$ – dave_thompson_085 Dec 14 '16 at 15:11
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your testing method is wrong. The minimum values might approach truth, but the maximums are far off. Your laptop was occasionally busy doing other things or there were other factors at play. The results should be deterministic and follow a predictable curve, which they clearly don't (you're saying -a 64 is slower than -a 100 in a third of the cases, assuming a uniform distribution). $\endgroup$ – Luc Dec 27 '18 at 19:43
  • $\begingroup$ Hello @Luc, yes that may be the case, all I really did was to write down my observations not caring about the testing method, thanks for the heads up to the readers. Happy new year =D $\endgroup$ – ZzAntáres Jan 1 at 1:54
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

-a 16 takes on average 0.24675 (seconds)
-a 32 takes on average 0.5862
-a 64 takes on average 1.20625
-a 100 takes on average 1.9618
-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 takes about a quarter of a second on a reasonable i5 CPU in 2018 (and CPUs aren't getting much faster anymore).


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:

$ 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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.