\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: & S1.27 (1st floor Strand Building)\\
  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}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Interlock Protocol}

\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 an 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
      Bruce Schneier\\
      NSA Surveillance and What To Do About It\\
      \url{https://www.youtube.com/watch?v=QXtS6UcdOMs}
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\small
\begin{bubble}[10cm]
Terrorists use encrypted mobile-messaging apps. The spy
agencies argue that although they can follow the conversations
on Twitter, they ``go dark'' on the encrypted message apps. To
counter this ``going-dark problem'', the spy agencies push for
the implementation of back-doors in iMessage and Facebook and
Skype and everything else UK or US-made, which they can use
eavesdrop on conversations without the conversants' knowledge
or consent.

\end{bubble}      

\begin{itemize}
\item What is the fallacy in the spy agencies going-dark
      argument?
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

\end{document}


%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: