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

• 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 at 15:27
• Was writing another comment, changed it into an answer, hopefully it answers your question. – Maarten Bodewes Nov 14 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.

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.

• Thanks sir! Very clear. I have another not-so-relevant question: got any examples of such hashes that use exponential work factors? Are you talking about memory hard KDF hashing functions? E.g. do you mean that this idea of quantifying KDF's contribution to increase in security (against bruteforcing) by using entropy bits is not new in the context of KDFs? I am just curious about this, because I couldn't find any entropy-interpretation of security offered by the likes of Scrypt and Argon2 yet. If you know any please let me know. Thanks again sir! – caveman Nov 16 at 13:41
• bcrypt uses a work factor that's exponential and doubles for each level, see e.g. here. Yes, that's a password hash, but not memory hard. scrypt uses PBKDF2 again, so that memory hard password hash doesn't use an exponential work factor. It calls it "CPU cost" instead. Yeah, it's a mess. PS I'm slightly allergic to be called "sir" (here in NL we often call CEO's by their first name) :) – Maarten Bodewes Nov 16 at 16:05
• Not sure I am following with bcrypt. I will read more about it. So far it seems to me to not really quantify its security gain in terms of bits, because itis different than the encryption algorithm. Here is an example of an algorithm that I am trying to define (and implement) that, when says "20 bits worth difficulty" it is actually guaranteed to give 20 bits-worth of difficulty because it uses the same encryption algorithm github.com/Al-Caveman/ciphart/releases/tag/2.0.0 (ignore master branch; currently adding memory-hardness to it; unusable: too lazy to use dev branch). – caveman Nov 16 at 23:04
• One more question sir, just to verify if my understanding is correct. It seems to me that your answer above is identical to my attempt earlier, except that my attempt works from the exponent into the iterations, while your attempt works the other way around from the iterations into the exponent. Am I right? Or am I missing something? (Didn't know that bit about the NL culture. I agree with it. I personally find sir to be funny and use it for banter. I also find that glorifying powerful entities, such as CEOs/presidents/etc, to be wrong.) – caveman Nov 18 at 13:47
• Yeah, I think they are both more or less identical. I just worked from the other way around to show that if there is a maximum, then that maximum is probably rather useless, unless a generated / really strong password is used in the first place, of course. – Maarten Bodewes Nov 18 at 17:53