<h1>Cryptographic hashes</h1>
<p>I don't think anything is known unconditionally.</p>
<p>We can analyze this question using a random oracle assumption.  MD5, SHA1, SHA256, etc., have a <a href="https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction" rel="nofollow noreferrer">Merkle-Damgaard structure</a>: they split the input <span class="math-container">$x$</span> up into blocks <span class="math-container">$x_1,\dots,x_n$</span>, then compute
<span class="math-container">$$h_i = F(x_i,h_{i-1})$$</span>
where <span class="math-container">$h_0$</span> is a constant and <span class="math-container">$h_n$</span> is used as the output of the hash function.  Now let's analyze this structure under the assumption that <span class="math-container">$F$</span> can be modelled as a random function (which is believed to be a good heuristic).</p>
<p>Suppose we want to construct a message <span class="math-container">$x_1,\dots,x_n$</span> that hashes to output <span class="math-container">$y$</span>.  Pick <span class="math-container">$x_1,\dots,x_{n-2}$</span> arbitrarily; this determines <span class="math-container">$h_{n-2}$</span>.  Now let's consider all possibilities for <span class="math-container">$x_{n-1},x_n$</span>, and the derived values of <span class="math-container">$h_{n-1},h_n$</span>.  If we focus on MD5, each <span class="math-container">$x_i$</span> is 512 bits and each <span class="math-container">$h_i$</span> is 128 bits.  Since <span class="math-container">$F$</span> is a random function, the chances that any particular value of <span class="math-container">$h_{n-1}$</span> is never reached by any choice of <span class="math-container">$x_{n-1}$</span> is <span class="math-container">$(1 - 1/2^{128})^{2^{512}} \approx 1-1/2^{384}$</span>; therefore it is overwhelmingly likely that all <span class="math-container">$2^{128}$</span> possible values of <span class="math-container">$h_{n-1}$</span> are attainable.  Now consider all <span class="math-container">$2^{640}$</span> possible combinations of <span class="math-container">$(h_{n-1},x_n)$</span>, and consider the resulting value of <span class="math-container">$h_n = F(x_n,h_{n-1})$</span>.  Since <span class="math-container">$F$</span> is a random function, the chance that none of these combinations yields <span class="math-container">$h_n=y$</span> is <span class="math-container">$(1-1/2^{128})^{2^{640}} \approx 1/2^{512}$</span>, i.e., vanishingly unlikely.  In conclusion: if you pick <span class="math-container">$x_1,\dots,x_{n-2}$</span> arbitrarily, it is overwhelmingly likely that there will exist a way to pick <span class="math-container">$x_{n-1},x_n$</span> so that the resulting hash function outputs the value <span class="math-container">$y$</span>.</p>
<p>It follows that, for MD5, there are infinitely many <span class="math-container">$x$</span>'s that yield the hash <span class="math-container">$y$</span>, assuming that treating <span class="math-container">$F$</span> as a random function is a good model.  In other words, for MD5, we expect all fibers to be infinite.</p>
<p>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 (<span class="math-container">$F$</span> doesn't behave like a random function).</p>
<p>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.</p>
<h1>xxHash64</h1>
<p>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 <a href="https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md" rel="nofollow noreferrer">works with</a> 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 <span class="math-container">$y$</span>, we can choose the first <span class="math-container">$n-32$</span> bytes arbitrarily, then choose the last 32 bytes (using the previous observation) to force its output to be <span class="math-container">$y$</span>, and that will give a <span class="math-container">$n$</span>-byte message that hashes to <span class="math-container">$y$</span>.  Since we can do that for all <span class="math-container">$n$</span> and all choices of the first <span class="math-container">$n-32$</span> bytes, all fibers are infinite.</p>

CC BY-SA 4.0
2020-12-05T15:57:57.243Z
Thank you for your effort and the great explanations!
Dominic van der Zypen
CC BY-SA 4.0
2020-12-05T08:28:20.540Z
2020-12-05T08:28:20.540Z
D.W.
<p>Let <span class="math-container">$\{0,1\}^{&lt;\omega}$</span> denote the collection of finite binary sequences. By a <em>hash function</em> we mean a computable map <span class="math-container">$$h: \{0,1\}^{&lt;\omega} \to \{0,1\}^n$$</span> for some fixed <span class="math-container">$n\in\omega$</span>. Define <span class="math-container">$\text{Fib}(h) = \{h^{-1}(\{y\}) : y \in \{0,1\}^n\}$</span> to be the set of <em>fibers</em> of <span class="math-container">$h$</span>. (That is, every element of <span class="math-container">$\text{Fib}(h)$</span> is the set of inputs being mapped to some fixed <span class="math-container">$y\in\{0,1\}^n$</span>.)</p>
<p>It is clear that some elements of <span class="math-container">$\text{Fib}(h)$</span> 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 <span class="math-container">$h: \{0,1\}^{&lt;\omega} \to \{0,1\}^n$</span>, there is <a href="https://mathoverflow.net/questions/378081/checking-for-finite-fibers-in-hash-functions">no procedure to determine whether all fibers are infinite</a>.</p>
<p><strong>Question.</strong> If we take <span class="math-container">$h$</span> 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, <span class="math-container">$\varnothing \notin\text{Fib}(h)$</span>?</p>

<hash-function>
Fibers of hash functions
Dominic van der Zypen
# Fibers of hash functions

(Asked by: username_0 on 2020-12-04)

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](https://mathoverflow.net/questions/378081/checking-for-finite-fibers-in-hash-functions).

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

**Tags:** hash-function

---

## 1 answers

### Answer by username_1 on 2020-12-05. Score: 3 | Accepted answer

# 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](https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction): 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](https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md) 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.

> **Comments:**
> **username_0**: Thank you for your effort and the great explanations!  

---

