What does ssh-keygen's -a option really mean?

Question

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

Answer 1

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 = 2^{work 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