"Intrinsic" verification ideas

[woodruffw]

Summarizing from a Slack thread with @hectorj2f, @bobcallaway, and @haydentherapper (sorry for the delay!)

I've been calling this basic idea "intrinsic" verification, which isn't a great name. The observation is that, given a URL like:

hxxps://github.com/foo/bar/.../v1.2.3.tar.gz

...we have a few different "intrinsic" identities available to us for verification:

1. We might trust GitHub user foo to sign for this artifact (xref Proposal: GitHub username identities with the GitHub IdP fulcio#1283)
2. We might trust any workflow running under foo/bar to sign for this artifact

The "cool" thing here is that, in principle, we can choose to verify against either of these identities without needing a signature or certificate ahead of time: if all we want to know is "foo signed for v1.2.3.tar.gz", then we can consult the artifact transparency log for signatures over v1.2.3.tar.gz, and confirm that at least one of those signatures came from a certificate bound to foo.

In other words: with "intrinsic" verification, we can bootstrap authenticity with just a single URL! This is especially cool for dependency or packaging ecosystems that perform referencing/indexing by URL: rather than having to stand up additional storage for Sigstore bundles (or cert + sig pairs), the ecosystem could ensure an intrinsic identity for every URL and leverage the transparency service for all state.

This idea hits reality in a few places:

1. This kind of by-hash transparency log lookup assumes efficient verifiable search over the Merkle tree, which doesn't currently exist. The best current thing is the /index/retrieve endpoint, which is (1) not verifiable, and (2) not guaranteed to be correct. Solving this is a hard problem.
2. A naive search for the expected signer is easy to abuse here: someone could spam the log with lots of signatures (from ephemeral keys) for the input, making the search grow linearly. This could be mitigated by searching by date of signature (searching for the earliest first), but this poses re-signing challenges and further complicates verifiable search.

I'm not yet sure any of this is a good idea: it has a different threat model from the normal Sigstore verification flow in ways that I haven't fully thought through yet.

[haydentherapper]

This is a perfect use case for verifiable maps. See https://github.com/google/trillian-examples/tree/master/experimental/batchmap or https://holbrook.no/share/papers/project1_report_ver3.pdf for some ideas around implementing this.

We have discouraged using Rekor as artifact/provenance storage, but using it to access certificates I think should be sound. A log would have to present a valid inclusion proof alongside the certificate, meaning that a signer would be able to verify inclusion of the certificate in the log so that the log could not manufacture a malicious certificate. We can assume witnesses monitor the log for consistency to prevent split-view attacks too.