Clarifications on cryptographic agility and versions

[kommendorkapten]

See https://github.com/sigstore/sig-clients/issues/16 for more background.

In short, we are adding support for cryptographic agility across numerous clients, but I think we must clarify some of this with a formal definition of the "protocol version" that indicates what algorithms are required by a client.

We are now in a situation where it's a bit hard to understand what's required from a client, and what signature algorithms that is supported, this state has led to some scenarios where SHA256/P384 have been used, but it's not listed as a supported algorithm, see https://github.com/sigstore/sigstore-go/pull/424#issuecomment-2720718126 and https://github.com/sigstore/protobuf-specs/blob/v0.4.0/protos/sigstore_common.proto#L78

Also there is no official list on what algorithms are required to implement by a client. The best we have is the sigstore-conformance test suite.

To lay out a plan forward, my suggestion is that we do the following:

1. The "protocol version" is the released version of protubuf-specs used, not the bundle version.
2. Release a patch version, 4.0.1 that adds PKIX_ECDSA_P384_SHA256 = x [deprecated = true]; algorithm type, making it clear to clients that this combinations can be encountered.
3. Prepare for a 4.1.0 release:
   1. document the required signature algorithms to support.
   2. document recommended signature algorithms to support.
   3. add a new flag to the verifier, allowDeprecatedAlgorithm (this could be used to implement fallback to P384/SHA256 in a controlled manner)
   4. update sigstore conformance test with a 4.1.0 test suite, to allow for clients to only test against required signature algorithms, this would also make it clear what is required to add a new client, the historical context may not be needed for a new ecosystem. I think this will be a big win in terms of clarity (today it can be overwhelming for new clients to add support for all the legacy behaviours we have, so 4.1.0 would be a new version where all this are properly clarified and the scope set).

The exact algorithms to require can be decided once we agree on an approach forward, but I'm thinking of a very minimal set:

• P256/SHA256
• P384/SHA384

Recommended algorithms

• RSA/PKCS1v15 2048, 3072 and 4096
• Ed25519 pure and ph

Other signature algorithms are optional to include, and relying on any of them means that interoperability is not guaranteed (this means that even using a recommended algorithm is not guaranteed to work across all clients).

It's 2025 and I think it's fair to not require support for RSA.

I will also bring this up on the next sigstore clients meeting.

cc @haydentherapper @loosebazooka @woodruffw @ret2libc @bobcallaway (for TSC awareness) @codysoyland

[haydentherapper]

This sounds good. To clarify, clients should fallback to the deprecated mapping (e.g. P384/SHA256) if signature verification fails with a "new" mapping (e.g P384/SHA384)?

As an alternative approach to falling back to a deprecated algorithm, I have a thought if we wanted to avoid falling back. PublicKeyIdentifier does not include PublicKeyDetails, and unfortunately the certificates we've issued include an OID for the "new" mapping. What do you think about adding an optional PublicKeyIdentifier to the bundle as part of VerificationMaterial? If it is missing, then the client should default to using the deprecated signature-digest algorithm mapping. Then we can decide if/when we release a new bundle revision how we handle this - we can drop the deprecated algorithms entirely, or allow a client to specify when a deprecated algorithm mapping is used, with the default being the "new" algorithm mappings.

As for what algorithms to support, I'd suggest P256/SHA256, P384/SHA384, P521/SHA512, and Ed25519-pure. Happy to make RSA optional. I could be convinced that Ed25519-ph should be optional since it's an edge case for handling Ed25519 signatures for hashedrekord.
The reason we should mandate Ed25519-pure support is that the witness network specification mandates Ed25519 checkpoint co-signatures, so clients will at the very least need to support Ed25519-pure to verify witness signatures in the near future. Supporting Ed25519 artifact signatures could be optional, since we add in the complexity of needing Ed25519-ph for hashedrekord.

[ret2libc]

What do you think about adding an optional PublicKeyIdentifier to the bundle as part of VerificationMaterial?

I thought we did not want to add this kind of information to the verification material. https://github.com/sigstore/sigstore-go/issues/74#issuecomment-2658788537

[kommendorkapten]

What do you think about adding an optional PublicKeyIdentifier to the bundle as part of VerificationMaterial?

I rather not, as there is a risk that this can be used for key confusion. I rather see the verifier provide a list of algorithms it supports. There is one problem though, how do we differentiate between P384/SHA384 and P384/SHA256? And that's where I think a flag --allow-deprecated can be provided, to let the verifier perform the fallback.

The provided algorithms looks good, I was thinking about require Ed25519 too, and it's fair to do it.

[ret2libc]

There is one problem though, how do we differentiate between P384/SHA384 and P384/SHA256? And that's where I think a flag --allow-deprecated can be provided, to let the verifier perform the fallback.

If we go with a user-provided flag, there's no need to enable/disable compat based on the protobuf/bundle versions, is there?

[kommendorkapten]

If we go with a user-provided flag, there's no need to enable/disable compat based on the protobuf/bundle versions, is there?

Yeah exactly. I'm thinking that for older versions they can silently fallback (fi this is our desired mode to not break existing clients). But from the newer versions of clients they would require this flag.

[ret2libc]

Yeah exactly. I'm thinking that for older versions they can silently fallback (fi this is our desired mode to not break existing clients). But from the newer versions of clients they would require this flag.

I'm not sure I follow. Thhe --allow-deprecated flag makes sense only for newer clients. Older versions of clients are not a problem at all, as those can already verify older signatures. So I would expect some grace period where --allow-deprecated (or --allow-compat-algorithms) is enabled by default to reduce as much as possible breaking changes to users.

[kommendorkapten]

So I would expect some grace period where --allow-deprecated (or --allow-compat-algorithms) is enabled by default to reduce as much as possible breaking changes to users.

Yeah, need to think about what's best here. It's tricky to not break older clients with updates.

But for the newer version of bundles (v4) we should forbid anything that's deprecated. But I think that has been mentioned before. So the deprecated algs should only be fore up to V3 bundles.

[woodruffw]

Thinking about this more, we might not need --allow-deprecated at all: "older" (i.e. v3 and lower) versions of the bundle format should transparently support these older suites, while "newer" (i.e. v4 and higher) versions should produce a hard failure on them.

I think this avoids the breakage concerns entirely, since older clients will reject newer bundle formats (or should...) anyways.

[kommendorkapten]

Yes, looking at only the bundle version is one option. What I was thinking of with the --allow-deprecated flag is to force newer clients to require this, to prevent downgrade attacks (of the bundle version).

I can't say that the threat is real, but if some manage to find a sha384 that matches a zero prefixed sha256 it could be a thing. Probably theoretical, but worth a discussion.

[haydentherapper]

Ack on not including the algorithm in the verification materials, I had forgotten about that discussion.

We could say that --allow-deprecated is a MAY for clients to implement, but I'd rather take a stronger stance of dropping support entirely. The downside, which William and I were chatting about, is now we cannot upgrade certain v3 bundles to v4+.

To clarify what we mean by "fallback", are we saying that current clients verifying v3 bundles should attempt to verify ECDSA signatures for P384 with both SHA256 and SHA384, and for P512, SHA256/SHA512? Just want to confirm.

[ret2libc]

To clarify what we mean by "fallback", are we saying that current clients verifying v3 bundles should attempt to verify ECDSA signatures for P384 with both SHA256 and SHA384, and for P512, SHA256/SHA512? Just want to confirm.

That's my understanding. And that's also what I implemented in https://github.com/sigstore/sigstore-go/pull/424 . Shall we maybe increase the version of the bundle created by new clients that use P384/SHA384 and P521/SHA512? In that way, there cannot be a v3 bundle that is signed with these newer algorithms and older clients that used to support v3 bundles will still be able to support all v3 bundles.

[haydentherapper]

Summarizing offline discussions: I do think we should create a new bundle revision soon, but we have a few more changes we'll need to include. Given that a lot of Sigstore BYOK usage is through Cosign, and Cosign isn't creating bundles by default, that gives us some more time to avoid proliferating too many v3 bundles with these new mappings.

I am OK with the approach of implementing a fallback so we can make progress on this now - there's going to work either way for clients.

[haydentherapper]

Looking over the sigstore-go implementation of the fallback, I'm now wondering if clients are going to have a harder time managing that than with validation of an algorithm in a new bundle revision.

I need client input at this point - which would be simpler, a fallback or supporting a new bundle revision?

[kommendorkapten]

Fallback for bundles up to and including v3, not supporting fallback for v4 and forward is what I would prefer.

[woodruffw]

Just giving an update: I'm looking into making the client spec changes now!

As part of that, I'm going to try and clean up some of the confusing disconnects between various parts of the client specification:

1. I'm going to move the Algorithm Registry (currently in this repo's docs/) into the architecture-docs repo, where it can live alongside the client spec;
2. I'm going to fix as many old/broken links to Google Docs as possible, replacing them with the living Markdown docs.

Edit: Opened https://github.com/sigstore/architecture-docs/pull/42 and #595.