% vim: set tw=78 aw:
\documentclass{beamer}

\usepackage[utf8x]{inputenc} % diacritice
\usepackage[english]{babel}
\usepackage{color}			 % highlight
\usepackage{alltt}			 % highlight
\usepackage{hyperref}        % folositi \url{http://...}
\usepackage{graphicx}
\mode<presentation>
{ \usetheme{Rochester} }		% TODO: settle this

% Titlul nu foloseşte Unicode pentru că e o problemă căreia nu i-am dat de
% cap.
\title[Cracking A5/1]{Cracking A5/1}
%\subtitle{}
\institute{OSP}
\author{Lucian Adrian Grijincu \\ \texttt{lucian.grijincu@gmail.com}}


\begin{document}

% Slide-urile cu mai multe părţi sunt marcate cu textul (cont.)
\setbeamertemplate{frametitle continuation}[from second]
% Arătăm numărul frame-ului
\setbeamertemplate{footline}[frame number]

\frame{\titlepage}
\frame{\tableofcontents}

\section{Introduction}
\frame{\tableofcontents[currentsection]}

\begin{frame}{A5/what?}
  \begin{itemize}
    \item A5/1 - stream cipher used for OTA privacy in GSM networks
    \item A5/2 - a weaker version of A5/1
    \item A5/3 - (aka KASUMI) newer version, other kind of algorithm
  \end{itemize}
\end{frame}


\begin{frame}{A5/1}
  \begin{itemize}
    \item designed from the start to be easy to break:
    \item 1994 - first disclosure of the algorithm
    \item 1997 - A5/1 shown academically broken
    \item 2000 - more proof ...
    \item 2003 - more proof ...
    \item 2005 - and then some more ...
    \item 2008 - rainbow tables computed (but never released publicly)
    \item 2009 - A5/1 Security Project announce project to build public rainbow table
    \item 2010 - rainbow tables released on bittorrent (2TB)
  \end{itemize}
\end{frame}

\begin{frame}{A5/1 used in GSM}
  \begin{itemize}
    \item first plain-text frames of a GSM call have a distinct
      pattern:
      \begin{itemize}
      \item some bits are always zero
      \item ACK bits
      \item state encoding bits
      \end{itemize}
    \item this limmits the search space significantly
  \end{itemize}
\end{frame}

\begin{frame}{History lesson}
  similar technique used to break the German cypher in WW2:
  \begin{itemize}
    \item messages longer than a page began with
    \item FORT (\textit{Fortsetzung})
    \item the time of the previous message between \texttt{Y}s
    \item the time of the previous message between \texttt{Y}s, again!
    \item ``continuation of message sent at 2330'' – ``FORTYWEEPYYWEEPY''
  \end{itemize}
\end{frame}


\section{Rainbow tables}
\frame{\tableofcontents[currentsection]}

\begin{frame}{Cypher tables}
  \begin{itemize}
  \item for each plain text
    \begin{itemize}
    \item for each password
      \begin{itemize}
        \item compute crypto(text, password)
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Cypher tables}
  \begin{itemize}
  \item pass=0000
    \begin{itemize}
    \item 0000 - A7B7
    \item 0001 - HJ89
    \item ...
    \item 9999 - 21J3
    \end{itemize}
  \item pass=0001
    \begin{itemize}
    \item 0000 - 32H4
    \item 0001 - 5JL3
    \item ...
    \item 9999 - HJ89
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Cypher tables}
  \begin{itemize}
  \item size grows exponentially with
    \begin{itemize}
      \item plain text length
      \item password length
    \end{itemize}
  \item duplicates in the table. HJ89 bellongs to:
    \begin{itemize}
    \item text=0001 and pass=0000
    \item text=9999 and pass=0001
    \item etc.
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Rainbow tables}
  \begin{itemize}
  \item select a random set of input secret values
  \item reduce the size of the table
  \item increase the lookup time
  \end{itemize}
\end{frame}

\begin{frame}{Rainbow tables}
  \includegraphics[scale=0.6]{pics/rainbow.png}
\end{frame}

\begin{frame}{Rainbow tables}
  \includegraphics[scale=0.6]{pics/r-lookup.png}
\end{frame}

\begin{frame}{Rainbow tables}
  \begin{itemize}
  \item R functions are not inverses of H!
  \item chains of $2^{15}$ R functions per table
  \item posibility of overlapping last entries:
  \item use many tables with other sets of R functions
  \end{itemize}
\end{frame}

\section{Hadoop}
\frame{\tableofcontents[currentsection]}

\begin{frame}{Hadoop}
  \begin{itemize}
  \item open source map-reduce
  \item highly scalable (thousand of nodes)
  \end{itemize}
\end{frame}

\begin{frame}{Hadoop}
  \textbf{Map}
  \begin{itemize}
  \item read input
  \item create basic $<key, value>$ pairs
  \end{itemize}
\end{frame}

\begin{frame}{Hadoop}
  \textbf{Reduce}
  \begin{itemize}
  \item combine $<key, value>$ pairs with same $key$
  \item write output
  \end{itemize}
\end{frame}




\section{Cracking A5/1 with Hadoop}
\frame{\tableofcontents[currentsection]}
\begin{frame}{Cracking steps}
  precalculate tables - done once
  \begin{enumerate}
  \item create a set of random initial secret values
  \item map-reduce the creation of the tables
  \end{enumerate}
  search for a secret based on hashes
\end{frame}


\begin{frame}{Table calculation - \textbf{Map}}
  \begin{itemize}
  \item break input set of secrets
  \item each mapper computes a chain
  \item results are sent with
    \begin{itemize}
    \item $key$=last secret in chain
    \item $value$=first secret in chain
    \end{itemize}
  \end{itemize}
\end{frame}


\begin{frame}{Table calculation - \textbf{Reduce}}
  \begin{itemize}
  \item reduce multiple $<key, value>$ pairs:
  \item group entries in tables
  \item group all start secrets that generate the same end secret
  \end{itemize}
\end{frame}

\begin{frame}{Lookup}
  in each table:
  \begin{itemize}
  \item \textbf{Map} - find all secrets that might generate the searched $hash$
  \item \textbf{Reduce} - from all secrets, only select the most
    frequent appearing secret
  \end{itemize}
\end{frame}

\begin{frame}{Lookup algorithm}
  \includegraphics[scale=0.6]{pics/r-lookup.png}
\end{frame}


\section{Conclusion}
\begin{frame}{Conclusion}
  \begin{itemize}
  \item depending on the size of the chains: 1TB - 32TB tables
  \item this permits near real-time lookup
  \end{itemize}
\end{frame}

\begin{frame}{Other GSM bad news}
  \begin{itemize}
  \item A5/2 - is weaker than A5/1
  \item key sizes less than 64 bits make cracking possible
  \item hardware and software (open source) for GSM radio
    transmissions is already avaliable
  \item A5/3 - has 64 and 128 bit key sizes
  \item devices that support A5/3 use 64 bits because it consumes less power
  \end{itemize}
\end{frame}

\begin{frame}{Why weak algorithms?}
  \begin{itemize}
  \item they don't protect the user privacy
  \item only protect network operator's pockets
  \item crippled from the start to permit eavesdropping
  \end{itemize}
\end{frame}

\begin{frame}{Other results}
  \begin{itemize}
  \item The C3 group used 40 NVIDIA CUDA machines for three months
  \item rainbow table size: 2TB
  \item efficient distribuition of this table permits real-time
    cracking if the call is intercepted from the start
  \end{itemize}
\end{frame}

\end{document}