# Fibers of hash functions

Let $$\{0,1\}^{<\omega}$$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $$n\in\omega$$. Define $$\text{Fib}(h) = \{h^{-1}(\{y\}) : y \in \{0,1\}^n\}$$ to be the set of fibers of $$h$$. (That is, every element of $$\text{Fib}(h)$$ is the set of inputs being mapped to some fixed $$y\in\{0,1\}^n$$.)

It is clear that some elements of $$\text{Fib}(h)$$ will be infinite. For a hash function to be "fair" in some sense, we would like all fibers to be infinite. Now, given a hash function $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$, there is no procedure to determine whether all fibers are infinite.

Question. If we take $$h$$ to be one of the well-known hash functions (such as MD5, SHA-256, xxHash64,...), is it known whether all their fibers are infinite? Or, more basically, if these functions are surjective, that is, $$\varnothing \notin\text{Fib}(h)$$?

# Cryptographic hashes

I don't think anything is known unconditionally.

We can analyze this question using a random oracle assumption. MD5, SHA1, SHA256, etc., have a Merkle-Damgaard structure: they split the input $$x$$ up into blocks $$x_1,\dots,x_n$$, then compute $$h_i = F(x_i,h_{i-1})$$ where $$h_0$$ is a constant and $$h_n$$ is used as the output of the hash function. Now let's analyze this structure under the assumption that $$F$$ can be modelled as a random function (which is believed to be a good heuristic).

Suppose we want to construct a message $$x_1,\dots,x_n$$ that hashes to output $$y$$. Pick $$x_1,\dots,x_{n-2}$$ arbitrarily; this determines $$h_{n-2}$$. Now let's consider all possibilities for $$x_{n-1},x_n$$, and the derived values of $$h_{n-1},h_n$$. If we focus on MD5, each $$x_i$$ is 512 bits and each $$h_i$$ is 128 bits. Since $$F$$ is a random function, the chances that any particular value of $$h_{n-1}$$ is never reached by any choice of $$x_{n-1}$$ is $$(1 - 1/2^{128})^{2^{512}} \approx 1-1/2^{384}$$; therefore it is overwhelmingly likely that all $$2^{128}$$ possible values of $$h_{n-1}$$ are attainable. Now consider all $$2^{640}$$ possible combinations of $$(h_{n-1},x_n)$$, and consider the resulting value of $$h_n = F(x_n,h_{n-1})$$. Since $$F$$ is a random function, the chance that none of these combinations yields $$h_n=y$$ is $$(1-1/2^{128})^{2^{640}} \approx 1/2^{512}$$, i.e., vanishingly unlikely. In conclusion: if you pick $$x_1,\dots,x_{n-2}$$ arbitrarily, it is overwhelmingly likely that there will exist a way to pick $$x_{n-1},x_n$$ so that the resulting hash function outputs the value $$y$$.

It follows that, for MD5, there are infinitely many $$x$$'s that yield the hash $$y$$, assuming that treating $$F$$ as a random function is a good model. In other words, for MD5, we expect all fibers to be infinite.

You can do the same for other Merkle-Damgaard hashes, like SHA1 or SHA256, and you'll reach the same conclusion: for SHA1 and SHA256, we expect all fibers to be infinite. If they're not, then there is likely some deeper structural problem with the hash ($$F$$ doesn't behave like a random function).

Of course none of this is a proof. The random oracle model has well-known limitations. But it is a heuristic that might help you form a conjecture about what we expect the answer to be.

# xxHash64

For xxHash64, it is not a cryptographic hash, so it is more amenable to analysis. The answer is yes, all fibers are infinite. In particular, xxHash64 works with four 64-bit "accumulators". If we are given the value of an accumulator before and after a single iteration, it is easy to find a value of the 64-bit message (input) that causes the accumulator to evolve in that way (and it is unique). So, this makes it easy to prove that all fibers are unique: given $$y$$, we can choose the first $$n-32$$ bytes arbitrarily, then choose the last 32 bytes (using the previous observation) to force its output to be $$y$$, and that will give a $$n$$-byte message that hashes to $$y$$. Since we can do that for all $$n$$ and all choices of the first $$n-32$$ bytes, all fibers are infinite.

• Thank you for your effort and the great explanations! Dec 5, 2020 at 15:57