CRLite: Speeding Up Secure Browsing

Published 2020-01-21 originally at Mozilla's Security Blog and cross-posted here.

CRLite pushes bulk certificate revocation information to Firefox users, reducing the need to actively query such information one by one. Additionally this new technology eliminates the privacy leak that individual queries can bring, and does so for the whole Web, not just special parts of it. The first two posts in this series about the newly-added CRLite technology provide background: Introducing CRLite: All of the Web PKI’s revocations, compressed and The End-to-End Design of CRLite.

Since mid-December, our pre-release Firefox Nightly users have been evaluating our CRLite system while performing normal web browsing. Gathering information through Firefox Telemetry has allowed us to verify the effectiveness of CRLite.

The questions we particularly wanted to ask about Firefox when using CRLite are:

What were the results of checking the CRLite filter?
- Did it find the certificate was too new for the installed CRLite filter;
- Was the certificate valid, revoked, or not included;
- Was the CRLite filter unavailable?
How quickly did the CRLite filter check return compared to actively querying status using the Online Certificate Status Protocol (OCSP)?

How Well Does CRLite Work?

With Telemetry enabled in Firefox Nightly, each invocation of CRLite emits one of these results:

Certificate Valid, indicating that CRLite authoritatively returned that the certificate was valid.
Certificate Revoked, indicating that CRLite authoritatively returned that the certificate was revoked.
Issuer Not Enrolled, meaning the certificate being evaluated wasn’t included in the CRLite filter set, likely because the issuing Certificate Authority (CA) did not publish CRLs.
Certificate Too New, meaning the certificate being evaluated was newer than the CRLite filter.
Filter Not Available, meaning that the CRLite filter either had not yet been downloaded from Remote Settings, or had become so stale as to be out-of-service.

Show that >50% of TLS connections would have been using CRLite — Figure 1: One month of CRLite results in Firefox Nightly (5 December 2019 to 6 Jan 2020)

Immediately, one sees that over 54% of secure connections (500M) could have benefited from the improved privacy and performance of CRLite for Firefox Nightly users.

Of the other data:

We plan to publish updates up to 4 times per day, which will reduce the incidence of the Certificate Too New result.
The Filter Not Available bucket correlates well with independent telemetry indicating a higher-than-expected level of download issues retrieving CRLite filters from Remote Settings; work to improve that is underway.
Certificates Revoked but used actively on the Web PKI are, and should be, rare. This number is in-line with other Firefox Nightly telemetry for TLS connection results.

How Much Faster is CRLite?

In contrast to OCSP which requires a network round-trip to complete before a web page can load, CRLite needs only to perform a handful of hash calculations and memory or disk lookups. We expected that CRLite would generally outperform OCSP, but to confirm we added measurements and let OCSP and CRLite race each other in Firefox Nightly.

Show that CRLite is faster than existing technology 99% of the time — Figure 2: How often is CRLite faster than OCSP? (11 December 2019 to 6 January 2020)

Over the month of data, CRLite was faster to query than OCSP 98.844% of the time.

CRLite is Faster 99% of the Time

The speedup of CRLite versus OCSP was rather stark; 56% of the time, CRLite was over 100 milliseconds faster than OCSP, which is a substantial and perceptible improvement in browsing performance.

Distribution of speedups of CRLite — Figure 3: Distribution of occurrences where CRLite outperformed OCSP, which was 99% of CRLite operations. [source]

Almost 10% of the collected data reports showed an entire second of speedup, indicating that the OCSP reached the default timeout. The delay in this figure shows time spent where a Firefox user is waiting for the page to start loading, so this has a substantial impact to perceived quickness in the browser.

To verify that outlier at the timeout, our OCSP telemetry probe shows that over the same period, 9.9% of OCSP queries timed out:

10% of OCSP queries time out — Figure 4: Results of Live OCSP queries in Firefox Nightly [source]

Generally speaking, when loading a website where OCSP wasn’t already cached, 10% of the time Firefox users pause for a full second before the site loads, and they don’t even get revocation data in exchange for the wait.

The 1% When OCSP is Faster

The 500k times that OCSP was faster than CRLite, it was generally not much faster: 50% of these occasions it was less than 40 milliseconds faster. Only 20% of the occasions found OCSP 100 milliseconds faster.

Distribution of slowdowns from CRLite — Figure 5: Distribution of occurrences where OCSP outperformed CRLite, which was 1% of CRLite operations. [source]

Interesting as this is, it represents only 1% of CRLite invocations for Firefox Nightly users in this time period. Almost 99% of CRLite operations were faster, much faster.

Much Faster, More Private, and Still Secure

Our study confirmed that CRLite will maintain the integrity of our live revocation checking mechanisms while also speeding up TLS connections.

At this point it’s clear that CRLite lets us keep checking certificate revocations in the Web PKI without compromising on speed, and the remaining areas for improvement are on shrinking our update files closer to the ideal described in the original CRLite paper.

In the upcoming Part 4 of this series, we’ll discuss the architecture of the CRLite back-end infrastructure, the iteration from the initial research prototype, and interesting challenges of working in a “big data” context for the Web PKI.

In Part 5 of this series, we will discuss what we’re doing to make CRLite as robust and as safe as possible.

☕️ Insufficient Coffee