461 $A \rightarrow S :$ & $A, B$\\

   461 $A \to S :$ & $A, B$\\

   462 $S \rightarrow A :$ & $\{K_{AB}\}_{K_{AS}}$ and $\{\{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$\\

   462 $S \to A :$ & $\{K_{AB}\}_{K_{AS}}$ and $\{\{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$\\

   463 $A \rightarrow B :$ & $\{K_{AB}\}_{K_{BS}}$\\

   463 $A \to B :$ & $\{K_{AB}\}_{K_{BS}}$\\

   464 $A \rightarrow B :$ & $\{m\}_{K_{AB}}$\\

   464 $A \to B :$ & $\{m\}_{K_{AB}}$\\

   538 The problem we want to study closer here is that

   538 The problem we want to study closer here is that protocols

   539 public-private key encryption is susceptible to

   539 based on public-private key encryption are susceptible to

   541 where $A$ and $B$ attempt to exchange secret messages using 

   541 where $A$ and $B$ attempt to exchange secret messages using

   547 \item $A$ sends message encrypted with $B$'s public 

   547 \item $A$ sends a message encrypted with $B$'s public 

   549 \item $B$ sends message encrypted with $A$'s public 

   549 \item $B$ sends a message encrypted with $A$'s public 

   553 

   553 \noindent In our formal notation for protocols, this would

   554 \bigskip\bigskip Keyfobs - protocol

   554 look as follows:

   555 

   556 \begin{center}

   557 \begin{tabular}{l@{\hspace{2mm}}l}

   558 $A \to B :$ & $K^{pub}_A$\smallskip\\

   559 $B \to A :$ & $K^{pub}_B$\smallskip\\

   560 $A \to B :$ & $\{A,m\}_{K^{pub}_B}$\smallskip\\

   561 $B \to A :$ & $\{B,m'\}_{K^{pub}_A}$

   562 \end{tabular}

   563 \end{center}

   564 

   565 \noindent Since we assume an attacker, say $E$, has complete

   566 control over the network, $E$ can intercept the first two 

   567 messages and substitutes her own public key. The protocol

   568 run would therefore be

   569 

   570 \begin{center}

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

   572 1) & $A \to E :$ & $K^{pub}_A$\smallskip\\

   573 2) & $E \to B :$ & $K^{pub}_E$\smallskip\\

   574 3) & $B \to E :$ & $K^{pub}_B$\smallskip\\

   575 4) & $E \to A :$ & $K^{pub}_E$\smallskip\\

   576 5) & $A \to E :$ & $\{A,m\}_{K^{pub}_E}$\smallskip\\

   577 6) & $E \to B :$ & $\{E,m\}_{K^{pub}_B}$\smallskip\\

   578 7) & $B \to E :$ & $\{B,m'\}_{K^{pub}_E}$\smallskip\\

   579 8) & $E \to A :$ & $\{E,m'\}_{K^{pub}_A}$

   580 \end{tabular}

   581 \end{center}

   582 

   583 \noindent where in steps 6 and 8, $E$ can modify the

   584 messages by including the $E$ in the message. Both messages

   585 are received encrypted with $E$'s public key; therefore it

   586 can decrypt it and repackage it with new content. $A$ and $B$

   587 have no idea that they talking to an attacker. Because $E$

   588 can modify messages, it seems very difficult to defend 

   589 against this attack. 

   590 

   591 But there is a clever trick\ldots{}dare I say some magic.

   592 Modify the protocol above so that $A$ and $B$ send their 

   593 messages in two halves.

   594 

   595 \begin{center}

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

   597 1) & $A \to B :$ & $K^{pub}_A$\smallskip\\

   598 2) & $B \to A :$ & $K^{pub}_B$\smallskip\\

   599 3) & & $\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$\\

   600 4) & $A \to B :$ & $H_1$\smallskip\\

   601 5) & $B \to A :$ & $\{H_1\}_{K^{pub}_A}$\smallskip\\

   602 6) & $A \to B :$ & $H_2$

   603 \end{tabular}

   604 \end{center}

   605 

   606 \noindent The idea is that in step 3, $A$ encrypts the

   607 message (with $B$'s public key) and then splits the encrypted

   608 message into two halves. Say the encrypted message is

   609 

   610 \begin{center}

   611 \texttt{\Grid{0X1peUVTGJK0XI7G+H70mMjAM8piY0sI}}

   612 \end{center}

   613  

   614 \noindent then $A$ splits it up into two halves

   615 

   616 \begin{center}

   617 $\underbrace{\texttt{\Grid{0X1peUVTGJK0XI7G}}}_{H_1}$\qquad

   618 $\underbrace{\texttt{\Grid{+H70mMjAM8piY0sI}}}_{H_2}$

   619 \end{center}

   620 

   621 \noindent sends the first half $H_1$ to $b$. $B$ (and also any

   622 potential attacker) cannot do much with this half. What $B$ 

   623 does, it encrypts it with $A$'s public key and sends it back

   624 to $A$. Now $A$ can decrypt it and if it matches with what it

   625 had send, it will send $B$ the second half $H_2$. Only after

   626 $B$ received this second part, it will be able to decrypt the

   627 entire message $\{A,m\}_{K^{pub}_B}$ and see what $A$ had 

   628 written.

   629 

   630 

   631 \begin{enumerate}

   632 \item $C$ generates a random number $r$

   633 \item $C$ calculates $(F,G) = \{r\}_K$

   634 \item $C \to T$: $r, F$

   635 \item $T$ calculates $(F',G') = \{r\}_K$

   636 \item $T$ checks that $F = F'$

   637 \item $T \to C$: $r, G'$

   638 \item $C$ checks that $G = G'$

   639 \end{enumerate}

   640