To what degree does a high PKBDF-HMAC-SHA1 iteration count compensate for a weak passphrase entropy?

Question

Lost a LUKS-encrypted laptop at the end of 2019 and now trying to figure out the odds of a very sophisticated attacker being able to break in.

The LUKS container was created mid-2017 with LUKS1 default settings.

The CPU I used back then was a Intel Core i7-6700K which I still have.

I ran some benchmarks with cryptsetup benchmark which produced the following value for PBKDF2-sha1.

PBKDF2-sha1      1659139 iterations per second for 256-bit key

I cannot remember the exact password I used (I have too many) except for the fact that it is at least 14 characters long and contains [a-z0-9] and it is not included in any dictionary (checked rockyou2021.txt).

I found a benchmark table on GitHub using the Nvidia GeForce RTX 3090.

Hashmode: 12000 - PBKDF2-HMAC-SHA1 (Iterations: 999)
Speed.#1.........:  9240.9 kH/s (47.48ms) @ Accel:16 Loops:499 Thr:1024 Vec:1

Hashmode: 12001 - Atlassian (PBKDF2-HMAC-SHA1) (Iterations: 9999)
Speed.#1.........:   923.3 kH/s (72.49ms) @ Accel:8 Loops:1024 Thr:1024 Vec:1

Hashmode: 22600 - Telegram Desktop App Passcode (PBKDF2-HMAC-SHA1) (Iterations: 3999)
Speed.#1.........:   328.7 kH/s (63.58ms) @ Accel:8 Loops:128 Thr:1024 Vec:1

Based on these numbers I concluded that the GPU can compute 9249 kH/s for 1000 iterations. If the iteration count is increased times 1659 to 1659139 that would mean the GPU speed would go down to: $\frac{9249 kH/s}{1659}$ = 5575 H/s. That means an attacker can effectively only check 5575 passwords per second with that one GPU.

The possible passwords based on the character set ([a-z0-9], length=14) is: $36^{14}$. For the sake of simplicity let's cut that in half which leaves us with an average case of: $\frac{36^{14}}{2}=3*10^{21}$.

That means it would take an attacker on average $\frac{3*10^{21}}{5575}=5*10^{17}$ seconds to find the right password which equates to $3*10^{9}$ years. That means even if the attacker had 1 million of those GPUs, it would still take 300 years to crack the password.

My questions are:

1. To what degree does the relatively high iteration count compensate for the relatively weak entropy of my password considering a brute-force or dictionary attack on a modern GPU?
2. Did I miss any important detail in my analysis?

Answer 1

Your password space is not considered small $36^{14}$ is for very strong passwords, this is 72 bits of entropy.

Small password spaces are those which are done with dictionary attacks, including dictionaries with transformations. Even the XKCD method promises only 44 bits of entropy.

You are unlikely to memorize a random 14 char password, so if you are using a password manager and are using strong random passwords, than indeed even a fairly weak KDF would suffice.

However for e.g 44 bits entropy that would lead to only several hundred hours on the GPU you mentioned, which most consider insufficient.

You can increase iteration count, but remember the attacker has an advantage, will do batches, will do bitslicing, and GPU and FPGA. I think a rule of thumb assuming the attacker has x1000 or even x10K advantage is reasonable. If you use a memory hard KDF you may be able to lessen this and assume a smaller advantage (say 100x). When increasing iteration count you are slowing yourself down as well, and need to make sure user experience and your own compute costs remain reasonable.