Subject: [TLS] Certificate compression draft

From: Victor Vasiliev <[email-masked]>
Date: Mon, 6 Mar 2017 17:58:08 -0500

Certificate compression has been discussed on this list briefly before, and
there was some interest in at least considering a draft for it.  The draft
now
exists (co-authored by Alessandro and myself), and it can be found at:

https://datatracker.ietf.org/doc/draft-ghedini-tls-certificate-compression/
  [ GitHub repo: https://github.com/ghedo/tls-certificate-compression ]

The proposed scheme allows a client and a server to negotiate a compression
algorithm for the server certificate message.  The scheme is purely opt-in
on
both sides.  The current version of the draft defines zlib and Brotli
compression, both of which are well-specified formats with an existing
deployment experience.

There are multiple motivations to compress certificates.  The first one is
that
the smaller they are, the faster they arrive (both due to the transfer time
and
a decreased chance of packet loss).

The second, and more interesting one, is that having small certificates is
important for QUIC in order to achieve 1-RTT handshakes while limiting the
opportunities for amplification attacks.  Currently, TLS 1.3 over TCP
without
client auth looks like this:

  Round trip 1: client sends SYN, server sends SYN ACK
    Here, the server provides its own random value which client will
    have to echo in the future.
  Round trip 2: client sends ACK, ClientHello, server sends
ServerHello...Finished
    Here, ACK confirms to server that the client can receive packets and is
not
    just spoofing its source address.  Server can send the entire
ServerHello to
    Finished flight.

In QUIC, we are trying to merge those two rounds into one.  The problem,
however, is that the ClientHello is one packet, and ServerHello...Finished
can
span multiple packets, meaning that this could be used as an amplification
attack vector since the client's address is not yet authenticated at this
point.
In order to address this, the server has to limit the number of packets it
sends
during the first flight (i.e. ServerHello...Finished flight).  Since
certificates make up the majority of data in that flight, making them
smaller
can push them under the limit and save a round-trip.

Cheers,
  Victor.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Mar 2017 10:06:44 +1100

Hi Victor,

Do you have any evidence to suggest that this reduces size in any
meaningful way?  Certificates tend to include both repetitious values
(OIDs), and non-repetitious values (keys).

On 7 March 2017 at 09:58, Victor Vasiliev <[email-masked]> wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Victor Vasiliev <[email-masked]>
Date: Mon, 6 Mar 2017 18:23:07 -0500

Hi Martin,

I've measured the effect of compression on a corpus of popular website
certificate chains I had lying around (Alexa Top 100k from a few years ago),
and the effect seems to be about -30% of size at the median and -48% at 95th
percentile (with Brotli, subtract 3-5% for zlib).

I think the most dramatic effect from the compression is observed for the
certificates with a lot of SNI values, which is not uncommon.

  -- Victor.

---

From: Viktor Dukhovni <[email-masked]>
Date: Mon, 6 Mar 2017 18:29:25 -0500

> On Mar 6, 2017, at 6:23 PM, Victor Vasiliev <[email-masked]> wrote:
> 
> Hi Martin,
> 

Is 30-50% enough to mitigate concerns about amplification attacks?  Introducing
compression increases the attack surface on TLS clients and adds CPU cost.  If
the compression is not sufficiently effective, it is not clear that the benefit
outweighs the cost.

Wouldn't amplification be better addressed via TCP cookies?  With TCP fast open
restricted to cookie-bearing clients?  With similar mechanisms for UDP, ...

-- 
	Viktor.

---

From: Vlad Krasnov <[email-masked]>
Date: Mon, 6 Mar 2017 15:32:41 -0800

Hi Victor,

Have you considered creating a common dictionary, similarly to what SPDY did for header compression?

Cheers,
Vlad

> On Mar 6, 2017, at 3:23 PM, Victor Vasiliev <[email-masked]> wrote:
> 
> Hi Martin,
> 
> On Mon, Mar 6, 2017 at 6:06 PM, Martin Thomson <[email-masked] <mailto:[email-masked]>> wrote:
> Hi Victor,
> 
> On 7 March 2017 at 09:58, Victor Vasiliev <[email-masked] <mailto:[email-masked]>> wrote:
> > https://datatracker.ietf.org/doc/draft-ghedini-tls-certificate-compression/ <https://datatracker.ietf.org/doc/draft-ghedini-tls-certificate-compression/>
> >   [ GitHub repo: https://github.com/ghedo/tls-certificate-compression <https://github.com/ghedo/tls-certificate-compression> ]
> >
> > [email-masked] <mailto:[email-masked]>
> > https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>
> >
>

---

From: Victor Vasiliev <[email-masked]>
Date: Mon, 6 Mar 2017 18:51:24 -0500

> the compression is not sufficiently effective, it is not clear that the

It's actually pretty good at this.  My relatively back-of-the-envelope
calculations show that compression increases number of handshakes that fit
into two packets from ~2% to ~54% (for three packets, it goes up from ~52%
to
~97%).

> restricted to cookie-bearing clients?  With similar mechanisms for UDP, ...

The goal here is to reduce the number of round-trips required to connect to
a
server previously unknown to the client from two to one (otherwise you can
just
put an equivalent of TCP cookie in the ticket).  TCP cookies only work if
you've connected to the server before.

  -- Victor.

---

From: Victor Vasiliev <[email-masked]>
Date: Mon, 6 Mar 2017 19:15:38 -0500

Hi Vlad,

This is still an open issue:
https://github.com/ghedo/tls-certificate-compression/issues/2

The problem here is creating a dictionary that is both neutral with respect
to
the certificate's issuing authority, and actually has a noticeable effect.
So
far my personal attempts at making such a dictionary have not been very
successful, but this might change.  Even if we get a dictionary, I do not
expect the effect to be large compared to the effect of just compressing the
chain in the first place.

  -- Victor.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Mar 2017 11:38:15 +1100

Seems like you might get some traction with adding www. .com, some DN
fields (CN=, O=, C=), common OIDs, with some OIDs attached to values
(like key usage and signature algorithm).  Most of that is relatively
short though.

---

From: Vlad Krasnov <[email-masked]>
Date: Mon, 6 Mar 2017 17:37:37 -0800

Don't know about neutral dictionary, but simply compressing Cloudflare cert using Google cert, gives an additional 6% using brotli -15.

I would rather have a biased dictionary than none at all :)

Cheers,
Vlad

> On Mar 6, 2017, at 4:38 PM, Martin Thomson <[email-masked]> wrote:
>

---

From: Ryan Sleevi <[email-masked]>
Date: Mon, 6 Mar 2017 21:13:46 -0500

On Mon, Mar 6, 2017 at 5:37 PM, Vlad Krasnov <[email-masked]> wrote:

> Don't know about neutral dictionary, but simply compressing Cloudflare
> cert using Google cert, gives an additional 6% using brotli -15.
>

I can appreciate that sentiment, but you do realize the natural consequence
of that - it creates an incentive structure for the larger CAs to get
larger, by virtue of the compression benefits afforded to them by such a
dictionary making such certificates more desirable. That, in turn, results
in more instability and insecurity for the PKI ecosystem and penalizes
non-participants of the WebPKI within TLS.

While such a desire for improved compression is natural, the external costs
should not be underestimated or dismissed.

I would rather have no compression than a biased dictionary, given these
concerns.

---

From: Viktor Dukhovni <[email-masked]>
Date: Mon, 6 Mar 2017 21:32:16 -0500

> On Mar 6, 2017, at 9:13 PM, Ryan Sleevi <[email-masked]> wrote:
> 
> I can appreciate that sentiment, but you do realize the natural consequence of that - it creates an incentive structure for the larger CAs to get larger, by virtue of the compression benefits afforded to them by such a dictionary making such certificates more desirable. That, in turn, results in more instability and insecurity for the PKI ecosystem and penalizes non-participants of the WebPKI within TLS.

Fewer WebPKI CAs (which are all trusted) seems like an improvement to me.
Though I doubt that compression efficiency would be a major factor in such
an outcome.  If we're ultimately going to use post-quantum certificates with
post-quantum keys and signature algorithms, and those keys and signatures
are noticeably larger than current RSA keys/signatures, then compression of
the rest of the certificate will not matter very much at all.

If scalable quantum computing never happens, then EdDSA certs have sufficiently
small keys and signatures for reasonably effective compression.

One might also note that 10Gbps+ networks tend to use 9Kbyte ethernet frames
these days, perhaps over time these will become the norm rather than the
exception...

-- 
	Viktor.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Mar 2017 14:33:07 +1100

On 7 March 2017 at 13:32, Viktor Dukhovni <[email-masked]> wrote:
> an outcome.

Like Ryan, I would rather not create any systemic biases in favour of
certain parties, however minor we each subjectively believe those
biases might be.

---

From: Hannes Tschofenig <[email-masked]>
Date: Tue, 7 Mar 2017 09:14:53 +0100

Hi Victor

why don't you use RFC 7924:
https://tools.ietf.org/html/rfc7924

This provides an even better "compression" ratio.

Ciao
Hannes

On 03/06/2017 11:58 PM, Victor Vasiliev wrote:
> there was some interest in at least considering a draft for it.  The
> draft now
> algorithm for the server certificate message.  The scheme is purely
> opt-in on
> There are multiple motivations to compress certificates.  The first one
> is that
> the smaller they are, the faster they arrive (both due to the transfer
> time and
>     Here, ACK confirms to server that the client can receive packets and
> is not
> however, is that the ClientHello is one packet, and
> ServerHello...Finished can
> attack vector since the client's address is not yet authenticated at
> this point.
> In order to address this, the server has to limit the number of packets
> it sends

---

From: Rob Stradling <[email-masked]>
Date: Thu, 9 Mar 2017 11:55:43 +0000

Hi Hannes.

Cached-Info is useful, but it can only "compress" if the client has 
previously seen and cached the server's certificate.

AIUI, the purpose of draft-ghedini-tls-certificate-compression is to 
enable compression even in cases where the client hasn't yet seen the 
server's certificate.

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 21 Mar 2017 16:30:50 -0700

This proposal seems like a reasonable idea. One question I had is what the
point of the "uncompressed length" field is:

       struct {
            uint24 uncompressed_length;
            opaque compressed_certificate_message<1..2^24-1>;
       } Certificate;

I initially thought maybe it was a sanity check, but if so it's not a very
good
one. I see that in S 5 you encourage receivers to limit the compressed
length, but having it expressed like this doesn't seem like that useful a
security measure because the attacker gets to choose both the compressed
data and the length. Is the idea just to let the receiver pre-allocate a
buffer
for decompression?

The text says:

   compressed_certificate_message  The compressed body of the
      Certificate message, in the same format as the server would
      normally express it.  The compression algorithm defines how the
      bytes in the compressed_certificate_message are converted into the
      Certificate message.

I assume in this case "body" means "not including the header bytes"? I
guess it's
redundant, but it might be worthwhile being very precise

Also:

   The implementations MUST limit the size of the resulting decompressed
   chain to the specified uncompressed length, and they MUST abort the
   connection if the size exceeds that limit.  Implementations MAY
   impose a lower limit on the chain size in addition to the 16777216
   byte limit imposed by TLS framing, in which case they MUST apply the
   same limit to the uncompressed chain before starting to decompress
   it.

Do you mean "upper" rather than "lower" for limit?

-Ekr

---

From: Victor Vasiliev <[email-masked]>
Date: Wed, 22 Mar 2017 17:34:54 -0400

> data and the length. Is the idea just to let the receiver pre-allocate a

It's to some extent for all of the purposes you've mentioned, but in
general knowing
the size of decompression target makes writing code easier (since you only
need
to call inflate() once).

> redundant, but it might be worthwhile being very precise

Indeed.  I'll see if I can make this more clear.

> Do you mean "upper" rather than "lower" for limit?

I meant "lower than 16M".  I've edited the editor's copy to make this
paragraph clearer.

  -- Victor.