\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 Access Control and \\[-3mm] 
  \LARGE Privacy Policies (11)\\[-6mm] 
  \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{itemize}
\item 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?\bigskip 

      \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}
\end{center}

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

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

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}

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

\begin{itemize}
\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, 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

\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\\\pause
\end{center}\pause

Lets say I found \bl{$28305819$}\ldots I try

\begin{center}\large
\bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip\\\pause
\end{center}\pause

I could be tempted to try \bl{$28305820$}\ldots\pause
but the real\\
\mbox{}\hfill 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

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

\begin{itemize}
\item 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?\bigskip 

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


\end{document}


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