Include Root Hash verification when verifying a Rekor Inclusion Proof

[asraa]

Description

Mentioned here:

 Not related to this PR, but something we need to add - We now return checkpoints (https://github.com/sigstore/rekor/blob/main/openapi.yaml#L608), signed root hashes. We need to add verification of these when verifying the inclusion proof, otherwise we're just verifying a list of hashes without any connection to the log.

You'll need to verify 1) the signature on the checkpoint and 2) the root hash in the checkpoint matches the root hash from the inclusion proof.

There's a code example here - https://github.com/sigstore/rekor/blob/4b1fa6661cc6dfbc844b4c6ed9b1f44e7c5ae1c0/pkg/verify/verify.go#L114

When verifying inclusion proof, there needs to be a pin on the root hash: this root hash can ideally come from verifying consistency with a stored client state, or verifying the signature on the root hash (e.g. a Signed Root Hash with the rekor public key). Since sigstore clients don't store a rekor state, their best option is the latter.

Otherwise inclusion proofs don't mitigate attacks where you are served a valid inclusion proof on some random log, not Rekor.

cc @haydentherapper

[woodruffw]

I'll tackle this next.

Since sigstore clients don't store a rekor state, their best option is the latter.

What would it mean for Sigstore clients to store a Rekor state? In other words, is this something we could do? More for my own curiosity; I'm happy to go the other route!

[haydentherapper]

Note that everything below is just relevant for online verification, not offline with the bundle.

What would it mean for Sigstore clients to store a Rekor state?

To verify consistency, that the log is append-only and no mutations have occurred between two points in time, you need a previous point from when you've verified consistency. This would be a previous checkpoint (the first verification would have to be TOFU). When you request an inclusion proof from the log, you would:

1. Verify the returned inclusion proof
2. Verify the signature on the returned checkpoint
3. Ask the log for a consistency proof from a persisted checkpoint to the returned checkpoint
4. Verify the consistency proof

It'd be nice to support being able to provide a previous checkpoint to optionally verify consistency. We considered this a much lower priority though, since monitors should already be verifying consistency. This would only be for clients that don't want to trust monitors, and can figure out how to store their checkpoints. (Also, just verifying consistency is not sufficient for clients that want no trust in the log, because split-view attacks are possible, where the log presents a different view to different clients. Each view can still be consistent. Mitigation for split-view isn't currently possible, this is what I'm thinking through for a future Rekor).

This is why we said that verifying the signed tree head/root hash is sufficient, just verifying that an inclusion proof came from a trusted log.

[woodruffw]

Thanks for the detailed explanation!

[woodruffw]

Otherwise inclusion proofs don't mitigate attacks where you are served a valid inclusion proof on some random log, not Rekor.

Making sure I understand this: given that sigstore-python only trusts a specific set of public keys, how would someone mount this attack? Wouldn't they need to pass me a log entry that's signed with a key I trust, which a random log wouldn't possess?

(I think I'm probably missing something 🙂)

[asraa]

There's two Rekor verifications that may happen:

1. SET verification - signed by Rekor's key. Then yes, your analysis is right, they would need to spoof a signature from the trusted key. Fairly impossible.
2. Inclusion proof verification. The content of an inclusion proof is NOT signed, it's just the list of hashes from the leaf hash that you're interested to a root hash. Since the root hash de facto is not signed, you could have a malicious Rekor serve you an inclusion proof to a bogus root hash. The ways you fix this is either by (1) verifying the root hash with a root hash signature (which is provided now) or (2) validating that other people or your existing client have seen this root hash (which can't happen right now without storing state or gossipping).

That being said, Bundles for offline verification don't include inclusion proofs - since it's an offline verification.

[woodruffw]

Makes sense, thank you!

I think my confusion was with the SET and its signature: I keep forgetting that the signature is over the entry without the inclusion proof, for the reasons you've mentioned.

In terms of storing the root hash state: is this conceivably something that could be done with TUF in the future? Specifically, does it make sense for it to be included in the trusted root target? That's based on me assuming that the root hash only changes when the log is rotated, which might be incorrect 🙂

[haydentherapper]

The root hash is updated every time an entry is processed. When you upload an entry to a merkle tree, it changes that node's parent, its parent, etc, all the way up to the root node (log(N) changes).