Compare a timestamp to Rekor v2 instance validity window

[haydentherapper]

Description

Each instance from a TrustedRoot includes a validity window. For each instance, we compare a timestamp from the verification material to verify that we didn't issue the material outside of the validity window of the instance: For Fulcio, we compare the "issued at" timestamp from the certificate, for the timestamp authority, the timestamp from the signed timestamp, and for Rekor, the integrated timestamp.

For Rekor v2, there is no timestamp from the service, so there's nothing to compare against. We could compare a timestamp from other verification material like the TSA timestamps - Open to discussion on if this adds value, but we think it's not meaningful since these instances are unrelated.

In a later revision of Rekor v2, checkpoints will be co-signed by witnesses. Witnesses provide a timestamp as part of the cosignature for an independent assertion of integrated time. Once we integrate Rekor v2 with a witness network, we can add a comparison of witness timestamps to Rekor validity windows.

cc @cmurphy

[kommendorkapten]

Until there is a witness network we can use, there is no general concept of time in Rekor V2.

My proposal is that we should ignore this until we have a witness network and can do the comparison against the witnesses. If we made the check now by choosing either a time from a cert or from a TSA, we would end up having code that is not strictly doing what we ask for (in the common case it would probably be correct though) which could in lead to wrong verification results.

I think we should keep this issue open for reference until we have witnessing, and address the comparison then.

[steiza]

If there's a period of time where there's no time associated with a Rekor entry (after transitioning to Rekor v2, before a witness network is set up) are we opening ourselves up to an attack?

Maybe this scenario is far-fetched, but say Rekor's private key is leaked. We can rotate to the new key in the trusted root, but if clients are doing offline verification, how will they know which key to use to verify the tlog entry in the bundle? Could someone take the old leaked key and create a tlog entry with it that would pass offline verification, even if you had an updated trusted root?

[kommendorkapten]

Great example @steiza, and I would say the answer is that would can a valid attack.

The tlog is used to prove that you are honest (adding transparency), so for this attack to become real, the attacker would need to have access to a signing key that a user trust. An entry on the log is not enough to convince a user (today with Rekor anyone can upload "anything").

The attack would be to hide your malicious signature from the world, and only present it to the victim, but as as said, for the attack to be successful, a signing key (or certificate) the user trust would be needed (an malicious actor could use this to sign a special version for a targeted audience that appears to be on the log).

How realistic is this? Hard to tell. Is it serious enough that we should create some abstraction on the signed entity to get "a timestamp" to use for looking up the validity for the log? We can do that by now taking either issued at from the cert, or the signed timestamp, then when we have witnessing, we can use a timestamp from a witness.

If we do it filtering based on certificate's issued at, we at least get a known timestamp before it was uploaded to the log. So we can use it to filer out old logs at least. If we now log x was valid until time t, we can reject signatures made at t+1 as it's impossible for that signature to be on the log (assuming certificates are not re-keyed with same signing key).

For signed timestamps it's a bit harder as the counter signature is not stored on the log, so the signed timestamp can be created both before or after the signature was stored on the log.

That that sounds about right?

[steiza]

If we do it filtering based on certificate's issued at, we at least get a known timestamp before it was uploaded to the log.

I think this would work, but I'd want to trace through sigstore-go codepaths to double-check.

... but then what about a Sigstore bundle signed with a key, where there's a public key hint instead of a Fulcio certificate?

This is giving me pause about moving to Rekor v2 before there's witnessing in place, but definitely open to feedback here!

[kommendorkapten]

Talking with @jku on this, the attack mentioned by @steiza is not a regression from Rekor V1. If an attacker gets access to a Rekor V1 key, they can equally forge a valid Rekor v1 entry with a Signed Entity Timestamp (integrated timestamp) as it's under the attackers control.

Best we can do before witnessing is to iterate over the Rekor V2 entries in the trusted root IMHO to see if any signature is matching.

[loosebazooka]

We do have time from TSAs, and in sigstore-java we're considering the option that at least one TSA timestamp (trusted by trustroot) falls into the validity window to be a stand-in for the rekorV1.integratedTime.

I didn't actually consider the case of the non-fulcio signing pathway. Perhaps we need to mandate TSAs for any rekor-v2 signing?

[kommendorkapten]

I didn't actually consider the case of the non-fulcio signing pathway. Perhaps we need to mandate TSAs for any rekor-v2 signing?

I would prefer to not be to prescriptive here, and instead wait for witnessing support, were we are getting one or more timestamps from the witnesses. This way we keep all the concerns separated which I think is a more desirable approach.

[haydentherapper]

Sorry for the delayed response! Great discussions thus far. As Fredrik and Jussi mentioned, this isn't a regression from Rekor v1, so I don't see this as something that needs to block Rekor v2.

We could use a timestamp from another source to compare the validity window for Rekor v2. Functionally, I think that's fine and wouldn't cause any issue. It would require creating another API to provide timestamps to Rekor's verifier - that asymmetry to other service APIs isn't ideal.

I'll also mention sigstore/rekor-tiles#230, which details a proposal for how to handle monitoring frozen logs. We've gone through a few iterations, but the current proposal is to bake the log size or final checkpoint into the trust root. This is an alternative to a validity window for a log and can be done without a timestamp. We decided to punt on this from the GA release of Rekor v2 because it's a pretty minor threat, that a log says it's frozen but continues to accept entries and issue proofs (either because the key is leaked or the log acts maliciously) but monitors think the log is frozen so they stop monitoring.