Timestamp verification should not fail unless the threshold is not met

[haydentherapper]

Description

Looking at https://github.com/sigstore/sigstore-go/blob/main/pkg/verify/tsa.go#L64, if any timestamp verification fails, then the verifier errors out. Instead, the verifier should succeed as long as the threshold for successful timestamp signatures is met. If there's N timestamps, and the threshold is 1, then the verifier only needs 1 timestamp to verify to succeed.

[phillmv]

When writing out that function, my interpretation was:

• suppose you have N timestamps
• you may stop verifying timestamps once you hit threshold M < N

But the question of how to handle invalid timestamps was curious.

Adopting the perspective of, well, writing an attestation/sigstore bundle store where we prize data integrity above all else, I found myself asking:

How exactly would you end up with an invalid timestamp embedded in the bundle? Either you received a timestamp that is outside of the validity period, which the signer should have rejected, or you used an "Observer" whose key is not part of the verifier's trusted materials.

---

In every other part of the spec we're careful to fail as early as possible and to stop processing the data as soon as we encounter an error. Initially, we were tempted to do the opposite, and try to muddle along the verification process so we could generate more meaningful errors: what if you have not just 1 but 2 or 3 different bugs in your signer?

But after meditating on this behaviour, I decided that it was wise to bail early: continuing to process the data after we entered invalid state would invite subtle bugs or exploits further down the road that could be used to compromise or fake verification.

So, on a similar note, I ask: is this a bug?

Under what circumstances are you legitimately creating a bundle with either a timestamp in an invalid range, or asking the verifier to verify a signature whose trusted materials we do not possess? On a balance of probabilities, it feels like it's more likely that shenanigans are happening.

I'm not wedded to this behaviour!, but the idea of aggressively rejecting shenanigans (aka weirdly shaped bundles) is appealing.

Could we narrow down the undesirable behaviour? Like, is it permissible to have a (signature-verified) timestamp that is outside of the validity period [which we do not count towards the threshold], but we fail early if we have a signature we can't verify?

I forget if the spec explains what the use case is for having M of N timestamp thresholds. Are we hoping to have multiple transparency logs whose keys are not always available?

[steiza]

I think the use-case of a medium-sized organization running their own Timestamp Authority, and so the bundles they publish have TSA entries that consumers won't necessarily be able to verify with what's in their trust root, is pretty straight-forward and clear that we should support it.

I proposed a fix for this in #45. Philosophically, I understand "fail fast and fail noisily" but there's also value in having the code be more straightforward and not having multiple error paths, some of which result in "ignore this TSA signature" and others which result in "fail the whole bundle".

¯\_(ツ)_/¯ Take a look at #45 and see what you think!

[haydentherapper]

+1 to Zach's example, there is no guarantee a signer and verifier trust the same authorities. To avoid signing an artifact twice that will be publicly distributed and used internally, a signer may choose to fetch a timestamp from its own internally trusted authority and a public TSA.

To give another concrete example, this comes up in Certificate Transparency. A CA may choose to publish a certificate to a set of CT logs it trusts, say one within its geography and one that is more widely trusted. A user agent (Chrome, Safari, iOS, etc) has its own "log list" that defines what it considers to be a trusted CT log. As long as a minimum policy is met (for Chrome, a proof from 2 logs), that certificate is considered trusted by the user agent.
To your question about multiple transparency log entries, yes, I would expect multiple entries. In the (hopefully near) future, I would like to see multiple logs (say, run by each package repository or other ecosystem participants), and each verifier or client should define what logs it trusts.

For verifiers who know the signer, maybe a closed ecosystem or a private deployment, would you like another policy flag that states that all verification material must be verifiable?

[kommendorkapten]

To give another concrete example, this comes up in Certificate Transparency. A CA may choose to publish a certificate to a set of CT logs it trusts, say one within its geography and one that is more widely trusted. A user agent (Chrome, Safari, iOS, etc) has its own "log list" that defines what it considers to be a trusted CT log. As long as a minimum policy is met (for Chrome, a proof from 2 logs), that certificate is considered trusted by the user agent.

This is the exact use-case we targeted when designing the trusted_root and sigstore_verification::Input, the verifier has its trust root, and provides a minimum number of signatures that must be valid given that trust root.