16
$\begingroup$

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.

$\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
  • 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$ Tested Ed25519 with: - -a 100 - -a 1000 - -a 100000 - -a 1000000 - -a 1000000000 ... but did not notice the remarkable difference. Is it normal behaviour? Created separate user for tests which had non-encrypted home folder. Did clear tests: removed previous keys in client (e.g. to avoid RSA fallback) and authorized_keys file in server before next test. Created also 1 MiB, 10 MiB files and tried to copy with scp. Tested login with: for x in {1..5};do /usr/bin/time ssh user@IP exit;done and scp with for x in {1..5};do /usr/bin/time scp test1MiB.img user@IP:/home/user/; done (repeated with te $\endgroup$ – zeroconf Dec 12 '16 at 0:38
  • 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
9
$\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.

| improve this answer | |
$\endgroup$
  • 1
    $\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
  • 1
    $\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 '19 at 1:54
  • 1
    $\begingroup$ Rather than seeing how long they take, you should be using the time utility or builtin. That will account for most scheduling quirks, assuming the system isn't too heavily loaded. $\endgroup$ – forest Jul 9 '19 at 6:49
10
$\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.

| improve this answer | |
$\endgroup$
9
$\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.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
| improve this answer | |
$\endgroup$
  • $\begingroup$ from the other answers: -a 100 in 2016: <5s. In 2018: <2s. 2020: <0.5s (measured now). $\endgroup$ – gcb Aug 24 at 0:11
  • $\begingroup$ @gcb for me it barely changed on a new laptop (1.7s for me now), cpus aren't really getting faster anymore (just more parallelized). If you get 0.5s then you're probably using a desktop rather than these crappy mobile CPUs they put in business laptops. Also, that "3.5-6s" from 2016 was a ridiculous testing method that made no sense at all; you're better off looking at cpu benchmarks and estimating. For example, my 2012 CPU had more benchmark points than the Q4 2016 CPU in my current laptop; it's really not doubling per year anymore... they're just using less power (by being slower, much wow!) $\endgroup$ – Luc Aug 24 at 10:49

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.