The Long Road to Fixing TLS Certificate Revocation
For most of the web's history, revoking a compromised TLS certificate was theoretically possible but practically useless. This is the story of how every attempted fix failed - and how a clever combination of data structures and Certificate Transparency finally made revocation work.
It has been over two decades of the smartest people on the internet trying to fix one of the web’s most stubborn unresolved problems. And failing. Repeatedly. On paper, the concept of certificate revocation is simple: if a certificate’s private key is compromised, you revoke it, and the browsers stop trusting it. In practice, however, every solution the industry tried was flawed in one way or another. As a result certificate revocation never really worked in practice. Today however, we seem to have a solution that is not only working well, but is also elegant enough that it caught my eye. So, here is my, somewhat lengthy, blog post on this topic.
What is certificate revocation anyway?
When you visit a website over HTTPS, your browser verifies that the server’s TLS certificate is valid and was issued by a trusted Certificate Authority (CA). This certificate binds together a public key with a domain name. The other, arguably even more important part, the private key, is stored (hopefully securely) by the certificate owner. But what happens when the owner didn’t store the private key as securely as we would have hoped and the certificate’s private key gets stolen before the expiration date?
Here is a scenario: an attacker breaches a web server and exfiltrates the certificate’s private key for doitall.example.ai. Without the certificate revocation process, the attacker can set up a malicious server with the legitimate certificate, intercept traffic (DNS hijacking, BGP poisoning, or MITM attack), and present a valid certificate to unsuspecting visitors. The browser would be ok with it, after all the website has a valid certificate. The certificate potentially would not expire for months which gives the attacker plenty of time to revel in his evil deeds. And the worst part is - victims would have no indication that anything was wrong.
Certificate revocation exists for this exact reason. It is the mechanism by which a CA or a domain owner can declare that a certificate should no longer be trusted, even though it hasn’t expired yet. Revocation is supposed to be the safety net for the entire TLS ecosystem. The problem is that, for most of the web’s history, that safety net had holes in it so large you could drive an entire stolen certificate through it.
Troubled history of certificate revocation
CRL: download the list of everything that’s revoked
The original revocation mechanism was baked into X.509 from the beginning - Certificate Revocation List (CRL). The idea was simple really: each CA publishes a signed list of all its revoked certificates, and clients will download these lists periodically to check the incoming server certificates against those lists.
This was surprisingly working reasonably well, when the encrypted web was still unreasonably small. But as the adoption of HTTPS exploded, especially after the Snowden leaks, so did the size of CRLs. A single CA might have millions of certificates, and a meaningful percentage get revoked over their lifetime. The resulting lists grew to unmanageable sizes - hundreds of megabytes across all CAs. A browser was required to download CRLs from dozens of different CAs just to browse the web for a single day. With increasing prevalence of slow, metered mobile connectivity, this was very impractical.
OCSP: ask the CA in real time
The next attempt to solving this problem once and for all was the Online Certificate Status Protocol (OCSP, RFC 6960, originally RFC 2560). Instead of downloading entire lists, the browser would simply ask the CA’s OCSP responder about a specific certificate’s status. The responder would then reply with a signed “good”, “revoked”, or “unknown” status.
This approach successfully solved the size scalability problem once and for all. And created three new ones.
First, latency: every new TLS connection now requires an additional network round trip to the CA’s OCSP responder before the web page could load. Mozilla’s own data showed the delay to be roughly 130 milliseconds on average. That is not nothing and with the amount of new TLS connections required to visit a single modern website that is a significant performance penalty - and that’s if the responder was working correctly.
Second, reliability: The CA’s OCSP responders became a critical dependency for every website using its certificates. If the responder went down, browsers faced an unwanted choice. Not knowing whether they can trust the certificate they could enforce a “hard-fail” policy - refuse the connection - which would mean that a single CA’s infrastructure outage could effectively take down vast swaths of the web. Or they could “soft-fail” - accept the connection anyway - which is what virtually every browser decided to do. But “soft-fail” is security theater: an attacker who can intercept your HTTPS connection can also block the OCSP query, causing the browser to shrug it away and continue with the connection. As Adam Langley, then a security engineer at Google, put it, soft-fail revocation checks are like a seatbelt that snaps when you crash - it works 99% of the time, but only when you don’t need it.
Third, privacy: every OCSP query tells the CA what website you’re visiting (along with your IP address). The CA can learn your browsing patterns in real time. Even if the CA promises not to log this data - even though this is exactly the sort of data advertisers would line their pockets with gold for - it could be compelled to do so by a court order. This privacy concern became one of the primary reasons Let’s Encrypt eventually killed OCSP entirely.
OCSP stapling: let the server do the asking
OCSP stapling (the status_request TLS extension, defined in RFC 6066) was an attempt to fix both the latency and privacy problems. Instead of letting the browser do the querying, the web server would periodically fetch its own OCSP response and “staple” it to the TLS handshake. The browser gets the revocation status without any additional queries and without revealing any information to the CA.
This was a real improvement - when it worked. In practice, much of the web infrastructure suffered from misconfiguration issues, or the servers didn’t support stapling at all. Moreover, stapling didn’t solve the fundamental hard-fail vs. soft-fail dilemma: if the server didn’t staple a response (or if an attacker stripped it), the browser was once again left stuck with the same old dilemma. If that wasn’t enough, there was also a replay vulnerability: an attacker could capture a “good” response before a certificate was revoked and keep presenting it during the validity window of that response - an attacker does have control over the web server after all.
Must-Staple: forcing the issue
RFC 7633 introduced the TLS Feature extension, commonly known as “Must-Staple.” A CA could include a flag in the certificate itself declaring that the server must provide a stapled OCSP response. If the server didn’t, the browser should reject the connection - a hard-fail by design.
Must-Staple, while the most secure option on paper, had a fatal flaw not dissimilar from the previous hard-fail solutions that preceded it. If a server’s OCSP stapling broke for whatever reason, the website would go completely dark with no option for graceful fallback. Unsurprisingly the adoption was minimal.
In 2025 Must-Staple received a final blow when Let’s Encrypt announced it would stop supporting OCSP and as a result Must-Staple requests would fail for all of its certificates. It is worth noting, of course, that Let’s Encrypt is actually the largest CA on the web. The result was unsurprising - Must-Staple became effectively dead as a general-purpose solution.
Push lists: CRLSets and OneCRL
Faced with the dumpster fire that online revocation checking became, browser vendors were forced to solve the most burning problems on their own with curated push lists - small, manually managed sets of revoked certificates distributed through the browser’s update mechanism.
These push lists were invaluable for emergency response - when a CA was compromised, or a critical intermediate needed to be revoked immediately, browser vendors could act within hours, pushing the necessary additions to the curated CRL. But this was never meant to be a complete solution.
For example, a 2015 measurement study found that CRLSets covered revocations from only a small fraction of CAs. In fact, the study found that CRLSets covered only 3.9% of CA certificates. Looking at the problem from a different angle, from all revoked certificates across existing CRLs (full lists published by CAs), only 0.35% ever appeared in the CRLSets. They were a band-aid for a very specific issue, not a general solution to the problem of certificate revocation.
Enter cascading bloom filters: the solution
In 2017, a team of researchers - James Larisch, David Choffnes, Dave Levin, Bruce Maggs, Alan Mislove, and Christo Wilson - presented a paper at the IEEE Symposium on Security and Privacy that proposed an elegant solution. Instead of asking the browser to make online queries or download enormous CRLs from a large number of CAs, they developed a way to compress the entire set of all revoked certificates into a space-efficient data structure small enough for a browser to download periodically, store locally and query instantly.
The system was called CRLite, and its core insight was surprisingly elegant. The reason it was even possible was another innovation that had matured a couple of years earlier: Certificate Transparency (CT). CT logs provide a public record of essentially every certificate issued by a publicly trusted CA. This meant that, for the first time, it was actually feasible to know the complete universe of valid certificates - you could enumerate not just the revoked ones, but all of them. And knowing the full universe is what makes the cascading bloom filter trick work so well.
A standard Bloom filter is a space-efficient probabilistic data structure that can answer the question “is this element in the set?” very effectively, using far less space than storing the set itself. The tradeoff is false positives: a Bloom filter might sometimes say “yes” for an element that isn’t actually in the set. It will never say “no” for an element that is in the set (no false negatives). This however, poses a problem for certificate revocation - it would cause valid certificates to be wrongly rejected, breaking websites for no reason whatsoever.
CRLite is brilliant in that it eliminates false positives through a cascade (multi-layer) structure, and this is where knowing the full universe through Certificate Transparency becomes critical.
Cascading bloom filters: how it works
The CRLite system operates as a pipeline with a server-side aggregator and client-side filters.
Server side - building the filter
An aggregator continuously monitors Certificate Transparency logs to build a complete picture of all known, unexpired certificates. It also downloads and verifies CRLs from all participating CAs to determine which of those certificates have been revoked. At regular intervals, it constructs a new filter.
Layer 1 (the “revoked” filter): All revoked certificate identifiers are inserted into a Bloom filter. When you query this filter for a certificate revocation, a “no” answer is definitive (no false negatives) - the certificate is definitely not revoked. But a “yes” answer might be a false positive - you could get a “yes” answer for a certificate that is, in fact, valid.
Identifying false positives: Because we have a complete list of all known, unexpired certificates from CT, we can test every single valid (not expired) certificate against Layer 1. Any certificate that the filter at Layer 1 incorrectly identifies as revoked is a false positive. We collect all of those.
Layer 2 - the “not actually revoked” filter: We insert all the false positives identified in the previous step into a second Bloom filter. This layer acts as a correction mechanism: if a certificate is flagged by Layer 1, we check Layer 2. If Layer 2’s answer is “no, this was not a false positive”, the certificate is definitely revoked. But a “yes” answer might, again, be a false positive.
However Layer 2 can also have false positives: Because Layer 2 might also give us false positives, some genuinely revoked certificates might pass through Layer 2. So we repeat the process: find false positives from Layer 2, insert them into Layer 3, and so on.
The cascade continues until there are no more false positives. Each successive layer is smaller than the previous one, so the total size converges quickly.
The resulting data structure gives perfectly accurate answers every time - zero false positives and zero false negatives - for every known certificate. The original 2017 paper demonstrated that the entire set of all valid certificates and revocations collected between November 17, 2016 and January 30, 2017 can fit into an initial download of 10 MB, with daily delta updates averaging at 580 kB.
Client side - using the filter
As with the original CRLs, a browser periodically downloads the data structure and its delta updates. But now, the daily delta is tiny in comparison, ultimately leading to more up-to-date revocation information.
When a browser encounters a certificate during a TLS handshake, it checks locally whether the certificate appears in the filter. No additional network requests, no privacy leaks. Moreover, given the perfectly accurate answers in combination with quick updates, the browser can adopt a hard-fail policy: if the filter says the certificate is revoked, the connection is refused, period.
There is, however, one important caveat: the filter can only give accurate answers for certificates that were known during its creation, or update. For newly issued certificates that haven’t yet propagated, the system will fall back to legacy revocation checking until the next filter update includes them.
The Plot Twist
The cascading bloom filter design looked like a perfect solution for CRLite. Mozilla implemented and deployed it experimentally starting in 2020. However when they tried to scale it up to all Firefox users, they hit a wall: the bandwidth requirements of even the CRLite were simply too high for a production rollout - the certificate universe grew much too large.
As of November 2024, the full Bloom filter cascade was 19.3 MB - encoding over 800 million valid certificates and nearly 12 million revoked certificates. Pushing that to hundreds of millions of browsers, with frequent updates, was not viable.
Enter Clubcards: the solution (again)
The solution came in two parts: a better filter type and a smarter way of structuring the data. The result is an entirely new data structure called Clubcard, which Mozilla presented at IEEE S&P 2025 and deployed in Firefox.
Part 1: Ribbon filters
A standard Bloom filter was a solid choice, however due to the way the information is encoded it still has an inherent space overhead - at least 44% over a theoretical minimum.
Clubcards replace Bloom filters with Ribbon filters, a data structure introduced by Peter Dillinger and Stefan Walzer in 2021. Ribbon filters take a different approach to information encoding. Instead of hashing elements to positions in a bit array, a Ribbon filter encodes set membership using complicated mathematical concepts that are out-of-scope for this, already lengthy, blog post (maybe in a future post).
Nevertheless CRLite with Ribbon filters can achieve roughly 12% overhead - much closer to the theoretical lower bound than Bloom filters can get.
Part 2: Partitioning by issuer
The second insight is that the WebPKI revocation set has a natural structure that can be exploited for better compression. The original CRLite design treated all certificates as one flat set, regardless of the CAs. Clubcards chose to partition the data by the certificate issuer - each CA gets its own little filter encoding only its own certificates and revocations.
Why does it help? Encoding the fact that 11.7 million certificates out of 816 million are revoked requires, at minimum, about 11 MB if you treat the set as unstructured. But the revocation rate varies enormously between issuers: some CAs might have 0.1% of their certificates revoked, while others might have 15%. When you partition by issuer, each sub-filter can be sized optimally for its specific revocation rate. The information-theoretic lower bound drops from 11 MB to 7.6 MB just from this partitioning.
Part 3: Two-level cascade instead of multi-level
The original CRLite used an arbitrary number of cascade levels - as many layers as were needed to eliminate false positives. A simplification was proposed: a two-level cascade. The first layer encodes the revoked set (with some valid certificates included as false positives). The second layer encodes only those false positives.
With only two layers there may still be some residual set of elements that will be misclassified by the filter. However by choosing the parameters carefully (balancing space efficiency and false positive rate), the residual set can be either eliminated entirely, or a small set of incorrectly encoded elements is published alongside the filter. The Clubcard paper demonstrates that this simpler structure is more bandwidth-efficient in practice than deeper cascades.
Putting it all together
The mechanism of constructing, distributing and using the filter remains largely the same, minus the number of cascades, data partitioning and the use of a different data structure.
As it turns out the size of the entire set as of August 2025 is roughly 4 MB with daily delta updates averaging at 300 kB. Overall Clubcards are 54% smaller than the original CRLite instantiation.
CRLite with Clubcards was enabled for all Firefox desktop users starting with Firefox 137 in April 2025.
What’s next?
Mozilla is actively working on further improvements. They are developing new partitioning strategies to handle mass revocation events more efficiently. They are also integrating HTTP compression dictionary transport, which allows delta updates to be further compressed against a shared dictionary. And as certificate lifetimes get shorter (47 days by 2029), the total number of unexpired certificates - and thus revocations - that the filter needs to encode at any given time will shrink, further reducing bandwidth requirements.
The best part is that the entire stack is open source: the Clubcard library, and the CRLite-specific Clubcard integration. Mozilla has explicitly expressed their hope that other browser vendors and software developers will adopt the technology.
Conclusion
So after over two decades it is safe to say that the seatbelt doesn’t snap on crash and is finally working as intended. The WebPKI has a definitive solution for certificate revocation. Or does it? As technology evolves around us, the solutions we’re so proud of and that we’ve considered final, are manifesting cracks that were never there before, or it outright breaks. But it is a good thing. It forces us to always innovate, make things better, move forward. At the same time as the old solutions break, the new opportunities present themselves. Often, but not always, better and more elegant than before. That seems to be the innate nature of technology. And that’s also the reason I enjoy it so much.