<commit_before>\documentclass[conference, letterpaper, 10pt]{IEEEtran}

\usepackage[utf8]{inputenc}

\title{On the security of encryption and compression composition under reflection attacks}

%\author{
%    Anonymized submission
%}

 \author{
     \IEEEauthorblockN{<NAME>}
     \IEEEauthorblockA{University of Athens \\
     <EMAIL>}
     \and
     \IEEEauthorblockN{<NAME>}
     \IEEEauthorblockA{University of Edinburgh\\
     <EMAIL>}
     \and
     \IEEEauthorblockA{<NAME>}
     \IEEEauthorblockA{University of Athens \\
     <EMAIL>}
 }

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

\usepackage{cite}

\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

\begin{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, and BREACH, even after TLS 1.3. We introduce an abstract
theoretical cryptographic model for such attacks, the \textit{adaptive
reflection security} game with the relevant security definitions. We propose a
model for \textit{compression idealness} and experimentally show that typical compression
functions expose partially ideal behavior. We then experimentally show that
typical plaintexts used in practice follow an interdependent joint distribution,
our stronger notion of dependent joint distributions. Based on these two
properties, we prove that \textit{compression-detectability} of predicates
arises, the ability to extract a predicate of the plaintext using reflection.
We then prove that all length-preserving encryption schemes are insecure when
composed with such functions. Our attack model describes two modes of attack,
one-shot and amplified. For the case of the BREACH attack, we discuss how it can
be described as an instance of our theoretical model. Motivated by the lack of
production-grade testing tools, we provide a modular scalable open-source
generic attack framework that implements compression side-channel attacks in a
robust manner. Finally, we propose a novel defense protocol, \textit{context
hiding}, that effectively eliminates the threat these attacks pose. This
protocol modifies the plaintext joint distribution so as to remove the
interdependence, thereby mitigating the problem.
\end{abstract}

\section{Introduction}\label{sec:prev}

Compression and encryption composition has caused serious security problems
in protocols such as TLS \cite{c15} over the years. These
include attacks like CRIME \cite{c1}, TIME \cite{c2}, and BREACH \cite{c3}.

However, the theoretical models for these classes of attacks has been limited.
The compression side-channel attack was first studied by Kelsey \cite{c4} in 2002.
Kelley and Tamassia\cite{c5}  discuss the notion of \textit{entropy-restricted} semantic
security, but this only models the case where two secrets compress to the same
length, and so it is difficult to capture practical techniques used in attacks
such as BREACH.

Alawatugoda etc. \cite{c6} introduce a model for \textit{Cookie recovery},
\textit{Random cookie indistinguishability}, as well as \textit{Chosen cookie indistinguishability}.
Nevertheless, their security models are limited in classes of rendering functions
that are very specific. In their models, the attacker is able to directly influence
the output of the rendering function through concatenation. While their results
have significant value in analyzing the security of compression, we believe
a generalization and abstraction of the rendering process is essential to
theoretically analyzing the security of generic compression and rendering functions.
Furthermore, generalized rendering and compression functions help better
capture and model specific attacks such as BREACH in the context of<commit_msg>Add CTX experiments mention to abstract<commit_after>\documentclass[conference, letterpaper, 10pt]{IEEEtran}

\usepackage[utf8]{inputenc}

\title{On the security of encryption and compression composition under reflection attacks}

%\author{
%    Anonymized submission
%}

 \author{
     \IEEEauthorblockN{<NAME>}
     \IEEEauthorblockA{University of Athens \\
     <EMAIL>}
     \and
     \IEEEauthorblockN{<NAME>}
     \IEEEauthorblockA{University of Edinburgh\\
     <EMAIL>}
     \and
     \IEEEauthorblockA{<NAME>}
     \IEEEauthorblockA{University of Athens \\
     <EMAIL>}
 }

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

\usepackage{cite}

\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

\begin{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, and BREACH, even after TLS 1.3. We introduce an abstract
theoretical cryptographic model for such attacks, the \textit{adaptive
reflection security} game with the relevant security definitions. We propose a
model for \textit{compression idealness} and experimentally show that typical compression
functions expose partially ideal behavior. We then experimentally show that
typical plaintexts used in practice follow an interdependent joint distribution,
our stronger notion of dependent joint distributions. Based on these two
properties, we prove that \textit{compression-detectability} of predicates
arises, the ability to extract a predicate of the plaintext using reflection.
We then prove that all length-preserving encryption schemes are insecure when
composed with such functions. Our attack model describes two modes of attack,
one-shot and amplified. For the case of the BREACH attack, we discuss how it can
be described as an instance of our theoretical model. Motivated by the lack of
production-grade testing tools, we provide a modular scalable open-source
generic attack framework that implements compression side-channel attacks in a
robust manner. Finally, we propose a novel defense protocol, \textit{context
hiding}, that effectively eliminates the threat these attacks pose. This
protocol modifies the plaintext joint distribution so as to remove the
interdependence, thereby mitigating the problem. We show that our method of
defense performs significantly more favourably in terms of compression rate when
compared to previous techniques.
\end{abstract}

\section{Introduction}\label{sec:prev}

Compression and encryption composition has caused serious security problems
in protocols such as TLS \cite{c15} over the years. These
include attacks like CRIME \cite{c1}, TIME \cite{c2}, and BREACH \cite{c3}.

However, the theoretical models for these classes of attacks has been limited.
The compression side-channel attack was first studied by Kelsey \cite{c4} in 2002.
Kelley and Tamassia\cite{c5}  discuss the notion of \textit{entropy-restricted} semantic
security, but this only models the case where two secrets compress to the same
length, and so it is difficult to capture practical techniques used in attacks
such as BREACH.

Alawatugoda etc. \cite{c6} introduce a model for \textit{Cookie recovery},
\textit{Random cookie indistinguishability}, as well as \textit{Chosen cookie indistinguishability}.
Nevertheless, their security models are limited in classes of rendering functions
that are very specific. In their models, the attacker is able to directly influence
the output of the rendering function through concatenation. While their results
have significant value in analyzing the security of compression, we believe
a generalization and abstraction of the rendering process is essential to
theoretically analyzing the security of generic compression and rendering functions.
Furthermore, generalized rendering and compression functions help better
capture and model specific attacks such as BREACH in the context of
{'fraction_non_alphanumeric': 0.06544654233754199, 'fraction_numerical': 0.006255067763234101, 'mean_word_length': 5.31140350877193, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, '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': '955464', 'n_tokens_mistral': 2328, 'n_tokens_neox': 2126, 'n_words': 979}