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

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

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

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

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

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

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

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

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

   587 no idea that they talking to an attacker. To them all messages

   588 can modify messages, it seems very difficult to defend 

   588 look legit. Because $E$ can modify messages, it seems very

   589 against this attack. 

   589 difficult to defend against this attack. 

   593 messages in two halves.

   593 messages in two halves, like

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

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

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

   603 6) & $A \to B :$ & $\{H_2, M_1\}_{K^{pub}_B}$\smallskip\\

   604 7) & $B \to A :$ & $M_2$

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

   613 $\underbrace{\texttt{\Grid{0X1peUVTGJK0XI7G+H70mMjAM8piY0sI}}}_{\{A,m\}_{K^{pub}_B}}$

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

   623 \noindent Similarly $B$ splits its message into two halves

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

   624 $M_1$ and $M_2$. However, $A$ initially only sends the first

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

   625 half $H_1$ to $B$. Which $B$ answers with the message

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

   626 consisting of the received $H_1$ and its own first half $M_1$

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

   627 encrypted with $A$'s public key. The message in step 5. $A$

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

   628 receives this message, decrypts it and only when the $H_1$

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

   629 matches with its first half it send out earlier, $A$

   628 written.

   630 will send out the second half. See step 6. For this $A$

   629 

   631 adds the received $M_1$ and encrypts both parts with $B$'s

   632 public key. Finally $B$ checks whether the received $M_1$

   633 matches with its first half, and if yes sends $A$ its

   634 second half $M_2$. Now $A$ and $B$ are in the possession 

   635 of $H_1$ and $H_2$, respectively $M_1$ and $M_2$ and can

   636 decrypt the corresponding messages.

   637 

   638 Now the big question is, why on earth does this splitting

   639 of messages in half and additional message exchange help

   640 with defending agains person-in-the-middle attacks? Well,

   641 lets try to be such an attacker. As before we intercept

   642 the messages where public keys are exchanged and inject

   643 our own.

   644 

   645 \begin{center}

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

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

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

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

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

   651 \end{tabular}

   652 \end{center}

   653 

   654 \noindent 

   655 Now $A$ and $B$ build the message halves:

   656 

   657 \[

   658 \{A,m\}_{K^{pub}_E} \;\mapsto\; H_1,H_2\qquad

   659 \{B,m'\}_{K^{pub}_E} \;\mapsto\; M_1,M_2

   660 \]

   661 

   662 \noindent and $A$ sends $E$ its first half of the message.

   663 

   664 \begin{center}

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

   666 5) & $A \to E :$ & $H_1$

   667 \end{tabular}

   668 \end{center}

   669 

   670 \noindent Neither $E$ nor $B$ can do much with this message.

   671 Remember it is only half of some ``garbled'' text that cannot

   672 be decrypted. $E$ could try to forward the message to $B$ and

   673 see what its reply is.

   674 

   675 \begin{center}

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

   677 6) & $E \to B :$ & $H_1$\\

   678 7) & $B \to E :$ & $\{H_1, M_1\}_{K^{pub}_E}$

   679 \end{tabular}

   680 \end{center}

   681 

   682 \noindent Although $E$ can decrypt the message with its

   683 private key, but it only gets the halves $H_1$ and $M_1$ which

   684 are of no use yet. In order to get more information it

   685 can send the message to $A$ with $A$'s public key.

   686 

   687 \begin{center}

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

   689 8) & $E \to A :$ & $\{H_1, M_1\}_{K^{pub}_A}$

   690 \end{tabular}

   691 \end{center}

   692 

   693 \noindent $A$ would receive this message, decrypt it and

   694 find out it matches with its expectation. It therefore

   695 sends out the message 

   696 

   697 \begin{center}

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

   699 9) & $A \to E :$ & $\{H_2, M_1\}_{K^{pub}_E}$

   700 \end{tabular}

   701 \end{center}

   702 

   703 \noindent Now $E$ is in the possession of $H_1$ and $H_2$,

   704 which it can join together in order to obtain

   705 $\{A,m\}_{K^{pub}_E}$ which it can decrypt. It seems

   706 like from now on all is lost, but lets see: in order to

   707 stay undetected it must send a message to $B$. It now has two

   708 options: one is to use the newly obtained knowledge and

   709 modify $A$'s message to be 

   710 

   711 \[

   712 \{E,m\}_{K^{pub}_B} \;\mapsto\; H'_1,H'_2

   713 \]

   714 

   715 \noindent But notice since $E$ changed the message,

   716 it will now receive two different halves. Let us call

   717 them $H'_1$ and $H'_2$. If $E$ now sends $B$ the $H'_2$,

   718 $B$ will be in the possession of $H_1$ and $H'_2$. But

   719 after joining both halves it will not be able to 

   720 decrypt the resulting message---the two halves simply

   721 do not fit. So it can only send out the original $H_2$

   722 as follows:

   723 

   724 \begin{center}

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

   726 10) & $E \to B :$ & $\{H_2, M_1\}_{K^{pub}_B}$

   727 \end{tabular}

   728 \end{center}

   729 

   730 \noindent 

   731 In this case $B$ can make sense out of the message and

   732 as a result sends $E$ back its second half $M_2$.

   733 

   734 \begin{center}

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

   736 11) & $B \to E :$ & $M_2$

   737 \end{tabular}

   738 \end{center}

   739 

   740 \noindent $E$ might be ecstatic by now, because it has now

   741 also received $M_1$ and $M_2$ which it can join to

   742 get $\{B, m'\}_{K^{pub}_E}$. It can decrypt this message

   743 but still is not finished completely, because it has to send

   744 $A$ a message. It could try to build the message 

   745 $\{E, m'\}_{K^{pub}_A}$, but like above $A$ would not be able

   746 to make sense out of the two halves (which again do not fit 

   747 together). So the only option is to send $M_2$. 

   748 

   749 With this the protocol has ended. $E$ was able to decrypt all

   750 messages, but what messages did $A$ and $B$ receive and from

   751 whom? Do you notice that they will find out that something

   752 strange has happened and probably not talk on this channel

   753 anymore? I leave you to think about it.

   754 

   755 Recall from the beginning that a person-in-the middle

   756 attack can easily be mounted at the key fob and car

   757 protocol unless we are careful. If you look at actual

   758 key fob protocols, they use a variant of the protocol

   759 described above. Suppose $C$ is the car and $T$ is the key fob

   760 (transponder). The HiTag2 protocol used in cars of

   761 VW \& friends is as follows: 

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

   764 \item $C$ generates a random number $N$

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

   765 \item $C$ calculates $\{N\}_K \mapsto F,G$

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

   766 \item $C \to T$: $N, F$

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

   767 \item $T$ calculates $\{N\}_K \mapsto F',G'$

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

   769 \item $T \to C$: $N, G'$