Fibers of hash functions Let $\{0,1\}^{&lt;\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{&lt;\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 &quot;fair&quot; in some sense, we would like all fibers to be infinite. Now, given a hash function $h: \{0,1\}^{&lt;\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 &quot;accumulators&quot;.  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.