<commit_before>\renewcommand*\chappic{img/diff-crypt.pdf}
\renewcommand*\chapquote{Just because it's automatic doesn't mean it works.}
\renewcommand*\chapquotesrc{<NAME>}
%
\chapter{Differential cryptanalysis}
\label{ch:dc}
%
In Chapter~\ref{ch:hash} we defined two hash functions. In this chapter
we consider such functions from a differential perspective. Differential
considerations will turn out to yield successful collision attacks on hash
functions. We introduce a notation to easily represent differential
characteristics.

\section{Motivation}
\label{sec:dc-motivation}
%
In August 2004, Wang et al. published results at Crypto'04~\cite{wang2004} which revealed
that MD4, MD5, HAVAL-128 and RIPEMD can be broken practically using differential cryptanalysis.
Their work is based on preliminary work by <NAME>~\cite{Dobbertin1998}.
On an IBM~P690 machine, an MD5 collision can be computed in about one hour using this approach.
Collisions for HAVAL-128, MD4 and RIPEMD were found as well. <NAME>'s \texttt{md4coll.c}
program~\cite{md4coll} implements Wang's approach and can find MD4 collisions in few seconds
on my Thinkpad~x220 setup specified in \hyperref[app:setup]{Appendix~\ref{app:setup}}.

Let $n$ denote the digest size, i.e. the size of the hash value $h(x)$ in bits.
Due to the birthday paradox, a collision attack has a generic complexity of $2^{n/2}$
whereas preimage and second preimage attacks have generic complexities of $2^n$.
In other words it is computationally easier to find any two colliding hash values
than the preimage or second preimage for a given hash value.

Following results by Wang et al., differential cryptanalysis was shown as
powerful tool for cryptanalysis of hash algorithms. This thesis applies those
ideas to satisfiability approaches.

\begin{table}[bt]
  \begin{center}
    \begin{tabular}{cccc}
      \hline \hline
      \multicolumn{4}{c}{Message 1} \\
      \hline
      4d7a9c83 & \textbf{d6cb927a} & \textbf{29d5a578} & 57a7a5ee \\
      de748a3c & dcc366b3 & b683a020 & 3b2a5d9f \\
      c69d71b3 & f9e99198 & d79f805e & a63bb2e8 \\
      \textbf{45dc8e31} & 97e31fe5 & 2794bf08 & b9e8c3e9 \\
      \hline
      \multicolumn{4}{c}{Message 2} \\
      \hline
      4d7a9c83 & \textbf{56cb927a} & \textbf{b9d5a578} & 57a7a5ee \\
      de748a3c & dcc366b3 & b683a020 & 3b2a5d9f \\
      c69d71b3 & f9e99198 & d79f805e & a63bb2e8 \\
      \textbf{45dd8e31} & 97e31fe5 & 2794bf08 & b9e8c3e9 \\
      \hline
      \multicolumn{4}{c}{Hash value of Message 1 and Message 2} \\
      \hline
      5f5c1a0d & 71b36046 & 1b5435da & 9b0d807a \\
      \hline \hline
    \end{tabular}
    \caption[Hexadecimal values of one MD4 collisions given in paper~\cite{wang2004}]{
      One of two MD4 hash collisions provided in~\cite{wang2004}.
      A message represents one block of 512~bits.
      %The hash value consists of 128~bits.
      Values are given in hexadecimal, message words are enumerated from
      left to right, top to bottom. Differences are highlighted in
      bold for illustration purposes. For comparison the first bits
      of Message 1 are \texttt{11000001\dots} and the last bits are
      \texttt{\dots10011101}.
    }
    \label{tab:wang-md4-collision1}
  \end{center}
\end{table}

\newpage
\section{Fundamentals}
\label{sec:dc-fundamentals}
%
\index{Hash collision}
\begin{defi}[Hash collision]
  Given a hash function $h$,
  a hash collision is a pair $(x_1, x_2)$ with $x_1 \neq x_2$ such that
  $h(x_1) = h(x_2)$.
\end{defi}

\index{Pseudo collision}
Pseudo-collisions are also often considered when attacking hash functions.
A \emph{pseudo collision} is given if a hash collision can be found for a given
hash function, but the initial vectors (IV) can be chosen arbitrarily.

Hash algorithms consume input values as blocks of bits.
As far as the length of the input must not conform to the block size,
padding is applied. Now consider such a block of input values
and another copy of it. We use those two blocks as inputs for two
hash algorithm instances, but provide slight modifications in few bits.
Differential cryptanalysis is based on the idea to consider those execution states
and tracing those difference to learn about the propagation of message differences.
Compare this setup with Figure~\ref{tab:collision-attack}.

\index{Avalanche effect}
At the very beginning only the few defined differences are given. But as the
hash algorithm progresses in computation, differences are propagated to more
and more bits. Most likely the final value will differ in many bits, because
of a desirable hash algorithm property called \emph{avalanche effect}.
A small difference in the input should lead to a significant difference
in the output (i.e. visually recognizable).

Visualizing those differences helps the cryptanalyst to find modifications
yielding a small number of differences in the evaluation state. The propagation
of differences in a particular hash algorithm is called \emph{differential
path}. Empirical results in differential cryptanalysis indicate that spare
paths are desirable, because it is easier to cancel out few differences in the
output compared to many differences.
The cryptanalyst consecutively modifies the input values to eventually
receive a collision in the output value.

\index{Differential path}
\index{Differential characteristic}
\begin{defi}
  The propagation of differences in a particular function is called
  \emph{differential path}. The complete differential state during
  a computation is called \emph{differential characteristic}.
\end{defi}

\begin{theorem}
  Assuming the number of differences in a differential path is small,
  this path is expected to result in a hash collision with higher probability.
\end{theorem}

\begin{figure}[pbt]
  \begin{center}
    \fbox{\includegraphics[width=0.55\textwidth]{img/diff_cryptanalysis.pdf}}
    \caption[Common attack setting for a collision attack]{
      Common attack setting for a collision attack:
      Hash function $f$ is applied to two inputs $M$ and $M^*$ which differ
      by some predefined bits. $\Delta M$ describes the difference between
      these values. A hash collision is given if and only if output values
      $C$ and $C^*$ show the same value. In differential cryptanalysis we observe
      the differences between two instances applying function $f$
      to inputs $M$ and $M^*$.
    }
    \label{tab:collision-attack}
  \end{center}
\end{figure}

\section{Differential notation}
\label{sec:dc-notation}
%
\index{Bit condition}
\index{Generalized bit condition}
\index{Differential notation}
Differential notation helps us to visualize differential characteristics
by defining so-called \emph{generalized bit conditions}.
It was introduced by <NAME> and <NAME>
in 2006~\cite[Section 3.2]{char-2006}, inspired by \emph{signed differences} by
Wang~et al. and is shown in Table~\ref{tab:diff-notation}.<commit_msg>No \fbox for diff crypt image.<commit_after>\renewcommand*\chappic{img/diff-crypt.pdf}
\renewcommand*\chapquote{Just because it's automatic doesn't mean it works.}
\renewcommand*\chapquotesrc{<NAME>}
%
\chapter{Differential cryptanalysis}
\label{ch:dc}
%
In Chapter~\ref{ch:hash} we defined two hash functions. In this chapter
we consider such functions from a differential perspective. Differential
considerations will turn out to yield successful collision attacks on hash
functions. We introduce a notation to easily represent differential
characteristics.

\section{Motivation}
\label{sec:dc-motivation}
%
In August 2004, Wang et al. published results at Crypto'04~\cite{wang2004} which revealed
that MD4, MD5, HAVAL-128 and RIPEMD can be broken practically using differential cryptanalysis.
Their work is based on preliminary work by <NAME>~\cite{Dobbertin1998}.
On an IBM~P690 machine, an MD5 collision can be computed in about one hour using this approach.
Collisions for HAVAL-128, MD4 and RIPEMD were found as well. <NAME>'s \texttt{md4coll.c}
program~\cite{md4coll} implements Wang's approach and can find MD4 collisions in few seconds
on my Thinkpad~x220 setup specified in \hyperref[app:setup]{Appendix~\ref{app:setup}}.

Let $n$ denote the digest size, i.e. the size of the hash value $h(x)$ in bits.
Due to the birthday paradox, a collision attack has a generic complexity of $2^{n/2}$
whereas preimage and second preimage attacks have generic complexities of $2^n$.
In other words it is computationally easier to find any two colliding hash values
than the preimage or second preimage for a given hash value.

Following results by Wang et al., differential cryptanalysis was shown as
powerful tool for cryptanalysis of hash algorithms. This thesis applies those
ideas to satisfiability approaches.

\begin{table}[bt]
  \begin{center}
    \begin{tabular}{cccc}
      \hline \hline
      \multicolumn{4}{c}{Message 1} \\
      \hline
      4d7a9c83 & \textbf{d6cb927a} & \textbf{29d5a578} & 57a7a5ee \\
      de748a3c & dcc366b3 & b683a020 & 3b2a5d9f \\
      c69d71b3 & f9e99198 & d79f805e & a63bb2e8 \\
      \textbf{45dc8e31} & 97e31fe5 & 2794bf08 & b9e8c3e9 \\
      \hline
      \multicolumn{4}{c}{Message 2} \\
      \hline
      4d7a9c83 & \textbf{56cb927a} & \textbf{b9d5a578} & 57a7a5ee \\
      de748a3c & dcc366b3 & b683a020 & 3b2a5d9f \\
      c69d71b3 & f9e99198 & d79f805e & a63bb2e8 \\
      \textbf{45dd8e31} & 97e31fe5 & 2794bf08 & b9e8c3e9 \\
      \hline
      \multicolumn{4}{c}{Hash value of Message 1 and Message 2} \\
      \hline
      5f5c1a0d & 71b36046 & 1b5435da & 9b0d807a \\
      \hline \hline
    \end{tabular}
    \caption[Hexadecimal values of one MD4 collisions given in paper~\cite{wang2004}]{
      One of two MD4 hash collisions provided in~\cite{wang2004}.
      A message represents one block of 512~bits.
      %The hash value consists of 128~bits.
      Values are given in hexadecimal, message words are enumerated from
      left to right, top to bottom. Differences are highlighted in
      bold for illustration purposes. For comparison the first bits
      of Message 1 are \texttt{11000001\dots} and the last bits are
      \texttt{\dots10011101}.
    }
    \label{tab:wang-md4-collision1}
  \end{center}
\end{table}

\newpage
\section{Fundamentals}
\label{sec:dc-fundamentals}
%
\index{Hash collision}
\begin{defi}[Hash collision]
  Given a hash function $h$,
  a hash collision is a pair $(x_1, x_2)$ with $x_1 \neq x_2$ such that
  $h(x_1) = h(x_2)$.
\end{defi}

\index{Pseudo collision}
Pseudo-collisions are also often considered when attacking hash functions.
A \emph{pseudo collision} is given if a hash collision can be found for a given
hash function, but the initial vectors (IV) can be chosen arbitrarily.

Hash algorithms consume input values as blocks of bits.
As far as the length of the input must not conform to the block size,
padding is applied. Now consider such a block of input values
and another copy of it. We use those two blocks as inputs for two
hash algorithm instances, but provide slight modifications in few bits.
Differential cryptanalysis is based on the idea to consider those execution states
and tracing those difference to learn about the propagation of message differences.
Compare this setup with Figure~\ref{tab:collision-attack}.

\index{Avalanche effect}
At the very beginning only the few defined differences are given. But as the
hash algorithm progresses in computation, differences are propagated to more
and more bits. Most likely the final value will differ in many bits, because
of a desirable hash algorithm property called \emph{avalanche effect}.
A small difference in the input should lead to a significant difference
in the output (i.e. visually recognizable).

Visualizing those differences helps the cryptanalyst to find modifications
yielding a small number of differences in the evaluation state. The propagation
of differences in a particular hash algorithm is called \emph{differential
path}. Empirical results in differential cryptanalysis indicate that spare
paths are desirable, because it is easier to cancel out few differences in the
output compared to many differences.
The cryptanalyst consecutively modifies the input values to eventually
receive a collision in the output value.

\index{Differential path}
\index{Differential characteristic}
\begin{defi}
  The propagation of differences in a particular function is called
  \emph{differential path}. The complete differential state during
  a computation is called \emph{differential characteristic}.
\end{defi}

\begin{theorem}
  Assuming the number of differences in a differential path is small,
  this path is expected to result in a hash collision with higher probability.
\end{theorem}

\begin{figure}[pbt]
  \begin{center}
    \includegraphics[width=0.55\textwidth]{img/diff_cryptanalysis.pdf}
    \caption[Common attack setting for a collision attack]{
      Common attack setting for a collision attack:
      Hash function $f$ is applied to two inputs $M$ and $M^*$ which differ
      by some predefined bits. $\Delta M$ describes the difference between
      these values. A hash collision is given if and only if output values
      $C$ and $C^*$ show the same value. In differential cryptanalysis we observe
      the differences between two instances applying function $f$
      to inputs $M$ and $M^*$.
    }
    \label{tab:collision-attack}
  \end{center}
\end{figure}

\section{Differential notation}
\label{sec:dc-notation}
%
\index{Bit condition}
\index{Generalized bit condition}
\index{Differential notation}
Differential notation helps us to visualize differential characteristics
by defining so-called \emph{generalized bit conditions}.
It was introduced by <NAME> and <NAME>
in 2006~\cite[Section 3.2]{char-2006}, inspired by \emph{signed differences} by
Wang~et al. and is shown in Table~\ref{tab:diff-notation}.
{'fraction_non_alphanumeric': 0.07514827137277592, 'fraction_numerical': 0.03934615940980761, 'mean_word_length': 4.096572060449687, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, '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': '2514437', 'n_tokens_mistral': 4285, 'n_tokens_neox': 3914, 'n_words': 1686}