Explanation of Second Pre-Image Attack on Merkle Trees (referenced in RFC 6962)?

[Bobo B.]

Hi All,

Could someone please point me to a resource on the "second preimage attack" with regards to Merkle trees (line 257: https://tools.ietf.org/idnits?url=https://tools.ietf.org/id/draft-ietf-trans-rfc6962-bis-21.txt)?

I've been searching in an attempt to find a description of this attack but have not been able to find something. I'm fairly confused at this point but my guess is it's related to one or more of the following:

• how you define the Merkle hash, e.g., hash(hash(A) || hash(B)) has some kind of problem because length of the tree is not denoted?
  
  
• hashes of data nodes (e.g., the leaf nodes on the Merkle tree) should be produced with a different hashing algorithm than the hashes of intermediate nodes and the root node (why?)
  
  
• what function you choose for the Merkle hash, e.g., SHA-256 is vulnerable to a length-extension attack but SHA-3 and BLAKE2 are not?
  
  
• for some reason, popular implementations of the Merkle tree get this wrong (e.g., BitTorrent - see Taylor's quoted email from Crypto Forum Research Group: https://www.ietf.org/mail-archive/web/cfrg/current/msg07520.html)
  

Any advice or pointer to a walkthrough of the attack and mitigating it would be very helpful. In particular I'm confused as to what it takes to execute the attack and what it would let an adversary do to a Merkle tree.

I've tried googling and read the following on length extension attacks (https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks) but am still unsure.

Thanks,
Bobo

[Matt Palmer]

On Tue, Nov 29, 2016 at 02:36:33PM -0800, Bobo B. wrote:
> Hi All,
>
> Could someone please point me to a resource on the "second preimage attack"
> with regards to Merkle trees (line 257:
> https://tools.ietf.org/idnits?url=https://tools.ietf.org/id/draft-ietf-trans-rfc6962-bis-21.txt
> )?

This Crypto SE question should explain everything:

http://crypto.stackexchange.com/q/2106/28811

(It's what I found most useful when I was learning about this aspect)

- Matt