Exhausting the entropy of a hash function

Question

In the case of password storage, consider the following:

I have an idea that one can exhaust the entropy of input to the MD5 function by using a 128 bit random value as the password (indeed, any hash function, using the output length as input). Is this a correct assumption, or is the entropy exhausted at 123.4 bit, this being the best attack to date? Or does this only apply to hash functions that for every value in the interval $[0, 2^{L}]$ provide another unique value in the same interval?

I hope you understand what I'm trying to ask here - I see that I have a hard time explaining it clearly. What I want to do with this idea is argue that in the case of MD5 stored passwords, there is no reason to use passwords with a higher entropy than the hash itself.

Answer 1

Entropy is not gas -- you do not "consume" it.

In the case of hashing passwords, entropy is a measure of what the password could have been. A password with "$n$ bits of entropy" is a password such that breaking it by dictionary attack (trying potential passwords until the right one is found) has average cost $2^{n-1}$.

It is useless to have a password entropy much beyond the output length of the employed hash function, because if you hash to $k$ bits, then trying random passwords will succeed with probability $2^{-k}$, hence average cost $2^{k}$. Thus, no need to go beyond $k+1$ bits or entropy for the password.

It is also useless to have a password entropy beyond the point where dictionary attacks are ludicrously expensive, regardless of the hash function output size. With today's technology, an 80-bit password entropy is already enough to defeat such endeavours. Actually, if the password hashing is done properly (with a slow password processing function, like bcrypt), then lower entropies are already fine (that's the point of slow hashing: to make low password entropy more tolerable).