\input{configpres}

\newcommand{\superscript}[1]{\ensuremath{^{\textrm{#1}}}}
\newcommand{\subscript}[1]{\ensuremath{_{\textrm{#1}}}}

% ----------------------------
\subsection{Cryptanalysis}

\title{Cryptanalysis}
\maketitle

% ----------------------------
\begin{frame}
\frametitle{Overview}
\tableofcontents
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Cryptanalysis}
\begin{itemize}
\item Goal: Information about Plaintext or Key
\item Analysis of:
 \begin{itemize}
 \item Data (Ciphertext)
 \item Algorithms
 \item Environment
 \end{itemize}
\item Motivation:
 \begin{itemize}
 \item Attack
 \item Privacy
 \item Knowledge (corporate-sponsored espionage)
 \item Secrets (sate-sponsored espionage)
 \end{itemize}
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Analysis methods and Attacks}
\begin{itemize}
\item Analysis Methods
 \begin{itemize}
 \item Frequency Analysis
 \item Linear cryptanalysis
 \item Differential cryptanalysis
 \item Integral cryptanalysis
 \item Mod-n cryptanalysis
 \end{itemize}
\item Direct attacks
 \begin{itemize}
 \item Brute force attack
 \item Dictionary attack
 \item Rainbow-table attack
 \end{itemize}
\item Environmental attacks
 \begin{itemize}
 \item Man-in-the-middle attack
 \item Replay attack
 \item Side-channel attack
 \item Timing attack
 \end{itemize}
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Scope of attacks}
\begin{itemize}
\item Ciphertext-only attack
 \begin{itemize}
 \item Attacker knows only some Ciphertexts
 \end{itemize}
\item Known-plaintext attack
 \begin{itemize}
 \item Attacker knows some Plaintext and Ciphertext pairs
 \end{itemize}
\item Chosen-plaintext attack
 \begin{itemize}
 \item Attacker can choose the encryption input (Pub-Key attacks)
 \end{itemize}
\item Chosen-ciphertext attack
 \begin{itemize}
 \item Recover knowledge about key by inserting random ciphertext in
       decryption path
 \end{itemize}
\item Related-key attack
 \begin{itemize}
 \item Analyze plaintext and ciphertext dependencies of a cipher algorithm
       with similar keys (e.g. only one key bit difference)
 \end{itemize}
\end{itemize}
\end{frame}

% ----------------------------
\subsection{Analysis}

\begin{frame}
\frametitle{Frequency Analysis}
\begin{itemize}
\item Main analysis for cipher methods before 1970
\item Goal: gain information about the cipher algorithm
 \begin{enumerate}
 \item Compare character frequencies in ciphertext and similar plaintext
 \item Use character exchange table to decode parts or whole ciphertext
 \end{enumerate}
\item Result: Knowledge about cipher and key
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Linear Analysis}
\begin{itemize}
\item Algorithm analysis
\item published 1992 (by Mitsuru Matsui)
\item Goal: find linear dependencies in cipher actions
\begin{enumerate}
\item find linear dependencies between plaintext, ciphertext and keys bits
\item use these dependencies together with known-plaintext and
known-ciphertext attack to derive key bits
\end{enumerate}
\item Result: weaken or compromise cipher algorithm
\end{itemize}
\end{frame}

% ----------------------------
\subsection{Attacks}

\begin{frame}
\frametitle{Brute Force}
\begin{itemize}
\item Classic approach for Key/Password search
\item Iterate all combinations
\item Effort: O(n) \\
      with n: Key/Password Length
\item Optimizations:
 \begin{itemize}
 \item Defined Character namespace
 \item Use Dictionaries instead of all combinations
 \item Rainbow-table
 \item Implementation in FPGA
 \item Parallel Computing
 \item Usage of Bot-Nets
 \end{itemize}
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Rainbow-Table}
\begin{itemize}
\item Focus on password hashes
\item Problem:
 \begin{itemize}
 \item Full pre-computed hash lookup-tables are very space consuming
 \end{itemize}
\item Solution:
 \begin{itemize}
 \item Table of starting- and end-points of hash-chains
 \item Iterate the chains with a given hash
 \end{itemize}
\item Hash-Chain:
 \begin{itemize}
 \item Hash function: password -> hash
 \item Reduction function: hash -> new password
 \end{itemize}
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Rainbow-Table II}
\begin{itemize}
\item Rainbow-table calculation
 \begin{enumerate}
 \item Start with password  P\subscript{0} and calculate hash H\subscript{0}
 \item Reduction function calculates P\subscript{1} from H\subscript{0}
 \item Calculate hash H\subscript{1} from P\subscript{1}
 \item Repeat step 2 and 3 n times
 \item Store P\subscript{0} and P\subscript{n}
 \item Repeat steps 1 to 5 with another password
 \end{enumerate}
\item Usage:
 \begin{enumerate}
 \item Start with a hash value H\subscript{x}
 \item Reduction function calculates P\subscript{x+1} from H\subscript{x}
 \item Compare P\subscript{x+1} with the chain endpoints
 \item If P\subscript{x+1} does not match, hash P\subscript{x+1} to
       H\subscript{x+1} and restart at step 2
 \item Otherwise take the matching hash-chain and recalculate it until
       P\subscript{x}
 \end{enumerate}
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Rainbow-Table III}
\begin{itemize}
\item Calculation:
\end{itemize}
\begin{figure}[h]
\centering
\includegraphics[width=8cm]{images/sec_rainbowtable_calc.png}
\end{figure}
\begin{itemize}
\item Start with Hash c89003:
 \begin{enumerate}
 \item R(c89003) = kheohn, no match
 \item H(kehohn) = 2cff73
 \item R(2cff73) = lizbus, \textbf{MATCH} in chain aaaaaa
 \item Recalculate chain aaaaaa until H(srlems) equals c89003
 \end{enumerate}
\item Result: \textbf{srlems} is the wanted password for hash \textbf{c89003}
\end{itemize}
\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Man-in-the-Middle}
\begin{itemize}
\item Attack against Key-exchange protocols (e.g. TLS)
\item Relay between two communication partners
\item Forward information but replace the keys
\end{itemize}
\begin{figure}[h]
\centering
\includegraphics[width=6cm]{images/sec_mitm.png}
\end{figure}

\end{frame}

% ----------------------------
\begin{frame}
\frametitle{Replay}
\begin{itemize}
\item Communication attack
\item Capture e.g. Authentication attack an replay it later
\item Mitigation: Timestamp authentication information
\end{itemize}
\end{frame}

% ----------------------------
\subsection{Summary}

\begin{frame}
\frametitle{Summary}
\begin{itemize}
\item Cipher algorithm classification with known analysis methods
\item Weaken or break Cipher algorithms with attacks
\item Attacks may compromise systems
\item Implementations may allow side-channel attacks
\end{itemize}
\end{frame}

% ----------------------------
\subsection*{}
\input{tailpres}