Merkle tree lacks second preimage resistance
Description
When performing a token withdrawal, a withdrawalHash is first calculated with the following:
var withdrawalHash [32]byte
{
seed := []byte{}
seed = binary.BigEndian.AppendUint64(seed, bridgeId)
seed = binary.BigEndian.AppendUint64(seed, req.Sequence)
seed = append(seed, sender...)
seed = append(seed, receiver...)
seed = append(seed, []byte(denom)...)
seed = binary.BigEndian.AppendUint64(seed, amount.Uint64())
withdrawalHash = sha3.Sum256(seed)
}The supplied proof is then used to verify it was included in the Merkle tree:
// should works with sorted merkle tree
rootSeed := withdrawalHash
proofs := req.WithdrawalProofs
for _, proof := range proofs {
switch bytes.Compare(rootSeed[:], proof) {
case 0, 1: // equal or greater
rootSeed = sha3.Sum256(append(proof, rootSeed[:]...))
case -1: // less
rootSeed = sha3.Sum256(append(rootSeed[:], proof...))
}
}The issue is that there is no distinction between leaf nodes and intermediate nodes, so it is technically possible to create a withdrawal hash that matches an intermediate node by appending a proof hash to a leaf node and then supplying a proof that matches the intermediate node:
func calculateRoot(bridgeId, sequence uint64, sender, receiver []byte, denom string, amount uint64, withdrawalProofs [][]byte) [32]byte {
var withdrawalHash [32]byte
{
seed := []byte{}
seed = binary.BigEndian.AppendUint64(seed, bridgeId)
seed = binary.BigEndian.AppendUint64(seed, sequence)
seed = append(seed, sender...)
seed = append(seed, receiver...)
seed = append(seed, []byte(denom)...)
seed = binary.BigEndian.AppendUint64(seed, amount)
withdrawalHash = sha3.Sum256(seed)
}
rootSeed := withdrawalHash
proofs := withdrawalProofs
for _, proof := range proofs {
switch bytes.Compare(rootSeed[:], proof) {
case 0, 1: // equal or greater
rootSeed = sha3.Sum256(append(proof, rootSeed[:]...))
case -1: // less
rootSeed = sha3.Sum256(append(rootSeed[:], proof...))
}
}
return rootSeed
}
func Test_FinalizeTokenWithdrawalPreimage4(t *testing.T) {
storageRoot := decodeHex(t, "326ca35f4738f837ad9f335349fc71bdecf4c4ed3485fff1763d3bab55efc88a")
withdrawalProofs := [][]byte{
decodeHex(t, "32e1a72a7c215563f9426bfe267b6fa22ba49b1fba7162d80094dc2f2b6c5a3a"),
decodeHex(t, "627dc2af9ee001b0e119100599dc3923ccdff2c53f06d89f40400edb1e7907e1"),
decodeHex(t, "bafac86e9ebc05a07701c151846c6de7bca68cd315f7a82fffe05fc4301ac47e"),
}
rootHash := calculateRoot(
uint64(1),
uint64(4),
decodeHex(t, "0000000000000000000000000000000000000004"),
decodeHex(t, "0000000000000000000000000000000000000001"),
"l1denom",
uint64(3_000_000),
withdrawalProofs[:],
)
require.Equal(t, storageRoot, rootHash[:])
rootHash = calculateRoot(
uint64(0x32e1a72a7c215563),
uint64(0xf9426bfe267b6fa2),
decodeHex(t, "2ba49b1fba7162d80094dc2f2b6c5a3a4402e743"),
decodeHex(t, "c5c72c0c727da13466d4fcd6dcd88d719f8b00b7"),
"",
uint64(0xd13cb6587a1ae64f),
withdrawalProofs[1:],
)
require.Equal(t, storageRoot, rootHash[:])
}Impact
In practice, this issue is unlikely to be exploitable, as the bridge ID will not exist and will not have a balance for the supplied denom and amount. However, it is a good practice to ensure that the Merkle tree has second preimage resistance.
Recommendations
A distinction should be made between leaf nodes and intermediate nodes in the Merkle tree. One common approach is to prepend 0x00 to leaf nodes and 0x01 to intermediate nodes, as mentioned in the Certificate Transparency specification↗.
Remediation