Entropy preservation through cryptographic hash function

Question

Background

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.

Question

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?

Answer 1

I didn't follow all of the question, but let's take a small example. Suppose $X$ is uniformly distributed in $\{1,2,3\}$, so that $\Pr[X = x] = 1/3$ for any $x \in \{1,2,3\}$. If we define

\begin{equation*} f(1) = 2, \qquad f(2) = 3, \qquad f(3) = 2, \end{equation*}

then we have

\begin{align*} \Pr[f(X) = 1] &= 0, \\ \Pr[f(X) = 2] &= \Pr[X = 1] + \Pr[X = 3] = 2/3, \\ \Pr[f(X) = 3] &= \Pr[X = 2] = 1/3. \end{align*}

The min-entropy of $X$ is $-\log \max_{x\in\{1,2,3\}} \Pr[X = x] = \log 3$, whereas the min-entropy of $f(X)$ is $-\log \max_{y\in\{1,2,3\}} \Pr[f(X) = y] = \log 1.5$.

In general, the entropy of $f(X)$ is related to the entropy of $X$ by $H[f(X)] \leq H[X]$, and equality holds if and only if $f$ is injective. When the domain and codomain of $f$ are the same, then it just so happens that $f$ is injective if and only if $f$ is surjective.

So what about SHA-256? Well, any distribution supported on fewer than $2^{256}$ distinct values cannot have 256 bits of entropy. If we model SHA-256 as a uniform random function $F$, then on any set of inputs, there's a nonzero probability that $F$ is not a surjection onto the 256-bit strings; on $2^{256 + k}$ distinct inputs, the expected fraction of distinct outputs is about $1 - e^{-2^k}$, which rapidly approaches $1$.

This doesn't exactly answer what the entropy of $\operatorname{SHA-256}(X)$ is, but it gives a rough proxy for the entropy attainable by $\operatorname{SHA-256}(X)$ in terms of the entropy of $X$, and it's why NIST suggests choosing double-size inputs for ‘full entropy’.

---

Note: This is only about injectivity and collisions. ‘Surjectivity’ is a red herring. You can take any surjection $f\colon A \to B$ and make it fail to be a surjection by artificially expanding its codomain and calling it $f'\colon A \to (B \cup C)$, but the entropy of $f(X)$ and $f'(X)$ would be exactly the same even though $f$ is technically a surjection and $f'$ is not. Similarly, you could take SHA-256, and append a string of 256 zero bits: $F(x) := \operatorname{SHA-256}(x) \mathbin\| 0^{256}$; then $F(X)$ has exactly the same entropy as $\operatorname{SHA-256}(X)$, even though $F(X)$ is a 512-bit string and $\operatorname{SHA-256}(X)$ is a 256-bit string.

Answer 2

It's simply due to a hash function acting (within it's block size $n$) as:-

You'll notice that there is no possible 'A' output as there was a collision at 'C'. It's a version of the pigeon hole principle meaning that when two birds occupy one hole, you must have an empty hole remaining. Some of the output bins of a pseudo random function (hash extractor) remain empty due to such pseudo random collisions. A proper hash function exhibits the avalanche effect with 50% of the output bits likely to change. Taken across the entire output domain, that means $1/e$ of them will always remain empty for $n$ sized inputs. Which is just common statistics or $P = (1-1/n)^n$ simplified.

$1/e$ ~ 37%. Since cryptography is about security, we conservatively round that to 50%. Hence you only get half out of what you put in. But that clearly still gives you missing values, and therefore a $\epsilon$ deviation from uniform randomness. NIST requires $\epsilon \leq 2^{-64}$ for 'full entropy'. They also suggest a minimum block width of 128 bits for 'approved' entropy conditioners. If you take the Left Over Hash lemma, the probability that the extractor output will deviate from a perfectly uniform k-bit string by $\epsilon = 2^{-(h_{\infty}-k)/2}$. Run the numbers, and you get $2^{-64} = 2^{-(256-128)/2}$. Or, always put in $2 \times$ as much, as per SP 800-90B.