How to estimate the maximum computational cost bound for Key Derivation Functions (KDFs) before it becomes useless security-wise?

Question

From my understanding of Key Derivation Functions (KDFs), e.g. scrypt, Argon2, etc, we can tune their parameters such that it eventually becomes harder for an attacker to brute force a password-to-key through them. At this point, the attacker may directly brute force the, say AES128, key.

It is nice to not over-tune the parameters of KDFs, so that the user is not needlessly suffering using a slow application. I think it is ideal if the KDF is tuned only so that the user suffers least while still maximum possible security out of, say, AES128-CBC (or whatever other symmetric cipher).

An easy way is to explore all improvements in hardware and algorithm design, in order to get an estimation how long would it take certain well-funded organisations have to wait until they finally manage to decrypt my cipers. But I think this approach is needless complex as I think we can probably say a lot about the computational bounds of KDFs by simply studying the problem from an information theoretic perspective.

Below is an attempt. My question is: can we make it tighter?

---

What I have done so far:

Let's say that $f$ is a 128 bit encryption/decryption function, and the KDF function is $k$. also let's say that a single round of $k$ equals the encryption/decryption of a single block by $f$. Let's say that our password has only $70$ bits of entropy.

So the total attempts to bruteforce all keys is $2^{128}$, while the total attempts to bruteforce the password is $2^{70}$. Since $f$ and $k$ computationally cost equally $c$, then the actual cost of bruteforcing the keys is $c \times 2^{128}$, while the password is $c \times 2^{70}$. In this case, the adversary will obviously go after bruteforcing the password.

To make the attacker not find the password easier to break, we can repeat the KDF $k$ for $r$ many times until the difficulty matches. Basically: $$\begin{split} c2^{128} &= rc2^{70} \\ 2^{128} &= r2^{70} \\ \frac{2^{128}}{2^{70}} &= r \\ 2^{128-70} &= r \\ 2^{58} &= r \\ \end{split}$$

If the KDF $k$ is itself is implemented by recursively calling $k$, then this $c$ is guaranteed, and simply repeating it long enough, recursively, will guarantee that the difficulty of bruteforcing the password via the KDF $k$ is as hard as bruteforcing keys with $128$ bits of entropy.

Meaning, if $r > 2^{58}$, then for the attacker would find it easier to bruteforce the key directly. In this case, the attacker would totally ignore the KDF $k$ and move on to bruteforce $f$'s key. In other words, $r>2^{58}$ is pointless.

Update: the above is also implemented as part of ciphart.

Answer 1

Generally we look at strength by looking at the order $O$ that it adds to the password search when an attacker is trying to guess passwords. That's just the same as the number of iterations basically, assuming a salt and correct password hash. Often it is simpler to just use bits, which is basically the $\log_2$ of the order.

So if a password strength is an average of about 40 bits, then you'd take the $log_2$ of the number of iterations and simply add the values together to get the resulting strength. So given 1048576 iterations, we'd get around $40 + \log_2(1,048,576) = 40 + 20 = 60$ bits of strength. Given the average weakness of passwords, there is no higher limit that is not entirely impractical. Obviously performing $2^{88}$ operations to allow for even average passwords to have 128 bits security is out of the question. So generally you should aim for the highest value possible for a specific service.

For the same reason it is very important to take other measures than just using a password hash with large iteration count. Possible measures are a max number of retries, an added delay before testing each password, requiring a good password with (likely) high entropy or using a password manager of some kind. Browsers nowadays offer internal password managers including generation for a good reason.

Note that some of password hashes such as bcrypt use a two-exponential "work factor" instead of an iteration count to give a better idea of the strength added to the password entropy in bits.