4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't think this property can hold for all inputs for non-constant functions. $\endgroup$ – SEJPM Nov 7 '17 at 18:56
  • 1
    $\begingroup$ @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. $\endgroup$ – Squeamish Ossifrage Nov 7 '17 at 18:59
  • $\begingroup$ @SqueamishOssifrage I see. Would you be able to explain how I can prove that it is not collision resistant? $\endgroup$ – user52948 Nov 7 '17 at 19:01
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Nov 7 '17 at 19:06
  • 1
    $\begingroup$ @poncho: No apologies needed—saved me a lot of investigative work! $\endgroup$ – Squeamish Ossifrage Nov 7 '17 at 19:11
8
$\begingroup$

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...

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

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy