--- a/slides/slides11.tex Thu Nov 19 20:59:24 2015 +0000
+++ b/slides/slides11.tex Thu Nov 26 09:10:47 2015 +0000
@@ -36,39 +36,18 @@
\begin{frame}[c]
\begin{itemize}
-\item you can still send me your homework\bigskip
-\item Unix AC question: use a terminal-based editor (vm,
- vim)\bigskip
-\item exams: 2 out of 3 questions, 5 or so subquestions
- each, you can fill in your answers on the question sheet
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Interlock Protocol}
-
-The interlock protocol (``best bet'' against MITM):
+\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
-\begin{center}
-\begin{tabular}{ll@{\hspace{2mm}}l}
-1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\\
-2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\\
-3. & & \bl{$\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$}\\
- & & \bl{$\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$}\\
-4. & \bl{$A \to B :$} & \bl{$H_1$}\\
-5. & \bl{$B \to A :$} & \bl{$\{H_1, M_1\}_{K^{pub}_A}$}\\
-6. & \bl{$A \to B :$} & \bl{$\{H_2, M_1\}_{K^{pub}_B}$}\\
-7. & \bl{$B \to A :$} & \bl{$M_2$}
-\end{tabular}
-\end{center}\pause
-
-\footnotesize
-\bl{$m$} = How is your grandmother? \bl{$m'$} = How is the
-weather today in London?
+ \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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -77,28 +56,7 @@
\begin{frame}[c]
\begin{center}
-\begin{tabular}{l@{\hspace{9mm}}l}
-\begin{tabular}[t]{@{}l@{}}
-\bl{$A \to C : K^{pub}_A$}\\
-\bl{$C \to B : K^{pub}_C$}\\
-\bl{$B \to C : K^{pub}_B$}\\
-\bl{$C \to A : K^{pub}_C$}\medskip\\
-\bl{$\{A,m\}_{K^{pub}_C} \;\mapsto\; H_1,H_2$}\\
-\bl{$\{B,n\}_{K^{pub}_C} \;\mapsto\; M_1,M_2$}\bigskip\\
-\bl{$\{C,a\}_{K^{pub}_B} \;\mapsto\; C_1,C_2$}\\
-\bl{$\{C,b\}_{K^{pub}_A} \;\mapsto\; D_1,D_2$}
-\end{tabular} &
-\begin{tabular}[t]{@{}l@{}}
-\bl{$A \to C : H_1$}\\
-\bl{$C \to B : C_1$}\\
-\bl{$B \to C : \{C_1, M_1\}_{K^{pub}_C}$}\\
-\bl{$C \to A : \{H_1, D_1\}_{K^{pub}_A}$}\\
-\bl{$A \to C : \{H_2, D_1\}_{K^{pub}_C}$}\\
-\bl{$C \to B : \{C_2, M_1\}_{K^{pub}_B}$}\\
-\bl{$B \to C : M_2$}\\
-\bl{$C \to A : D_2$}
-\end{tabular}
-\end{tabular}
+\includegraphics[scale=0.6]{../pics/escher.jpg}
\end{center}
\end{frame}
@@ -106,28 +64,335 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 you have to ask something that cannot imitated
- (requires \bl{$A$} and \bl{$B$} know each other)
-\item what happens if \bl{$m$} and \bl{$n$} are voice
- messages?\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, 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}}
-\item the moral: establishing a secure connection from ``zero'' is
-almost impossible---you need to rely on some established
-trust\medskip
+\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);
-\item that is why we rely on certificates, which however are
-badly, badly realised (just today a POODLE attack against SSL)
+\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}