Merkle Tree Certificates: The Third Iteration of Web PKI

Over the last three months, I've been exploring post-quantum cryptography, its impact on the internet, and how it's reshaping the state of cryptography and network security. In this blog post, my 7th and last in the series, I'll look at how Web authentication is being reengineered through Merkle Tree Certificates (MTCs).

In the beginning, there was just Internet PKI that covered all public authentication among client and server software of all sorts. In case you're not familiar, PKI stands for Public Key Infrastructure. Despite the word "public" in the name, PKIs don't have to be public or for everyone, but Internet PKI is.

The story of how Internet PKI came to be is fascinating, but essentially boils down to one early Netscape engineer, Kipp Hickman, taking three months to figure it all out. By the way, that time included work to create the first version of Secure Sockets Layer (SSL) and Internet PKI (building on X.509, which had been a thing). Reportedly, the latter part (authentication) was largely an afterthought. With Kipp's work, Netscape ushered in the era of secure communication, and the world followed.

This first system worked for about a decade, but eventually the cracks were too big to ignore. CA/Browser Forum, an industry group of CAs and browsers, formed in 2005 and, in 2007, issued its first document to begin formalizing certificate issuance. That work has been ongoing since.

In parallel, browser vendors, largely with Google in the lead, began to exert increasing control over what is considered secure. Browsers began consuming certificates in a slightly different way, which led to the creation of Web PKI. Initially, the differences were small. A new technology called Certificate Transparency (CT) became mandatory in 2018 and fundamentally changed Web PKI. This addition marked the second iteration of Web PKI, which we enjoy today. The recent removal of client authentication was the final change that solidified the differences.

I will elaborate on the details in a second, but the decision to reengineer Web PKI boils down to the following three key problems:

1. The existing CT ecosystem is fragile as it is
2. The planned certificate lifetime reduction is very likely to break it
3. The larger post-quantum signatures are going to bury it in the ground

In a nutshell, the post-quantum migration is the trigger that will help us justify the work to make everything run much more smoothly. There's going to be a lot of new work, but we're not throwing away everything we've learned so far.

The role of Certificate Transparency (CT) is to ensure full visibility into worldwide certificate issuance. This is achieved by logging certificates to CT logs, which are protected using cryptography. As a result, CT logs have become a critical part of Web authentication.

Because all major browsers and many operating systems now require CT, certificates cannot be issued unless they are logged, which means that we have to have highly-available CT logs that support the world's peak issuance peaks, and then some. Although we haven't had major downtime so far, if you're on the right mailing lists, you will know that there have been challenges. People are nervous about this.

The decisions already made will make the situation worse. By 2029, we will reduce the maximum allowed certificate lifetime to only 47 days, down from 1 year, which was fairly recent. This means we will switch from yearly to monthly issuance, a 12x increase.

It's also possible that further lifetime reductions will be introduced. Apple's early post-quantum authentication policy, for example, allows only 7 days. It's not clear whether that's only required during the trial or if the intention is to launch it. If it stays, that's another 4x increase on top of the previous shortest monthly issuance. Altogether, about 50x the current load on the CT ecosystem in terms of the number of issuances.

The increased number of certificates is only one part of it. If you recall from my earlier post, post-quantum signatures and public algorithms are much larger, which alone could lead to a 10-20x increase in certificate (and CT log) size. Multiply the two, and you'll understand why people are nervous.

The third iteration, in the form of Merkle Tree Certificates (MTCs), is designed as a fix.

The most important difference with MTCs is that they marry X.509 and CT. In the current arrangement, CT is an add-on. Logging certificates to CT is a separate step. Organisations issuing certificates are different from the organisations logging them to CT. This represents a structural weakness and leads to an incentive misalignment.

With MTC, each CA runs one instance of a (next-generation) CT log and writes certificates to it. The sentence you will hear often is that they will "issue by logging". Where there were two steps before, there is now only one. Because of this change, every CA now has to also participate in the CT ecosystem; there is no other way.

Because MTCs are issued by logging, precertificates, which are currently required in CT, are no longer needed. Going forward, only one object will be logged. This change reduces operational complexity and may reduce the size of CT logs by up to half. (The biggest current CAs submit both precertificates and certificates to CT.)

An important aspect of CT is that certificate issuance is witnessed and mirrored by third parties. We don't trust any one organisation to do the right thing. In CT v1, certificates are recorded individually. A CT log contains a variety of certificates issued by different CAs. In addition, anyone can submit a certificate to be recorded to the log.

With MTC, witnessing and mirroring occur at the log level. CAs issue certificates by logging them to their own logs. They're signed, then witnessed and mirrored in batches. A mirror log is identical to the original log. This has some great benefits:

• Batched operations are more streamlined and efficient.
• Third parties can no longer submit arbitrary certificates, which reduces duplication of work (certificates that were needlessly recorded) and avoids overloading CT logs.
• Monitors don't have to monitor all CT logs worldwide to get all certificates; they only need to monitor one instance, or even load-balance across multiple instances of the same log.

Because all MTC issuers are also MTC log operators, they're likely to pair up with other CAs with similar issuance volumes to mirror one another's certificates.

In the early days of CT, logs had only one instance each, and that worked fine for a while. The first logs were yearly because once all certificates in a log had expired, you no longer needed to keep them. However, the yearly logs eventually became too large, so smaller shards (e.g., 6-month intervals) were added.

The creation and management of the CT log shards create a significant continuous operational load. Operators have to spend a lot of time creating and managing the shards, then destroying them. Then new shards must be monitored and validated in collaboration with the primary consumers (browser vendors). Then, their information has to be propagated to the actual end users.

MTCs add support for log pruning. Because of how the logs are constructed internally (and how cryptographic validation is designed), it's possible to remove expired parts altogether. This will be a very welcome change for the people who have to ensure that the ecosystem is running and running well.

In the current CT design, each entry contains the associated public key and CA signature. These are currently small, but their sizes will explode with PQC. With MTCs, public keys are omitted and replaced with a combination of an algorithm identifier and a hash. CA signatures are also excluded (because MTC logs are signed in batches).

This change significantly reduces the size of the CT logs, especially given that there will be no precertificates going forward and that logging of arbitrary certificates won't be possible.

We've seen by now that MTCs will make it much easier to support the transparency aspects of web authentication. Most writeups, however, focus on the reduced size of TLS handshakes. To understand this problem, I suggest you read my earlier post on post-quantum signature sizes and their impact on networking performance. You may also enjoy this follow-up post that focuses on the evidence for the performance claims.

Merkle Tree Certificates come in two forms. One is called standalone, which is roughly equivalent in form to the certificates as we know them today (X.509 + CT).

In standalone certificates, signatures are replaced by an inclusion proof, a hash-based structure that serves a similar purpose. Crucially, although inclusion proofs are larger than the RSA and EC signatures we have today (at about 384 bytes), they're much smaller than post-quantum signatures. As a result, standalone MTCs are much smaller individually.

There's another change. MTCs are issued directly by trusted CAs, so we no longer need intermediate certificates in the TLS handshake, further reducing the size.

Standalone certificates are conceptually uncomplicated, but they don't do enough to bring down the size of PQC TLS handshakes to where they are today. If we want to do better, we need to do more and substantially increase complexity. This comes via the second form MTCs can take, called landmark-relative certificates.

Standalone certificates are smaller, but they still need to carry signatures, which are very large in the post-quantum world. Landmark-relative certificates (LRCs) are much smaller because their only authentication mechanism is an inclusion proof; they contain no signatures. The inclusion proof in LRCs is not the same as in the standalone certificates, so it's slightly larger, but not a huge amount (about 736 bytes, roughly 2x).

There is a catch. For LRCs to work, they need inclusion proofs issued against landmarks, which are groups (subtrees) of issued certificates. For user agents to authenticate these inclusion proofs, they must have prior information about the corresponding landmarks, which means they must continuously fetch something from somewhere for every CA they trust. Ouch.

If you're an end user, you're not going to care about any of this. There is a lot of additional complexity involved in supporting LRCs, but this is something that will be handled and "paid for" by the user agent developers and server operators. For the latter group, the hope is that most of it will be handled by the automation software, via ACME.

Landmark-relative certificates are an optimisation. When things work out, TLS handshakes will be short and fast. Otherwise, user agents will fall back to standalone certificates, which will be slower, but there won't be any breakage.

On the positive side, according to Cloudflare, LRCs provide 9% better performance than the classical certificate chains we have today. The performance over standalone certificates would be much better, and significantly better over some theoretical X.509 + ML-DSA certificate chains we don't want to use on the public internet.

That said, on private networks, which are controlled environments and often have much faster networking, the performance differences may not be as pronounced. Straightforward evolution of X.509 to add ML-DSA may work out just fine.

After all this, let's try to figure out how many certificates we might need to operate at peak performance. Today, the most robust configuration is to have two certificates: a faster EC one and the widely supported RSA.

To neutralise the threat of cryptographically-relevant quantum computers, we'll need to switch to post-quantum authentication via MTCs. At a minimum, this means supporting standalone certificates. So we'll need at least three, to support both modern user agents and those that are lagging.

Unfortunately, with only a standalone certificate, our TLS handshake performance will be slower than it is today. Maybe that's fine, but if we want to fix it, we also need to support landmark-relative certificates. But we're going to need two of those, not just one.

Thus, we'll need at least five certificates per service.

There are a couple of reasons why we have standalone and landmark-relative certificates in the first place. Standalones can be created immediately on issuance. On the other hand, LRCs are batched, so you can't access them immediately. Instead, you'll have to wait a period of time (e.g., 1 hour) before you can obtain one that matches your standalone certificate.

That's not all. If you recall, for an LRC to be authenticated, user agents must first fetch information from the CA. (Indirectly, via a user agent update service.) User agents won't monitor for new landmarks continuously; they'll fetch only periodically. Further, they may be offline for a period of time. As a result, user agents typically won't have the latest landmarks.

To sum up: 1) you need a standalone certificate for everyone, 2) one older landmark-relative certificate for most user agents, and 3) one newer landmark certificate that will eventually transition to your main one as user agents catch up.

Just try to imagine doing these things manually. No wonder we need ACME… automation is the only way to make this work. And even then, troubleshooting authentication and performance problems will get more difficult. Continuous monitoring to catch problems early will be necessary for a much wider range of organisations.