2

I discovered the newer OpenSSH format for storing SSH private keys (ssh-keygen -o) uses bcrypt to generate the symmetric key to encrypt the private key. I understand that the -a option is used to adjust the bcrypt work factor. However, I don't understand the exact relationship between the work factor and the given value. -a 200 takes about 5 seconds on my CPU, while this benchmark maxes out with a work factor of 20 taking over a minute. The work factor is a logarithmic scale, and I doubt my laptop is really >2^10 times faster than this person's laptop.

Clearly -a does not directly translate to the bcrypt work factor. So what is the relationship?

The reason I want to know is to extrapolate a "worst-case" cracking rate for my chosen -a value based on this benchmark of a top-end (for 2017) cracking rig (which guesses ~100k hashes/sec across 8 GPUs, using a bcrypt work factor of 5 for the tests).

  • 1
    First, I notice typical ssh-keygen use single core. seconds, please edit your question and provide the exact command line and crypto bits. When trying ssh-keygen -a 200 , my i7 3600 2.2Ghz CPU show "Sieve next 67043328 plus 2047-bit", "Sieved with 203277289 small primes in 184 seconds" – mootmoot Jun 19 '17 at 8:13
  • there is no single exact command line; this is talking about a whole range of uses of ssh-keygen. The relevant options are -o to specify using the OpenSSH format instead of the older PEM format, and -a <number> to specify work factor. Here is an example to generate a test key though: ssh-keygen -o -a 200 -f ./testkey -N password123 – user371366 Jun 19 '17 at 8:59
3

This differs between ssh-keygen versions. From this post:

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.

My original answer was based on the man page for ssh-keygen which states the following:

-a rounds 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).

Therefore a value of 200 will iterate the KDF 200 times. This is an equivalent of a work factor of 7.64, not 200 as you are expecting.

If you wanted your workfactor of 200 you would have to specify -a 1606938044258990275541962092341162602522202993782792835301376.

This won't work for two reasons:

  • Invalid number (too large) is returned.
  • You don't have a few universes of time to spare.

If you wanted to try 20 like in the example, go with this number, 1048576.

Basically you need the following two formulae:

Work factor = log2(rounds)

Rounds = 2work factor

Update

Therefore, if using the bhash version, divide the number from my working above by 64.

$ time ssh-keygen -o -a 16384 -f ./testkey -N password123
Generating public/private rsa key pair.
Your identification has been saved in ./testkey.
Your public key has been saved in ./testkey.pub.
The key fingerprint is:
SHA256:eU/T6ex/wDJNsb8soOzGN/uxup0Zdjthvxt1e23wb6c foo@bar
The key's randomart image is:
+---[RSA 2048]----+
|                 |
|              .  |
|               o |
|         .   .o. |
|        S . o++.o|
|         . +o++=*|
|        o . o*==O|
|         = oooB=X|
|        o..+**EBO|
+----[SHA256]-----+

real    2m17.181s
user    2m16.677s
sys 0m0.005s
  • Thank you! I was starting to suspect this as I experimented, somehow I didn't think to actually take the man page at its word. – user371366 Jun 19 '17 at 19:48
  • In a situation like this where this is well said and clearly the right answer, should I accept right away, or should I still give other people a chance first? – user371366 Jun 19 '17 at 19:49
  • Your call on how to run it. Completely up to you. ;-) – SilverlightFox Jun 19 '17 at 19:50
  • whoops, turns out this is not exactly correct after all, as per this answer: crypto.stackexchange.com/a/40910/49054 – user371366 Jun 21 '17 at 2:10
  • Yes I wondered if the format specified changed the behaviour. It is still correct, just that the internal function does multiple iterations per the count specified. I can update my answer later. – SilverlightFox Jun 21 '17 at 7:22

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.