Certificate revocation on the web has been quietly broken for years. Browsers ask a certificate authority whether a certificate is still valid, and that question leaks your browsing, adds latency, and often fails open when the answer never arrives. CRLite is a different bet: ship the entire list of revocations to the browser, compressed small enough to fit, and never ask anyone anything.
When your browser connects to a site over HTTPS, it receives a certificate that proves the site controls its domain. Sometimes a certificate needs to be pulled before it expires, because the private key leaked, the certificate was issued in error, or the domain changed hands. That is revocation. The hard part was never deciding to revoke. It was getting the news to every browser, in time, without creating new problems along the way.
Why the Old Ways Failed
The two traditional mechanisms both have structural flaws. Certificate revocation lists (CRLs) are files a CA publishes listing every revoked serial number. They grew large and were fetched rarely, so a browser's copy was often stale. The Online Certificate Status Protocol (OCSP) replaced the big file with a live query: before trusting a certificate, the browser asks the CA about that specific certificate.
OCSP fixed staleness and introduced three new problems. It is slow, adding a network round trip to the CA on the critical path of every new connection. It is a privacy leak, because the CA learns which sites you visit and when. And it usually fails open: if the OCSP responder is unreachable, browsers proceed rather than break the web, which means an attacker who can block the query defeats the check entirely. OCSP stapling helps with the speed and privacy issues by having the server attach a fresh proof, but it depends on server operators enabling it, and adoption was never universal.
The privacy problem in one line: Every OCSP request tells a certificate authority that a particular user is about to visit a particular website. A revocation check should not double as a browsing-history feed to a third party.
The CRLite Bet: Push Everything
CRLite, a system that came out of research published in 2017 and was later built into Firefox, takes the position that the browser should just hold the answer for every certificate locally. No live query, no leak, no failing open. To do that it needs two things: a complete list of all publicly trusted certificates, and knowledge of which of them are revoked.
The complete list comes from Certificate Transparency logs, which record essentially every certificate issued by a publicly trusted CA. The revocation status comes from aggregating the CAs' own CRLs. Combine them and you can partition the entire universe of known certificates into two sets: the ones that are still valid, and the ones that are revoked. The trouble is size. That universe is hundreds of millions of certificates. You cannot ship that to every browser several times a day.
The Bloom Filter Cascade
Here is the elegant part. A Bloom filter is a compact structure that answers set-membership questions with a useful asymmetry: if it says an item is not in the set, that is always true, but if it says an item is in the set, it might be wrong. Those wrong answers are false positives, and their rate depends on how much space you spend.
CRLite builds a cascade of these filters. Because it knows the full universe in advance, it can do something a normal Bloom filter cannot.
- Layer 1. Build a Bloom filter over the set of revoked certificates. Query it for every valid certificate too. Most valid certificates correctly come back as not revoked, but a small number are false positives that the filter wrongly flags as revoked.
- Layer 2. Take exactly those false positives, the valid certificates that layer 1 got wrong, and build a second Bloom filter over them. Now a few revoked certificates will be false positives in this layer.
- Layer 3. Build a filter over that set of mistakes. Each layer only has to correct the errors of the layer above, so each layer is far smaller than the last.
The layers alternate, correcting each other, and the error shrinks geometrically until it reaches zero over the known universe. To check a certificate, the browser walks the layers in order. The first layer that says not present gives a definitive answer, and the level at which the item drops out tells you whether it was revoked or valid. Because the whole set was known when the cascade was built, there are no false positives and no false negatives for any certificate in that universe.
A single Bloom filter trades accuracy for space. A cascade uses a second filter to catch the first one's mistakes, a third to catch the second's, and so on, until the structure is exact over the exact set it was built from.
The result compresses the revocation status of the entire web into a few megabytes, small enough to distribute to browsers regularly, with much smaller delta updates in between full builds. The check then happens entirely on your device, offline, in microseconds, with no CA learning anything.
What CRLite Does and Does Not Cover
CRLite is not magic, and its guarantees have edges worth stating plainly.
| Concern | How CRLite handles it |
|---|---|
| Privacy | Fully addressed. Checks are local, so no revocation query reveals your browsing to a CA. |
| Speed | Fully addressed. No network round trip on the connection path. |
| Freshness window | A revocation is only known after the next dataset is built and pushed. Very recent revocations may not yet be reflected, though delta updates keep the gap short. |
| Coverage | Bounded by what Certificate Transparency and the aggregated CRLs contain. A certificate outside those sources is outside the dataset. |
In other words, CRLite decisively fixes the privacy and performance failures of live checking, and it turns fail-open into a locally held, hard answer. What it cannot do is know about a revocation faster than the pipeline that feeds it. That is a far better failure mode than the one it replaces, where a blocked query meant no check at all.
Why It Matters Beyond the Browser
CRLite is a case study in a pattern that shows up throughout privacy engineering. The obvious approach, asking a server in real time, leaks information and creates a dependency on availability. The better approach is often to move the data to the user and let the check happen locally, so no query ever has to be made. The same instinct drives k-anonymity in breach checking and local-first designs generally.
The takeaway for anyone evaluating a system that promises to check something on your behalf is to ask where the check happens and what it reveals. A check that phones home is a check that watches you. CRLite shows that with the right data structure, you can often keep the check and drop the surveillance, and that trade is almost always worth making.
Originally published at havenmessenger.com
Top comments (0)