First, while studying MinEntropy a bit, I came across an NIST paper, "DRAFT SP 800-90B (second draft)," which suggests "twice" the entropy of the underlying block of a cryptographic hash function be used as input in order to have an output hash having fully saturated entropy capacity. This seemed unnecessary to me, for in my hobbyist study I had learned prior that one could assume -- even though obviously one can't, given that surjection hasn't, to my knowledge, been proven -- that a cryptographic hash function that isn't broken ought to preserve each entropy bit of input in the output, up to the bit length of the output.
From similar questions here, which are so many years old I figured I ought to ask a new one instead of reply, I heard it claimed that using a hash function -- let's say SHA256 for the sake of conversation -- to hash an input string having N < 257 bits of entropy, could produce -- specifically because of collisions -- an output having less than N bits of entropy.
I understand that if you have a set of 2^64 elements, and consider this set as constituting 64 bits of entropy because of being essentially a state machine with that many states, that if you were to hash each element of this domain subset into the codomain subset it corresponds to, that you could end up with fewer than 2^64 elements in the codomain subset because of collisions, which are certain because of the pigeonhole principle -- cryptographic hash functions are non-injective.
However, if you have an arbitrary single input, rather than a set of inputs, so, say, a string containing within it 64 bits of entropy, it seems different than having a set of 2^64 elements. Clearly the 2^64 elements may not each map to individual codomain elements, and in this context I see how collisions can reduce entropy, particularly as the input set size increases toward 2^256, in the case of SHA256. But what does that really say about the entropy of an output produced from a single input having 64, or 256, bits of entropy?
I can imagine that I ought think from the perspective of an attacker trying to crack a 256 bit symmetric algorithm's key or password. So, the user had a password with, say, 256 bits of entropy, and hashed it with SHA256 to make it to the appropriate size (or because of whatever reason). My thought was that this would result in 256 bits of entropy in the output hash, but it seems many are arguing that, because of having such an entropy:output_bit_count ratio (1 here, but even when approaching 1), the output hash will have less entropy in it than was input into the function, because of collisions.
Well, certainly trying to guess the user's password -- directly -- will require 2^256 operations to have certainty of success. So will trying to directly guess the hash output, but it would regardless of the input entropy simply because of being an unknown 256 bit string. Trying to indirectly guess the hash output by guessing the password correctly would require 2^256 operations just the same as guessing the password, other than for that other guesses than the valid password could produce the same output hash because of a collision, and the goal is guessing the hash, not the input per se.
So, if I know that there are 2^256 potential passwords (and am not smart enough to just directly attack the key instead), I may not need to go through them to the correct one, but only to one that has a collision with it.
But is this really the collision -- the lack of being injective -- causing the loss of entropy, or is it because from a 2^256 domain subset to a 2^256 codomain, lacking the property of being injective means there is a lack of surjectivity? Because two inputs go to one output, it isn't injective. But because the (subset) domain is the same element count as the codomain, the lack of 1:1 guarantees a lack of surjectivity.
I already know that a cryptographic hash function that isn't surjective can't maintain entropy in up to the bit length out; it can't produce outputs with more entropy than its own state space, so if it can't cover the codomain it can only preserve entropy in up to the log2(state space) it can cover bits, instead of the full output bit length, which is only true assuming it is surjective such that the state space is 2^bit_length_out.
I think it is important to know if it is truly the collision that reduced the entropy, or the lack of being surjective when constrained to a subset of the domain. Because the domain is vastly larger than the codomain, so there are actually very many ways 256 bits of entropy can be expressed in the domain, but only 2^256 ways it can be in the codomain.
If it is indeed because of the lack of being injective, what, if any, implications are there by the fact of the lack of 1:1 in the 2^256 element (subset)domain/(full)codomain relation intrinsically means a lack of being surjective as well? Is the loss of entropy in the output, by the collision, equal to, or even the same as, the entropy loss by the lack of being surjective?