0
$\begingroup$

Let $H : \{0, 1\}^∗ \mapsto \{0, 1\}^ n$ be a collision-resistant hash function. Define $H_0(M) = H(M)\mathbin\|0^{n−10}$. That is, $H_0$ appends ($n − 10$) zeros to the output of $H$. Clearly $H_0$ is collision resistant.

Now let $H_{00}$ be the result of truncating the output of $H_0$ to $n$ bits. The question is to show that if the truncation is done incorrectly, then $H_{00}$ will not be collision resistant. In other words, a truncated collision resistant function need not be collision resistant.

Improve this question
$\endgroup$
6
  • $\begingroup$ Welcome to cryptography. I've edited your dump with $\LaTeX$ and here we have MathJax, too. Please check the edits. Is this a homework question? In Cryptography.SE we only provide hints for such questions, and this seems so. Hint: What if you remove the first part from $H_0(M)$? $\endgroup$
    – kelalaka
    Commented Feb 23, 2020 at 12:59
  • $\begingroup$ Yes, but the question said H00 truncates H0 to n bits, so the H0(M) part can not be totally removed. $\endgroup$
    – Jenny
    Commented Feb 23, 2020 at 13:01
  • $\begingroup$ $H_{00} = H(M)|_{10} \mathbin\| 0^{n-10}$ you have 10 bit unkown. Which makes only little search? $\endgroup$
    – kelalaka
    Commented Feb 23, 2020 at 13:26
  • $\begingroup$ Hint: What is $H_{00}$ with respect to $H$? And what does that become if instead one defines $H_{00}$ to keep the last $n$ bits? $\endgroup$
    – fgrieu ♦
    Commented Feb 23, 2020 at 14:11
  • 1
    $\begingroup$ Consider SHA-256 as H then in $H_{00}$ you will only have 10 bit output of the SHA-256 and the rest is all zeros. There is no need to distinguish! Just get $2^5$ values hash them then you will have collision with 50% probability by the birthday paradox. $\endgroup$
    – kelalaka
    Commented Feb 23, 2020 at 14:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.