Attacking Merkle Trees with a second preimage attack

[OR13]

The Merkle hash root does not indicate the tree depth, enabling a second-preimage attack in which an attacker creates a document other than the original that has the same Merkle hash root. For the example above, an attacker can create a new document containing two data blocks, where the first is hash 0-0 + hash 0–1, and the second is hash 1-0 + hash 1-1.[13][14]

One simple fix is defined in Certificate Transparency: when computing leaf node hashes, a 0x00 byte is prepended to the hash data, while 0x01 is prepended when computing internal node hashes.[12] Limiting the hash tree size is a prerequisite of some formal security proofs, and helps in making some proofs tighter. Some implementations limit the tree depth using hash tree depth prefixes before hashes, so any extracted hash chain is defined to be valid only if the prefix decreases at each step and is still positive when the leaf is reached.

• https://en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack
• https://news.ycombinator.com/item?id=16572793

This raises the question of what effect starting with "salted member leaf nodes" has.

[lawwman]

https://flawed.net.nz/2018/02/21/attacking-merkle-trees-with-a-second-preimage-attack/

In the above example, our inputs are L1, L2, L3, and L4. These eventually output the root hash value at the top of the diagram. But as you can see from the diagram, the inputs to the middle layer are the concatenated hashes of the previous layer, and we can just pass those two values directly into the Merkle Tree and get the same root hash value back.

A second preimage attack can easily be constructed by taking the intermediate hashes as inputs to the merkle tree. This would result in the same merkle root being formed.

So far, I have noticed 2 possible solutions to this:

• prepending fixed data
• using different hash functions for leaves and internals

^ my understanding is that both of these ideas revolve around treating leaf and internal nodes differently.

I feel that using different hash functions for leaves and internals is the current behaviour of your implementation.

Although computeNextLevel() always uses the same hash function, I would like to consider the process of salting members as part of leaf node's hash function. If this assumption is accepted, then there are effectively 2 different hashes:

• internal node's hash: hash(m)
• leaf node's hash: hash(hash(Buffer.concat([m, calculateMessageNonce(m, i, rootNonce, hash)])))

A second preimage attack by taking intermediate hashes as inputs, would result in those intermediate hashes being salted, and having a different resulting merkle root.