4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ There seems to be a bit of repetition in your question. In the end I was getting worried that you would yourself enter a cycle ;) $\endgroup$ – Maarten - reinstate Monica Nov 13 at 14:47
  • $\begingroup$ I agree with the above comment and I think you should clean up your question and make it more precise exactly what you are asking. $\endgroup$ – kodlu Nov 13 at 19:27
  • $\begingroup$ I removed a paragraph that was arguably needless because of being repetitive. I can see how it still has some repetition in it, but I believe a little to be helpful for keeping things in working memory. And you made me smile Maarten, thanks for that. $\endgroup$ – Gratis Nov 13 at 21:52
  • $\begingroup$ This answer studies the special case of a $h$-bit hash, modeled as a random function, fed with uniformly random $h$-bit string. It shows that the expected entropy on output is next to $h−0.827245\ldots$ bits for $h\ge2$. That entropy reduction is due to collisions in the hash. Is the question extending that to a $w\ne h$-bit input string with $b\ll w$ entropy? Or did things boil down to this shorter question? $\endgroup$ – fgrieu Nov 15 at 8:10
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the case of your SHA256 example, the reason why they have the same entropy, however, is exactly because F(x) is not surjective over the 512 bit codomain, and only can cover up to 2^256 elements of it, while a surjective SHA256(x) covers 2^256 too. The distinction that I feel you may be missing (I'm asking questions because I don't know, though) is that expanding the codomain for f' doesn't just make f-256 into f'-256, but also increases 256 to be log2(artificially expanded co-domain). So, the entropy is exactly the same, but it is because f' isn't surjective over the new space. $\endgroup$ – Gratis Nov 14 at 0:53
  • $\begingroup$ @Gratis The point is that ‘surjectivity’ is a matter of perspective about what codomain you think of the function in, and unlike injectivity has nothing to do with entropy. It is, perhaps, relevant to efficiency, but that doesn't seem to be what you were asking about. Can you expand on why you are concerned with surjectivity? $\endgroup$ – Squeamish Ossifrage Nov 14 at 1:02
  • $\begingroup$ It is certain that surjectivity has to do with entropy. If SHA256 is surjective over the 256 bit string codomain, it would not, by this, be prevented from preserving 256 bits of input entropy in the output hash; however, if it always produces one of 2^120 outputs, which means it isn't surjective over the 256 bit string codomain, then it cannot preserve 256 bits of entropy from input to output. Rather, only up to 120 bits of entropy could be preserved. $\endgroup$ – Gratis Nov 14 at 1:12
  • $\begingroup$ Let's take another example: The function $\phi\colon n \mapsto \operatorname{Salsa20}_k(n) - (0,n,0)$ from 128-bit strings to 512-bit strings is injective, but not a surjection onto all 512-bit strings. Since it is injective, it preserves entropy: if $N$ has 256 128 of entropy, then $\phi(N)$ has 128 bits of entropy. It is a surjection onto its image (i.e., the space of all $2^{128}$ strings of the form $\phi(n)$ for some $n$), but not a surjection onto the space of all 512-bit strings. It's a surjection onto one space but not another, but it preserves entropy because it's injective. $\endgroup$ – Squeamish Ossifrage Nov 14 at 1:19
  • $\begingroup$ Now, if you're asking whether the size of the image sets a bound on the entropy, then obviously the answer is yes! If the image has size $\ell$, then obviously the entropy of the output cannot exceed $\log \ell$ no matter what the entropy of the input is. But I lost track of what you're trying to get at with surjectivity. $\endgroup$ – Squeamish Ossifrage Nov 14 at 1:22
1
$\begingroup$

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

non-surjective

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.

$\endgroup$
  • $\begingroup$ That is, to the extent I could follow it, what I had assumed. It isn't really because of the collision per se, but rather is because the collision -- assuming the domain and codomain have equivalent element counts -- intrinsically means a lack of surjectivity. However, what happens when we realize that the massively larger domain element count means that there could still be surjectivity when not (artificially) constraining ourselves to a domain with an equivalent element count to the codomain? $\endgroup$ – Gratis Nov 13 at 21:47
  • $\begingroup$ @Gratis It doesn't matter. The I/O relationship is irrelevant as there is a fixed output size (what ever that might be). Given the avalanche effect, $1/e$ bin collisions are unavoidable. Entropy will always be 'collided' out of existence and $\epsilon$ will always lurk therein. If you maintain the same $h_{\infty}$ input rate, all that changes is either the level of $\epsilon$ you're willing to tolerate, or $k$ in the Left Over Hash lemma formula. So I suggest that it is down to collisions per se, otherwise it's not a cryptographic hash. $\endgroup$ – Paul Uszak Nov 13 at 22:47
  • $\begingroup$ SHA256 domain is $2^{2^{64}-1}$; codomain is $2^{256}$. $2^{2^{64}-1} \mod{2^{256}} = 0$ I think. So, if the collisions are uniformly distributed such that each of the $2^{256}$ codomain elements has the same number of domain elements mapping to it -- a lack of injectivity nevertheless -- it seems to me that it can still preserve entropy up to 256 output bits. Input any domain element, provided it has 256 bits of entropy, a selection is made equiprobably from a space of 2^256 outputs, the log2 of which obviously being 256. Conversely, if all "lines" to one codomain item are removed, it can't. $\endgroup$ – Gratis Nov 14 at 3:13
  • 1
    $\begingroup$ Put another way, there is more than one way to throw a die such that it lands with "6" facing up. However, rolling a balanced die still produces log2(6) bits of entropy, so long as it isn't with two faces having "5" and none having "6." I don't see why two unique throws being able to produce "6" -- a collision -- reduces the entropy of the throw. Clearly the entropy output is less than the input because of the codomain (ways of landing) having fewer states than the domain (ways of being thrown), but you are always limited to producing no more entropy than the output bit length. Add more faces. $\endgroup$ – Gratis Nov 14 at 3:19
  • $\begingroup$ @Gratis Because dice are physical entropy sources that create Kolmogorov random entropy that grows in line with $O(throws)$ and $O(log(faces))$. A mathematical function can't do that. It can only destroy/decimate Kolmogorov entropy, as through internal collisions. $\endgroup$ – Paul Uszak Nov 14 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.