<commit_before>\documentclass[a4paper, 11 pt, conference]{article}
\usepackage[utf8]{inputenc}

\title{On the security of encryption and compression composition under reflection attacks}
\author{
<NAME>
\and
<NAME>
\and
<NAME>
}
\date{May 2016}

\usepackage{url}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage[xetex,colorlinks=true,linkcolor=blue,citecolor=green]{hyperref}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\let\oldemptyset\emptyset
\let\emptyset\varnothing

\newtheorem*{lemma}{Lemma}

\newcommand\defeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}

\begin{document}

\maketitle

\section{Abstract}\label{sec:abstract}
When compression is composed with encryption, unexpected vulnerabilities can
arise. Such vulnerabilities have been explored in practical attacks against TLS
such as CRIME, TIME, BREACH, and HEIST. We introduce an abstract theoretical
model for such attacks, the \textit{adaptive reflection security} model. We
discuss what properties common compression function have, such as the
\textit{compression-detectability} of predicates, and we show that all
length-preserving encryption schemes are vulnerable when composed with such
functions. Finally, we provide a modular scalable open-source production-grade
generic attack framework where these attacks are implemented in a robust
manner.

\section{Reflection security}\label{sec:refsec}

\subsection{Adaptive reflection game}\label{subsec:refsecgame}

Let $\mathcal{PE} = (\mathcal{K}, \mathcal{E}, \mathcal{D})$ be a public-key
encryption scheme, $\mathcal{A}$ be an adversary and $\mathcal{S}$ be a
simulator of $\mathcal{A}$.  The game
$\text{Game}_{\text{REF-SEC}}^{\mathcal{PE},\mathcal{A}}(\lambda,  f,
\mathcal{V}, g)$ is parameterized with a rendering function $f(\cdot, \cdot,
\cdot)$, a noise distribution $\mathcal{V}$, the security parameter $\lambda$,
some function $g$ of the plaintext, and a distribution of secrets $\mathcal{M}$
such that $\forall s \in \mathcal{M}: |s| = \lambda$.

The challenger produces a $\lambda$-bit key $(pk, sk) \leftarrow
\mathcal{K}(\lambda)$. The adversary is given $pk$, $\mathcal{V}$, $g$ and $f$.
The challenger then chooses a secret $s \leftarrow \mathcal{M}$.

The adversary is then allowed to run and make arbitrary calls to a reflection
oracle. The oracle is parameterized by $s$, the secret unknown to the
adversary.  For the reflection oracle call, the adversary chooses a reflection
string $r_i$ and sends it to the oracle. The oracle produces a noise string
$v_i \leftarrow \mathcal{V}$ and computes $m_i = f(s, r_i, v_i)$.  Subsequently
$m_i$ is encrypted as $c_i = \mathcal{E}_\kappa(m_i)$, and $c_i$ is sent back
to the adversary.

When the adversary decides to complete the game, they output a guess $y$. The
adversary is successful if $g(s) = y$.

Formally, let the public key adversarial game be defined as follows:

\begin{lstlisting}[texcl,mathescape]
def $\text{Game}_{\text{REF-SEC}}^{\mathcal{PE},\mathcal{A}}(\lambda, f, \mathcal{V}, \mathcal{M}, g)$:
    $(pk, sk) \leftarrow \mathcal{K}(\lambda)$
    $s \leftarrow \mathcal{M}$
    $y \leftarrow \mathcal{A}^{\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r)}(\lambda, f, \mathcal{V}, \mathcal{M}, g)$
    if $y = g(s)$:
        return 1
    else:
        return 0
\end{lstlisting}

Where the reflection oracle provided to the adversary is as follows:

\begin{lstlisting}[texcl,mathescape]
def $\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r)$:
    $v \leftarrow \mathcal{V}$
    $m = f(s, r, v)$
    $c \leftarrow \mathcal{E}_{pk}(m)$
    return $c$
\end{lstlisting}

Let the simulator game be defined as follows:

\begin{lstlisting}[texcl,mathescape]
def $\text{Game}_{\text{REF-SIM}}^{\mathcal{PE},\mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g)$:
    $y \leftarrow \mathcal{S}(f, \mathcal{V}, \mathcal{M}, g)$
    $s \leftarrow \mathcal{M}$
    if $y = g(s)$:
        return 1
    else:
        return 0
\end{lstlisting}

Let

\begin{equation*}
    \text{Adv}_{\mathcal{PE}, \mathcal{A}, \mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g)
    \defeq
    |Pr[\text{Game}_{\text{REF-SEC}}^{\mathcal{PE},\mathcal{A}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = 1]
    -
    Pr[\text{Game}_{\text{REF-SIM}}^{\mathcal{PE},\mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = 1]|.
\end{equation*}

The above game can be modified to deal with symmetric encryption. For this, the
choice of key is changed to be limited to a secret key instead of a public and
private key pair. The adversary is not given access to any key material.
Instead, the adversary is given access to an encryption oracle which encrypts a
given message using the secret key and returns the respective ciphertext, in
addition to the existing reflection oracle. Both oracles can be called an
arbitrary number of times by the challenger.

In the following proofs, we will assume that the game is played symmetrically.
As the attack does not pertain to the key exchange mechanism, all theorems can
be directly translated between the two versions of the game.

\subsection{Adaptive reflection security}\label{subsec:adaptiverefsec}

Given a polynomially computable rendering function $f(\cdot, \cdot, \cdot)$ and
a  noise distribution $\mathcal{V}$, a public-key encryption scheme
$\mathcal{PE}$ is \textit{reflection-secure} if:

\begin{equation*}
\forall \mathcal{M}:
\forall g:
\forall PPT \mathcal{A}:
\exists PPT \mathcal{S}:
\text{Adv}_{\mathcal{PE}, \mathcal{A}, \mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = negl(\lambda)
\end{equation*}

\section{The security of compression}\label{sec:comsec}

\subsection{Compression functions}\label{subsec:comfunc}

A compression function $Com$ is a polynomial polynomially reversible $1 - 1$
function that takes an input $x$ and outputs $y$. $x$ is a random variable that
follows the distribution $X$. $y = Com(x)$ will follow the
distribution $Com(X)$.  $E(|y|) / E(|x|) < 1$ is the metric that defines the
function's performance, where $E$ denotes expectation.

\subsection{Composing with compression}\label{subsec:comcompose}

We now shift our interest to algorithms which compose compression and
encryption.  Therefore, we treat the public-key encryption scheme above as a
composition of a compression and encryption algorithm:

\begin{equation*}
    \mathcal{E} = Enc \circ Com
\end{equation*}

$Com$ denotes a compression function as defined above, while $Enc$ denotes an
encryption function. We stress our important assumption that $Enc$ is defined
on $\{0, 1\}^*$ and not on some fixed-length input.

\subsection{Length monotonicity}\label{subsec:lenmonotone}

An important assumption for our attack is that the encryption function $Enc$ is
\textit{length monotonic}. Specifically,

\begin{equation*}
\begin{split}
\forall m_1, m_2 \in \{0, 1\}^*\\
\forall \kappa_1, \kappa_2 \in \mathcal{K}\\
|m_2| > |m_1|
\Rightarrow
|Enc_{\kappa_1}(m_2)| \geq |Enc_{\kappa_2}(m_1)|
\end{split}
\end{equation*}

If the last inequality becomes strict, we call the encryption function
\textit{strictly length monotonic}.

A practical instance of a length monotonic encryption function is AES.
Stream ciphers can be treated as strictly monotonic to the bit level.

\section{Property compressibility}\label{sec:propertycom}

Let $\mathcal{M}$ be a plaintext distribution and $Q(s)$ be a predicate on the
plaintext $s \in \mathcal{M}$. Let us use $\mathcal{M}_Q$ to denote the subset
of $\mathcal{M}$ restricted over the elements for which $Q$ holds
proportionally retaining measure and assuming $\mathcal{M}_Q \neq \emptyset$
and $\mathcal{M}_{\lnot Q} \neq \emptyset$.

For the specific property $Q$ and plaintext distribution $\mathcal{M}$, define:

\begin{equation*}
    \pi \defeq max(Pr[Q(s), s \leftarrow \mathcal{M}], 1 - Pr[Q(s), s \leftarrow \mathcal{M}])
\end{equation*}

Let $\mathcal{V}$ be a noise distribution from which a pair of noises
$\overbar{v} = (v_1, v_2) \leftarrow \mathcal{V}^2$ is drawn.  Let $\overbar{r}
= (r_1, r_2) \in \mathcal{M}^2$ be a reflection string pair, $Com$ be a
compression function, $f$ be a rendering function, and let $\alpha(\lambda)$ be
a non-negligible function.

The reflection pair $\overbar{r}$ \textit{detects} predicate $Q$ under
compression $Com$ rendered with rendering function $f$ over the secret
distribution $\mathcal{M}$ and the noise distribution $\mathcal{V}$ when:

\begin{align*}
    dct(Q, \overbar{r}, f, Com, \mathcal{M}, \mathcal{V})
    \defeq\\
    \exists \alpha \text{ non-negl}:\\
    Pr[|Com(f(s, r_1, v_1))| &< |Com(f(s, r_2, v_2))| \land\\
       |Com(f(s', r_1, v_1))| &> |Com(f(s', r_2, v_2))|,\\
        s &\leftarrow \mathcal{M}_Q,\\
        s' &\leftarrow \mathcal{M}_{\lnot Q},\\
        v_1 &\leftarrow \mathcal{V},\\
        v_2 &\leftarrow \mathcal{V}
       ]
    \geq
    \pi + \alpha(\lambda)
\end{align*}

We call $Q$ \textit{compression-detectable} if a pair $\overbar{r}$ exists,
such that:

\begin{equation*}
    \exists \overbar{r} = r_1, r_2 \in \mathcal{M}:
    dct(Q, \overbar{r}, f, Com, \mathcal{M}, \mathcal{V})
\end{equation*}

Furthermore we require that such a pair $\overbar{r}$ is polynomially
computable:

\begin{align*}
    \exists \text{PPT } \mathcal{O}_R:\\
    dct(Q, \overbar{r}, f, Com, \mathcal{M}, \mathcal{V}),\\
    \overbar{r} \leftarrow \mathcal{O}_R(Com, f, Q, \mathcal{M}, \mathcal{V})
\end{align*}

The compression-detectability property exists in all common compression
functions as long as $s$ and $r$ compress in the same context. We will
illustrate such examples later in this work.

\section{The BREACH model}\label{sec:breachmodel}
We now turn our attention to the BREACH attack specifically, which utilizes
the properties explored above, and we show that, under ideal modeling,
the above attack is instantiated when the TLS algorithms are in use.

In the BREACH model, we deal with a specific function $f$, property $Q$,
compression function $Com$, length-leaking $Enc$, and secret distribution
$\mathcal{M}$.

In the next paragraphs, we describe a simplified model of the attack that
lends itself to formal theoretical proofs, while abstracting away the complex
practical details of the attack pertaining to the networking and particularities
of the implementation that are of little significance to the cryptographic
formalisms presented here.

\subsection{The rendering context assumption}\label{subsec:rendering}

In the modern web, function $f$ represents a specific attack target, which
constitutes the renderer of a web page, given a specific secret, reflection,
and noise. Typically, $f$ will concatenate instances of the secret, the
reflection, and the noise, between some context strings which constitute the
static portions of the site.

We assume that $f$ outputs a concatenation of various instances of $s$, $r$,
and $v$ with arbitrary repetitions, in addition to concatenating with some
constant context whose position is independent of the values of $s, r, v$.  The
number of repetitions of $s, r, v$ are also independent of the values of $s, r,
v$.

Formally, assume that the symbols $\{\beta_1, \beta_2, \beta_3\}$ do not appear
in the alphabet of the secret.

Our assumptions for $f$ can be stated as follows. Let

\begin{equation*}
\begin{split}
\exists \mu \in \{0, 1, \beta_1, \beta_2, \beta_3\}^*\\
\exists u_1, v_1, u_2, v_2, u_3, v_3 \in \{0, 1, \beta_1, \beta_2, \beta_3\}^*\\
\mu = u_1 \beta_1 v_1 \land\\
\mu = u_2 \beta_2 v_2 \land\\
\mu = u_3 \beta_3 v_3 \land\\
\forall s, r, v \in \{0, 1\}^*\\
f(s, r, v) = Rep(Rep(Rep(\mu, \beta_1, s), \beta_2, r), \beta_3, v)
\end{split}
\end{equation*}

Where $Rep$ is the string replacement function:

\begin{align*}
Rep(\epsilon, \alpha, \beta) &\defeq \epsilon\\
Rep(\alpha:xs, \alpha, \beta) &\defeq \beta:Rep(xs, \alpha, \beta)\\
Rep(x:xs, \alpha, \beta) &\defeq x:Rep(xs, \alpha, \beta)
\end{align*}

Where $:$ denotes the concatenation of a symbol with a string.

We call $f$ functions that exhibit such behavior \textit{concatenative}.

\subsection{The compression function assumption}\label{subsec:comfuncassumption}

In BREACH, $Com$ is a variant of LZ77. In this compression algorithm,
repetitions of strings are well-compressed. In our ideal model, we examine a
simplified version of LZ77 which we describe in this paragraph.

Our version of LZ77 is not composed with a symbol-compressing algorithm such as
Huffman coding. Therefore, a way is needed to encode literal symbols and
compression symbols. The LZ77 algorithm treats the uncompressed text as a
series of bits. Let the plaintext be $p$ and its length be $n = |p|$. The LZ77
compression function needs to have an alphabet of 2 symbols for representing
literals (the bits $0$ and $1$ of the plaintext) as well as an alphabet of an
additional $n$ symbols for representing compression distances from $1$ to $n$
and lengths from $1$ to $n$ (the same symbol is used to represent a distance
and a length). This makes an alphabet of a total of $n + 2$ symbols which are
represented by bit sequences of exactly $\ceil{lg(n + 2)}$ bits each.

We first describe the decompression algorithm. At the beginning of the
compressed string, the number of characters in the uncompressed plaintext is
encoded in ASCII followed by the "$\$$" ASCII character as a separator. This
allows the decoder to compute how many bits are used to represent each symbol
in the compressed text.

Ordering these bit strings lexicographically, the first two bit strings will
correspond to the literal "$0$" and "$1$" bits of the plaintext. The next bit
strings will correspond to \textit{distance} bit sequences of values $1, 2,
\ldots, n$ respectively.

After the "$\$$" separator, an encoding of the plaintext is given. The encoding
can be decompressed by linearly reading it one character at a time. If a bit
sequence corresponding to a literal is given, this is decoded as the respective
literal bit of the plaintext. If a distance bit sequence of value $a$ is given,
then another distance bit sequence of value $b$ sequence follows.  Then $a$
must be less than or equal to the plaintext characters decoded so far, while
$b$ is arbitrary. This pair of values is decoded as follows. The decompressed
text beginning at a distance of $a$ bits behind the current position decoding
position and of length $b$ bits is taken into account. That text is then the
new decompressed plaintext which is appended to the existing decompressed
plaintext one bit at a time. This procedure can cause self-overlapping texts.
In the end, the decoded text must be $n$ bits long, otherwise the compression
is invalid.

\begin{lstlisting}[texcl,mathescape]
def $\text{LZ77}^{-1}(c)$:
    parts = c.split("$\$$")
    plaintextLength = parse_int(parts[0])
    bitsPerSymbol = $\ceil{lg(\text{plaintextLength}) + 2}$
    encodedPlaintext = stringToBinaryArray("".join(parts[1:]))

    plaintext = ''
    for i in range(0, len(encodedPlaintext), bitsPerSymbol):
        symbol = binaryToInt(encodedPlaintext[i:bitsPerSymbol])
        if symbol = 0:
            plaintext += '0'
        else if symbol = 1:
            plaintext += '1'
        else:
            distance = symbol - 1
            i += bitsPerSymbol
            length = int(encodedPlaintext[i:bitsPerSymbol])
            if distance > len(plaintext):
                return $\bot$
            while length:
                plaintext += plaintext[-distance]
                length -= 1
    if len(plaintext) != plaintextLength:
        return $\bot$
    else:
        return plaintext
\end{lstlisting}

Where negative and range array indexing and the $range$ function is as in
Python.

Our LZ77 compressor can then be described simply: It chooses the shortest in
bits compressed text, which, when decoded using the above algorithm yields the
desired plaintext.

% TODO: Prove that it is a compression function for some $\mathcal{M}$

\subsection{The full-text predicate assumption}\label{subsec:fulltextassumption}

The BREACH attack is a specific instance of reflection-based attacks in which
the $Q$ property pertains to a prefix of the secret. It asks "Does the secret
begin with such text?"

We require $X$ to be of compressible length,
i.e. the following equation must be satisfied:

\begin{equation*}
    |X| > \ceil{lg(f(X, X, \epsilon) + 2)}
\end{equation*}

In practical terms, this requires the secret that needs to be stolen to be at
least 3 bytes so that it is better compressed rather than represented as a
literal.

\subsection{BREACH prefixes are
compression-detectable}\label{subsec:breachprefix}

Let $startswith(v, s)$ be the $k$-length prefix checking predicate on a
$\lambda$-bit secret $s$:

\begin{equation*}
    startswith(v, s) \defeq \exists w: s = v w
\end{equation*}

\begin{lemma}

Let $f$ be a concatenative rendering function and let $Com = LZ77$. Then:

\begin{equation}
Pr[startswith(v, \cdot) \textrm{ compression-detectable under } f, Com] = \text{non-negl}(\lambda - k)
\end{equation}

Where the probability randomness is taken uniformly over all $k$-bit prefixes $v \in \{0, 1\}^k$.

\end{lemma}

\begin{proof}
?
\end{proof}

\section{The compression distinguishing attack}\label{sec:comattack}

\begin{lemma}[Compression attack]

Let $Com$ be a compression function, $f$ be a rendering function and $Q$ be a
plaintext predicate. If $Q$ is compression-detectable under a rendering of $f$
compressed with $Com$ under plaintext distribution $\mathcal{M}$, reflection
alphabet $\mathcal{M}$ and noise distribution $\mathcal{V}$, then:

\begin{align*}
\forall Enc:
\exists g:
\exists PPT \mathcal{A}:
\forall PPT \mathcal{S}:
\text{Adv}_{\mathcal{SE}(Enc, Com), \mathcal{A}, \mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = P(\lambda)
\end{align*}

Where $P$ is a non-negligible function and $Enc$ is strictly length-monotonic.

\end{lemma}

\begin{proof}

Let $g$ be the boolean function $Q$ on the plaintext. Define the adversary
$\mathcal{A}$ as follows:

\begin{lstlisting}[texcl,mathescape]
def $\mathcal{A}(Q, \mathcal{M}, y)$:
    $(r_1, r_2) \leftarrow \mathcal{O}_R(Com, f, Q, \mathcal{M}, \mathcal{V})$

    $l_1 = |\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r_1)|$
    $l_2 = |\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r_2)|$
<commit_msg>Use \alpha instead of p for non-negl advantage for consistency<commit_after>\documentclass[a4paper, 11 pt, conference]{article}
\usepackage[utf8]{inputenc}

\title{On the security of encryption and compression composition under reflection attacks}
\author{
<NAME>
\and
<NAME>
\and
<NAME>
}
\date{May 2016}

\usepackage{url}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage[xetex,colorlinks=true,linkcolor=blue,citecolor=green]{hyperref}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\let\oldemptyset\emptyset
\let\emptyset\varnothing

\newtheorem*{lemma}{Lemma}

\newcommand\defeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}

\begin{document}

\maketitle

\section{Abstract}\label{sec:abstract}
When compression is composed with encryption, unexpected vulnerabilities can
arise. Such vulnerabilities have been explored in practical attacks against TLS
such as CRIME, TIME, BREACH, and HEIST. We introduce an abstract theoretical
model for such attacks, the \textit{adaptive reflection security} model. We
discuss what properties common compression function have, such as the
\textit{compression-detectability} of predicates, and we show that all
length-preserving encryption schemes are vulnerable when composed with such
functions. Finally, we provide a modular scalable open-source production-grade
generic attack framework where these attacks are implemented in a robust
manner.

\section{Reflection security}\label{sec:refsec}

\subsection{Adaptive reflection game}\label{subsec:refsecgame}

Let $\mathcal{PE} = (\mathcal{K}, \mathcal{E}, \mathcal{D})$ be a public-key
encryption scheme, $\mathcal{A}$ be an adversary and $\mathcal{S}$ be a
simulator of $\mathcal{A}$.  The game
$\text{Game}_{\text{REF-SEC}}^{\mathcal{PE},\mathcal{A}}(\lambda,  f,
\mathcal{V}, g)$ is parameterized with a rendering function $f(\cdot, \cdot,
\cdot)$, a noise distribution $\mathcal{V}$, the security parameter $\lambda$,
some function $g$ of the plaintext, and a distribution of secrets $\mathcal{M}$
such that $\forall s \in \mathcal{M}: |s| = \lambda$.

The challenger produces a $\lambda$-bit key $(pk, sk) \leftarrow
\mathcal{K}(\lambda)$. The adversary is given $pk$, $\mathcal{V}$, $g$ and $f$.
The challenger then chooses a secret $s \leftarrow \mathcal{M}$.

The adversary is then allowed to run and make arbitrary calls to a reflection
oracle. The oracle is parameterized by $s$, the secret unknown to the
adversary.  For the reflection oracle call, the adversary chooses a reflection
string $r_i$ and sends it to the oracle. The oracle produces a noise string
$v_i \leftarrow \mathcal{V}$ and computes $m_i = f(s, r_i, v_i)$.  Subsequently
$m_i$ is encrypted as $c_i = \mathcal{E}_\kappa(m_i)$, and $c_i$ is sent back
to the adversary.

When the adversary decides to complete the game, they output a guess $y$. The
adversary is successful if $g(s) = y$.

Formally, let the public key adversarial game be defined as follows:

\begin{lstlisting}[texcl,mathescape]
def $\text{Game}_{\text{REF-SEC}}^{\mathcal{PE},\mathcal{A}}(\lambda, f, \mathcal{V}, \mathcal{M}, g)$:
    $(pk, sk) \leftarrow \mathcal{K}(\lambda)$
    $s \leftarrow \mathcal{M}$
    $y \leftarrow \mathcal{A}^{\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r)}(\lambda, f, \mathcal{V}, \mathcal{M}, g)$
    if $y = g(s)$:
        return 1
    else:
        return 0
\end{lstlisting}

Where the reflection oracle provided to the adversary is as follows:

\begin{lstlisting}[texcl,mathescape]
def $\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r)$:
    $v \leftarrow \mathcal{V}$
    $m = f(s, r, v)$
    $c \leftarrow \mathcal{E}_{pk}(m)$
    return $c$
\end{lstlisting}

Let the simulator game be defined as follows:

\begin{lstlisting}[texcl,mathescape]
def $\text{Game}_{\text{REF-SIM}}^{\mathcal{PE},\mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g)$:
    $y \leftarrow \mathcal{S}(f, \mathcal{V}, \mathcal{M}, g)$
    $s \leftarrow \mathcal{M}$
    if $y = g(s)$:
        return 1
    else:
        return 0
\end{lstlisting}

Let

\begin{equation*}
    \text{Adv}_{\mathcal{PE}, \mathcal{A}, \mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g)
    \defeq
    |Pr[\text{Game}_{\text{REF-SEC}}^{\mathcal{PE},\mathcal{A}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = 1]
    -
    Pr[\text{Game}_{\text{REF-SIM}}^{\mathcal{PE},\mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = 1]|.
\end{equation*}

The above game can be modified to deal with symmetric encryption. For this, the
choice of key is changed to be limited to a secret key instead of a public and
private key pair. The adversary is not given access to any key material.
Instead, the adversary is given access to an encryption oracle which encrypts a
given message using the secret key and returns the respective ciphertext, in
addition to the existing reflection oracle. Both oracles can be called an
arbitrary number of times by the challenger.

In the following proofs, we will assume that the game is played symmetrically.
As the attack does not pertain to the key exchange mechanism, all theorems can
be directly translated between the two versions of the game.

\subsection{Adaptive reflection security}\label{subsec:adaptiverefsec}

Given a polynomially computable rendering function $f(\cdot, \cdot, \cdot)$ and
a  noise distribution $\mathcal{V}$, a public-key encryption scheme
$\mathcal{PE}$ is \textit{reflection-secure} if:

\begin{equation*}
\forall \mathcal{M}:
\forall g:
\forall PPT \mathcal{A}:
\exists PPT \mathcal{S}:
\text{Adv}_{\mathcal{PE}, \mathcal{A}, \mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = negl(\lambda)
\end{equation*}

\section{The security of compression}\label{sec:comsec}

\subsection{Compression functions}\label{subsec:comfunc}

A compression function $Com$ is a polynomial polynomially reversible $1 - 1$
function that takes an input $x$ and outputs $y$. $x$ is a random variable that
follows the distribution $X$. $y = Com(x)$ will follow the
distribution $Com(X)$.  $E(|y|) / E(|x|) < 1$ is the metric that defines the
function's performance, where $E$ denotes expectation.

\subsection{Composing with compression}\label{subsec:comcompose}

We now shift our interest to algorithms which compose compression and
encryption.  Therefore, we treat the public-key encryption scheme above as a
composition of a compression and encryption algorithm:

\begin{equation*}
    \mathcal{E} = Enc \circ Com
\end{equation*}

$Com$ denotes a compression function as defined above, while $Enc$ denotes an
encryption function. We stress our important assumption that $Enc$ is defined
on $\{0, 1\}^*$ and not on some fixed-length input.

\subsection{Length monotonicity}\label{subsec:lenmonotone}

An important assumption for our attack is that the encryption function $Enc$ is
\textit{length monotonic}. Specifically,

\begin{equation*}
\begin{split}
\forall m_1, m_2 \in \{0, 1\}^*\\
\forall \kappa_1, \kappa_2 \in \mathcal{K}\\
|m_2| > |m_1|
\Rightarrow
|Enc_{\kappa_1}(m_2)| \geq |Enc_{\kappa_2}(m_1)|
\end{split}
\end{equation*}

If the last inequality becomes strict, we call the encryption function
\textit{strictly length monotonic}.

A practical instance of a length monotonic encryption function is AES.
Stream ciphers can be treated as strictly monotonic to the bit level.

\section{Property compressibility}\label{sec:propertycom}

Let $\mathcal{M}$ be a plaintext distribution and $Q(s)$ be a predicate on the
plaintext $s \in \mathcal{M}$. Let us use $\mathcal{M}_Q$ to denote the subset
of $\mathcal{M}$ restricted over the elements for which $Q$ holds
proportionally retaining measure and assuming $\mathcal{M}_Q \neq \emptyset$
and $\mathcal{M}_{\lnot Q} \neq \emptyset$.

For the specific property $Q$ and plaintext distribution $\mathcal{M}$, define:

\begin{equation*}
    \pi \defeq max(Pr[Q(s), s \leftarrow \mathcal{M}], 1 - Pr[Q(s), s \leftarrow \mathcal{M}])
\end{equation*}

Let $\mathcal{V}$ be a noise distribution from which a pair of noises
$\overbar{v} = (v_1, v_2) \leftarrow \mathcal{V}^2$ is drawn.  Let $\overbar{r}
= (r_1, r_2) \in \mathcal{M}^2$ be a reflection string pair, $Com$ be a
compression function, $f$ be a rendering function, and let $\alpha(\lambda)$ be
a non-negligible function.

The reflection pair $\overbar{r}$ \textit{detects} predicate $Q$ under
compression $Com$ rendered with rendering function $f$ over the secret
distribution $\mathcal{M}$ and the noise distribution $\mathcal{V}$ when:

\begin{align*}
    dct(Q, \overbar{r}, f, Com, \mathcal{M}, \mathcal{V})
    \defeq\\
    \exists \alpha \text{ non-negl}:\\
    Pr[|Com(f(s, r_1, v_1))| &< |Com(f(s, r_2, v_2))| \land\\
       |Com(f(s', r_1, v_1))| &> |Com(f(s', r_2, v_2))|,\\
        s &\leftarrow \mathcal{M}_Q,\\
        s' &\leftarrow \mathcal{M}_{\lnot Q},\\
        v_1 &\leftarrow \mathcal{V},\\
        v_2 &\leftarrow \mathcal{V}
       ]
    \geq
    \pi + \alpha(\lambda)
\end{align*}

We call $Q$ \textit{compression-detectable} if a pair $\overbar{r}$ exists,
such that:

\begin{equation*}
    \exists \overbar{r} = r_1, r_2 \in \mathcal{M}:
    dct(Q, \overbar{r}, f, Com, \mathcal{M}, \mathcal{V})
\end{equation*}

Furthermore we require that such a pair $\overbar{r}$ is polynomially
computable:

\begin{align*}
    \exists \text{PPT } \mathcal{O}_R:\\
    dct(Q, \overbar{r}, f, Com, \mathcal{M}, \mathcal{V}),\\
    \overbar{r} \leftarrow \mathcal{O}_R(Com, f, Q, \mathcal{M}, \mathcal{V})
\end{align*}

The compression-detectability property exists in all common compression
functions as long as $s$ and $r$ compress in the same context. We will
illustrate such examples later in this work.

\section{The BREACH model}\label{sec:breachmodel}
We now turn our attention to the BREACH attack specifically, which utilizes
the properties explored above, and we show that, under ideal modeling,
the above attack is instantiated when the TLS algorithms are in use.

In the BREACH model, we deal with a specific function $f$, property $Q$,
compression function $Com$, length-leaking $Enc$, and secret distribution
$\mathcal{M}$.

In the next paragraphs, we describe a simplified model of the attack that
lends itself to formal theoretical proofs, while abstracting away the complex
practical details of the attack pertaining to the networking and particularities
of the implementation that are of little significance to the cryptographic
formalisms presented here.

\subsection{The rendering context assumption}\label{subsec:rendering}

In the modern web, function $f$ represents a specific attack target, which
constitutes the renderer of a web page, given a specific secret, reflection,
and noise. Typically, $f$ will concatenate instances of the secret, the
reflection, and the noise, between some context strings which constitute the
static portions of the site.

We assume that $f$ outputs a concatenation of various instances of $s$, $r$,
and $v$ with arbitrary repetitions, in addition to concatenating with some
constant context whose position is independent of the values of $s, r, v$.  The
number of repetitions of $s, r, v$ are also independent of the values of $s, r,
v$.

Formally, assume that the symbols $\{\beta_1, \beta_2, \beta_3\}$ do not appear
in the alphabet of the secret.

Our assumptions for $f$ can be stated as follows. Let

\begin{equation*}
\begin{split}
\exists \mu \in \{0, 1, \beta_1, \beta_2, \beta_3\}^*\\
\exists u_1, v_1, u_2, v_2, u_3, v_3 \in \{0, 1, \beta_1, \beta_2, \beta_3\}^*\\
\mu = u_1 \beta_1 v_1 \land\\
\mu = u_2 \beta_2 v_2 \land\\
\mu = u_3 \beta_3 v_3 \land\\
\forall s, r, v \in \{0, 1\}^*\\
f(s, r, v) = Rep(Rep(Rep(\mu, \beta_1, s), \beta_2, r), \beta_3, v)
\end{split}
\end{equation*}

Where $Rep$ is the string replacement function:

\begin{align*}
Rep(\epsilon, \alpha, \beta) &\defeq \epsilon\\
Rep(\alpha:xs, \alpha, \beta) &\defeq \beta:Rep(xs, \alpha, \beta)\\
Rep(x:xs, \alpha, \beta) &\defeq x:Rep(xs, \alpha, \beta)
\end{align*}

Where $:$ denotes the concatenation of a symbol with a string.

We call $f$ functions that exhibit such behavior \textit{concatenative}.

\subsection{The compression function assumption}\label{subsec:comfuncassumption}

In BREACH, $Com$ is a variant of LZ77. In this compression algorithm,
repetitions of strings are well-compressed. In our ideal model, we examine a
simplified version of LZ77 which we describe in this paragraph.

Our version of LZ77 is not composed with a symbol-compressing algorithm such as
Huffman coding. Therefore, a way is needed to encode literal symbols and
compression symbols. The LZ77 algorithm treats the uncompressed text as a
series of bits. Let the plaintext be $p$ and its length be $n = |p|$. The LZ77
compression function needs to have an alphabet of 2 symbols for representing
literals (the bits $0$ and $1$ of the plaintext) as well as an alphabet of an
additional $n$ symbols for representing compression distances from $1$ to $n$
and lengths from $1$ to $n$ (the same symbol is used to represent a distance
and a length). This makes an alphabet of a total of $n + 2$ symbols which are
represented by bit sequences of exactly $\ceil{lg(n + 2)}$ bits each.

We first describe the decompression algorithm. At the beginning of the
compressed string, the number of characters in the uncompressed plaintext is
encoded in ASCII followed by the "$\$$" ASCII character as a separator. This
allows the decoder to compute how many bits are used to represent each symbol
in the compressed text.

Ordering these bit strings lexicographically, the first two bit strings will
correspond to the literal "$0$" and "$1$" bits of the plaintext. The next bit
strings will correspond to \textit{distance} bit sequences of values $1, 2,
\ldots, n$ respectively.

After the "$\$$" separator, an encoding of the plaintext is given. The encoding
can be decompressed by linearly reading it one character at a time. If a bit
sequence corresponding to a literal is given, this is decoded as the respective
literal bit of the plaintext. If a distance bit sequence of value $a$ is given,
then another distance bit sequence of value $b$ sequence follows.  Then $a$
must be less than or equal to the plaintext characters decoded so far, while
$b$ is arbitrary. This pair of values is decoded as follows. The decompressed
text beginning at a distance of $a$ bits behind the current position decoding
position and of length $b$ bits is taken into account. That text is then the
new decompressed plaintext which is appended to the existing decompressed
plaintext one bit at a time. This procedure can cause self-overlapping texts.
In the end, the decoded text must be $n$ bits long, otherwise the compression
is invalid.

\begin{lstlisting}[texcl,mathescape]
def $\text{LZ77}^{-1}(c)$:
    parts = c.split("$\$$")
    plaintextLength = parse_int(parts[0])
    bitsPerSymbol = $\ceil{lg(\text{plaintextLength}) + 2}$
    encodedPlaintext = stringToBinaryArray("".join(parts[1:]))

    plaintext = ''
    for i in range(0, len(encodedPlaintext), bitsPerSymbol):
        symbol = binaryToInt(encodedPlaintext[i:bitsPerSymbol])
        if symbol = 0:
            plaintext += '0'
        else if symbol = 1:
            plaintext += '1'
        else:
            distance = symbol - 1
            i += bitsPerSymbol
            length = int(encodedPlaintext[i:bitsPerSymbol])
            if distance > len(plaintext):
                return $\bot$
            while length:
                plaintext += plaintext[-distance]
                length -= 1
    if len(plaintext) != plaintextLength:
        return $\bot$
    else:
        return plaintext
\end{lstlisting}

Where negative and range array indexing and the $range$ function is as in
Python.

Our LZ77 compressor can then be described simply: It chooses the shortest in
bits compressed text, which, when decoded using the above algorithm yields the
desired plaintext.

% TODO: Prove that it is a compression function for some $\mathcal{M}$

\subsection{The full-text predicate assumption}\label{subsec:fulltextassumption}

The BREACH attack is a specific instance of reflection-based attacks in which
the $Q$ property pertains to a prefix of the secret. It asks "Does the secret
begin with such text?"

We require $X$ to be of compressible length,
i.e. the following equation must be satisfied:

\begin{equation*}
    |X| > \ceil{lg(f(X, X, \epsilon) + 2)}
\end{equation*}

In practical terms, this requires the secret that needs to be stolen to be at
least 3 bytes so that it is better compressed rather than represented as a
literal.

\subsection{BREACH prefixes are
compression-detectable}\label{subsec:breachprefix}

Let $startswith(v, s)$ be the $k$-length prefix checking predicate on a
$\lambda$-bit secret $s$:

\begin{equation*}
    startswith(v, s) \defeq \exists w: s = v w
\end{equation*}

\begin{lemma}

Let $f$ be a concatenative rendering function and let $Com = LZ77$. Then:

\begin{equation}
Pr[startswith(v, \cdot) \textrm{ compression-detectable under } f, Com] = \text{non-negl}(\lambda - k)
\end{equation}

Where the probability randomness is taken uniformly over all $k$-bit prefixes $v \in \{0, 1\}^k$.

\end{lemma}

\begin{proof}
?
\end{proof}

\section{The compression distinguishing attack}\label{sec:comattack}

\begin{lemma}[Compression attack]

Let $Com$ be a compression function, $f$ be a rendering function and $Q$ be a
plaintext predicate. If $Q$ is compression-detectable under a rendering of $f$
compressed with $Com$ under plaintext distribution $\mathcal{M}$, reflection
alphabet $\mathcal{M}$ and noise distribution $\mathcal{V}$, then:

\begin{align*}
    \forall Enc:\\
    \exists g:\\
    \exists PPT \mathcal{A}:\\
    \forall PPT \mathcal{S}:\\
    \text{Adv}_{\mathcal{SE}(Enc, Com), \mathcal{A}, \mathcal{S}}(\lambda, f, \mathcal{V}, \mathcal{M}, g) = \alpha(\lambda)
\end{align*}

Where $\alpha$ is a non-negligible function and $Enc$ is strictly
length-monotonic.

\end{lemma}

\begin{proof}

Let $g$ be the boolean function $Q$ on the plaintext. Define the adversary
$\mathcal{A}$ as follows:

\begin{lstlisting}[texcl,mathescape]
def $\mathcal{A}(Q, \mathcal{M}, y)$:
    $(r_1, r_2) \leftarrow \mathcal{O}_R(Com, f, Q, \mathcal{M}, \mathcal{V})$

    $l_1 = |\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r_1)|$
    $l_2 = |\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r_2)|$

{'fraction_non_alphanumeric': 0.12484759814679347, 'fraction_numerical': 0.007640412907420954, 'mean_word_length': 4.263833428408443, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 17, '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': '5959438', 'n_tokens_mistral': 11699, 'n_tokens_neox': 11182, 'n_words': 4515}