Criminology: Refined Techniques for Compression Side-Channel Attacks

It has been known for two decades that performing compression before encryption is dangerous, because it introduces a side channel leaking information about plaintexts through ciphertext lengths: the compressed plaintext length may be visible in the ciphertext length, and the amount of compression obtained is plaintext-dependent; hence an adversary can obtain some leakage about the plaintext via observation of ciphertext lengths. This issue was first pointed out by Kelsey (FSE 2002) and turned into a practical plaintext recovery attack in the form of the CRIME attack on SSL and TLS by Rizzo and Duong in 2012. A long series of variations and attacks against other systems followed. Despite the known dangers, the compress-then-encrypt paradigm is still prevalent in practice today. This may be because the compression-based side channel is susceptible to noise and may require a large number of queries to enable plaintext recovery, and so can be mitigated by either adding noise (e.g. with random padding) or limiting an adversary's interaction with the system.

We demonstrate that this side channel is much more powerful than previously thought. We focus on the widely-used DEFLATE algorithm in our analysis. We present novel techniques that enable strong amplification of small length differences arising during compression. Our telescoping and chaining amplification techniques exploit the way in which DEFLATE replaces common strings by shorter back-references. Our collision-based amplification technique focusses on exploiting hash table collisions in DEFLATE implementations. This involves a deeper examination (and exploitation) of the internals of DEFLATE than in previous works. These insights result in compressed length differences growing linearly with the length of queries. Compared with length differences of a few bits or bytes in prior work, our new amplification techniques thus enable us to defeat existing noise-based countermeasures.

Finally, we introduce the concept of CRIME automata, these being carefully crafted query strings that enable an attacker to exert fine control over the internal behaviour of DEFLATE and produce differences in the output lengths of the compressor according to various criteria (such as whether the DEFLATE sliding window contains a given target string). In turn, our automata are composed in a modular fashion from gadgets having different functions, including matching against target strings, performing logical operations between other gadgets, and, most importantly, amplifying differences in output lengths using the above-mentioned techniques. We provide multiple, concrete automata designs that serve different attack goals. These designs are supported by experiments and a publicly available codebase demonstrating the power, flexibility, and practical impact of our CRIME automata approach.