Unifying timestamp verification across SETs and TSA signed timestamps

[haydentherapper]

Description

With the current spec, a client specifies how many SETs and how many timestamps are expected. The current implementation expects that every timestamp that is present is verifiable by material in the trusted root. We propose changing this in two ways: First, ignoring any timestamps that cannot be verified, as long as the threshold is met (noted in the bug below). Two, treating SETs and TSA signed timestamps as equals for fetching verified timestamp.

One approach for this is to expose a policy configuration that states a timestamp can be obtained from either an SET or TSA signed timestamp. This could be via a policy flag that states a threshold must be met for either SETs or signed timestamps. Personally, I like this approach of unifying the two, as SETs no longer are used as a proof of inclusion and instead are just a signed timestamp from the log. This also opens us up to adding timestamp providers, like Roughtime.

Related bug: #43 - Once fixed, as long as some number of timestamps are found that meet the threshold, verification will continue, and any failures will be ignored.

[haydentherapper]

I believe this summarizes everything we discussed @steiza @loosebazooka @woodruffw @kommendorkapten

If we go with this approach, there is no need for significant changes to the client spec. This will still be a policy decision by the client, though I would expect most clients to simply set the policy to be 1 trusted timestamp.

Also, this is an edge case, as we expect the typical bundle to contain only a signed timestamp or SET, not both.

[kommendorkapten]

We already have this option define: https://github.com/sigstore/protobuf-specs/blob/main/protos/sigstore_verification.proto#L69

Verbatim copy:

        message TimestampAuthorityOptions {
                // The number of signed timestamps that are expected.
                int32 threshold = 1;
                // Disable signed timestamp verification.
                bool disable = 2;
        }

How about update the comment to clarify mention that the signed timestamps can be any of:

• Rekor SET
• RFC 3161
• Roughtime or something else (for the future)

This way, if a client does not care if RFC3161 or a SET is used, the threshold can be set to 1. If both are required, a value of 2 can be set.

As the verifier is in control over the trust root, and we perform deduplication of Rekor Entries, I don't see any immediate risk with this. Thoughts?

Edit: removed "clarify" as the intent from the beginning was not for the TimestampAuthoroityOptions to be anything else than a what's in TimeStampVerificationData which currently only allows for RFC3161 signed timestamps.

And if we would change that a SET from Rekor is valid as timestamp alone, should that be more visible? Now in the VerificationMaterial they are different fields (tlog_entries vs timestamp_verification_data), and that's why there are different options for verification.

TimestampVerificationData: https://github.com/sigstore/protobuf-specs/blob/main/protos/sigstore_bundle.proto#L41
VerificationMaterial: https://github.com/sigstore/protobuf-specs/blob/main/protos/sigstore_bundle.proto#L52

[phillmv]

I need to catch up on this discussion!, but in the meantime I would like to put out I am broadly supportive of this interpretation & we kind of foresaw something like this happening; this is why we ended up calling the set of {Rekor entries, TSA entries} "ObserverTimestamps":

sigstore-go/pkg/verify/signed_entity.go

Line 423 in fcb55a2

verifiedTimestamps, err := v.VerifyObserverTimestamps(entity)

I'd have to think about the interface a bit more - sometimes we want to specify that we do NOT expect a rekor entry - but in principle I'd support folding WithSignedTimestamps and WithTransparencyLog options into a WithObserverTimestamps option that specifies either/or.

[haydentherapper]

It looks like WithTransparencyLog sets a policy for both how many logs an entry should be recorded to and how many instances of an SET should be present for timestamps. I think this is conflating two separate policy decisions, it should be possible to set these two independently.

Thinking out loud, if we were to have as many configurations as possible, it would be:

• WithTransparencyLog - Number of logs an entry is recorded to. This will verify inclusion proofs or SETs, but will not extract timestamps.
• WithSignedTimestamps - Number of TSA-signed timestamps
• WithSignedEntryTimestamps - Number of log-issued timestamps/SETs. This will extract timestamps from SETs
• WithObserverTimestamps - Number of TSA-signed timestamps or log-issued SETs

A benefit to this is if WithTransparencyLog only refers to entry inclusion policy, then you could set a policy that you do not expect a Rekor entry.

In practice, I would expect the typical verifier would only use WithTransparencyLog and WithObserverTimestamps. If a verifier is opinionated on only allowing TSA timestamps, then they would use WithTransparencyLog and WithSignedTimestamps.

How does this sound?

Edit: This also is documented in the client spec, separating timestamp extraction from log inclusion verification.

[haydentherapper]

Working on a PR now for more discussion, I'll post a WIP shortly.

[kommendorkapten]

The proposal is a bit of a deviation from the ArtifactVerificationOptions.
We should update that message too to reflect the standard verification options we a Sigstore client should have.

[kommendorkapten]

Could WithTransparencyLog and WithSignedEntryTimestamps be combined:

func WithTransparencyLog(threshold int, verifySET bool) VerifierOption {

[kommendorkapten]

See https://github.com/sigstore/protobuf-specs/pull/179/files#diff-84ba96fbb758e3fc5ba115bb8e8d0d43bb721f47b0b389adc885c68080ceda44 for a proposal if verification options

[haydentherapper]

Good idea! I posted about this in the linked PR, but roughly, if we combine these, we get the following acceptable combos (x,y = some threshold):

• WithTLog(x, true) + WithTSA(y) = x promises or proofs + y TSA timestamps
• WithTLog(x, true) + WithObserverTimestamp(y) = x promises or proofs + y TSA timestamps or SET timestamps
• WithTLog(x, false) + WithTSA(y) = x proofs, y TSA timestamps
• WithTLog(x, false) + WithObserverTimestamp(y) = x proofs, y TSA timestamps or SET timestamps

I think this should cover all expected states. The only state we're missing is (only SETs, no TSA sigs), but I can't think of a use case for disallowing TSA sigs, simply don't include TSAs in the trust root.

Does this look good to everyone?

Invalid states:

• WithTLog(x, true/false) = not valid, must specify WithInsecureNoTimestamp too
• WithTSA(y) + WithObserverTimestamp(y) = must specify one or the other

[kommendorkapten]

The fourth option:

• WithTLog(x, false) + WithObserverTimestamp(y) = x proofs, y TSA timestamps or SET timestamps

if verifySet is false, but SET timestamps are valid for observing time. That would mean that we require a SET in the bundle, but we don't verify it against the content of the bundle? I feel like I'm missing something as we must verify it to be able to trust the SET, and so this would be equal to the second example:

• WithTLog(x, true) + WithObserverTimestamp(y) = x promises or proofs + y TSA timestamps or SET timestamps

Or is the thinking that if verifySET is true, we trust the Rekor entry even if there is no inclusion proof? This would not be valid for a v0.2 bundle though as in v0.2 the promise is optional and proof required.

[kommendorkapten]

This last discussion is highly related to the discussion in this PR sigstore/protobuf-specs#179 (comment)

We should probably stick to having the comments in one place, so lets keep them here if that's easier.

[haydentherapper]

if verifySet is false, but SET timestamps are valid for observing time. That would mean that we require a SET in the bundle, but we don't verify it against the content of the bundle? I feel like I'm missing something as we must verify it to be able to trust the SET, and so this would be equal to the second example:

For this example, what I meant as that the SET would not count towards the Rekor threshold, but we would still verify the SET to extract out the timestamp. I wanted some way to distinguish between an SET as a valid proof vs as a valid timestamp. My proposal is that verifySET means it counts towards a valid proof, but we still try to verify SETs if they're present to extract out a timestamp. But to your other point below...

Or is the thinking that if verifySET is true, we trust the Rekor entry even if there is no inclusion proof? This would not be valid for a v0.2 bundle though as in v0.2 the promise is optional and proof required.

Yes, that was my thought initially. But good point about the bundle requirements, I forgot that. I agree with your comment on the other PR about this just being about trusting the time.

One nit: verifySET is not entirely accurate, since we can also get the integrated time from a request to Rekor. Maybe it should be trustIntegratedTime? This also aligns with this being about time and not about proofs.

Revising this...

For v0.2+ bundles:

• WithTLog(x, true) + WithTSA(y) = x proofs, y TSA timestamps
• WithTLog(x, true) + WithObserverTimestamp(y) = x proofs, y TSA timestamps or SET timestamps
• WithTLog(x, false) + WithTSA(y) = x proofs (ignoring SET if present), y TSA timestamps (same as 1)
• WithTLog(x, false) + WithObserverTimestamp(y) = x proofs (ignoring SET if present), y TSA timestamps

For v0.1 bundles (which is the same as v0.2, except SETs count towards the log threshold):

• WithTLog(x, true) + WithTSA(y) = x proofs or promises, y TSA timestamps
• WithTLog(x, true) + WithObserverTimestamp(y) = x proofs or promises, y TSA timestamps or SET timestamps
• WithTLog(x, false) + WithTSA(y) = x proofs or promises, y TSA timestamps (same as 1)
• WithTLog(x, false) + WithObserverTimestamp(y) = x proofs or promises, y TSA timestamps

Separate question: Would we be OK dropping support for v0.1 bundles? It would make this a bit easier to reason about.

Edit: Another option is to drop trustedIntegratedTime and instead just use the signal of whether WithTSA or WithObserverTimestamp is used. If the latter is set, then it's assumed that you want to trust the log's timestamp.

The other thing is that with v0.1 bundles, you cannot distinguish between proofs and promises. Then I'd propose a verifySET flag, only for v0.1 bundles (v0.2 bundles will never use SETs towards the log threshold). This is tangential though, so I can discuss this elsewhere.

[kommendorkapten]

Good summary @haydentherapper, I completely agree with the updated understanding.

I would rather keep support for v0.1 bundles, although it does increase the complexity a bit. There are some bundles out in the wild using that format. Also if people want to perform a similar translation as described in #30 keeping support for older bundles is good.

Re: trustIntegratedTime vs WithTSA or WithObserverTiemstamp, It' a bit harder. I probably would favour keeping the trustIntegratedTime even though it complicates the API a slight bit, as I would assume require explicit trust would lead to less surprises in the future for verifies. One can argue that if a verifier is using WithObserverTiemstamp they are making a choice, but still, when it comes to security I think you should make it hard to end up in a situation where you can be surprised. I.e construct the API so that it's hard to the "wrong" thing.

[haydentherapper]

My main goal is both secure by default and ease of use. I would like a verifier to get reasonable defaults without much configuration, but have the option to configure it to further restrict verification. Something like WithTlog(threshold, opts...) where opts includes trustIntegratedTime, setCountsTowardsThreshold, or any other optional configuration. Secure by default would mean false for all options, to not trust the integrated time or count the SET towards the threshold.

I've been thinking that by using WithObserverTimestamp, it's making the explicit decision to use both the TSA and SET timestamps. This is OK when it's a decision only between these 2, but maybe it's worth considering, what about if we add in Roughtime?
One way to think of this is that WithObserverTimestamp is the unification of all timestamp options. You can use WithTlog and WithObserverTimestamp to trust all timestamp formats, which is equivalent to WithTlog(threshold, trustTime=true) + WithTSA() + WithRoughtime(). If you want to trust a subset of timestamp providers, you can do easily do so. And we can say that WithObserverTimestamp cannot be used with other timestamp options, to avoid the confusion of one overriding another.

How does this sound?

[haydentherapper]

I think I've found a good approach for the API balancing usability and optionality. By adding an option to set a threshold for integrated timestamps, rather than only trusting them, it makes log timestamps look more like signed timestamps. This also covers an edge case of wanting a different threshold for the number of log proofs and log timestamps.

So you can either create a verifier like:

• WithTLog(threshold).WithIntegratedTimestamps(threshold).WithTSA(threshold) or
• WithTLog(threshold).WithObserverTimestamps(threshold) which uses timestamps from all providers (trusted by the root).

Or even WithTlog(threshold).WithTSA(threshold).WithObserverTimestamps(threshold) which would mean you require a minimum number of signed timestamps in addition to an overall timestamp threshold.

Edit: Implemented in 09ad1f8