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
.
libsodium
on my machine says that it will be accomplished after 300+ centuries). Maybe2^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). $\endgroup$