Subject: [pkix] Compressed CRLs

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 9 Oct 2014 08:55:07 -0400

I sent this to TLS in the first instance but it might be of more
interest here. It turns out that we can compress CRLs much better than
anyone imagined. Using compression we can issue a CRL for every
unexpired SSL Server cert  using less than the 250K that is the limit
on Google's curated CRLSet.

Please note:

http://datatracker.ietf.org/doc/draft-hallambaker-compressedcrlset/
Also note the pending IPR disclosure.

In brief Rob Stradling and myself have come up with a radically new
approach to certificate status that is vastly more efficient than any
previous proposal that provides finer grain certificate status than
the certificate validity interval.

While compressing hash tables might appear to be a fools errand, it
turns out that if the problem is correctly understood, CRLs actually
compress astonishingly well. It is actually possible to represent the
status of every one of the half million revoked certificates in the
WebPKI using fewer bytes than the heavily edited Google CRLSet.

There is still a powerful case for short lived certificates. But the
minimum feasible expiry interval for short lived certs is 48 hours.
Using a compressed CRL in combination with short lived certs would
allow the vulnerability window to be reduced to minutes.

We are of course aware that deployment will require a licensing regime
that meets the need of all parties including competing CAs, open
source software providers, etc. However lacking an existing licensing
regime for the rights holder (if indeed any are granted), I thought it
best to bring this to people's attention first.

The nature of the invention is such that not applying for a patent
would open the possibility that someone else might make a claim as has
happened to me on numerous other occasions. In the past five years
over $50 million has been spent on defending against such patent
claims.

---

From: Erwann Abalea <[email-masked]>
Date: Thu, 16 Oct 2014 19:17:49 +0200

Interesting draft. Can be implemented by a third party if and only if it
has access to all the unexpired certificates (insert GoogleCT here), or by
the CA itself.
Will there be more details on the additional optimizations by Rob? Does
this additional optimization apply to a complete CRLSet or only to deltas?

Regarding the encoding, my preference goes to ASN.1 over JSON. ASN.1 has a
native BITSTRING type and several already standardized encoding rules, one
of them being optimized for space (PER and unaligned PER, X.691). But this
is only a serialization issue and doesn't conflict with the general idea;
some don't like ASN.1 (for bad reasons), some don't like PER (for not so
bad reasons). A good compact and easy encoding may be the recently approved
OER (X.696).

2014-10-09 14:55 GMT+02:00 Phillip Hallam-Baker <[email-masked]>:

> The nature of the invention is such that not applying for a paten;t
> _______________________________________________
> pkix mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/pkix
>

-- 
Erwann.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 20 Oct 2014 08:26:50 -0400

> this additional optimization apply to a complete CRLSet or only to deltas?

I want to get folk to focus on the specific way they want to use it before
we drill down into exactly how to represent it. If we are doing one big CRL
per day then extra compression makes a lot of sense. If we are doing deltas
we need to look at the total complexity of the scheme.

> bad reasons). A good compact and easy encoding may be the recently approved

We don't use ASN.1, never have. We use tools that happen to take ASN.1
syntax. And that is a huge difference.

Unless the authors of OpenSSL and NSSAPI etc. tell me their compilers work
just fine with PER than it doesn't exist as far as I am concerned.

We have already broken with ASN.1 in TRANS which does not use ASN.1 for
internal structures. It uses the TLS schema.

As far as my personal code set goes, I can switch from generating ASN.1 to
TLS or JSON at will. (I don't use ASN.1 schema which simplifies a lot.) So
I am not protecting my code here. But in general discussions over encoding
don't have a lot of weight for me unless they begin 'I am the maintainer of
X. widely used code library).