<commit_before>\section{Introduction}\label{sec:prev}

Compression and encryption composition has caused serious security problems in
protocols such as TLS \cite{dierks2008tls} over the years with an array of
attacks making major headlines in computer security dissemination forums,
including BREACH \cite{gluck2013breach}, TIME \cite{be2013perfect}, and CRIME
\cite{duong2012crime}. Although the idea that compression is a side-channel that
can be exploited is certainly folklore in the cryptography community and is
documented at least as early as Kelsey's work \cite{kelsey2002compression}, a
proper theoretical model capturing the real-world perspective of these
side-channel attacks is still elusive.

Motivated by this, in this paper we introduce a general model that incorporates
the rendering process that is exploited during these attacks and facilitate a
thorough theoretical analysis of the security of encryption-compression
composition. We showcase the power of our approach by (i) demonstrating an
improved attack framework, called Rupture, that improves substantially the
performance of previous attacks, (ii) showing how attacks like BREACH
\cite{gluck2013breach}, TIME \cite{be2013perfect}, and CRIME
\cite{duong2012crime}, can be expressed as instances of our compression
side-channel attack template, (iii) presenting a general mitigation strategy,
called CTX, that strikes a good balance between security and efficiency and can
be readily incorporated in a TLS deployment without a significant performance
degradation.

\subsection{Contributions}
Our contributions are as follows.

First we introduce a novel model for analyzing compression and encryption
composition attacks, the \textit{adaptive reflection game}, with an accompanying
security definition. This model is quite general in that it does not describe
specific instances of the rendering function $f$ or the compression function
$\textrm{Com}$. Furthermore, it allows for general distributions of secret $\mathcal{M}$
and distributions of noise $\mathcal{V}$ which can affect the rendering. Section
\ref{sec:refsec} contains the definition of this model.

We wish to prove that all encryption functions are insecure when composed with
compression. In order to produce this proof, we build a series of required
assumptions.

We define \textit{interdependence}, a property that characterizes dependent
random variables drawn from a joint distribution. Interdependence is an
important notion when exploring the effects of the reflection when compressed
with a secret. We introduce interdependence in section
\ref{subsec:interdependence}.

Another property of compression functions is \textit{compression idealness} with
respect to a message distribution. We
define idealness in theory and demonstrate how it applies on the compression
algorithms that are widely used in section \ref{subsec:com_idealness}.

Based on the properties of compression idealness and interdependence, we prove
that predicates on the secrets can be learned by choosing adversarial
reflections. We call this property \textit{compression detectability}, which we
explore in section \ref{sec:propertycom}.

The final part of our theoretical work on the attack is to show that this
somewhat innocent property directly allows the construction of an attacker,
which we prove breaks the security of the scheme in section
\ref{sec:comattack}. We also prove that such attacks can be amplified to
achieve better confidence.

At this point we implement Rupture\footnotemark[1], a production-grade open
source framework for conducting compression and encryption composition attacks.
This generic framework provides an extensible mechanism for experimentally
testing attack techniques in a modular setting. We implement specific
compression attack instances such as BREACH. This is the first time a working
tool is provided for this class of attacks.  Based on our attack framework we
achieve significant improvements in our implementation compared to previous
attempts. We improve the complexity from linear to logarithmic in the secret
alphabet's size, we attack block ciphers in addition to stream ciphers and we
employ practical techniques for network level optimization.  Rupture is further
described in section \ref{subsec:rupture}.

Having established the attack premises, we shift our interest in defending
against such attacks. Although there are several proposed defenses, we feel that
none achieves good compression performance in real-world system terms. In this
direction, we propose \textit{context hiding}, a method that mitigates a class
of practical compression side-channel attacks like BREACH. Context hiding aims
at preventing the compression detectability of a predicate $Q$ of a secret $s$
in presense of reflection as described in section \ref{sec:defense}.

Our implementation of the context hiding defense technique is called
CTX\footnote[1]{The GitHub repositories of the Rupture and CTX projects make the
source code openly available but have been removed for anonymization purposes
and can be provided upon request.}. CTX runs at the application layer of web
services and is opt-in. It is implemented in Python and Javascript and can be
used in the common web frameworks Django, Flask and Node.js. CTX achieves
balance between security and compression performance that is unprecedented
compared to other proposed defense methods.

We experimentally show in section \ref{subsubsec:ctx_experiments} that CTX
performs well in terms of size and time overhead. Specifically, we find that the
performance penalty of CTX compared to other proposed methods, like secret
masking, is significantly lower and within accepted rates for real-world
applications.
<commit_msg>Rephrase contributions section using new Usenix structure<commit_after>\section{Introduction}\label{sec:prev}

Compression and encryption composition has caused serious security problems in
protocols such as TLS \cite{dierks2008tls} over the years with an array of
attacks making major headlines in computer security dissemination forums,
including BREACH \cite{gluck2013breach}, TIME \cite{be2013perfect}, and CRIME
\cite{duong2012crime}. Although the idea that compression is a side-channel that
can be exploited is certainly folklore in the cryptography community and is
documented at least as early as Kelsey's work \cite{kelsey2002compression}, a
proper theoretical model capturing the real-world perspective of these
side-channel attacks is still elusive.

Motivated by this, in this paper we introduce a general model that incorporates
the rendering process that is exploited during these attacks and facilitate a
thorough theoretical analysis of the security of encryption-compression
composition. We showcase the power of our approach by (i) demonstrating an
improved attack framework, called Rupture, that improves substantially the
performance of previous attacks, (ii) showing how attacks like BREACH
\cite{gluck2013breach}, TIME \cite{be2013perfect}, and CRIME
\cite{duong2012crime}, can be expressed as instances of our compression
side-channel attack template, (iii) presenting a general mitigation strategy,
called CTX, that strikes a good balance between security and efficiency and can
be readily incorporated in a TLS deployment without a significant performance
degradation.

\subsection{Contributions}
Our contributions are as follows.

First, we implement Rupture\footnotemark[1], a production-grade open source
framework for conducting compression and encryption composition attacks.  This
generic framework provides an extensible mechanism for experimentally testing
attack techniques in a modular setting. We implement specific compression attack
instances such as BREACH. An extensive description of Rupture's architecture is
in section \ref{subsec:rupture}. This is the first time a working tool is
provided for this class of attacks.

We then introduce a novel model for analyzing compression and encryption
composition attacks, the \textit{adaptive reflection game}, with an accompanying
security definition. This model is quite general in that it does not describe
specific instances of the rendering function $f$ or the compression function
$\textrm{Com}$. Furthermore, it allows for general distributions of secret
$\mathcal{M}$ and distributions of noise $\mathcal{V}$ which can affect the
rendering. Section \ref{sec:refsec} contains the definition of this model.

We wish to prove that all encryption functions are insecure when composed with
compression. In order to produce this proof, we build a series of required
assumptions.

We define \textit{interdependence}, a property that characterizes dependent
random variables drawn from a joint distribution. Interdependence is an
important notion when exploring the effects of the reflection when compressed
with a secret. We introduce interdependence in section
\ref{subsec:interdependence}.

Another property of compression functions is \textit{compression idealness} with
respect to a message distribution. We define idealness and demonstrate how it
applies on the compression algorithms that are widely used in section
\ref{subsec:com_idealness}.

Based on the properties of compression idealness and interdependence, we prove
that predicates on the secrets can be learned by choosing adversarial
reflections. We call this property \textit{compression detectability}, which we
explore in section \ref{sec:propertycom}.

The final part of our theoretical work on the attack is to show that this
somewhat innocent property directly allows the construction of an attacker,
which we prove breaks the security of the scheme in section \ref{sec:comattack}.
We also prove that such attacks can be amplified to achieve better confidence.

Based on our attack framework we achieve significant improvements in our
implementation compared to previous attempts. We improve the complexity from
linear to logarithmic in the secret alphabet's size, we attack block ciphers in
addition to stream ciphers and we employ practical techniques for network level
optimization. The attack optimizations implemented in Rupture are further
described in section \ref{subsec:optimizations}.

Having established the attack premises, we shift our interest in defending
against such attacks. Although there are several proposed defenses, we feel that
none achieves good compression performance in real-world system terms. In this
direction, we propose \textit{context hiding}, a method that mitigates a class
of practical compression side-channel attacks like BREACH. Context hiding aims
at preventing the compression detectability of a predicate $Q$ of a secret $s$
in presense of reflection as described in section \ref{sec:defense}.

Our implementation of the context hiding defense technique is called
CTX\footnote[1]{The GitHub repositories of the Rupture and CTX projects make the
source code openly available but have been removed for anonymization purposes
and can be provided upon request.}. CTX runs at the application layer of web
services and is opt-in. It is implemented in Python and Javascript and can be
used in the common web frameworks Django, Flask and Node.js. CTX achieves
balance between security and compression performance that is unprecedented
compared to other proposed defense methods.

We experimentally show in section \ref{subsubsec:ctx_experiments} that CTX
performs well in terms of size and time overhead. Specifically, we find that the
performance penalty of CTX compared to other proposed methods, like secret
masking, is significantly lower and within accepted rates for real-world
applications.

{'fraction_non_alphanumeric': 0.03536396489416624, 'fraction_numerical': 0.005850972293925314, 'mean_word_length': 5.581540203850509, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4608844', 'n_tokens_mistral': 2706, 'n_tokens_neox': 2481, 'n_words': 1577}