Long passwords and key derivation functions

Question

Not being a security expert, I have a rather theoratical question that I have been thinking about for quite a while now:

Let's imagine an encryption software that takes a user-provided password, passes it through a key derivation function and then uses its output as a key for AES-256 in order to encrypt a file. Assuming a key space of 100 characters and further assuming that an attacker knows the setup and is aware of the length of the password, is it correct to say that adding more characters to a 39-character password does not increase the user's security because 2^256 < 100^39 and, thus, the attacker would rather try to brute-force the actual derived key instead of the user-entered password?

(I'm aware that brute-forcing a random password of that length is completely unfeasible now and in the foreseeable future.)

Answer 1

If the attacker knows for sure that the (character space size) ^ (password length) is greater than 2 ^ (AES key length), then, yes, it's a better idea for the attacker to brute-force the AES key. Given such an assumption of the attacker's knowledge, it's a mathematical fact that the search size for the AES key will be smaller.

Such an assumption of attacker knowledge could possibly be satisfied, for example, by a physically-nearby attacker who listens to you type out your lengthy passphrase on a keyboard for a very long time (i.e., more than 39 keystrokes).

However, if the password is not selected truly at random from the space of all possible passwords (for example, it's known that the password is made entirely or partially of English words) then the true search space of the password (given such a weakening assumption) may be much smaller than the theoretical maximum of (character space size) ^ (password length), and thus may be smaller than the search space of all AES keys.