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

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.

• Any idea how much entropy is generally in passwords? And, yes, $2^{58}$ is too large (my C implementation using libsodium on my machine says that it will be accomplished after 300+ centuries). Maybe 2^20 is more realistic. This whole thing is just meant to be an example to see if we can interpret KDF complexity in terms of information theory to actually have a clue about what is going on (as opposed to simply waiting without any guidance, in a mere test of blind patience). – caveman Nov 14 '20 at 15:27
• Was writing another comment, changed it into an answer, hopefully it answers your question. – Maarten Bodewes Nov 14 '20 at 20:27

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.