<commit_before>\section{Compression attacks}\label{sec:comattack}

\subsection{One-shot attack}

\begin{lemma}[Compression attack]

Let $\textrm{Com}$ be a compression function, $\textrm{Enc}$ be a strictly length-monotonic
encryption function, $f$ be a rendering function and $Q$ be a plaintext
predicate detectable with non-negligible advantage $\alpha$ over plaintext
distribution $\mathcal{M}$ and noise distribution $\mathcal{V}$.

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

\end{lemma}

The non-negligible advantage is achieved by the following adversary:

\begin{lstlisting}[texcl,mathescape,basicstyle=\small]
def $\mathcal{A}(Q, \mathcal{M}, y)$:
    $(r_1, r_2) \leftarrow \mathcal{O}_R(\kappa, 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)|$

    if $l_1 < l_2$:
        return True
    else:
        return False
\end{lstlisting}

For a full proof, see Appendix A.

\subsection{Amplified attack}\label{subsec:amplification}

We can now amplify the attack to achieve a better probability of success by a small modification in our adversary.
The amplification is parameterized by an odd parameter $k$.

Let the amplification adversary be defined as follows:

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

    $low = 0$
    $high = 0$

    for $i$ = $0$ to $k$:
        $l_1 = |\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r_1)|$
        $l_2 = |\text{Reflect}^{\mathcal{E}_{pk}, \mathcal{V}}_s(r_2)|$

        if $l_1 < l_2$:
            $low = low + 1$
        else:
            $high = high + 1$

    if $low > high$:
        return True
    else:
        return False
\end{lstlisting}

\begin{lemma}[Amplification]

Under the assumptions of the Compression Attack Theorem against $f, \textrm{Com}$
and compression-detectable predicate $Q$ with non-negligible
detectability margin $\alpha(\lambda)$,
the amplified adversary achieves an arbitrarily large advantage
against a non-negligible subset of elements, the
\textit{amplifiable elements} distinguished by predicate $Amp$.
\begin{align*}
    \forall \textrm{Enc}:
    \exists g:\\
    \exists PPT \mathcal{A}:
    \forall PPT \mathcal{S}:\\
    \exists Amp:
    \exists B \text{ non-negl}:
    \exists C \text{ negl}:\\
    \Pr_{s \leftarrow \mathcal{M}}[Amp(s)] = B(\lambda) \land\\
    \text{Adv}_{\mathcal{SE}(\textrm{Enc}, \textrm{Com}), \mathcal{A}, \mathcal{S}_{Amp}}
    (\lambda, f, \mathcal{V}, \mathcal{M}, g) = 1 - \pi - C(k)
\end{align*}

\end{lemma}

The complete proof can be found in Appendix A.

\subsection{Reflection game instances}
Having established our theoretical model, it is important to explain how
practical attacks can be described as instances of this model. For this case we
describe BREACH, CRIME, and TIME in the context of the reflection security model.

These attack share some common functionality features that we describe, before
elaborating on each one separately.

The encryption algorithm and key are included in the implementation of the TLS
protocol. In most real-world systems, the encryption algorithm is AES and the
key is typically 128 or 256 bits. In relation to the reflection game, this is
represented by the $\textrm{Enc}$ and the $Gen$ functions, whereas the AES
key used for the TLS application data is $sk$. The ciphertext $c$ is the
encrypted output of the encryption function.

The support of the distribution $\mathcal{M}$ contains all strings that consist
of a known prefix concatenated with each character in the secret's alphabet. The
secret's alphabet is in typically the digits and letters of the English alphabet.
In order to bootstrap the attack, the adversary already knows this prefix of the
secret.

The adversary issues consecutive requests, each containing a candidate string
drawn from $\mathcal{M}$ as the reflection. The secret also exists in the
support of $\mathcal{M}$ so one of the reflections is bound to match it. The
goal of the adversary is to recognize which reflection that is.

The noise distribution $\mathcal{V}$ contains strings with the same alphabet as
$\mathcal{M}$. Noise data is generally unpredictable, so the adversary issues
multiple requests per reflection candidate in order to statistically bypass the
margin of error that noise introduces in the analysis. This is a practical
example of the amplified attack described in section \ref{subsec:amplification}.
We describe how statistical methods can be used to implement this in practice in
section \ref{subsec:blockalign}.

The reflection $r$ consists of the known prefix concatenated with a single
character. In cases when $r$ matches a prefix of the secret $s$, the probability
of this prefix in $c$ will be greater than in cases of no match.
Given this interdependence between the secret and the reflection the predicate
$Q$ of the secret is compression detectable by the reflection set. The
reflection vector $\bar{r}$ contains strings $r_1, r_2, ...$, where $r_i$
consists of the known prefix concatenated with character $i$ in the secret's
alphabet.

The predicate $Q$ in this case checks whether the prefix of $s$ is equal to a
certain value. Specifically, when $Q$ is detectable, the adversary is able to
find if the length of $c$ containing the reflection $r_1$ is less than
$c$ which contains the reflection $r_2$. If that is the case, then
interdependence and compression idealness lead the adversary to conclude that
$r_1$ is a prefix of $s$, thus decrypting the character in the secret that
follows the known prefix.

\subsubsection{BREACH}
As we described in section \ref{subsec:example}, the adversary that issues the
BREACH attack fulfills some basic assumptions. He has found a vulnerable
endpoint in the web service under attack which allows him to inject a chosen
reflection in the response data along with a secret. He is also able to issue an
arbitrary amount of requests from the user's browser to said endpoint and
observe the encrypted network traffic.

The challenger, in terms of the reflection game, is the server that handles the
user's request.

The secret $s$ is a predefined data element in the response that was generated
by either a user or the service. In the original BREACH paper, $s$ is a CSRF
token.

The reflection oracle constructs the encrypted responses by concatenating the
secret, the reflection, noise and static data and rendering them with function
$f$, compressing them with compression function $\textrm{Com}$ and encrypting them with
the encryption algorithm $\textrm{Enc}$. The reflection oracle in this case is the web
application framework that implements the encryption function and the underlying
web server that contains modules for compression and encryption. The final part
of the oracle, sending the ciphertext $c_i$ to the adversary, is impemented by
the Man-in-the-Middle module that gives the adversary the ability to monitor the
user's network traffic.

The rendering function $f$ is the backend that generates the HTML response code.
The HTML contains the secret, the reflection, and the noise. All will be
compressed by the compression algorithm used by the web service, the most
commonly used being the DEFLATE algorithm. The DEFLATE algorithm is the
$\textrm{Com}$ function in terms of the reflection game.

\subsubsection{CRIME}
The CRIME attack is a similar instance of the reflection game as BREACH, but
with a few key differences.

The main difference is that CRIME targets HTTP requests instead of responses. In
this case, the challenger and the oracle exist in the user's browser. The secret
$s$ is a Cookie that is included in the request, whereas the reflection $r$ is
the same GET parameter described in BREACH. In this case, the need for
reflection exists in the requests, so the responses from the target endpoint are
ignored and they need not contain the reflection.

The rendering function $f$ is the browser's function that crafts the request
payload. The compression function $\textrm{Com}$ and encryption function
$\textrm{Enc}$ are again
the DEFLATE algorithm and the TLS protocol.

The rest of the parameters are the same as in BREACH. The adversary follows the
same strategy in order to craft the reflections $r_1$ and $r_2$, compare
different size lengths of requests that contain each one along with $s$ and
decrypt a prefix of $s$.

\subsubsection{TIME}
The TIME attack's novelty is the absence of a MitM module and the usage of a
time side-channel. In this case, the adversary does not have access to the
length, as is the case in BREACH, but the timings of the responses.

This attack measures the time until the response is complete. This time value
depends on the response length, since a longer response results in slower
network transmission.

TIME as a reflection game instance is very close to BREACH. The main difference
is found in the oracle. In TIME the last part of the oracle, sending the
ciphertext $c$ to the adversary, is implemented in the same script that issues the
requests. Also the oracle does not send $c$ to the adversary, but
rather an approximation of $\rvert c \rvert$.
<commit_msg>Remove noise references from compression attacks section<commit_after>\section{Compression attacks}\label{sec:comattack}

\subsection{One-shot attack}

\begin{lemma}[Compression attack]

Let $\textrm{Com}$ be a compression function, $\textrm{Enc}$ be a strictly length-monotonic
encryption function, $f$ be a rendering function and $Q$ be a plaintext
predicate detectable with non-negligible advantage $\alpha$ over plaintext
distribution $\mathcal{M}$.

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

\end{lemma}

The non-negligible advantage is achieved by the following adversary:

\begin{lstlisting}[texcl,mathescape,basicstyle=\small]
def $\mathcal{A}(Q, \mathcal{M}, y)$:
    $(r_1, r_2) \leftarrow \mathcal{O}_R(\kappa, Q, \mathcal{M})$

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

    if $l_1 < l_2$:
        return True
    else:
        return False
\end{lstlisting}

For a full proof, see Appendix A.

\subsection{Amplified attack}\label{subsec:amplification}

We can now amplify the attack to achieve a better probability of success by a small modification in our adversary.
The amplification is parameterized by an odd parameter $k$.

Let the amplification adversary be defined as follows:

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

    $low = 0$
    $high = 0$

    for $i$ = $0$ to $k$:
        $l_1 = |\text{Reflect}^{\mathcal{E}_{pk}}_s(r_1)|$
        $l_2 = |\text{Reflect}^{\mathcal{E}_{pk}}_s(r_2)|$

        if $l_1 < l_2$:
            $low = low + 1$
        else:
            $high = high + 1$

    if $low > high$:
        return True
    else:
        return False
\end{lstlisting}

\begin{lemma}[Amplification]

Under the assumptions of the Compression Attack Theorem against $f, \textrm{Com}$
and compression-detectable predicate $Q$ with non-negligible
detectability margin $\alpha(\lambda)$,
the amplified adversary achieves an arbitrarily large advantage
against a non-negligible subset of elements, the
\textit{amplifiable elements} distinguished by predicate $Amp$.
\begin{align*}
    \forall \textrm{Enc}:
    \exists g:\\
    \exists PPT \mathcal{A}:
    \forall PPT \mathcal{S}:\\
    \exists Amp:
    \exists B \text{ non-negl}:
    \exists C \text{ negl}:\\
    \Pr_{s \leftarrow \mathcal{M}}[Amp(s)] = B(\lambda) \land\\
    \text{Adv}_{\mathcal{SE}(\textrm{Enc}, \textrm{Com}), \mathcal{A}, \mathcal{S}_{Amp}}
    (\lambda, f, \mathcal{M}, g) = 1 - \pi - C(k)
\end{align*}

\end{lemma}

The complete proof can be found in Appendix A.

\subsection{Reflection game instances}
Having established our theoretical model, it is important to explain how
practical attacks can be described as instances of this model. For this case we
describe BREACH, CRIME, and TIME in the context of the reflection security model.

These attack share some common functionality features that we describe, before
elaborating on each one separately.

The encryption algorithm and key are included in the implementation of the TLS
protocol. In most real-world systems, the encryption algorithm is AES and the
key is typically 128 or 256 bits. In relation to the reflection game, this is
represented by the $\textrm{Enc}$ and the $Gen$ functions, whereas the AES
key used for the TLS application data is $sk$. The ciphertext $c$ is the
encrypted output of the encryption function.

The support of the distribution $\mathcal{M}$ contains all strings that consist
of a known prefix concatenated with each character in the secret's alphabet. The
secret's alphabet is in typically the digits and letters of the English alphabet.
In order to bootstrap the attack, the adversary already knows this prefix of the
secret.

The adversary issues consecutive requests, each containing a candidate string
drawn from $\mathcal{M}$ as the reflection. The secret also exists in the
support of $\mathcal{M}$ so one of the reflections is bound to match it. The
goal of the adversary is to recognize which reflection that is.

The reflection $r$ consists of the known prefix concatenated with a single
character. In cases when $r$ matches a prefix of the secret $s$, the probability
of this prefix in $c$ will be greater than in cases of no match.
Given this interdependence between the secret and the reflection the predicate
$Q$ of the secret is compression detectable by the reflection set. The
reflection vector $\bar{r}$ contains strings $r_1, r_2, ...$, where $r_i$
consists of the known prefix concatenated with character $i$ in the secret's
alphabet.

The predicate $Q$ in this case checks whether the prefix of $s$ is equal to a
certain value. Specifically, when $Q$ is detectable, the adversary is able to
find if the length of $c$ containing the reflection $r_1$ is less than
$c$ which contains the reflection $r_2$. If that is the case, then
interdependence and compression idealness lead the adversary to conclude that
$r_1$ is a prefix of $s$, thus decrypting the character in the secret that
follows the known prefix.

\subsubsection{BREACH}
As we described in section \ref{subsec:example}, the adversary that issues the
BREACH attack fulfills some basic assumptions. He has found a vulnerable
endpoint in the web service under attack which allows him to inject a chosen
reflection in the response data along with a secret. He is also able to issue an
arbitrary amount of requests from the user's browser to said endpoint and
observe the encrypted network traffic.

The challenger, in terms of the reflection game, is the server that handles the
user's request.

The secret $s$ is a predefined data element in the response that was generated
by either a user or the service. In the original BREACH paper, $s$ is a CSRF
token.

The reflection oracle constructs the encrypted responses by concatenating the
secret, the reflection, and static data and rendering them with function
$f$, compressing them with compression function $\textrm{Com}$ and encrypting them with
the encryption algorithm $\textrm{Enc}$. The reflection oracle in this case is the web
application framework that implements the encryption function and the underlying
web server that contains modules for compression and encryption. The final part
of the oracle, sending the ciphertext $c_i$ to the adversary, is impemented by
the Man-in-the-Middle module that gives the adversary the ability to monitor the
user's network traffic.

The rendering function $f$ is the backend that generates the HTML response code.
The HTML contains the secret, and the reflection. All will be compressed by the
compression algorithm used by the web service, the most commonly used being the
DEFLATE algorithm. The DEFLATE algorithm is the $\textrm{Com}$ function in terms
of the reflection game.

\subsubsection{CRIME}
The CRIME attack is a similar instance of the reflection game as BREACH, but
with a few key differences.

The main difference is that CRIME targets HTTP requests instead of responses. In
this case, the challenger and the oracle exist in the user's browser. The secret
$s$ is a Cookie that is included in the request, whereas the reflection $r$ is
the same GET parameter described in BREACH. In this case, the need for
reflection exists in the requests, so the responses from the target endpoint are
ignored and they need not contain the reflection.

The rendering function $f$ is the browser's function that crafts the request
payload. The compression function $\textrm{Com}$ and encryption function
$\textrm{Enc}$ are again
the DEFLATE algorithm and the TLS protocol.

The rest of the parameters are the same as in BREACH. The adversary follows the
same strategy in order to craft the reflections $r_1$ and $r_2$, compare
different size lengths of requests that contain each one along with $s$ and
decrypt a prefix of $s$.

\subsubsection{TIME}
The TIME attack's novelty is the absence of a MitM module and the usage of a
time side-channel. In this case, the adversary does not have access to the
length, as is the case in BREACH, but the timings of the responses.

This attack measures the time until the response is complete. This time value
depends on the response length, since a longer response results in slower
network transmission.

TIME as a reflection game instance is very close to BREACH. The main difference
is found in the oracle. In TIME the last part of the oracle, sending the
ciphertext $c$ to the adversary, is implemented in the same script that issues the
requests. Also the oracle does not send $c$ to the adversary, but
rather an approximation of $\rvert c \rvert$.

{'fraction_non_alphanumeric': 0.08128452290696415, 'fraction_numerical': 0.0037907505686125853, 'mean_word_length': 4.264253135689851, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, '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': '3302638', 'n_tokens_mistral': 5141, 'n_tokens_neox': 4884, 'n_words': 2573}