1
$\begingroup$

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)$?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your effort and the great explanations! $\endgroup$ – Dominic van der Zypen Dec 5 '20 at 15:57

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.