32

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.

Basil Bourque
  • 103
  • 4
Peter Tseng
  • 423
  • 1
  • 4
  • 6
  • 1
    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). – SEJPM Sep 29 '16 at 12:22
  • I'm talking about the -o option in ssh-keygen, e.g. ssh-keygen -o -a 100 -t ed25519 (see https://blog.g3rt.nl/upgrade-your-ssh-keys.html). 100k would take forever, so I guess it's something different than what you're thinking? – Peter Tseng Sep 29 '16 at 21:04
  • -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. – SEJPM Oct 22 '16 at 19:11
  • Oh sorry. Yes I meant the -a option – Peter Tseng Oct 24 '16 at 21:50
  • 1
    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. :) – Tom Hale Dec 12 '16 at 00:34
  • 1
    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 – zeroconf Dec 12 '16 at 00:38
  • @zeroconf Rather than testing scp, why not just try logging in? You should notice that -a 1000000000 takes a long time. – Peter Tseng Dec 13 '16 at 00:33
  • 1
    @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. – dave_thompson_085 Dec 14 '16 at 15:11
  • 2
    -o is redundant with -t ed25519. Notice last sentence of “man” page in macOS High Sierra: *ssh-keygen -o Causes ssh-keygen to save private keys using the new OpenSSH for- mat 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.* – Basil Bourque Nov 28 '18 at 06:31
  • 1
    @BasilBourque+ as of 7.8 released 2018-08-23, new format is now the default for all types and -o is a no-op; you can use -m PEM to get old format except for ed25519. – dave_thompson_085 Dec 28 '18 at 03:10

3 Answers3

19

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
Luc
  • 1,508
  • 3
  • 19
  • 34
  • 1
    from the other answers: -a 100 in 2016: <5s. In 2018: <2s. 2020: <0.5s (measured now). – gcb Aug 24 '20 at 00:11
  • @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!) – Luc Aug 24 '20 at 10:49
  • Another data-point for benchmarks: AMD Ryzen 5 2600 yields -a 100 = ~1.30s. This is a quite powerful desktop CPU (6C, 12T, 3.4GHz), launched in 2018, so whatever @gcb ran in 2020 to get this <0.5s figure is really impressive. I'd assume ~2s for the "average joe"'s laptop in 2021 to be a bit more realistic. – MestreLion Apr 06 '21 at 06:25
  • For locales using , as decimal separator, replace tr -d s with sed 's/,/./;s/s//' (works for US too). And to make it work with gawk, prepend it with LC_ALL=C. The full line becomes: done |& grep real | awk -F m '{print $2}' | sed 's/,/./;s/s//' | LC_ALL=C awk '{sum+=$1} END{print sum/NR}'; – MestreLion Apr 06 '21 at 06:47
  • Interesting data point: a 2010 AMD Phenom II X4 960T gets ~1.4s. You're right @Luc, there was very little improvement on raw CPU performance (per core) in the last decade. This little (ancient) beast can still beat many modern (basic) laptops. – MestreLion Apr 06 '21 at 07:01
  • @MestreLion Interesting data and also thanks for sharing the more compatible command line :) – Luc Apr 06 '21 at 08:27
17

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.

zzantares
  • 302
  • 3
  • 4
  • 1
    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). – Luc Dec 27 '18 at 19:43
  • 1
    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 – zzantares Jan 01 '19 at 01:54
  • 3
    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. – forest Jul 09 '19 at 06:49
14

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.