\documentclass[dvipsnames,14pt,t]{beamer}

\usepackage{../slides}

\usepackage{../langs}

\usepackage{../graphics}

\usepackage{../data}

\usepackage{../grammar}

% beamer stuff 

\renewcommand{\slidecaption}{SEN 11, King's College London}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\

  \LARGE Security Engineering 

  \end{tabular}}\bigskip\bigskip\bigskip

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

  Office: & N7.07 (North Wing, Bush House)\\

  Slides: & KEATS (also homework is there)\\

  \end{tabular}

  \end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\begin{bubble}[10cm]

Imagine you have a completely innocent email message, like

birthday wishes to your grandmother. Why should you still

encrypt this message and your grandmother take the effort to

decrypt it?

\end{bubble}

\begin{itemize}

\item \small  

      (Hint: The answer has nothing to do with preserving the

      privacy of your grandmother and nothing to do with

      keeping her birthday wishes super-secret. Also nothing to

      do with you and grandmother testing the latest

      encryption technology, nor just for the sake of it.)

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\begin{center}

\includegraphics[scale=0.6]{../pics/escher.jpg}\\

\footnotesize\mbox{M.C.Escher, Amazing World (from Gödel, Escher, Bach by D.Hofstadter)} 

\end{center}

\hfill\includegraphics[scale=0.3]{../pics/hofstadter.jpg}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Interlock Protocols}

\mbox{A Protocol between a car \bl{$C$} and a key transponder \bl{$T$}:}\bigskip 

\begin{enumerate}

\item \bl{$C$} generates a random number \bl{$N$}

\item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$}

\item \bl{$C \to T$}: \bl{$N, F$}\bigskip

\item \bl{$T$} calculates \bl{$(F',G') = \{N\}_K$}

\item \bl{$T$} checks that \bl{$F = F'$}

\item \bl{$T \to C$}: \bl{$N, G'$}

\item \bl{$C$} checks that \bl{$G = G'$}

\end{enumerate}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Zero-Knowledge Proofs}

\begin{itemize}

\item Essentially every NP-problem can be used for ZKPs\bigskip

\item modular logarithms: Alice chooses public \bl{$A$},  \bl{$B$}, \bl{$p$}; and private \bl{$x$}

\begin{center}

\large\bl{$A^x \equiv B\; mod\; p$}

\end{center} 

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Modular Arithmetic}

It is easy to calculate

\begin{center}

\large\bl{$\alt<1>{?}{10} \equiv 46\; mod\; 12$}

\end{center}\bigskip\pause 

A: \bl{$10$}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Modular Logarithm}

Ordinary, \emph{non}-modular logarithms: 

\begin{center}\large

\begin{tabular}{ll}

& \bl{$10^? = 17$}\bigskip\\\pause

$\Rightarrow$ & \bl{$log_{10} 17 = 1.2304489\ldots$}\\\pause

$\Rightarrow$ & \bl{$10^{1.2304489} = 16.999999$}\\\pause

\end{tabular}

\end{center}

Conclusion: \bl{$1.2304489$} is very close to the \emph{true}

solution, slightly low

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Modular Logarithm}

In contrast, modular logarithms behave much differently:

\begin{center}\large

\bl{$2^? \equiv 88319671\;\; mod\;\; 97330327$}\bigskip

\end{center}\pause

Lets say I `found' \bl{$28305819$} and I try

\begin{center}\large

\bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip

\end{center}\pause

Slightly lower. I might be tempted to try \bl{$28305820$}\ldots\pause

but the real answer is \bl{12314}.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Commitment Stage}

\begin{enumerate}

\item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}.

\item Alice sends Bob for all \bl{$1..z$} 

\begin{center}

\bl{$h_i = A^{r_i} \;mod\; p$}

\end{center}\bigskip

\item Bob generates random bits   \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin

\item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where

\begin{center}

\begin{tabular}{ll}

\bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\

\bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\

\end{tabular}

\end{center}

where \bl{$r_j$} is the lowest \bl{$j$} with \bl{$b_j = 1$}

\end{enumerate}

\only<2>{

\begin{textblock}{7}(7.9,3.9)

\begin{bubble}[5cm]\small

\begin{center}

  \begin{tabular}{lcccc}

  Alice \bl{$r_i$}:\; & \bl{4} & \bl{9} & \bl{1} & \bl{3}\\ 

  Bob \bl{$b_i$}:\; & \bl{0} & \bl{1} & \bl{0} & \bl{1}\\

  & & \bl{$\uparrow$} \\

  & & \bl{$j$}

  \end{tabular}             

  \end{center}    

\end{bubble}

\end{textblock}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Confirmation Stage}

\begin{enumerate}

\item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol

\begin{center}

\begin{tabular}{ll}

\bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv h_i\;mod\;p$}\\

\bl{$b_i = 1$}: & \bl{$A^{s_i}  \equiv h_i * h_j^{-1}  \;mod\; p$}\\

\end{tabular}

\end{center}\bigskip

Bob was sent

\begin{center}

\begin{tabular}{l}

\bl{$h_1, \ldots, h_z$},\\

\bl{$r_1 - r_j$},  \bl{$r_2 - r_j$}, \ldots, \bl{$r_z - r_j \;\;mod \;p - 1$} 

\end{tabular}

\end{center}

where the corresponding bits were 

\bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$}

\end{enumerate}

\only<2>{

\begin{textblock}{7}(7.9,1)

\begin{bubble}[5cm]\small

\begin{center}

\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

$A^{s_i}$ & $=$ & $A^{r_i - r_j}$\\ 

          & $=$ & $A^{r_i} * A^{-r_j}$\\

          & $=$ & $h_{r_i} * h_{r_j}^{-1}\;mod\;p$   

\end{tabular}}

\end{center}    

\end{bubble}

\end{textblock}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Proving Stage}

\begin{enumerate}

\item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\

she sends

\begin{center}

\bl{$s_{z+1} = (x - r_j)$}

\end{center}

\item Bob confirms

\begin{center}

\bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$}

\end{center}

\end{enumerate}\bigskip\pause

In order to cheat, Alice has to guess all bits in advance. She

has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{How can Alice cheat?}

\begin{itemize}

\item Alice needs to coordinate what she sends as \bl{$h_i$}

      (in step 2), \bl{$s_i$} (in step 4) and

      \bl{$s_{z+1}$} (in step 6).\pause\bigskip

\item for \bl{$s_{z+1}$} she solves the easy

\begin{center}

\bl{$A^{s_{z+1}} \equiv B * y \;mod\;p$}

\end{center}

for \bl{$y$}.\pause

\item if she can guess \bl{$j$} (first \bl{$1$}) then 

  she sends \bl{$y$} as \bl{$h_j$}

and \bl{$0$} as \bl{$s_j$}.\pause

\item however she does not know \bl{$r_j$} because she would 

need to solve

\begin{center}

\bl{$A^{r_j} \equiv y \;mod\;p$}

\end{center}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{How can Alice cheat?}

\begin{itemize}

\item Alice still needs to decide on the other \bl{$h_i$} and 

\bl{$s_i$}. They have to satisfy the test:

\[\bl{A^{\alert{s_i}} \stackrel{?}{\equiv} \alert{h_i} * h_j^{-1}  \;mod\; p}\]

\pause

\item Lets say she choses the \bl{$s_i$} at random, then she 

needs to solve

\[\bl{A^{s_i} \equiv z * h_j^{-1}  \;mod\; p}\] 

for \bl{$z$}.\pause{} It still does not allow us to find out

the \bl{$r_i$}. Let us call an \bl{$h_i$} calculated in this 

way as \alert{bogus}.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{How can Alice cheat?}

\begin{itemize}

\item Alice has to produce bogus \bl{$h_i$} for all bits that 

are going to be \bl{$1$} in advance.\bigskip\pause

\item Lets say \bl{$b_i = 1$} where Alice guessed \bl{$0$}: 

She already has sent \bl{$h_i$} and \bl{$h_j$} and now must find a

correct \bl{$s_i$} (which she chose at random at first)

\[\bl{A^{s_i} \equiv h_i * h_j^{-1}  \;mod\; p}\]

If she knew \bl{$r_i$} and \bl{$r_j$}, then easy: 

\bl{$s_i = r_i - r_j$}. But she does not. So she will be found 

out.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{How can Alice cheat?}

\begin{itemize}

\item Alice has to produce bogus \bl{$h_i$} for all bits that 

are going to be \bl{$1$} in advance.\bigskip

\item Lets say \bl{$b_i = 0$} where Alice guessed \bl{$1$}: 

She has to send an \bl{$s_i$} so that 

\[\bl{A^{s_i} \equiv h_i\;mod\;p}\]

She does not know \bl{$r_i$}. So this is too hard and 

she will be found out.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\tikzset{alt/.code args={<#1>#2#3#4}{%

  \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path

}}

\begin{frame}[t]

\frametitle{Buffer Overflow Attacks}

\begin{itemize}

\item the problem arises from the way C/C++ organises its function calls\\[-8mm]\mbox{}

\end{itemize}

\begin{center}

\begin{tikzpicture}[scale=1]

%\draw[black!10,step=2mm] (0,0) grid (9,4);

%\draw[black!10,thick,step=10mm] (0,0) grid (9,4);

\node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}};

\draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8);

\draw[line width=0mm, white, alt=<9->{fill=red}{fill=blue}] (0,0.2) rectangle (1,0.5);

\draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5);

\draw[line width=1mm, alt=<6->{fill=red}{fill=blue}] (0,1.0) rectangle (1,2.0);

\draw[line width=1mm, alt=<7->{fill=yellow}{fill=blue}] (0,0.5) rectangle (1,1.0);

\draw[line width=1mm] (0,0) -- (0,4);

\draw[line width=1mm] (1,0) -- (1,4);

\node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}};

\draw[line width=1mm, alt=<{4-5,8}>{fill=red}{fill=blue}] (3,1.0) rectangle (4,3.0);

\onslide<3-4>{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);}

\onslide<5>{\draw[<-, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {res=24} (3,1);}

\onslide<7-8>{\draw[->, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {n=3} (3,3);}

\onslide<9>{\draw[<-, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {res=6} (3,1);}

\node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}};

\draw[line width=1mm] (7,3.5) -- (7,0.5) -- (8.5,0.5) -- (8.5,3.5);

\onslide<3,4,7,8>{

\node at (7.75, 1.4) {ret};

\draw[line width=1mm] (7,1.1) -- (8.5,1.1);

\node at (7.75, 2.0) {sp};

\draw[line width=1mm] (7,2.3) -- (8.5,2.3);

}

\onslide<3,4>{

\node at (7.75, 0.8) {4};

\draw[line width=1mm] (7,1.7) -- (8.5,1.7);

}

\onslide<7,8>{

\node at (7.75, 0.8) {3};

\draw[line width=1mm] (7,1.7) -- (8.5,1.7);

}

\end{tikzpicture}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\begin{center}

\begin{tikzpicture}[scale=1]

%\draw[black!10,step=2mm] (0,0) grid (9,4);

%\draw[black!10,thick,step=10mm] (0,0) grid (9,4);

\node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}};

\draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8);

\draw[line width=1mm, white, fill=blue] (0,1.0) rectangle (1,2.0);

\draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5);

\draw[line width=1mm] (0,0) -- (0,4);

\draw[line width=1mm] (1,0) -- (1,4);

\node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}};

\draw[line width=0mm, alt=<{4-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,3.0);

\draw[line width=0mm, alt=<{5-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,2.0);

\draw[line width=0mm, alt=<{7-}>{red, fill=red}{blue, fill=blue}] (3,2.0) rectangle (4,1.0);

\draw[line width=1mm] (3,1.0) rectangle (4,3.0);

\onslide<3->{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);}

\onslide<5->{\draw[<-, line width=2mm,red] (4,2) to node [above,sloped,midway] 

{\begin{tabular}{l}user\\[-1mm] input\end{tabular}} (6,2);}

\onslide<8->{\draw[<-, line width=1mm,red] (1,-2) to (3,1);}

\node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}};

\draw[line width=1mm] (7,3.5) -- (7,-0.1) -- (8.5,-0.1) -- (8.5,3.5);

\onslide<3->{

\node at (7.75, 0.2) {4};

\draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,0.5) rectangle (8.5,1.1);

\node at (7.75, 0.8) {\alt<6->{@a\#}{ret}};

\draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,1.1) rectangle (8.5,1.7);

\node at (7.75, 1.4) {\alt<6->{!?w;}sp};

}

\onslide<4->{

\draw[line width=1mm,fill=red] (7,1.7) rectangle (8.5,3.0);

\node[white] at (7.75, 2.4) {buffer};

}

\end{tikzpicture}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Coming Back To\ldots}

\begin{bubble}[10cm]

Imagine you have a completely innocent email message, like

birthday wishes to your grandmother. Why should you still

encrypt this message and your grandmother take the effort to

decrypt it?

\end{bubble}\pause

\begin{itemize}      

\item \small Any wild guesses?\pause

\item \small

      Bruce Schneier\\

      NSA Surveillance and What To Do About It\\

      \url{https://www.youtube.com/watch?v=QXtS6UcdOMs}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%