The benefit of PBKDF2 for big keyfile?

Question

The man page of cryptsetup says:

Whenever a passphrase is added to a LUKS header (luksAddKey, luksFormat), the user may specify how much the time the passphrase processing should consume. The time is used to determine the iteration count for PBKDF2 and higher times will offer better protection for low-entropy passphrases, but open will take longer to complete. For passphrases that have entropy higher than the used key length, higher iteration times will not increase security.

Does it mean that a binary keyfile of more than 64 random bytes (each having 8 bits of entropy?) is useless with PBKDF2 and a hash of 512 bits like SHA-512? The cost of testing all the hashes directly being cheaper than testing all the keyfiles.

Does it also mean that reducing the iteration time to 1 millisecond (or just to 1 iteration if it's even possible?) for such a keyfile doesn't affect the security?

And finally does it mean that using PBKDF2 with such a big keyfile, by reducing its size to just 512 bits, actually lower the security of a LUKS header?

Answer 1

Does it mean that a binary keyfile of more than 64 random bytes (each having 8 bits of entropy?) is useless with PBKDF2 and a hash of 512 bits like SHA-512? The cost of testing all the hashes directly being cheaper than testing all the keyfiles.

Yes, it does. After 128 to about 256 bits security the amount of security provided by the bits alone doesn't make sense anymore (impossible is impossible).

Does it also mean that reducing the iteration time to 1 millisecond (or just to 1 iteration if it's even possible?) for such a keyfile doesn't affect the security?

Yes, if the input does indeed have that much entropy (and is therefore not really a usable password or passphrase), then you might as well perform one operation per ms. Or much faster.

And finally does it mean that using PBKDF2 with such a big keyfile, by reducing its size to just 512 bits, actually lower the security of a LUKS header?

No, that's unlikely. The amount of information lost by performing many, many operations is still minimal, so you will probably maintain the security of the underlying HMAC.

Note that security proofs like salts. Removing the salt entirely may make the calculation - at least theoretically - less secure. So it is probably best to replace the password hash with e.g. HKDF, a key based key derivation function that optionally takes a salt.

Answer 2

The assertion made

For passphrases that have entropy higher than the used key length, higher iteration times will not increase security.

is valid in any context where a potential attacker has the opportunity to directly enumerate the key output from the entropy-stretching function (here PBKDF2), rather than enumerate passphrases. Such context includes LUKS, where the natural assumption is that the adversary can access the enciphered data and run an attack from that.

We can make things quantitative: if it costs the adversary $a$ to test a $k$ bit key, and $n\cdot b$ to run PBKDF2 for $n\ge1000$ steps and test the result, then for a passphrases with $e$ bits of entropy, the expected cost of attack for an adversary choosing the best method is the lowest of $a\cdot2^{k-1}$ (key enumeration) and $(n\cdot b)\cdot2^{e-1}$ (passphrase search). The assertion in the question is that when $e>k$, increasing $n$ won't change that minimum, which follows from $n\cdot b\gg a$. In fact, raising $n$ above approximately $2^{k-e}\cdot a/b$ is pointless. Or, in more practical terms: the passphrase is the weak spot when $e<k-\log_2(n\cdot b/a)$.

Assuming $k=128$, a properly parameterized PBKDF2 adding say 0.5 second of delay, and nanoseconds to test a key, $\log_2(n\cdot b/a)$ might be $24\pm8$. Thus any passphrase with less than about $104\pm8$ bits of entropy is likely to be the weak spot. Which is, any passphrase that most humans are willing to type. And the quoted sentence (putting that bound to $128$ bits) is true, and extremely conservative, but devoid of practical consequence even if we remove some margin: in LUKS, the right upper limit of $n$ is what gives a tolerable wait, except for unusually good passphrases.