\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\small
\begin{bubble}[10cm]
Even good passwords consisting of 8 characters, can be broken
in around 50 days (obviously this time varies a lot and also
gets shorter and shorter over time). Do you think it is good
policy to require users to change their password every 3
months (as King's did until recently)?\medskip

Under which
circumstance should users be required to change their
password?
\end{bubble}      


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



\end{document}


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