39 \item you can still send me your homework\bigskip 

    39 \item Imagine you have an completely innocent email message,

    40 \item Unix AC question: use a terminal-based editor (vm, 

    40       like birthday wishes to your grandmother? Why should you

    41   vim)\bigskip 

    41       still encrypt this message and your grandmother take the

    42 \item exams: 2 out of 3 questions, 5 or so subquestions 

    42       effort to decrypt it?\bigskip 

    43   each, you can fill in your answers on the question sheet

    43 

    44       \small  

    45       (Hint: The answer has nothing to do with preserving the

    46       privacy of your grandmother and nothing to do with

    47       keeping her birthday wishes super-secret. Also nothing to

    48       do with you and grandmother testing the latest

    49       encryption technology, nor just for the sake of it.)

    54 The interlock protocol (``best bet'' against MITM):

    69 Protocol between a car \bl{$C$} and a key transponder \bl{$T$}:\bigskip 

    55 

    70 

    56 \begin{center}

    71 \begin{enumerate}

    57 \begin{tabular}{ll@{\hspace{2mm}}l}

    72 \item \bl{$C$} generates a random number \bl{$N$}

    58 1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\\

    73 \item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$}

    59 2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\\

    74 \item \bl{$C \to T$}: \bl{$N, F$}\bigskip

    60 3. & & \bl{$\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$}\\

    75 \item \bl{$T$} calculates \bl{$(F',G') = \{N\}_K$}

    61    & & \bl{$\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$}\\

    76 \item \bl{$T$} checks that \bl{$F = F'$}

    62 4. & \bl{$A \to B :$} & \bl{$H_1$}\\

    77 \item \bl{$T \to C$}: \bl{$N, G'$}

    63 5. & \bl{$B \to A :$} & \bl{$\{H_1, M_1\}_{K^{pub}_A}$}\\

    78 \item \bl{$C$} checks that \bl{$G = G'$}

    64 6. & \bl{$A \to B :$} & \bl{$\{H_2, M_1\}_{K^{pub}_B}$}\\

    79 \end{enumerate}

    65 7. & \bl{$B \to A :$} & \bl{$M_2$}

    80 

    81 \end{frame}

    82 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

    83 

    84 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    85 \begin{frame}[c]

    86 \frametitle{Zero-Knowledge Proofs}

    87 

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

    89 

    90 \begin{itemize}

    91 \item modular logarithms: Alice chooses public \bl{$A$},  \bl{$B$}, \bl{$p$}; and private \bl{$x$}

    92 

    93 \begin{center}

    94 \large\bl{$A^x \equiv B\; mod\; p$}

    95 \end{center} 

    96 \end{itemize}

    97 

    98 \end{frame}

    99 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   100 

   101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   102 \begin{frame}[c]

   103 \frametitle{Modular Arithmetic}

   104 

   105 It is easy to calculate

   106 

   107 \begin{center}

   108 \large\bl{$\alt<1>{?}{10} \equiv 46\; mod\; 12$}

   109 \end{center}\bigskip\pause 

   110 

   111 A: \bl{$10$}

   112 

   113 \end{frame}

   114 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   115 

   116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   117 \begin{frame}[c]

   118 \frametitle{Modular Logarithm}

   119 

   120 Ordinary, non-modular logarithms: 

   121 

   122 \begin{center}\large

   123 \begin{tabular}{ll}

   124 & \bl{$10^? = 17$}\bigskip\\\pause

   125 $\Rightarrow$ & \bl{$log_{10} 17 = 1.2304489\ldots$}\\\pause

   126 $\Rightarrow$ & \bl{$10^{1.2304489} = 16.999999$}\\\pause

    69 \footnotesize

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

    70 \bl{$m$} = How is your grandmother? \bl{$m'$} = How is the

   147 

    71 weather today in London?

   148 \begin{center}\large

   149 \bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip\\\pause

   150 \end{center}\pause

   151 

   152 I could be tempted to try \bl{$28305820$}\ldots\pause

   153 but the real\\

   154 \mbox{}\hfill answer is \bl{12314}.

   155 

   156 \end{frame}

   157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   158 

   159 

   160 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   161 \begin{frame}[c]

   162 \frametitle{Commitment Stage}

   163 

   164 \begin{enumerate}

   165 \item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}.

   166 \item Alice sends Bob for all \bl{$1..z$} 

   167 \begin{center}

   168 \bl{$h_i = A^{r_i} \;mod\; p$}

   169 \end{center}\bigskip

   170 \item Bob generates random bits   \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin

   171 \item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where

   172 

   173 \begin{center}

   174 \begin{tabular}{ll}

   175 \bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\

   176 \bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\

   177 \end{tabular}

   178 \end{center}

   179 where \bl{$r_j$} is the lowest \bl{$j$} with \bl{$b_j = 1$}

   180 \end{enumerate}

   181 

   182 \only<2>{

   183 \begin{textblock}{7}(7.9,3.9)

   184 \begin{bubble}[5cm]\small

   185 \begin{center}

   186   \begin{tabular}{lcccc}

   187   Alice \bl{$r_i$}:\; & \bl{4} & \bl{9} & \bl{1} & \bl{3}\\ 

   188   Bob \bl{$b_i$}:\; & \bl{0} & \bl{1} & \bl{0} & \bl{1}\\

   189   & & \bl{$\uparrow$} \\

   190   & & \bl{$j$}

   191   \end{tabular}             

   192   \end{center}    

   193 \end{bubble}

   194 \end{textblock}}

   195 

   196 \end{frame}

   197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   198 

   199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   200 \begin{frame}[c]

   201 \frametitle{Confirmation Stage}

   202 

   203 \begin{enumerate}

   204 \item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol

   205 

   206 \begin{center}

   207 \begin{tabular}{ll}

   208 \bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv h_i\;mod\;p$}\\

   209 \bl{$b_i = 1$}: & \bl{$A^{s_i}  \equiv h_i * h_j^{-1}  \;mod\; p$}\\

   210 \end{tabular}

   211 \end{center}\bigskip

   212 

   213 Bob was sent

   214 

   215 \begin{center}

   216 \begin{tabular}{l}

   217 \bl{$h_1, \ldots, h_z$},\\

   218 \bl{$r_1 - r_j$},  \bl{$r_2 - r_j$}, \ldots, \bl{$r_z - r_j \;\;mod \;p - 1$} 

   219 \end{tabular}

   220 \end{center}

   221 

   222 where the corresponding bits were 

   223 \bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$}

   224 \end{enumerate}

   225 

   226 \only<2>{

   227 \begin{textblock}{7}(7.9,1)

   228 \begin{bubble}[5cm]\small

   229 \begin{center}

   230 \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

   231 $A^{s_i}$ & $=$ & $A^{r_i - r_j}$\\ 

   232           & $=$ & $A^{r_i} * A^{-r_j}$\\

   233           & $=$ & $h_{r_i} * h_{r_j}^{-1}\;mod\;p$   

   234 \end{tabular}}

   235 \end{center}    

   236 \end{bubble}

   237 \end{textblock}}

   238 

   239 \end{frame}

   240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   241 

   242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   243 \begin{frame}[c]

   244 \frametitle{Proving Stage}

   245 

   246 \begin{enumerate}

   247 \item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\

   248 she sends

   249 

   250 \begin{center}

   251 \bl{$s_{z+1} = (x - r_j)$}

   252 \end{center}

   253 

   254 \item Bob confirms

   255 

   256 \begin{center}

   257 \bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$}

   258 \end{center}

   259 \end{enumerate}\bigskip\pause

   260 

   261 In order to cheat, Alice has to guess all bits in advance. She

   262 has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\

   263 

   264 \end{frame}

   265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   266 

   267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   268 \tikzset{alt/.code args={<#1>#2#3#4}{%

   269   \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path

   270 }}

   271 

   272 \begin{frame}[t]

   273 \frametitle{Buffer Overflow Attacks}

   274 

   275 \begin{itemize}

   276 \item the problem arises from the way C/C++ organises its function calls\\[-8mm]\mbox{}

   277 \end{itemize}

   278 

   279 \begin{center}

   280 \begin{tikzpicture}[scale=1]

   281 %\draw[black!10,step=2mm] (0,0) grid (9,4);

   282 %\draw[black!10,thick,step=10mm] (0,0) grid (9,4);

   283 

   284 \node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}};

   285 \draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8);

   286 \draw[line width=0mm, white, alt=<9->{fill=red}{fill=blue}] (0,0.2) rectangle (1,0.5);

   287 \draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5);

   288 \draw[line width=1mm, alt=<6->{fill=red}{fill=blue}] (0,1.0) rectangle (1,2.0);

   289 \draw[line width=1mm, alt=<7->{fill=yellow}{fill=blue}] (0,0.5) rectangle (1,1.0);

   290 \draw[line width=1mm] (0,0) -- (0,4);

   291 \draw[line width=1mm] (1,0) -- (1,4);

   292 

   293 \node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}};

   294 \draw[line width=1mm, alt=<{4-5,8}>{fill=red}{fill=blue}] (3,1.0) rectangle (4,3.0);

   295 

   296 \onslide<3-4>{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);}

   297 \onslide<5>{\draw[<-, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {res=24} (3,1);}

   298 

   299 \onslide<7-8>{\draw[->, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {n=3} (3,3);}

   300 \onslide<9>{\draw[<-, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {res=6} (3,1);}

   301 

   302 

   303 \node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}};

   304 \draw[line width=1mm] (7,3.5) -- (7,0.5) -- (8.5,0.5) -- (8.5,3.5);

   305 

   306 \onslide<3,4,7,8>{

   307 \node at (7.75, 1.4) {ret};

   308 \draw[line width=1mm] (7,1.1) -- (8.5,1.1);

   309 \node at (7.75, 2.0) {sp};

   310 \draw[line width=1mm] (7,2.3) -- (8.5,2.3);

   311 }

   312 \onslide<3,4>{

   313 \node at (7.75, 0.8) {4};

   314 \draw[line width=1mm] (7,1.7) -- (8.5,1.7);

   315 }

   316 \onslide<7,8>{

   317 \node at (7.75, 0.8) {3};

   318 \draw[line width=1mm] (7,1.7) -- (8.5,1.7);

   319 }

   320 

   321 

   322 \end{tikzpicture}

   323 \end{center}

   324 

   325 \end{frame}

   326 

   327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   328 \begin{frame}[t]

   329 

   330 \begin{center}

   331 \begin{tikzpicture}[scale=1]

   332 %\draw[black!10,step=2mm] (0,0) grid (9,4);

   333 %\draw[black!10,thick,step=10mm] (0,0) grid (9,4);

   334 

   335 \node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}};

   336 \draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8);

   337 \draw[line width=1mm, white, fill=blue] (0,1.0) rectangle (1,2.0);

   338 \draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5);

   339 \draw[line width=1mm] (0,0) -- (0,4);

   340 \draw[line width=1mm] (1,0) -- (1,4);

   341 

   342 \node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}};

   343 \draw[line width=0mm, alt=<{4-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,3.0);

   344 \draw[line width=0mm, alt=<{5-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,2.0);

   345 \draw[line width=0mm, alt=<{7-}>{red, fill=red}{blue, fill=blue}] (3,2.0) rectangle (4,1.0);

   346 \draw[line width=1mm] (3,1.0) rectangle (4,3.0);

   347 

   348 \onslide<3->{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);}

   349 \onslide<5->{\draw[<-, line width=2mm,red] (4,2) to node [above,sloped,midway] 

   350 {\begin{tabular}{l}user\\[-1mm] input\end{tabular}} (6,2);}

   351 \onslide<8->{\draw[<-, line width=1mm,red] (1,-2) to (3,1);}

   352 

   353 \node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}};

   354 \draw[line width=1mm] (7,3.5) -- (7,-0.1) -- (8.5,-0.1) -- (8.5,3.5);

   355 

   356 \onslide<3->{

   357 \node at (7.75, 0.2) {4};

   358 \draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,0.5) rectangle (8.5,1.1);

   359 \node at (7.75, 0.8) {\alt<6->{@a\#}{ret}};

   360 \draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,1.1) rectangle (8.5,1.7);

   361 \node at (7.75, 1.4) {\alt<6->{!?w;}sp};

   362 }

   363 

   364 \onslide<4->{

   365 \draw[line width=1mm,fill=red] (7,1.7) rectangle (8.5,3.0);

   366 \node[white] at (7.75, 2.4) {buffer};

   367 }

   368 

   369 \end{tikzpicture}

   370 \end{center}

   371 

   372 \end{frame}

   373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   374 

   375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   376 \begin{frame}[c]

   377 

   378 \begin{itemize}

   379 \item Imagine you have an completely innocent email message,

   380       like birthday wishes to your grandmother? Why should you

   381       still encrypt this message and your grandmother take the

   382       effort to decrypt it?\bigskip 

   383 

   384       \small  

   385       (Hint: The answer has nothing to do with preserving the

   386       privacy of your grandmother and nothing to do with

   387       keeping her birthday wishes super-secret. Also nothing to

   388       do with you and grandmother testing the latest

   389       encryption technology, nor just for the sake of it.)

   390 \end{itemize}