Binary file handouts/ho05.pdf has changed

--- a/handouts/ho05.tex	Wed Oct 29 21:58:08 2014 +0000
+++ b/handouts/ho05.tex	Thu Oct 30 00:39:01 2014 +0000
@@ -580,26 +580,28 @@
 \end{tabular}
 \end{center}
 
-\noindent where in steps 6 and 8, $E$ can modify the
-messages by including the $E$ in the message. Both messages
-are received encrypted with $E$'s public key; therefore it
-can decrypt it and repackage it with new content. $A$ and $B$
-have no idea that they talking to an attacker. Because $E$
-can modify messages, it seems very difficult to defend 
-against this attack. 
+\noindent where in steps 6 and 8, $E$ can modify the messages
+by including the $E$ in the message. Both messages are
+received encrypted with $E$'s public key; therefore it can
+decrypt it and repackage it with new content. $A$ and $B$ have
+no idea that they talking to an attacker. To them all messages
+look legit. Because $E$ can modify messages, it seems very
+difficult to defend against this attack. 
 
 But there is a clever trick\ldots{}dare I say some magic.
 Modify the protocol above so that $A$ and $B$ send their 
-messages in two halves.
+messages in two halves, like
 
 \begin{center}
 \begin{tabular}{ll@{\hspace{2mm}}l}
 1) & $A \to B :$ & $K^{pub}_A$\smallskip\\
 2) & $B \to A :$ & $K^{pub}_B$\smallskip\\
 3) & & $\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$\\
+   & & $\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$\\
 4) & $A \to B :$ & $H_1$\smallskip\\
-5) & $B \to A :$ & $\{H_1\}_{K^{pub}_A}$\smallskip\\
-6) & $A \to B :$ & $H_2$
+5) & $B \to A :$ & $\{H_1, M_1\}_{K^{pub}_A}$\smallskip\\
+6) & $A \to B :$ & $\{H_2, M_1\}_{K^{pub}_B}$\smallskip\\
+7) & $B \to A :$ & $M_2$
 \end{tabular}
 \end{center}
 
@@ -608,7 +610,7 @@
 message into two halves. Say the encrypted message is
 
 \begin{center}
-\texttt{\Grid{0X1peUVTGJK0XI7G+H70mMjAM8piY0sI}}
+$\underbrace{\texttt{\Grid{0X1peUVTGJK0XI7G+H70mMjAM8piY0sI}}}_{\{A,m\}_{K^{pub}_B}}$
 \end{center}
  
 \noindent then $A$ splits it up into two halves
@@ -618,26 +620,161 @@
 $\underbrace{\texttt{\Grid{+H70mMjAM8piY0sI}}}_{H_2}$
 \end{center}
 
-\noindent sends the first half $H_1$ to $b$. $B$ (and also any
-potential attacker) cannot do much with this half. What $B$ 
-does, it encrypts it with $A$'s public key and sends it back
-to $A$. Now $A$ can decrypt it and if it matches with what it
-had send, it will send $B$ the second half $H_2$. Only after
-$B$ received this second part, it will be able to decrypt the
-entire message $\{A,m\}_{K^{pub}_B}$ and see what $A$ had 
-written.
+\noindent Similarly $B$ splits its message into two halves
+$M_1$ and $M_2$. However, $A$ initially only sends the first
+half $H_1$ to $B$. Which $B$ answers with the message
+consisting of the received $H_1$ and its own first half $M_1$
+encrypted with $A$'s public key. The message in step 5. $A$
+receives this message, decrypts it and only when the $H_1$
+matches with its first half it send out earlier, $A$
+will send out the second half. See step 6. For this $A$
+adds the received $M_1$ and encrypts both parts with $B$'s
+public key. Finally $B$ checks whether the received $M_1$
+matches with its first half, and if yes sends $A$ its
+second half $M_2$. Now $A$ and $B$ are in the possession 
+of $H_1$ and $H_2$, respectively $M_1$ and $M_2$ and can
+decrypt the corresponding messages.
+
+Now the big question is, why on earth does this splitting
+of messages in half and additional message exchange help
+with defending agains person-in-the-middle attacks? Well,
+lets try to be such an attacker. As before we intercept
+the messages where public keys are exchanged and inject
+our own.
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+1) & $A \to E :$ & $K^{pub}_A$\smallskip\\
+2) & $E \to B :$ & $K^{pub}_E$\smallskip\\
+3) & $B \to E :$ & $K^{pub}_B$\smallskip\\
+4) & $E \to A :$ & $K^{pub}_E$
+\end{tabular}
+\end{center}
+
+\noindent 
+Now $A$ and $B$ build the message halves:
+
+\[
+\{A,m\}_{K^{pub}_E} \;\mapsto\; H_1,H_2\qquad
+\{B,m'\}_{K^{pub}_E} \;\mapsto\; M_1,M_2
+\]
+
+\noindent and $A$ sends $E$ its first half of the message.
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+5) & $A \to E :$ & $H_1$
+\end{tabular}
+\end{center}
+
+\noindent Neither $E$ nor $B$ can do much with this message.
+Remember it is only half of some ``garbled'' text that cannot
+be decrypted. $E$ could try to forward the message to $B$ and
+see what its reply is.
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+6) & $E \to B :$ & $H_1$\\
+7) & $B \to E :$ & $\{H_1, M_1\}_{K^{pub}_E}$
+\end{tabular}
+\end{center}
+
+\noindent Although $E$ can decrypt the message with its
+private key, but it only gets the halves $H_1$ and $M_1$ which
+are of no use yet. In order to get more information it
+can send the message to $A$ with $A$'s public key.
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+8) & $E \to A :$ & $\{H_1, M_1\}_{K^{pub}_A}$
+\end{tabular}
+\end{center}
 
+\noindent $A$ would receive this message, decrypt it and
+find out it matches with its expectation. It therefore
+sends out the message 
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+9) & $A \to E :$ & $\{H_2, M_1\}_{K^{pub}_E}$
+\end{tabular}
+\end{center}
+
+\noindent Now $E$ is in the possession of $H_1$ and $H_2$,
+which it can join together in order to obtain
+$\{A,m\}_{K^{pub}_E}$ which it can decrypt. It seems
+like from now on all is lost, but lets see: in order to
+stay undetected it must send a message to $B$. It now has two
+options: one is to use the newly obtained knowledge and
+modify $A$'s message to be 
+
+\[
+\{E,m\}_{K^{pub}_B} \;\mapsto\; H'_1,H'_2
+\]
+
+\noindent But notice since $E$ changed the message,
+it will now receive two different halves. Let us call
+them $H'_1$ and $H'_2$. If $E$ now sends $B$ the $H'_2$,
+$B$ will be in the possession of $H_1$ and $H'_2$. But
+after joining both halves it will not be able to 
+decrypt the resulting message---the two halves simply
+do not fit. So it can only send out the original $H_2$
+as follows:
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+10) & $E \to B :$ & $\{H_2, M_1\}_{K^{pub}_B}$
+\end{tabular}
+\end{center}
+
+\noindent 
+In this case $B$ can make sense out of the message and
+as a result sends $E$ back its second half $M_2$.
+
+\begin{center}
+\begin{tabular}{ll@{\hspace{2mm}}l}
+11) & $B \to E :$ & $M_2$
+\end{tabular}
+\end{center}
+
+\noindent $E$ might be ecstatic by now, because it has now
+also received $M_1$ and $M_2$ which it can join to
+get $\{B, m'\}_{K^{pub}_E}$. It can decrypt this message
+but still is not finished completely, because it has to send
+$A$ a message. It could try to build the message 
+$\{E, m'\}_{K^{pub}_A}$, but like above $A$ would not be able
+to make sense out of the two halves (which again do not fit 
+together). So the only option is to send $M_2$. 
+
+With this the protocol has ended. $E$ was able to decrypt all
+messages, but what messages did $A$ and $B$ receive and from
+whom? Do you notice that they will find out that something
+strange has happened and probably not talk on this channel
+anymore? I leave you to think about it.
+
+Recall from the beginning that a person-in-the middle
+attack can easily be mounted at the key fob and car
+protocol unless we are careful. If you look at actual
+key fob protocols, they use a variant of the protocol
+described above. Suppose $C$ is the car and $T$ is the key fob
+(transponder). The HiTag2 protocol used in cars of
+VW \& friends is as follows: 
 
 \begin{enumerate}
-\item $C$ generates a random number $r$
-\item $C$ calculates $(F,G) = \{r\}_K$
-\item $C \to T$: $r, F$
-\item $T$ calculates $(F',G') = \{r\}_K$
+\item $C$ generates a random number $N$
+\item $C$ calculates $\{N\}_K \mapsto F,G$
+\item $C \to T$: $N, F$
+\item $T$ calculates $\{N\}_K \mapsto F',G'$
 \item $T$ checks that $F = F'$
-\item $T \to C$: $r, G'$
+\item $T \to C$: $N, G'$
 \item $C$ checks that $G = G'$
 \end{enumerate}
 
+\noindent The assumption is that the key $K$ is only known to
+the car and the transponder. Again, I leave it to you to find
+out the magic why this protocol is immune from
+person-in-the-middle attacks. 
+
 
 \subsubsection*{Further Reading}
 

Binary file slides/slides05.pdf has changed

--- a/slides/slides05.tex	Wed Oct 29 21:58:08 2014 +0000
+++ b/slides/slides05.tex	Thu Oct 30 00:39:01 2014 +0000
@@ -404,10 +404,10 @@
 \begin{itemize}
 \item \bl{$A$} sends public key  to \bl{$B$}
 \item \bl{$B$} sends public key  to \bl{$A$}
-\item \bl{$A$} encrypts message with \bl{$B$}'s public key, 
-  send's {\bf half} of the message to \bl{$B$}
-\item \bl{$B$} encrypts message with \bl{$A$}'s public key, 
- send's {\bf half} of the message back to \bl{$A$}
+\item \bl{$A$} encrypts a message with \bl{$B$}'s public key, 
+  sends {\bf half} of the message to \bl{$B$}
+\item \bl{$B$} encrypts a message with \bl{$A$}'s public key, 
+ sends {\bf half} of the message back to \bl{$A$}
 \item \bl{$A$} sends other half, \bl{$B$} can now decrypt 
  entire message
 \item \bl{$B$} sends other half, \bl{$A$} can now decrypt