# HG changeset patch # User Christian Urban # Date 1414629541 0 # Node ID 4f4612d5f6702d470695d49f1fef166e1bb1b99e # Parent 4796f424cf122be4a72d16095503accea518ed3a updated diff -r 4796f424cf12 -r 4f4612d5f670 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 4796f424cf12 -r 4f4612d5f670 handouts/ho05.tex --- 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} diff -r 4796f424cf12 -r 4f4612d5f670 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 4796f424cf12 -r 4f4612d5f670 slides/slides05.tex --- 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