CRLite: From Academia to the "Real World"

written by James Larisch on January 13th, 2020.

On January 9th, 2020 Mozilla announced preliminary completion of their implementation of CRLite, a research project I worked on, in Firefox. This is a big deal for the security and privacy of Firefox users.

I worked on CRLite during my undergraduate years at Northeastern University with an amazing team of professors: Christo Wilson, Alan Mislove, Dave Levin, Bruce M. Maggs, and Dave Choffnes. It’s been almost three years since we presented the work at IEEE S&P (Oakland) 2017 and it’s been highly encouraging to see Mozilla work on adopting it.

For background: TLS certificates are revoked by either website administrators or Certificate Authorities (CAs, institutions that issue certificates) when the certificate’s private key is compromised or in the wake of attacks like Heartbleed. Generally speaking, checking whether a particular certificate is revoked is difficult because the browser must either obtain a complete list of revoked certificates to check against (CRLs), or ask someone trustworthy whether that specific certificate is revoked (OCSP). This process must be repeated for each new certificate encountered as the user browses the web.

Certificate revocation lists (CRLs) are distributed by each CA and can get quite large (Apple had a 70MB CRL!). Asking CAs whether a particular certificate is revoked (OCSP) is a breach of privacy, adds an extra RTT to each initial HTTPS request, and browsers fail-open, so if an attacker blocks the OCSP request, the browser assumes the certificate is not-revoked.

As a result, many browsers perform revocation checks only in certain cases, and mobile browsers perform no checking at all.

Using CRLite, the browsers stores certificates revocation information in a “cascade” of bloom filters using only ~1MB when compressed. The browser downloads daily updates (on the order of ~500KB/day at the time the paper was written, but it should be smaller now). As a result, CRLite provides the following properties:

Which means it is strictly better for the user than current revocation options.

CRLite can utilize a bloom filter cascade because as of recently, all issued and valid certificates are enumerable, due to Google’s Certificate Transparency project. Chrome rejects certificates that are not logged in CT, so at a high level we can search the CT logs for all valid certificates, then check whether they are revoked. For more details on why our bloom filter cascade does not return false positives, check out the blog posts and paper below. But the critical insight is that we can enumerate all the false positives that would occur (since we know all valid, non-revoked certificates).

Mozilla’s work on bringing CRLite into Firefox demonstrates their commitment to complete browser security. If another Heartbleed were to occur post-CRLite-deployment, Firefox users would receive more complete, up-to-date revocation information than users of other browsers. In addition, revocation checking via CRLite is more efficient, more private, and more complete than alternative methods of revocation checking. I think Mozilla should be applauded for their interest in research solutions and hope other browser vendors follow suit.

Mozilla has written an excellent series of blog posts (overview and design) on CRLite and the their implementation, which I highly recommend. You can also read the paper and watch my talk.