Dual-sign checkpoint with PQC signing algorithm

[Hayden-IO]

Why?

Background into Sigstore and PQC: https://blog.sigstore.dev/post-quantum-2025/

tl;dr - Let's sign Rekor v2 checkpoints with Ed25519 and ML-DSA-65

The proposal outlined in this issue would enable a slow transition over to PQC, without requiring that all signatures produced throughout Sigstore are with PQC algorithms. Let's look at a possible post-quantum attack on code signing:

• A signing key is recovered for an artifact signature. That key could then be reused, but signatures generated with that key would have to be logged in Rekor, which would make the attack discoverable
• Alternatively, a signing key for an identity token is recovered, and an identity certificate is retrieved and used when signing an artifact. That would also have to be logged for discoverability
• Alternatively, Fulcio's signing key is recovered, an identity certificate is forged, and used to sign an artifact. Again, this must be logged for discoverability
• But what if Rekor's signing key is compromised? Now proofs can be forged - a checkpoint for a split-view could be forged. Witness cosignatures could be forged as well to co-sign the split view. Now, an attacker can hide their forged identity certificates.

A simple solution is to PQ-sign-all-the-things (insert meme). This comes at the cost of a significant increase in storage and egress, with PQ signatures for an artifact, Fulcio certificate, Rekor checkpoint, and timestamp, along with a few signatures for TUF. Instead, we should look for opportunities to reduce the number of signatures throughout Sigstore, but this is a harder problem and one which will take time. How can we mitigate the risk of PQ now?

This issue proposes signing the Rekor v2 checkpoint with both classical and post-quantum cryptography. The former means we won't break clients that don't support PQC. The latter provides a way to know if an artifact was signed at a time when there were no known attacks against classical crypto. The above attack isn't prevented, but it's mitigated by having a log commitment that can be trusted when artifact signatures can't be. Once we know of an attack, we can set a policy that past a given log index, only PQ signatures on artifacts will be trusted. Any signatures before that index can be trusted, as long as the Rekor checkpoint's PQ signature is verified.

Implementation and Rollout

Checkpoints can be signed by the origin log with multiple keys, and Tessera has built-in support for this.

We'll use ML-DSA-65. We've added ML-DSA-65 and ML-DSA-87 to the algorithm registry. ML-DSA-65 signatures are around ~3k bytes, compared to ~4k for ML-DSA-87 and ~8k+ for SLH-DSA. Note the impact to consumers will be larger offline proofs/bundles, since checkpoints will be larger due to the additional PQ signature.

We'd need a SignerVerifier implementation that signs with ML-DSA. We won't require every client to support ML-DSA verification - it's a nice to have, but not every ecosystem has well-vetted implementations of the algorithm. Whether or not PQ verification is required can be gated behind a client flag initially. For Go, we can either implement a SignerVerifier with a pure-Go ML-DSA implementation (like Cloudflare's CIRCL) or ship a plugin alongside the Rekor v2 binary for signing and Cosign for verification, as proposed in sigstore/sigstore#2129.

Note that we do not need to update the list of supported algorithms for public-good Rekor entries, as the public instance of the log won't support PQ-signed entries due to the large signature size. Only checkpoints will be signed with a PQC algorithm.

We should aim to test this before GA, since clients may not handle this correctly. We'll need two entries in the TrustedRoot for the same origin, and clients will need to verify a checkpoint with multiple origin signatures. If this can't be tested before GA, we'll just be slower in the rollout and enable this on a new shard rather than on an existing shard as we iron out client support.

[arthurus-rex]

I think this is a great proposal, couple thoughts. I'm equally concerned about ML-DSA's size, and am cognizant of a future where it may be found insecure or no longer preferred by future CNSA versions. How much of a burden would it be to introduce flexibility in which PQC algorithm we select for Rekor v2 checkpoints following this model you've detailed here? As in, the PGI checkpoints could stay on ML-DSA-65 for size constraints, but private deployments could use ML-DSA-87 or select from whichever PQC algorithms are legally recommended/required. This would help minimize computational load and risk, while still allowing the most stringent deployments to be compliant. What I'm most concerned about is getting blocked in the future because we've hard-coded an algorithm into Rekor v2.

[Hayden-IO]

How much of a burden would it be to introduce flexibility in which PQC algorithm we select for Rekor v2 checkpoints following this model you've detailed here?

This would be fully supported. If an algorithm needs to change, we'd just create a new log shard and update the TrustedRoot to specify the new public keys. More generically, the feature to implement would be configuring Rekor v2 to sign a checkpoint with multiple SignerVerifiers, where each could be for any signing algorithm, PQ or otherwise.