Subject: New I-D: Security Considerations Regarding Compression Dictionaries

From: "W. Felix Handte" <[email-masked]>
Date: Tue, 29 Oct 2019 19:20:09 -0400

Hello all,

At IETF 104, I presented a teaser of the exploratory work I've been 
doing into dictionary-based compression for HTTP [0]. At the time, I 
promised that I would follow up with an analysis of the security 
properties of dictionary-based compression.

That time has come! I've just uploaded a draft [1] that attempts to 
address that need and provide a useful survey of the interactions 
between dictionaries, internet protocols, and security.

I would eventually like for this document to find a home in the HTTP WG; 
your feedback and thoughts are greatly appreciated.

I look forward to seeing you all in Singapore!

Thanks,
Felix

[0] https://youtu.be/GIRgsVIYG7I?t=6889
[1] https://datatracker.ietf.org/doc/draft-handte-httpbis-dict-sec/

---

From: Watson Ladd <[email-masked]>
Date: Tue, 29 Oct 2019 16:54:12 -0700

> your feedback and thoughts are greatly appreciated.

I'm not sure I appreciate the distinction of "dictionary-based"
compression vs. other compression algorithms you draw in the draft.
The BREACH attack didn't look at changes to the Huffman table, which
was dominated by good old ETOAIN SHRDLU. Instead it changed the length
of matches back into the datastream, and thus the length of the
observed output. There isn't a separate dictionary to match substrings
in in DEFLATE.

A perfect compression algorithm reveals the Kolmogorov complexity of
the input. This is enough (if you can compute Kolmogorov complexity)
to reveal the differences between "hunter2 h" and "hunter2 z", and
then "hunter2 hu" and "hunter2 ha", etc.

It's true that a static Huffman tree isn't vulnerable to this problem,
but that's because the Huffman tree compresses character by character
using source statistics that don't change as the message is processed.
A dynamic Huffman tree (or range encoder) with only symbols (not per
context) would also leak overall number of symbols, while one with
context dependent probabilities would leak quite a bit more. No
dictionary here!

---

From: "W. Felix Handte" <[email-masked]>
Date: Tue, 29 Oct 2019 22:17:10 -0400

> observed output. There isn't a separate dictionary to match substrings

Yeah, "dictionary" is an extremely overloaded term in compression, to
say nothing of computer science generally. This has produced a great
deal of confusion. But I haven't come up with a better term for the concept.

What I mean by "dictionary" in this context is mostly a user-supplied
buffer that the compressor makes LZ77-style matches into. (Though, as
the document notes, various algorithms expect various kinds of data in
the dictionaries they accept.) This makes it very much a potential
vector for exactly that kind of attack. And DEFLATE, at least as
implemented by zlib, does support dictionaries of this form [0].

> then "hunter2 hu" and "hunter2 ha", etc.

Right, compression as it exists today has real outstanding security
issues. My goal with the document is to assess whether the use of
dictionaries introduces additional problems on top of the existing ones.

[0] https://github.com/madler/zlib/blob/master/zlib.h#L611

---

From: "Soni L." <[email-masked]>
Date: Wed, 30 Oct 2019 06:43:20 -0300

> [0] https://github.com/madler/zlib/blob/master/zlib.h#L611
So, what you're saying, is that this wouldn't be an issue if we were 
using public-key-based authentication and session tokens?

Like this? https://soniex2.autistic.space/posts/2019/06/uweb.xhtml (or, 
perhaps, this? https://awoo.space/@SoniEx2/102972533369915352 )

(This also touches on another post I've sent this list, but it's not 
relevant here.)

---

From: "W. Felix Handte" <[email-masked]>
Date: Wed, 30 Oct 2019 12:15:22 -0400

> perhaps, this? https://awoo.space/@SoniEx2/102972533369915352 )

Secret tokens (passwords, keys, cookies, etc.) are likely the most 
important kind of content to protect, but also definitely not the only 
kind. Message bodies themselves may contain secrets worth attacking 
(credit card numbers).

---

From: "Soni L." <[email-masked]>
Date: Wed, 30 Oct 2019 18:18:20 -0300

(sorry, I seem to have made a mistake when posting this/replying the 
first time around.)

On 2019-10-30 1:15 p.m., W. Felix Handte wrote:
>> Like this? https://soniex2.autistic.space/posts/2019/06/uweb.xhtml 
>> (or, perhaps, this? https://awoo.space/@SoniEx2/102972533369915352 )
>
Ah. Yeah. I forgot about that. .-.

(altho, probably in my ideal world my computer would have an NFC or 
chip-and-pin reader and the whole thing would be end-to-end encrypted 
between the parties. I don't get why we don't have those yet. but, 
anyway, I digress.)