TrustFabric and Post-Quantum

The quantum problem

Digital authentication is under threat from quantum computers.  While quantum computers cannot yet break current encryption or authentication, waiting until they can to secure systems against such attacks would be too late.  Google recently issued a call to action to secure the quantum era with post-quantum cryptography, setting a timeline of 2029.  Cloudflare and Let’s Encrypt have made similar commitments to this timeline, and cryptography experts are encouraging others to follow suit.

This shift is based on progress (1, 2) towards breaking elliptic curve cryptography.  Soon, cryptographically relevant quantum computers (CRQCs) may be able to break classical public-key cryptography by using Shor’s Algorithm to calculate private keys from published public keys. This will leave digital signatures forgeable and, therefore, effectively meaningless.

The good news is that post-quantum cryptographic algorithms have been developed, and standardised.  The primary standard for protecting digital signatures is ML-DSA - a set of lattice-based digital signature algorithms believed to be secure in the face of CRQCs.  Switching to ML-DSA is the recommended way forward, and organisations like Android are doing just that.

It’s worth noting that quantum computers don’t pose a threat to hashing algorithms.  Hash functions do not rely upon the same underlying mathematical principles as digital signature schemes, and while Grover’s algorithm provides a quadratic speed up in searches for hash collisions, a 256-bit hash would only be reduced to the equivalent of 128 bits of security - still an impractically large space to search for collisions.

What this means for transparency ecosystems

Digital signatures are relied upon extensively within transparency ecosystems.  The ability to forge digital signatures would undermine transparency as a whole, enabling targeted malicious behaviour to go undetected.

Transparency logs organize data into an append-only Merkle Tree, and, at regular intervals, sign the root of this tree to produce a signed checkpoint.  This signature is a public assertion by the log that the hash within represents the contents of the log at that moment.  Clients trust and use these signed checkpoints to cryptographically verify that their specific data is included in the tree, and that the tree is being used in an append-only manner.  If these signed checkpoints were forgeable, a bad actor could sabotage the log by signing a tree root that commits to a different set of entries, and cause inconsistency when checking the log’s append-only behaviour.  The log would be deemed to be misbehaving and become unusable, even though it did nothing wrong, as clients wouldn’t be able to distinguish the forged checkpoint from an authentic one.

To prevent different versions of a log’s tree being presented to different users (known as a split-view attack), independent witnesses audit the growth of logs.  When a witness verifies that a log's state has evolved in a strictly append-only way, it attests to this by cosigning the corresponding checkpoint with its own private key.  If these witness signatures become forgeable, witnesses become useless and split-view attacks may not be detected, as any bad actor can add any signature they need to any checkpoint they like.

What TrustFabric is doing about it

It is likely that CRQCs will be able to forge transparency log signatures and witness signatures that use elliptic curve cryptography algorithms.  Therefore, the TrustFabric team is actively implementing support for post-quantum cryptography to mitigate the future risk posed by CRQCs.  Specifically:

• We have worked with the community and fellow C2SP maintainers to update the C2SP specification for tlog signatures to support the use of ML-DSA as the signature algorithm in transparency logs.

• ML-DSA support has been implemented in Tessera, so that providing either an Ed25519 key, or an ML-DSA key will work.  Eventually, the use of non-ML-DSA signatures will be deprecated.

• We have added the ability for witnesses to use ML-DSA keys to cosign checkpoints, and the TrustFabric staging witnesses are now returning ML-DSA-44 cosignatures.

This work has already been completed, allowing log and witness operators that use our code base to migrate their systems to use post-quantum signatures as soon as they choose to, and some Tessera-based logs now provide ML-DSA-signed checkpoints with ML-DSA cosignatures from our staging witnesses.

A new problem

While switching from elliptic curve cryptography to post-quantum cryptography primitives like ML-DSA may seem like a quick fix to secure the post-quantum era, it presents its own problems for Certificate Transparency (CT) and the web PKI.  Specifically, ML-DSA keys and signatures are significantly larger than in previous schemes.  Public keys go from being as few as 32 bytes using ECDSA P-256 to at least 1,312 bytes with ML-DSA-44 - the smallest of the ML-DSA schemes.  Signatures similarly go from 64 bytes to at least 2,420 bytes.  For a leaf certificate that must contain at least two SCTs alongside its own signature and the public key of the site it is for, this size increase is compounded to the point where certificates become unwieldy, using significantly more bandwidth to transmit, slowing down the whole web PKI, and drastically increasing the storage requirements for CT logs.

Solution: Merkle Tree Certificates (MTCs)

The current working solution to this problem is Merkle Tree Certificates (MTCs).  The MTC idea redesigns the web PKI to require fewer of these large signatures to be transmitted and stored.

Instead of issuing a signed certificate for every request that comes in from an authenticating party (like a domain owner), a certificate authority (CA) stores these requests in a merkle tree, and regularly signs the tree root to state that the CA has issued every entry in the tree that that root hash represents.  That checkpoint is then sent to cosigners, who verify the append-only behaviour of the CA log, and cosign the checkpoint to attest that the CA log is consistent.  Instead of a traditional certificate for their individual domain, the authenticating party receives a certificate from the CA consisting of:

• the original TBSCertificate request

• an inclusion proof from their specific request to the checkpoint

• signatures from the CA and cosigners for the checkpoint

This results in each CA signature covering a batch of certificates instead of the 1:1 relationship that exists in the current system.

From the user agent point of view, they stay up to date on key checkpoints from the CAs.  When an authenticating party wishes to connect, all they have to send is their TBSCertificate and an inclusion proof to a key checkpoint, requiring only hashes to be sent to set up a connection, and no large ML-DSA keys or signatures.

A benefit of the MTC system is that transparency isn’t bolted on as an afterthought.  It is inherently built in by the nature of CA certificate issuance being the action of logging the TBSCertificate to a merkle tree log.  In this new web PKI, monitors would monitor the CA logs directly for domains of interest, similarly to how they monitor CT logs in the existing system.

How TrustFabric is supporting MTCs

MTCs will be a large shift for the whole of the web PKI.  TrustFabric is supporting this effort by:

• Providing infrastructure for MTC CA logs.  We are adding support for building MTC CA logs to Tessera.

• Providing the infrastructure to run MTC mirrors.  An optional function of MTC cosigners is that they can also mirror the CA log contents to give monitors an additional source of CA log information.  TrustFabric is building a cosigner implementation that also provides this mirroring option.  We currently have an early version of a POSIX-backed MTC mirror, which we invite you to experiment with and provide feedback on to help shape its further development.

• Working with the wider community to provide early implementor feedback on the MTC system design.

To get the Web PKI shifted over to MTCs by the 2029 deadline will be a big task.  In order to best support this accelerated timeline, we intend to have the POSIX-backed implementations of the CA log and mirror ready by late 2026, with other backends following shortly after that, as determined by demand.

In Summary

The post-quantum era is coming fast, and the TrustFabric team is committed to adapting the infrastructure we provide in order to best support transparency ecosystems that rely upon it, and working with the wider transparency and web PKI communities to ensure everyone is ready for what comes next.

If you have any questions or comments, please reach out on the transparency.dev slack.