\documentclass{article}\usepackage{../style}\usepackage{../langs}\usetikzlibrary{patterns,decorations.pathreplacing}\begin{document}\section*{Handout 5 (Protocols)}Protocols are the computer science equivalent to fractals andthe Mandelbrot set in mathematics. With the latter two youhave a simple formula, which you just iterate and then youtest whether a point is inside or outside a region\ldots{}itdoes not look exciting, but voila something magicallyhappened.\footnote{\url{http://en.wikipedia.org/wiki/Fractal},\url{http://en.wikipedia.org/wiki/Mandelbrot_set}} Protocolsare similar: they are simple exchanges of messages, but in theend something ``magical'' can happen---for example a secretchannel has been established or two entities haveauthenticated themselves to each other. Even in face of strongadversaries where we have no control over the network overwhich our messages are exchanged. The problem with magic is ofcourse it is poorly understood and even experts often got, andget, it wrong with protocols.To have an idea what kind of protocols we are interested in, letus look at a few examples. One example are (wireless) key fobs, which operate the central locking system and theignition in a car.\begin{center}\includegraphics[scale=0.075]{../pics/keyfob.jpg}\quad\includegraphics[scale=0.2025]{../pics/startstop.jpg}\end{center}\noindent The point of these key fobs is that everything isdone over the ``air''---there is no physical connectionbetween the key, doors and engine, as was the case with theold solid metal keys. With the key fobs we must achievesecurity by exchanging certain messages between the key fob onone side and the doors and engine on the other. Clearly whatwe like to accomplish is that I can get into my car and startit, but that thieves are kept out. The problem is thateverybody can ``overhear'' or skim the exchange of messagesbetween the key fob and car. In this scenario the simplestattack you need to defend against is a person-in-the-middleattack. For this imagine you park your car in front of asupermarket. One thief follows you with a strong transmitter.A second thief ``listens'' to the signals from the car andwirelessly transmits them to the ``colleague'' who followedyou. This thief silently enquires what the key fob answers.This answer is then send back to the thief at the car. If doneproperly the car will dutifully open and possibly start. Noneed to steal your keys anymore.But there are many more such protocols we like to treat.Another example is Wifi---you might sit at a Starbucks andtalk wirelessly to the free access point there and from theretalk to your bank. Moreover, even if your have to touch yourOyster card at the reader each time you enter or exit theTube, it actually operates wirelessly and with appropriateequipment over some quite large distance (several meters). Butthere are many, many more examples (Bitcoins, mobilephones,\ldots). The common characteristics of the protocols weare interested in is that an adversary or attacker is assumedto be in complete control over the network or channel overwhich we exchanging messages. An attacker can install a packetsniffer on a network, inject packets, modify packets, replayold messages, or fake pretty much everything else. In thishostile environment, the purpose of a protocol (that isexchange of messages) is to achieve some security goal. Forexample only allow the owner of the car in, but everybody elseshould stay out.The protocols we are interested here are generic descriptionsof how to exchange messages in order to achieve a goal. Unlikethe distant past where, for example, we had to meet a person inorder to authenticate him or her (via a passport for example),the problem we are facing on the Internet is that we cannoteasily be sure who we are ``talking'' to. The obvious reasonis that only some electrons arrive at our computer; we do notsee the person, or computer, behind the incoming electrons(messages). To start, let us look at one of the simplest protocols thatare part of the TCP protocol (which underlies the Internet).This protocol does not do anything security relevant, it justestablishes a ``hello'' from a client to a server which theserver answers with ``I heard you'' and the client answers in turn with something like ``thanks''. This protocolis often called a \emph{three-way handshake}. Graphically itcan be illustrated as follows\begin{center}\includegraphics[scale=0.5]{../pics/handshake.png}\end{center}\noindent On the left-hand side is a client, say Alice, on theright-hand side is a server, say. Time is running from top tobottom. Alice initial SYN message needs some time to travel tothe server. The server answers with SYN-ACK, which willrequire some time to arrive at Alice. Her answer ACK willagain take some time to arrive at the server. After the messages are exchanged Alice and the server simply have established a channel to communicate over. Alice doesnot know whether she is really talking to the server (somebody else on the network might have intercepted her messageand replied in place of the server). Similarly, theserver has no idea who it is talking to. That this can be established depends on what is exchanged next and is thepoint of the protocols we want to study in more detail.Before we start in earnest, we need to fix a moreconvenient notation for protocols. Drawing pictures likethe one above would be awkward in the long-run. Thenotation already abstracts away from a few details we arenot interested in: for example the time the messagesneed to travel between endpoints. What we are interestedin is in which order the messages are sent. For the SYN-ACKprotocol we will therefore use the notation \begin{equation}\begin{array}{l@{\hspace{2mm}}l}A \to S: & SYN\\S \to A: & SYN\_ACK\\A \to S: & ACK\\\end{array}\label{SYNACK}\end{equation}\noindent The left-hand side specifies who is the sender andwho is the receiver of the message. On the right of the colonis the message that is send. The order from top to downspecifies in which order the messages are sent. We alsohave the convention that messages like above $SYN$ are sendin clear-text over the network. If we want that a message is encrypted, then we use the notation\[\{msg\}_{K_{AB}}\] \noindent for messages. The curly braces indicate a kind ofenvelope which can only be opened if you know the key $K_{AB}$with which the message has been encrypted. We always assumethat an attacker, say Eve, cannot get the content of themessage, unless she is also in the possession of the key. Weexplicitly exclude in our study that the encryption can bebroken.\footnote{\ldots{}which of course is what a goodprotocol designer needs to ensure and more often than notprotocols are broken. For example Oyster cards contain a veryweak encryption mechanism which has been attacked.} It is alsopossible that an encrypted message contains several parts. Inthis case we would write something like\[\{msg_1, msg_2\}_{K_{AB}}\] \noindent But again Eve would not be able to know this unless she also has the key. We also allow the possibility that a message is encrypted twice under different keys. In this case we write\[\{\{msg\}_{K_{AB}}\}_{K_{BC}}\] \noindent The idea is that even if attacker Eve has thekey $K_{BC}$ she could decrypt the outer envelop, butstill do not get to the message, because it is stillencrypted with the key $K_{AB}$. Note, however,while an attacker cannot obtain the content of the messagewithout the key, encrypted messages can be observedand be recorded and then replayed at another time, orsend to another person!Another very important point is that the notation forprotocols such as shown in \eqref{SYNACK} is a\underline{schema} how the protocol should proceed.It could be instantiated by an actual protocol runbetween Alice, say, and the server Calcium at King's. In this case the specific instance would look like\[\begin{array}{l@{\hspace{2mm}}l}\text{Alice} \to \text{Calcium}: & SYN\\\text{Calcium} \to \text{Alice}: & SYN\_ACK\\\text{Alice} \to \text{Calcium}: & ACK\\\end{array}\]\noindent But a server like Calcium of course needs toserve many clients. So there could be the same protocolalso running with Bob, say\[\begin{array}{l@{\hspace{2mm}}l}\text{Bob} \to \text{Calcium}: & SYN\\\text{Calcium} \to \text{Bob}: & SYN\_ACK\\\text{Bob} \to \text{Calcium}: & ACK\\\end{array}\]\noindent And these two instances of the protocol could berunning in parallel or be at different stages. So the protocolschema shown in \eqref{SYNACK} can be thought of how two programs need to run on the side of $A$ and $S$ in order to successfully complete the protocol. But it is really just a blue print how the communication is supposed to proceed. This is actually already a way how such protocols can fail. Although very simple the $SYN\_ACK$ protocol can cause headaches for system administrators where an attackerstarts the protocol, but does not complete it. This looks graphically like\begin{center}\includegraphics[scale=0.4]{../pics/synflood.png}\end{center}\noindent The attacker sends lots of $SYN$ requests which theserver dutifully answers, but needs to keep track of suchprotocol exchanges. So every time a little bit of memoryresource will be eaten away on the server side until allresources are exhausted and when Alice tries to contact theserver then the server is overwhelmed and does not respondanymore. This kind of attack are called \emph{SYNfloods}.\footnote{\url{http://en.wikipedia.org/wiki/SYN_flood}}After reading four pages, you might be wondering where themagic is. For this let us take a closer look at authentication protocols.\subsubsection*{Authentication Protocols}The simplest authentication protocol between principals$A$ and $B$, say is\begin{center}$A \to B: K_{AB}$ \end{center}\noindent It can be sought of as $A$ sends a common secret to$B$ like a password. The idea is that if only $A$ and $B$ knowthe key $K_{AB}$ then this should be sufficient for $B$ toinfer it is talking to $A$. But this is of course too naive,if the message can be observed by everybody else on thenetwork. Eve could just record this message $A$ just send, andnext time send the same message to $B$ and $B$ would believeit talked to $A$. But actually it talked to Eve which nowclears out $A$s back account if $B$ had been a bank.A more sophisticated protocol which tries to avoid thereplay attack is as follows\begin{center}\begin{tabular}{l@{\hspace{2mm}}l}$A \to B:$ & $HELLO$\\$B \to A:$ & $N$\\$A \to B:$ & $\{N\}_{K_{AB}}$\\\end{tabular}\end{center} \noindent With this protocol the idea is that $A$ first sends a message to $B$ saying ``I want to talk to you''. $B$ sends then a challenge in form of a random number $N$. In protocols such random numbers are often called \emph{nonce}. What is thepurpose of this nonce? Well, if an attacker records $A$ answer, it will not make sense to replay this message, becausenext time this protocol is run the nonce $B$ sends will bedifferent. So if we run this protocol, what can $B$ infer:it has send out an (unpredictable) nonce to $A$ andreceived this challenge back, but encoded under the key $K_{AB}$. If $B$ assumes only $A$ and $B$ know the key $K_{AB}$and the nonce is unpredictable, then $B$ is able toinfer it must be talking to $A$. Of course the implicit assumption on this inference are that nobody else knowsabout the key $K_{AB}$ and nobody else can decrypt themessage. $B$ of course can decrypt the answer from $A$and check whether the answer corresponds to the challenge(nonce) $B$ has send earlier.But what about $A$? Can $A$ make any assumptions about who ittalks to? It dutifully answered the challenge and hopes itsbank, say, will be the only one to understand her answer. Butis this the case? No! Lets consider an attacker Eve who hascontrol over the network. She could have intercepted themessage $HELLO$ and just replied herself to $A$ using a randomnumber\ldots{} for example one which she observed in aprevious run of this protocol. Remember that if a message issend without curly braces it is sent in clear text. Then$A$ would encrypt the nonce with the key $K_{AB}$ and sendit back to Eve. She just throws the answer away. $A$ wouldhope that she talked to $B$ because she followed the protocol,but unfortunately she cannot be sure who she is talking to. The solution is to follow a \emph{mutual challenge-response}protocol. There $A$ already starts off with a challenge (nonce)on her own.\begin{center}\begin{tabular}{l@{\hspace{2mm}}l}$A \to B:$ & $N_A$\\$B \to A:$ & $\{N_A, N_B\}_{K_{AB}}$\\$A \to B:$ & $N_B$\\\end{tabular} \end{center}\noindent As seen, $B$ receives this nonce, $N_A$, adds hisown nonce, $N_B$ and encrypts it with the key $K_{AB}$. $A$receives this message, is able to decrypt it since we assumeshe has the key $K_{AB}$, and sends back the nonce of $B$.Let us analyse which assumptions $A$ and $B$ can make after the protocol has run. $B$ received a challenge and answered correctly to $A$ (in the encrypted message). An attackerwould just not be able to answer this challenge correctly because the attacker is assumed to not be in the possession ofthe key $K_{AB}$; so could not have formed this message.It could also not have just replayed an old message, because$A$ would send out each time a fresh nonce. So with thisprotocol you can ensure also for $A$ that it talks to $B$.I leave you to argue that $B$ can be sure to talk to $A$.Of course these arguments will depend on the assumptions thatonly $A$ and $B$ know the key $K_{AB}$ and that nobody canbreak the encryption unless they have this key and that thenonces are fresh each time the protocol is run.There might be something mysterious about the nonces, therandom numbers, that are sent around. They need to beunpredictable and in this way fulfil an important role inprotocols. Suppose\begin{enumerate}\item I generate a nonce and send it to you encrypted with a key we share\item you increase it by one, encrypt it under a key I know and send it back to me \end{enumerate}\noindent In our notation this would correspond to the protocol\begin{center}\begin{tabular}{l@{\hspace{2mm}}l}$I \to Y:$ & $\{N\}_{K_{IY}}$\\$Y \to I:$ & $\{N + 1\}_{K_{IY}}$\\\end{tabular} \end{center}\noindent What can I infer from this simple exchange:\begin{itemize}\item you must have received my message (it could not just be deflected by somebody on the network, because the response required some calculation; doing the calculation and sending the answer requires the key $K_{IY}$)\item you could only have generated your answer after I send you my initial message (since my $N$ is always new, it could not have been a message that was generated before I myself knew what $N$ is)\item if only you and me know the key $K_{IY}$, the message must have come from you\end{itemize}\noindent Even if this does not seem much information I canglean from such an exchange, it is in fact the basic building blocks for establishing some secret or achieving some security goal (like authentication).While the mutual challenge-response protocol solves alreadythe authentication problem, there are some problems. One is ofcourse that it requires a pre-shared secret key. That issomething that needs to be established beforehand. Not allsituations allow such an assumption. For example if I am awhistle blower (say Snowden) and want to talk to a journalist(say Greenwald) then I might not have a secret pre-shared key.Another problem is that such mutual challenge-response systemsoften work in the same system in the ``challenge mode'' butalso in the ``response mode''. For example if two servers wantto talk to each other---they would need the protocol inresponse mode, but also if they want to talk to other serversin challenge mode. Similarly if you in an military aircraftyou have to challenge everybody you see, in case there is afriend amongst the targets you like to shoot, but you alsohave to respond to any of your own anti-aircraft guns on theground lest they shoot you. In these situations you have to becareful to not decode, or answer, your own challenge. Recall the protocol is\begin{center}\begin{tabular}{l@{\hspace{2mm}}l}$A \rightarrow B$: & $N_A$\\ $B \rightarrow A$: & $\{N_A, N_B\}_{K_{AB}}$\\$A \rightarrow B$: & $N_B$\\\end{tabular}\end{center}\noindent but it does not specify who is $A$ and who is $B$.If, as supposed, the protocol works in response and in challenge mode, then $A$ will be $A$ in one instance, but $B$in the other. I hope this makes sense. Let us look at the details and lets assume our adversary is $E$ who just deflectsour messages back to us. \begin{center}\begin{tabular}{lllll}& \multicolumn{2}{l}{challenge mode:} & \multicolumn{2}{l}{response mode:}\smallskip\\1. & $A \rightarrow E$: & $N_A$\\ 2. & & & $E \rightarrow A$: & $N_A$\\ 3. & & & $A \rightarrow E$: & $\{N_A, N_A'\}_{K_{AB}}$\\4. & $E \rightarrow A$: & $\{N_A, N_A'\}_{K_{AB}}$\\5. & $A \rightarrow E$: & $N_A'$\\\end{tabular}\end{center}\noindent In the first step we challenge $E$ with a nonce wecreated. Since we also run the protocol in ``response mode'',$E$ can now feed us the same challenge in step 2. We do notknow where it came from (it's over the air), but if we are inan aircraft we should better quickly answer it, otherwise werisk to be shot. So we add our own challenge $N'_A$ andencrypt it under the secret key $K_{AB}$ (step 3). Now $E$does not need to know this key in order to form the correctanswer for the first protocol. It will just replays thismessage back to us in the challenge mode (step 4). I happilyaccept this message---after all it is encrypted under thesecret key $K_{AB}$ and it contains the correct challenge fromme, namely $N_A$. So I accept that $E$ is a friend and sendeven back the challenge $N'_A$. The problem is that $E$ nowstarts firing at me and I have no clue what is going on. Imight suspect, erroneously, that an idiot must have leaked thesecret key. Because I followed in both cases the protocol tothe letter, but somehow $E$, unknowingly to me with my help,managed to disguise as a friend. As a pilot, I would be a bitpeeved at that moment and would have preferred the designer ofthis challenge-response protocol had been a tad smarter. Forone thing they violated the best practice in protocol designof using the same key, $K_{AB}$, for two differentpurposes---challenging and responding. They better had usedtwo different keys. This would have averted this attack andwould have saved me a lot of trouble.\subsubsection*{Trusted Third Parties}One limitation the protocols we discussed so far isthat they pre-suppose a secret shared key. As already mentioned, this is a convenience we cannot always assume.How to establish a secret key then? Well, if both parties,say $A$ and $B$, mutually trust a third party, say $S$, then they can use the following protocol:\begin{center}\begin{tabular}{l@{\hspace{2mm}}l}$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}\noindent The assumption in this protocol is that $A$ and $S$share a secret key, and also $B$ and $S$ ($S$ being thetrusted third party). The goal is that $A$ can send $B$ amessage $m$ under a shared secret key $K_{AB}$, which at thebeginning of the protocol does not exist yet. How does thisprotocol work? In the first step $A$ contacts $S$ and saysthat it wants to talk to $B$. In turn $S$ invents a new key$K_{AB}$ and sends two messages back to $A$: one message is$\{K_{AB}\}_{K_{AS}}$ which is encrypted with the key $A$ and$S$ share, and also the message$\{\{K_{AB}\}_{K_{BS}}\}_{K_{AS}}$. which is encrypted with$K_{AB}$ but also a second time with $K_{BS}$. The point ofthe second message is that it is a message intended for $B$.So a receives both messages and can decrypt them---in thefirst case it obtains the key $K_{AB}$ which $S$ suggested touse. In the second case it obtains a message it can forward to$B$. $B$ receives this message and since it knows the key itshares with $S$ obtains the key $K_{AB}$. Now $A$ and $B$ canstart to exchange messages with the shared secret key$K_{AB}$. What is the advantage of $S$ sending $A$ two messages instead of contacting $B$ instead? Well, for onethere can now be a time-delay between the second andthird step in the protocol. At some point in the past$A$ and $S$ need to have come together to sharea key, similarly $B$ and $S$. After that $B$ does not need tobe ``online'' anymore until $A$ actually starts sending messagesto $B$. $A$ and $S$ can completely on their own negotiate anew key. The major limitation of this protocol however is that I needto trust a third party. And in this case completely, because$S$ can of course also read easily all messages $A$ sends to$B$. The problem is that I cannot really think of anyinstitution who could serve as such a trusted third party. Onewould hope the government would be such a trusted party, butin the Snowden-era we know that this is wishful thinking inthe West, and if I lived in Iran or North Korea, for example,I would not even start to hope for this.The cryptographic ``magic'' of public-private keys seems to offer an elegant solution for this, but as we shall see in the next section, this requires some very cleverprotocol design.\subsubsection*{Averting Person-in-the-Middle Attacks}The idea of public-private key encryption is that one can makepublic the key $K^{pub}$ which people can use to encryptmessages for me. and I can use my key $K^{priv}$ to be theonly one that can decrypt them. While this sounds all good, itrelies that people can associate me, for example, with mypublic key. That i snot so trivial as it sounds. For example,if I would be the government, say Cameron, and try to find outwho are the trouble makers in the country, I would publish aninnocent looking webpage and say I am The Guardian newspaper(or alternatively The Sun for all the juicy stories), publisha public key on it, and then just wait for incoming messages. This problem is supposed to be solved by using certificates.The purpose of certification organisations is that they verifythat a public key, say $K^{pub}_{Bob}$, really belongs to Bob.This is also the mechanism underlying the HTTPS protocol. Theproblem is that this system is essentially completelybroken\ldots{}but this is a story for another time. Sufficeto say for now that one of the main certificationorganisations, VeriSign, has limited its liability to \$100 incase it issues a false certificate. This is really a joke andreally the wrong incentive for the certification organisationsto clean up their mess.The problem we want to study closer here is that protocolsbased on public-private key encryption are susceptible toperson-in-the-middle attack. Consider the following protocolwhere $A$ and $B$ attempt to exchange secret messages usingpublic-private keys. \begin{itemize}\item $A$ sends public key to $B$\item $B$ sends public key to $A$\item $A$ sends a message encrypted with $B$'s public key,\\ $B$ decrypts it with its private key\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 wouldlook as follows:\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 completecontrol over the network, $E$ can intercept the first two messages and substitutes her own public key. The protocolrun 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 messagesby including the $E$ in the message. Both messages arereceived encrypted with $E$'s public key; therefore it candecrypt it and repackage it with new content. $A$ and $B$ haveno idea that they talking to an attacker. To them all messageslook legit. Because $E$ can modify messages, it seems verydifficult 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, 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, 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}\noindent The idea is that in step 3, $A$ encrypts themessage (with $B$'s public key) and then splits the encryptedmessage into two halves. Say the encrypted message is\begin{center}$\underbrace{\texttt{\Grid{0X1peUVTGJK0XI7G+H70mMjAM8piY0sI}}}_{\{A,m\}_{K^{pub}_B}}$\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 Similarly $B$ splits its message into two halves$M_1$ and $M_2$. However, $A$ initially only sends the firsthalf $H_1$ to $B$. Which $B$ answers with the messageconsisting 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$'spublic key. Finally $B$ checks whether the received $M_1$matches with its first half, and if yes sends $A$ itssecond half $M_2$. Now $A$ and $B$ are in the possession of $H_1$ and $H_2$, respectively $M_1$ and $M_2$ and candecrypt the corresponding messages.Now the big question is, why on earth does this splittingof messages in half and additional message exchange helpwith defending against person-in-the-middle attacks? Well,lets try to be such an attacker. As before we interceptthe messages where public keys are exchanged and injectour 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 cannotbe decrypted. $E$ could try to forward the message to $B$ andsee 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 itsprivate key, but it only gets the halves $H_1$ and $M_1$ whichare of no use yet. In order to get more information itcan 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 andfind out it matches with its expectation. It thereforesends 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 seemslike from now on all is lost, but lets see: in order tostay undetected it must send a message to $B$. It now has twooptions: one is to use the newly obtained knowledge andmodify $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 callthem $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$. Butafter joining both halves it will not be able to decrypt the resulting message---the two halves simplydo 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 andas 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 nowalso received $M_1$ and $M_2$ which it can join toget $\{B, m'\}_{K^{pub}_E}$. It can decrypt this messagebut 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 ableto 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 allmessages, but what messages did $A$ and $B$ receive and fromwhom? Do you notice that they will find out that somethingstrange has happened and probably not talk on this channelanymore? I leave you to think about it.Recall from the beginning that a person-in-the middleattack can easily be mounted at the key fob and carprotocol unless we are careful. If you look at actualkey fob protocols, they use a variant of the protocoldescribed above. Suppose $C$ is the car and $T$ is the key fob(transponder). The HiTag2 protocol used in cars ofVW \& friends is as follows: \begin{enumerate}\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$: $N, G'$\item $C$ checks that $G = G'$\end{enumerate}\noindent The assumption is that the key $K$ is only known tothe car and the transponder. The claim is that $C$ and $T$ canauthenticate to each other. Again, I leave it to you to findout the magic why this protocol is immune fromperson-in-the-middle attacks. \subsubsection*{Further Reading}If you want to know more about how cars can be hijacked,the paper \begin{center}\url{http://www.cs.ru.nl/~rverdult/Gone_in_360_Seconds_Hijacking_with_Hitag2-USENIX_2012.pdf}\end{center}\noindent is quite amusing to read. Obviously an even more amusingpaper would be ``Dismantling Megamos Crypto: Wirelessly Lockpicking aVehicle Immobilizer'' by the same authors, but because of the courtinjuction by VW in this case, we are denied this entertainment.Person-in-the-middle-attacks from the ``wild'' are described with real data in the blog post\begin{center}\url{http://www.renesys.com/2013/11/mitm-internet-hijacking}\end{center}\noindent The conclusion in this post is that person-in-the-middle-attackscan be launched from any place on Earth---it is not required that you sit in the ``middle'' of the communication of two people.You just have to route their traffic through a node you own.\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: