# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1414619888 0
# Node ID 4796f424cf122be4a72d16095503accea518ed3a
# Parent  8f2749152f1ec555df20440232ec6aaba1355961
updated

diff -r 8f2749152f1e -r 4796f424cf12 handouts/ho05.pdf
Binary file handouts/ho05.pdf has changed
diff -r 8f2749152f1e -r 4796f424cf12 handouts/ho05.tex
--- a/handouts/ho05.tex	Wed Oct 29 19:36:15 2014 +0000
+++ b/handouts/ho05.tex	Wed Oct 29 21:58:08 2014 +0000
@@ -458,10 +458,10 @@
 
 \begin{center}
 \begin{tabular}{l@{\hspace{2mm}}l}
-$A \rightarrow S :$ & $A, B$\\
-$S \rightarrow A :$ & $\{K_{AB}\}_{K_{AS}}$ and $\{\{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$\\
-$A \rightarrow B :$ & $\{K_{AB}\}_{K_{BS}}$\\
-$A \rightarrow B :$ & $\{m\}_{K_{AB}}$\\
+$A \to S :$ & $A, B$\\
+$S \to A :$ & $\{K_{AB}\}_{K_{AS}}$ and $\{\{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$\\
+$A \to B :$ & $\{K_{AB}\}_{K_{BS}}$\\
+$A \to B :$ & $\{m\}_{K_{AB}}$\\
 \end{tabular}
 \end{center}
 
@@ -535,23 +535,109 @@
 really the wrong incentive for the certification organisations
 to clean up their mess.
 
-The problem we want to study closer here is that
-public-private key encryption is susceptible to
+The problem we want to study closer here is that protocols
+based on public-private key encryption are susceptible to
 person-in-the-middle attack. Consider the following protocol
-where $A$ and $B$ attempt to exchange secret messages using 
+where $A$ and $B$ attempt to exchange secret messages using
 public-private keys. 
 
 \begin{itemize}
 \item $A$ sends public key  to $B$
 \item $B$ sends public key  to $A$
-\item $A$ sends message encrypted with $B$'s public 
+\item $A$ sends a message encrypted with $B$'s public 
 key,\\ $B$ decrypts it with its private key
-\item $B$ sends message encrypted with $A$'s public 
+\item $B$ sends a message encrypted with $A$'s public 
 key,\\ $A$ decrypts it with its private key
 \end{itemize}
   
+\noindent In our formal notation for protocols, this would
+look as follows:
 
-\bigskip\bigskip Keyfobs - protocol
+\begin{center}
+\begin{tabular}{l@{\hspace{2mm}}l}
+$A \to B :$ & $K^{pub}_A$\smallskip\\
+$B \to A :$ & $K^{pub}_B$\smallskip\\
+$A \to B :$ & $\{A,m\}_{K^{pub}_B}$\smallskip\\
+$B \to A :$ & $\{B,m'\}_{K^{pub}_A}$
+\end{tabular}
+\end{center}
+
+\noindent Since we assume an attacker, say $E$, has complete
+control over the network, $E$ can intercept the first two 
+messages and substitutes her own public key. The protocol
+run would therefore be
+
+\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$\smallskip\\
+5) & $A \to E :$ & $\{A,m\}_{K^{pub}_E}$\smallskip\\
+6) & $E \to B :$ & $\{E,m\}_{K^{pub}_B}$\smallskip\\
+7) & $B \to E :$ & $\{B,m'\}_{K^{pub}_E}$\smallskip\\
+8) & $E \to A :$ & $\{E,m'\}_{K^{pub}_A}$
+\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. 
+
+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.
+
+\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$\\
+4) & $A \to B :$ & $H_1$\smallskip\\
+5) & $B \to A :$ & $\{H_1\}_{K^{pub}_A}$\smallskip\\
+6) & $A \to B :$ & $H_2$
+\end{tabular}
+\end{center}
+
+\noindent The idea is that in step 3, $A$ encrypts the
+message (with $B$'s public key) and then splits the encrypted
+message into two halves. Say the encrypted message is
+
+\begin{center}
+\texttt{\Grid{0X1peUVTGJK0XI7G+H70mMjAM8piY0sI}}
+\end{center}
+ 
+\noindent then $A$ splits it up into two halves
+
+\begin{center}
+$\underbrace{\texttt{\Grid{0X1peUVTGJK0XI7G}}}_{H_1}$\qquad
+$\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.
+
+
+\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 $T$ checks that $F = F'$
+\item $T \to C$: $r, G'$
+\item $C$ checks that $G = G'$
+\end{enumerate}
+
 
 \subsubsection*{Further Reading}
 
diff -r 8f2749152f1e -r 4796f424cf12 slides/slides05.pdf
Binary file slides/slides05.pdf has changed
diff -r 8f2749152f1e -r 4796f424cf12 slides/slides05.tex
--- a/slides/slides05.tex	Wed Oct 29 19:36:15 2014 +0000
+++ b/slides/slides05.tex	Wed Oct 29 21:58:08 2014 +0000
@@ -364,9 +364,9 @@
 \begin{itemize}
 \item \bl{$A$} sends public key  to \bl{$B$}
 \item \bl{$B$} sends public key  to \bl{$A$}
-\item \bl{$A$} sends message encrypted with \bl{$B$}'s public key, \bl{$B$} decrypts it
+\item \bl{$A$} sends a message encrypted with \bl{$B$}'s public key, \bl{$B$} decrypts it
 with its private key
-\item \bl{$B$} sends message encrypted with \bl{$A$}'s public key, \bl{$A$} decrypts it
+\item \bl{$B$} sends a message encrypted with \bl{$A$}'s public key, \bl{$A$} decrypts it
 with its private key
 \end{itemize}
 
@@ -387,7 +387,7 @@
 \item \bl{$B$} sends public key  to \bl{$A$} --- \bl{$C$} 
   intercepts this message and send his own public key 
   \bl{$A$}  
-\item \bl{$A$} sends message encrypted with \bl{$C$}'s public key, \bl{$C$} decrypts it
+\item \bl{$A$} sends a message encrypted with \bl{$C$}'s public key, \bl{$C$} decrypts it
 with its private key, re-encrypts with \bl{$B$}'s public key 
 \item similar the other way
 \end{itemize}
diff -r 8f2749152f1e -r 4796f424cf12 style.sty
--- a/style.sty	Wed Oct 29 19:36:15 2014 +0000
+++ b/style.sty	Wed Oct 29 21:58:08 2014 +0000
@@ -10,3 +10,19 @@
 
 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
 \definecolor{codegray}{gray}{0.9}
+
+\newcommand\grid[1]{%
+\begin{tikzpicture}[baseline=(char.base)]
+  \path[use as bounding box]
+    (0,0) rectangle (1em,1em);
+  \draw[red!50, fill=red!20]
+    (0,0) rectangle (1em,1em);
+  \node[inner sep=1pt,anchor=base west]
+    (char) at (0em,\gridraiseamount) {#1};
+\end{tikzpicture}}
+\newcommand\gridraiseamount{0.12em}
+
+\makeatletter
+\newcommand\Grid[1]{%
+  \@tfor\z:=#1\do{\grid{\z}}}
+\makeatother