Exhausting the entropy of a hash function

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.

-

3
MD5 restricted to 128-bit inputs is likely not injective (and thus also not surjective), independently of any attacks on the hash function. A hash function models a random function, not a random permutation. But you are right, there is no point in having passwords with higher entropy than the hash output size. – Paŭlo Ebermann♦ Nov 30 '12 at 8:34

1 Answer

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

-
Would you agree that the max. reasonable entropy of a password is equal to that of the best preimage attack? This would be the threshold where dictionary and preimage resistance meet. – Henning Klevjer Nov 30 '12 at 15:32

1
There are details. There are also online dictionary attacks, which are performed against the live target server, without knowing the hash value. Specific preimage resistance of the hash function is irrelevant for that. But if the attacker knows the hash value, then yes, there is no need, even academic, to push the password entropy beyond the preimage resistance of the hash function. – Thomas Pornin Nov 30 '12 at 16:28
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9240207076072693, "perplexity_flag": "middle"}