# Collision resistance in a hash function

I'm confused about whether the following hash function is collision resistant. $x \sqsubseteq y$ denotes that x is equal to y or x precedes y.

$H:\{0, 1\}^* \rightarrow \{0, 1\}^n$

If $x \sqsubseteq y$ then $h(x) \sqsubseteq h(y)$

Does this mean H is collision resistant?

• I don't think this property can hold for all inputs for non-constant functions. – SEJPM Nov 7 '17 at 18:56
• @SEJPM: Sure it can. E.g., $00 \mapsto 0, 01 \mapsto 0, 10 \mapsto 1, 11 \mapsto 1$. But it seems unlikely that such a function could possibly be collision-resistant. – Squeamish Ossifrage Nov 7 '17 at 18:59
• @SqueamishOssifrage I see. Would you be able to explain how I can prove that it is not collision resistant? – user52948 Nov 7 '17 at 19:01
• Well, I could take the time to carry out my intuitive reasoning to a formal reason, but it looks like @poncho beat me to it. – Squeamish Ossifrage Nov 7 '17 at 19:06
• @poncho: No apologies needed—saved me a lot of investigative work! – Squeamish Ossifrage Nov 7 '17 at 19:11

Does this mean H is collision resistant?

No, it cannot be collision resistant.

Consider $H(x)$ over all possible values $x \in \{ 0, 1 \}^k$ for $k \ggg n$. There are $2^k$ possible inputs, and only $2^n$ possible outputs; furthermore, the preimages for any specific output must be contiguous.

Hence, if we consider $x$ stepping from the minimal possible value $0^k$ through consecutive values to the maximal value $1^k$, then $H(x)$ must be split up into (at most) $2^{n}$ ranges, where any two inputs in the same range will generate the same output; for those $2^k$ inputs, there are at most $2^n-1$ places where adjacent inputs produce different outputs.

Hence, if we select a random $r \in \{ 0, 1 \}^{k-1}$, and consider $H( r \mathbin\Vert 0 ), H( r \mathbin\Vert 1)$, then with high probability (at least $1 - 2^{n - k - 1}$), those two hashes will be the same, and that's a collision...

• Thank you! This helps a lot. Why is the probability $1 - 2^{n-k-1}$ ? I'm having a little difficulty understanding that part. – user52948 Nov 7 '17 at 19:10
• @ProgammGurl: does the additional text I inserted help? – poncho Nov 7 '17 at 19:29

As @poncho points out, $H$ is not a collision resistant hash function: here's a simpler argument. Since $H$ is monotonous (i.e., If $x⊑y$ then $h(x)⊑h(y)$), one can find a collision through a binary search (on the space $\{0,1\}^n$). The idea is to check whether the value of the hash of $x\in\{0,1\}^n$ is greater than $x$ and then depending on the hash recursively search either the left half or right half of the space. If you don't find a collision at the end of the search (which means that $H$ is identity on $\{0,1\}^n$), return $1^n$ and $1\|0^n$ as the collision.