2
$\begingroup$

If a hash function $H$ is collision resistant, are the following two hash functions collision resistant or not? ($||$ is concatenation)

$H'(m) = H(H(m)) || H(m)$

$H''(m) = H(m) || H(m)$

My first approach to the problem for the first function is this: by proof of contradiction, I find that there aren't $m_1 \ne m_2$ so that $H'(m_1) = H'(m_2)$, because:

$H'(m_1) = H'(m_2) \iff H(H(m_1))||H(m_1) = H(H(m_2))||H(m_2)$

If we suppose that $m'_1 = H(m_1)$ and $m'_2 = H(m_2)$ then:

$H(m'_1)||m'_1 = H(m'_2)||m'_2$ which is false because $H$ is collision resistant.

Is my solution correct or am I missing something?

I can apply the same technique to the second function, but what confuses me is that first half bits are always the same as the last half bits, and this definitely doesn't look secure. But collision resistance is all I need.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your first approach $H'(m) = H(H(m)) || H(m)$ will not have any improvement collision resistance. The reason being is that a collision in the right half automatically causes a collision in the left half, since the output of $H$ is identical for the colliding messages. The left half is not a function of the message, but of the message hash, the concatenation will have the same collision resistance as the hash itself, but take up twice the space and require an additional hash iteration, with no improvement in any security property

The second approach will also have identical collision resistance to $H$, but simply take up twice the space, with no improvement in any security property.

$\endgroup$
2
  • $\begingroup$ Thank you Richie for your answer. So, the question now is: Is the fact that the new function has the same security with twice the space, enough to claim that it is not collision resistant? $\endgroup$
    – naervaer
    Feb 11, 2016 at 0:37
  • 2
    $\begingroup$ @naervaer no, it is still collision resistant if $H$ is, however the expected collision resistance does not increase, even though the size of the output doubles, which is what one expects when the hash output increases. $\endgroup$ Feb 11, 2016 at 2:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.