Bug: Proofs of Absence can be Forged

[preston-evans98]

Bug: Proofs of Absence can be Forged

Problem

The namespaced merkle tree exposes a VerifyNamespace method whose documentation states that it "verifies that the namespace is complete and no leaf of that namespace was left out in the proof."

This API allow consumers to write code like the following:

proof, namespaceData := getUntrustedProofFor(namespaceId)
// check that the namespaceData was all returned
if proof.VerifyNamespace(sha256.New(), namespaceId, namespaceData, n.Root()) {
    process(namespaceData)
} else {
    return errors.New("prover lied about namespace data")
}

Unfortunately, this code is vulnerable. A malicious prover can falsely claim that the namespace is empty, and, as long as he also provides an empty proof, the claim will be accepted.

Test Case

A simple test case which reproduces the issue is as follows:

func TestNMT_forgeNamespaceEmptinessProof(t *testing.T) {
	data := [][]byte{
		append(namespace.ID{0}, []byte("leaf_0")...),
		append(namespace.ID{0}, []byte("leaf_1")...),
		append(namespace.ID{1}, []byte("leaf_2")...),
		append(namespace.ID{1}, []byte("leaf_3")...)}
	// Init a tree with the namespace size as well as
	// the underlying hash function:
	tree := New(sha256.New(), NamespaceIDSize(1))
	for _, d := range data {
		if err := tree.Push(d); err != nil {
			panic(fmt.Sprintf("unexpected error: %v", err))
		}
	}

	root := tree.Root()
	actualLeaves := tree.Get(namespace.ID{0})
	if len(actualLeaves) == 0 {
		t.Fatalf("Get(namespace.ID{0}) should have returned two leaves but returned none.")
	}

	forgedProof := Proof{
		start:                   0,
		end:                     0,
		nodes:                   [][]byte{},
		leafHash:                []byte{},
		isMaxNamespaceIDIgnored: true,
	}

	forged_proof_succes := forgedProof.VerifyNamespace(sha256.New(), namespace.ID{0}, [][]byte{}, root)
	if forged_proof_succes {
		t.Fatalf("Successfully verified proof that non-empty namespace was empty")
	}
}

Root Cause

This behavior is introduced by the following condition here:

// empty range, proof, and data: always checks out
if len(data) == 0 && isEmptyRange && len(proof.nodes) == 0 {
    return true
}

Suggested Solution

Currently, the handling of empty range proofs is not well defined. I propose to reject all proofs that do not contain at least one node in either the proof.nodes or data arguments, unless the tree is the empty. (Without this special case, it's impossible to check range proofs against the empty tree). This will change the semantics of the NMT, causing some existing test cases to fail.

[liamsi]

Regarding the root cause, mentioned above, I think changing that if condition to this should fix it:

if len(data) == 0 && isEmptyRange && len(proof.nodes) == 0 {
	// empty range, proof, and data and nID < min or nID > max: always checks out
	if nID.Less(min) || max.Less(nID) {
		return true
	}
	return false
}

This would ensure that an empty range is only valid if nID < min or nID > max in the root. Need to think a bit further about the empty-tree case though. Note that an empty tree is defined as this (or base-case here) but I think that would also work with the above.

[preston-evans98]

I think this change is good. I would just add a special case for the empty root since its purported min and max namespaces aren't accurate.

if len(data) == 0 && isEmptyRange && len(proof.nodes) == 0 {
	// empty range, proof, and data and nID < min or nID > max: always checks out
	if nID.Less(min) || max.Less(nID) || bytes.Equal(root, nth.EmptyRoot())  {
		return true
	}
	return false
}

The extra check is necessary - otherwise, it's impossible to verify a proof of absence for namespace 0 in the empty tree

func TestNMT_absenceProofInEmptyTree(t *testing.T) {
	tree := New(sha256.New(), NamespaceIDSize(1))
	root := tree.Root()
	emptyleaves, proof, err := tree.GetWithProof(namespace.ID{0})
	if err != nil {
		t.Fatalf("GetWithProof()  could not get namespace{0}. err: %v ", err)
	}
	if len(emptyleaves) != 0 {
		t.Fatalf("Get(namespace.ID{0}) should have returned no leaves but returned %v", emptyleaves)
	}
	if !proof.VerifyNamespace(sha256.New(), namespace.ID{0}, emptyleaves, root) {
		t.Fatalf("Could not verify proof of absence of namespace zero in empty tree")
	}
}