Presenters

Source

Quantum-Proofing Sigstore: Three Bold Approaches to Secure Our Software Supply Chain 🚀

The digital world runs on trust, and in the realm of software, that trust increasingly relies on robust supply chain security. Sigstore stands as a critical pillar, ensuring the integrity and authenticity of software artifacts. But what happens when the very foundations of our cryptographic security are threatened? Enter quantum computing – a game-changer that could render today’s most secure algorithms obsolete.

Kevin Conner and Firas Ghanmi from Red Hat’s Trusted Artifact Signer team, who are contributing to Sigstore, recently unveiled their groundbreaking work on integrating Post-Quantum Cryptography (PQC) into Sigstore. Their mission: to gather vital experience and data, exploring how we can future-proof our software supply chain against the looming quantum threat. This isn’t just theory; it’s a deep dive into practical solutions, complete with demos and crucial lessons learned.

The Quantum Threat: Why We Need PQC Now 💡

Imagine a world where a malicious actor, armed with a powerful quantum computer, could effortlessly derive your private signing key from its public counterpart. They could then impersonate you, signing fraudulent software artifacts on your behalf, sowing chaos and undermining trust. This isn’t science fiction; it’s the potential reality if quantum computers become powerful enough to run Shor’s algorithm.

Currently, breaking RSA 2048 with Shor’s algorithm would require a quantum computer with millions of qubits. While that sounds distant, the timeline is uncertain. Recent (though unverified) claims suggest algorithms might achieve this with as few as 5,000 qubits. We might believe we have a “couple of years,” but that window could close tomorrow.

Beyond the immediate threat, PQC introduces a significant practical challenge: size. Traditional signatures and keys are typically measured in bytes. PQC, however, pushes these into the kilobyte range, with signatures alone potentially reaching 3.5 to 4.5 kilobytes. This massive increase impacts storage, network traffic, and database assumptions across the board.

The team focused on two key areas for quantum protection:

1. Log Protection: Ensuring the transparency log itself remains tamper-proof, even against quantum adversaries.
2. Certificate Protection: Allowing for the creation of secure, offline-verifiable bundles.

Three Paths to a Quantum-Resistant Sigstore 🛣️

Kevin and Firas explored three distinct approaches to integrate PQC into Sigstore, each with its own benefits and tradeoffs.

1. Hybrid Transparency Log: Fortifying the Audit Trail 🛡️

This approach represents the most conservative path, designed to minimize disruption to the existing ecosystem.

• How it Works: The core idea is to add PQC solely to the transparency log layer. Rekor, Sigstore’s transparency log, dual-signs every single log entry and checkpoint. It uses both a classical algorithm (like ECDSA) and a post-quantum algorithm (like ML-DSA).
• The Benefit: This creates a quantum-resistant audit trail. Even if a quantum attacker breaks the classical ECDSA signature, they cannot alter the log without detection by a PQC-aware client.
• The Catch (Limitations):
  • Security Boundary: This method only protects the log, not the artifact signature or certificates. The Fulcio Certificate Authority (CA) key remains classical, leaving certificate forgery a possibility in a post-quantum scenario.
  • Size Overhead: A classical Sigstore bundle is typically around 6.5 kilobytes. With hybrid Rekor, this bundle almost doubles to roughly 12-13 kilobytes. The extra size primarily comes from the additional SETs (Signed Entry Timestamps) and checkpoint signatures, each contributing around 3.3 kilobytes.
  • Adoption: Legacy clients can safely ignore the PQC SETs, but they won’t gain any PQC benefits. Full post-quantum protection requires verifier upgrades.
• Tools in Action: Cosign, Rekor, ECDSA, ML-DSA.

2. Hybrid X.509 Certificates: Self-Contained Quantum Safety 📜

Shifting focus from the log to the certificate layer, this approach embeds PQC directly into X.509 certificates.

• How it Works: The team uses three hybrid extensions within a standard X.509 certificate. These extensions contain an alternative post-quantum public key and a PQC signature (ML-DSA) alongside the classical ones.
• The Benefit:
  • The certificate carries a PQC signature from the CA, making it inherently more secure.
  • It’s self-contained, meaning no network access is needed for PQC verification.
  • It’s backward compatible: Legacy clients simply ignore the unknown PQC extensions.
  • When combined with the Transparency Log Hybrid, this provides a full PQC stack from the CA through the log to the verifier.
• Critical Signing Order: The post-quantum signature must be computed first. The classical signature then covers the entire certificate, including the newly added PQC signature, ensuring both strong PQC protection and backward compatibility.
• The Catch (Limitations):
  • Per-Certificate PQC Overhead: This is the primary concern. There’s no economy of scale. A hybrid certificate is approximately eight times larger than a classical certificate, growing to about 8 kilobytes. This impacts every signing event and bundle, posing a “real concern” for large ecosystems like npm or pip.
• Tools in Action: X.509, OpenSSL, Go crypto.

3. Merkle Tree Certificates (MTC): Batching for Efficiency (and Complexity) 🌳

This innovative approach aims to reduce the amount of information logged into Rekor by introducing an additional layer of Merkle trees.

• How it Works: Instead of a single Merkle tree in the transparency log, MTC uses two.
  1. Fulcio Batches: Fulcio, Sigstore’s certificate authority, batches multiple client requests. Once a certain number of requests or a timeout is reached, Fulcio creates its own Merkle tree.
  2. Fulcio Signs & Logs: Fulcio then signs the root of this batch Merkle tree with its certificates and passes this information to Rekor.
  3. Rekor Logs: Rekor then incorporates this into its own Merkle tree (the transparency log).
• The Benefit: This approach benefits from the dual-signing changes made to the transparency log, providing comprehensive PQC coverage from the certificate all the way through to the transparency log.
• The Catch (Limitations):
  • Breaking Change: This is a completely new approach with no backward compatibility. All verifiers would require updates.
  • Latency: Throughput directly impacts latency. High throughput means low latency, but low or variable throughput requires careful tuning of batch size or timeout periods.
  • Extensive Modifications: This necessitates modifications across many parts of Sigstore, including Fulcio and clients. Rekor monitoring aspects still require changes.
• Bundle Size: While designed for batching, a single certificate within an MTC bundle is roughly 2.5 kilobytes.
• Tools in Action: Fulcio, Rekor, Merkel trees.

A Side-by-Side Look: Comparing the Approaches 📊

Feature	Transparency Log Hybrid	Hybrid X.509 Certificate	Merkle Tree Certificates (MTC)
PQC Coverage	Log only	Certificate only	Certificate & Log (via batch)
Backward Compatibility	Yes (legacy clients ignore)	Yes (legacy clients ignore)	No (breaking change)
Log Entry Size	~7 KB	~0.7 KB	~2.5 KB (per cert in batch)
Certificate Size	~1 KB (classical)	~8 KB (8x larger)	~1 KB (classical)
Bundle Size	~13 KB	~14.5 KB	~2.5 KB (per cert)
Disruption Level	Low	Moderate	High

The team notes that the transparency log changes can be combined with either Hybrid X.509 or MTC to achieve broader post-quantum coverage. The only part not yet addressed is the initial generation of the public key used to sign the artifact itself.

Key Learnings from the Quantum Frontier 🧠

Developing these PQC solutions provided invaluable insights:

• cryptox509 Reliance: The Sigstore codebase heavily relies on cryptox509 directly, often hardcoding algorithms. This makes it challenging to introduce new cryptographic functions.
• Centralization is Key: By extending core packages like signature and crypto utils to handle key marshaling, ML-DSA support, and certificate parsing, the team achieved agility. Switching the codebase to use these centralized packages allowed for seamless adoption of new algorithms.
• Size Assumptions Break Systems: Many underlying systems—databases, Protobuff messages, HTTP requests—operate on assumptions about cryptographic object sizes, expecting them to be in bytes. The shift to kilobytes for PQC signatures causes “little cracks” in these assumptions, leading to unexpected issues.

The Road Ahead: Your Role in Quantum-Proofing Sigstore 🌐

This groundbreaking work is just the beginning. The next crucial step involves the wider community. A proposal has already been submitted to the Sigstore Technical Steering Committee (TSC), and discussions are expected to commence in earnest soon.

Kevin and Firas strongly encourage anyone interested in post-quantum cryptography and Sigstore to:

• Join the Sigstore Slack: Engage with the community.
• Explore the Code: Dive into the open-source implementations.
• Get Involved in Discussions: Contribute your expertise and perspectives.

Your participation is vital as the community makes critical decisions on how to integrate PQC effectively and securely into Sigstore.

Diving Deeper: Your Questions Answered 💬

During the presentation, the audience had some insightful questions:

• Q: Did you batch classical signatures for the MTC approach?
  • A: No, the team focused on dual-signing with PQC. However, the implementation is agnostic, meaning it could support classical batching if configured. The reported numbers for MTC compare classical without batching to PQC with batching.
• Q: Should PQC-supporting clients also verify non-PQC signatures? What if one fails?
  • A: Kevin implemented the “most strict route”: any signature the client understands and supports must pass. While acknowledging the debate and lack of a single “right answer,” this approach simplifies the coding by treating all supported algorithms equally.
• Q: How can people get involved in these discussions?
  • A: The best way is to join the Sigstore Slack channel and attend the regular Sigstore meetings, particularly the Golang and client meetings where these topics will be discussed.

This experimentation provides crucial data, laying the groundwork for meaningful community discussions and decisions. The journey to a quantum-resistant software supply chain has begun, and your involvement can help shape its future!

Appendix