\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, likebirthday wishes to your grandmother. Why should you stillencrypt this message and your grandmother take the effort todecrypt 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}\pauseLets say I `found' \bl{$28305819$} and I try\begin{center}\large\bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip\end{center}\pauseSlightly lower. I might be tempted to try \bl{$28305820$}\ldots\pausebut 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}\bigskipBob 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\pauseIn order to cheat, Alice has to guess all bits in advance. Shehas 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 outthe \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 acorrect \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, likebirthday wishes to your grandmother. Why should you stillencrypt this message and your grandmother take the effort todecrypt 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 spyagencies argue that although they can follow the conversationson Twitter, they ``go dark'' on the encrypted message apps. Tocounter this ``going-dark problem'', the spy agencies push forthe implementation of back-doors in iMessage and Facebook andSkype and everything else UK or US-made, which they can useeavesdrop on conversations without the conversants' knowledgeor 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 brokenin around 50 days (obviously this time varies a lot and alsogets shorter and shorter over time). Do you think it is goodpolicy to require users to change their password every 3months (as King's did until recently)?\medskipUnder whichcircumstance should users be required to change theirpassword?\end{bubble} \end{frame}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: