Allow configurable client signing algorithms

[tetsuo-cpp]

Description

I've filed similar issues under Cosign and Rekor. I realise there's a lot of overlap in maintainers, but wanted to make sure that we discuss each project that we plan to touch. Apologies if this feels a bit spammy.

Hi there! At Trail of Bits, we're looking at potentially implementing part of the Configurable Crypto Algorithms proposal (specifically Phase 1). I wanted to float this idea to each of the relevant Sigstore sub-projects so we can hash out the details in a more concrete way.

Across the Sigstore stack, we default to using ECDSA for signatures and SHA256 for hashing. There's more detail in the linked proposal but there are a number of motivations for wanting to customise the signatures that are generated, including paving the way for post-quantum signatures. The proposed design includes having a "supported algorithm" registry (perhaps this can go in the Protobuf specs) that outlines enumerates the approved signature/hash algorithm combinations. We specifically don't want to allow arbitrary mixing and matching of signature and hash algorithm to avoid some of the security pitfalls listed in the proposal.

I'm not super familiar with the Fulcio side of things but I expect that there's a few places where the assumption that the client signing algorithm is ECDSA-SHA256 is hardcoded, so we'll need to make those more flexible. We can also add a flag like --client-signing-algorithms=alg-1,alg-2 that can be used in case a given Fulcio instance wants to constrain the list of supported algorithms to be more restrictive than the aforementioned registry.

[haydentherapper]

There aren't many places where the signing algorithm is hardcoded. To give a quick overview, there's a few CA "backends" that implement signing logic given a key in some format - KMS, Tink, in-memory, etc. For each backend:

• KMS - This uses a cloud KMS to sign certificates. The signing algorithm and hash are provided from the sigstore/sigstore library. Once a KMS provider has added support for PQ signing algorithms, we'll just need to add that to s/s.
• Tink - In-memory signing where the signing key is encrypted with a KMS key. Tink will need to be updated to support PQ algorithms (which I assume is on their roadmap)
• File-based - Meant as a test CA since keys stored on disk (even password-protected) aren't ideal. This supports any signing key type supported in sigstore/sigstore.
• Ephemeral - This is a test CA which hardcodes ECDSA P-256 where the signing key lives in-memory. We can easily make this configurable.

tl;dr is that you'll need to make changes to sigstore/sigstore to support PQ signing keys. If Tink doesn't add support for PQ any time soon, another CA "backend" that loads a KMS-encrypted key into memory might be useful so we don't proliferate the use of the file-based CA (though KMS providers will need to add support for PQ encryption too).

We'll also need to specify the OID of the signature algorithm in the relevant extension, which currently is populated by the Go x509 library rather than self-specific.

You'll also need to update certificate-transparency-go to support PQ, since the SCTs are signed. I'm not sure how this library detects the signing algorithm.

This also assumes that the OIDC provider is going to be updated to sign tokens with a PQ algorithm, but I think it's fine to consider this out of scope (though the OIDC library will need to be updated).

[tetsuo-cpp]

Awesome, thanks for the details @haydentherapper.

Since we're supporting configurable client signing algorithms only as a first pass, I believe that we can kick the can down the road and address the majority of this work later. Most of those points look to be related to configuring the algorithm that Fulcio as a CA uses to sign the issued certificates rather than the type of key embedded in the issued certificates, about SCTs, etc.

To allow configurable algorithms for client signing, I believe we need to add a flag to restrict the allowed subset of algorithms. It looks like we're handling already handling most of the key types we want here but we'd need to add LMS.

[ret2libc]

I think there might be some problems because cosign still uses a “hand-made” proof of possession instead of using the CSR, so there is no place where the full client algorithm is specified in the message. Fulcio just assumes the hash algorithm is always SHA256, however with recent PRs we also accept SHA384 and SHA512.

That means however that if a client uses cosign with e.g. ecdsa-sha2-384-nistp384, Fulcio will refuse to provide a certificate because it does not understand it should use sha384 for verifying the proof of possession.

What do you think is the best way to handle this? We might just ignore this and accept that cosign will only work with sha256 and at some point it will move to the CSR message.

cc @woodruffw @haydentherapper

[ret2libc]

See https://github.com/sigstore/fulcio/pull/1517/files#diff-648d47fb9eeb444c1a09095dd41e4012ee5aafcb37b712f7f3bf492d8410017dR146 for how the in-progress PR tries to handle this, but this works only if you assume that a given type of public key only has one type of hash algorithm.

[ret2libc]

Also, shall we assume ed25519-ph in Fulcio? There is no way to distinguish between ed25519 and ed25519-ph. Are both used by (some) clients, in some cases? This may poses other problems to keep compatibility.

[haydentherapper]

What do you think is the best way to handle this? We might just ignore this and accept that cosign will only work with sha256 and at some point it will move to the CSR message.

This would be my proposal as well. It is straightforward to generate a CSR in Golang, so we can easily switch over now. We'll need to continue to support older Cosign versions or API callers, so assuming sha256 seems reasonable.

A few alternatives:

• Add an option to specify the hash and or signature algorithm in the PublicKeyRequest message. We'd still need to fallback to sha256 if no alg is specified. I'm not opposed to this approach, and maybe it's worth doing in addition to using the CSR for clients where CSR generation is not as straightforward.
• Change the challenge. I want to do this in the near future anyways, to make the challenge more ACME-like to avoid challenge reuse. We could add algorithm details as part of the challenge response. However this is a more significant change and I was planning to wait until we're ready for a breaking API change.

Also, shall we assume ed25519-ph in Fulcio? There is no way to distinguish between ed25519 and ed25519-ph. Are both used by (some) clients, in some cases? This may poses other problems to keep compatibility.

One thing to note is that the signature algorithm OID is derived from this call, during x509.CreateCertificate. Given our currently supported set of signing algorithms, besides ed25519ph, we should not need to pass SignatureAlgorithm in the template.

ed25519ph is not one of the supported algorithms. My understanding is because it was not specified in https://datatracker.ietf.org/doc/html/rfc8410 (it was in an earlier revision of the rfc).

This is going to get a bit messy - You could sign the challenge with pure ed25519, Fulcio verifies the challenge with ed25519, and certify the key as pure ed25519 [1]. The client will then know to sign the artifact with ed25519ph for hashedrekord or ed25519 for other types. In Rekor, when the verifier is loaded, again it knows which signature algorithm to expect for each Rekor type, so it doesn't matter what the signature algorithm is in the certificate. (italicized because this has yet to be fully verified, but I don't believe any client in sigstore looks at the signature algorithm).

[1] You could also sign the challenge with ed25519ph, and then Fulcio would verify the challenge either as ed25519ph or ed25519. But given it can only certify the key as ed25519, I'd rather just avoid Fulcio being aware of -ph entirely.

[ret2libc]

ed25519ph is not one of the supported algorithms. My understanding is because it was not specified in https://datatracker.ietf.org/doc/html/rfc8410 (it was in an earlier revision of the rfc).

Ok, this is going to be messy then :) Do you have any idea if there ed25519-ph is ever going to be part of the supported algorithms? Otherwise, what you said might work, but it relies on a lot of assumptions across the whole system.

[haydentherapper]

There was an OID (https://oid-rep.orange-labs.fr/get/1.3.101.114) allocated in an earlier revision of the RFC, but for whatever reason, it was removed. I assume this OID would be reused if it were to be standardized.

To provide a custom signature algorithm OID, I'm unfortunately not sure if you can. With extensions, you'd need to craft your own extension in ExtraExtensions which should override a default extension (for example, we do this to force the extended key usage to be critical when timestamping code). With this, it's not an extension but a certificate field, and it seems like it only accepts a set of enums code. We might need to file a request for custom signature algorithms on the Golang issue tracker.

[haydentherapper]

Also this is going to be an issue when we want to experiment with PQ-signed certificates (not sure what sig algs are being used currently).

I'd poke around cloudflare's codebase, since they've done a lot with PQ, they might have some code pointers for custom signature algorithms.

Edit: I also asked internally if there is support for custom sig alg identifiers.

[haydentherapper]

From asking around, some more info:

• Support for ed25519ph has stalled after it was not included in RFC8410. The reason, from the working group summary, is that they could not find a use case for needing the prehash variant, specifically dealing with large data. Large CRLs were brought up, but the preferred solution was segmenting CRLs, rather than supporting large CRLs.
• Golang would be unlikely to accept a PR to add support for nonstandard signature algorithms, as the focus in on webPKI
• We could patch crypto/x509, specifically x509.go, although I'm reluctant to maintain a fork of this. It would be quite simple to do so, modifying signingParamsForPublicKey and signatureAlgorithmDetails

[haydentherapper]

I would recommend proceeding with certifying ed25519ph keys as ed25519. Since we're adding the feature to Rekor to allow hashedrekord + ed25519ph, any client that has dealt with ed25519 keys would have to be for the byo-key use case. While this would require contextual verification, knowing that ed25519 + hashedrekord = ed25519ph, this should be possible to build into all clients.