1
$\begingroup$

I am trying to understand why Merkle Tree doesn't suffer the birthday attack?

Can you help me?

$\endgroup$
  • 1
    $\begingroup$ Birthday attack against what? Collision resistance? All hashes suffer from that one, including merkle-trees, that's why we need 256 bit hashes for 128 bits of collision resistance. $\endgroup$ – CodesInChaos Dec 6 '15 at 14:35
  • $\begingroup$ What I know in general (I am not saying is correct) is that Merkle Tree is Collision resistant and since the birthday attack is a way to break that property I thought that is not possible attack the Merkle Tree. Now the my doubt is if Merkle Tree is collision resistant. $\endgroup$ – 4nf3rt Dec 6 '15 at 15:24
4
$\begingroup$

The birthday attack, birthday paradox or - probably most accurately - birthday problem does occur for Merkle-trees. This is both the case for the output of the hash algorithms used for the nodes, the in between hash values in the tree as well as the final hash value.

What's probably confusing you here is that the birthday attack isn't really a practical attack against secure hash functions unless the output size is not large enough. In other words, it is the output size of the hash values that protect against the birthday problem becoming a practical issue.

$\endgroup$
  • $\begingroup$ In general as I replied in the previous answer, my doubt now is if the Merkle Tree is collision resistant. $\endgroup$ – 4nf3rt Dec 6 '15 at 15:32
  • $\begingroup$ Of course it is. It is collision resistant and vulnerable to the birthday "attack". The birthday problem is a general property for all hash functions, that's why the security of the hash function is about half of the output size, for these kind of attacks. Note that you did not voice your doubt in your question. $\endgroup$ – Maarten Bodewes Dec 6 '15 at 16:40
  • $\begingroup$ But exists a hash function resistant to birthday attack? $\endgroup$ – 4nf3rt Dec 6 '15 at 17:52
  • 1
    $\begingroup$ @MaartenBodewes is of course correct. The birthday attack runs in time $2^{n/2}$ where $n$ is the output length. It is thus an exponential-time attack. An attack is only considered to break the primitive if it runs in polynomial time. Of course, concretely, we need to make sure that $n$ is large enough to prevent a practical attack. No hash function should have less than $n=256$ today. $\endgroup$ – Yehuda Lindell Dec 7 '15 at 16:27

Your Answer

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

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