\documentclass{article}\usepackage{../style}\usepackage{../langs}\begin{document}\fnote{\copyright{} Christian Urban, 2014}%% the expectation is that anything encrypted today, will be%% decrypted in 20 years time\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. This can happen evenin face of strong adversaries who have complete control overthe network involved in the message exchange. The problem withmagic is of course it is poorly understood and even expertsoften got, and get, 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. That this is an attack one needs to reckon with isdemonstrated by the fact that dodgywebsites\footnote{\url{http://autokeydevices.com/product/wave/}\ldots{} funnily this webpage says ``not intended for illegaluse'', but I have a hard time finding any legal purpose forsuch a device.} sell the necessary equipment for top Ruble.This webpage is notable for the very helpful pictureof a person-in-the-middle attack (see Figure~\ref{rsa}).\begin{figure}[t]\begin{center}\includegraphics[scale=0.15]{../pics/rsa_attack_eng.jpg}\end{center}\caption{From a dodgy webpage about modern car theft. Note thestylish attackers.\label{rsa}}\end{figure}But there are many more such protocols we like to study.Another example is Wifi---you might sit at a Starbucks andtalk wirelessly to the free access point there and from theretalk to your bank (see The Guardian article cited at the veryend of this handout). Moreover, even if you have to touch inand out your Oyster card at the reader each time you enter orexit the Tube, it actually operates wirelessly and withappropriate equipment over some quite large distance (severalmeters). But there are many, many more examples for protocols(Bitcoins, Tor, mobile phones,\ldots). The common characteristics of the protocols we are interestedin is that an adversary or attacker is assumed to be incomplete control over the network or channel over which weexchanging messages. An attacker can install a packet snifferon a network, inject packets, intercept packets, modifypackets, replay old messages, or fake pretty much everythingelse. In this hostile environment, the purpose of a protocol(that is exchange of messages) is to achieve some securitygoal. For example only allow the owner of the car in, buteverybody else should be kept 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.45]{../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 themessages are exchanged, Alice and the server simply haveestablished a channel to communicate over. Alice does not knowwhether she is really talking to the server (somebody else onthe network might have intercepted her message and replied inplace of the server). Similarly, the server has no idea who itis talking to. Whether they can authenticate themselvesdepends on what is exchanged next and is the point of theprotocols we want to study in more detail.Before we start in earnest, we need to fix a more convenientnotation for protocols. Drawing pictures like the one abovewould be awkward in the long-run. The notation we will adoptabstracts away from a few details we are not interested in:for example the time the messages need to travel betweenendpoints. What we are interested in is in which order themessages are sent. For the SYN-ACK protocol we will thereforeuse 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 of each clause specifies who isthe sender and who is the receiver of the message. On theright of the colon is the message that is send. The order fromtop to down specifies in which order the messages are sent. Wealso have the convention that messages, like $SYN$ above, aresend in clear-text over the network. If we want that a messageis encrypted, then we use the notation\[\{msg\}_{K}\] \noindent for messages. The curly braces indicate a kind ofenvelope which can only be opened if you know the key $K$with which the message has been encrypted. We always assumethat an attacker, say Eve, cannot get to 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 because of a weak encryption method. Forexample Oyster cards contain a very weak encryption mechanismwhich has been attacked and broken.} It is alsopossible that an encrypted message contains several parts. Inthis case we would write something like\[\{msg_1, msg_2\}_{K}\] \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_1}\}_{K_2}\] \noindent The idea is that even if attacker Eve has thekey $K_2$ she could decrypt the outer envelop, butstill does not get to the message, because it is stillencrypted with the key $K_1$. 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 our 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 blueprint for 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 causeheadaches for system administrators where an attacker startsthe protocol, but then does not complete it. This looksgraphically 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 in doing so the server needs tokeep track of such protocol exchanges. As a result every timethe protocol is initiated a little bit of memory will be eatenaway on the server side until all memory is exhausted. Whenpoor Alice then tries to contact the server, it is overwhelmedand does not respond anymore. This kind of attack is called\emph{SYNfloods}.\footnote{\url{http://en.wikipedia.org/wiki/SYN_flood}}After reading four pages, you might be wondering where themagic is with protocols. For this let us take a closer look atauthentication 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 thought of as $A$ sends a common secret to$B$, for example a password. The idea is that if only $A$ and$B$ know the key $K_{AB}$ then this should be sufficient for$B$ to infer it is talking to $A$. But this is of course toonaive in the context where the message can be observed byeverybody else on the network. Eve, for example, could justrecord this message $A$ just sent, and next time sends the samemessage to $B$. $B$ has no other choice than believing ittalks to $A$. But actually it talks to Eve, who now clearsout $A$'s bank account assuming $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 sendsa message to $B$ saying ``I want to talk to you''. $B$ sendsthen a challenge in form of a random number $N$. In protocolssuch random numbers are often called \emph{nonce}. What is thepurpose of this nonce? Well, if an attacker records $A$'sanswer, it will not make sense to replay this message, becausenext time this protocol is run, the nonce $B$ sends out willbe different. So if we run this protocol, what can $B$ infer?It has send out an (unpredictable) nonce to $A$ and receivedthis challenge back, but encoded under the key $K_{AB}$. If$B$ assumes only $A$ and $B$ know the key $K_{AB}$ and thenonce is unpredictable, then $B$ is able to infer it must betalking to $A$. Of course the implicit assumption on thisinference is that nobody else knows about the key $K_{AB}$and nobody else can decrypt the message. $B$ of course candecrypt the answer from $A$ and check whether the answercorresponds to the challenge (nonce) $B$ has sent earlier.But what about $A$? Can $A$ make any inferences about whom ittalks to? It dutifully answered the challenge and hopes his orher bank, say, will be the only one to understand her answer.But is this the case? No! Let us consider again an attackerEve who has control over the network. She could haveintercepted the message $HELLO$ and just replied herself to$A$ using a random number\ldots{}for example one which sheobserved in a previous run of this protocol. Remember that ifa message is sent without curly braces it is sent in cleartext. $A$ would encrypt the nonce with the key $K_{AB}$ andsend it back to Eve. She just throws away the answer. $A$would hope that she talked to $B$ because she followed theprotocol, but unfortunately she cannot be sure who she istalking to---it might be Eve. 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}$ too, and sends back the nonce of $B$.Let us analyse which inferences $A$ and $B$ can make after theprotocol has run. $B$ received a challenge and answeredcorrectly to $A$ (inside the encrypted message). An attackerwould not be able to answer this challenge correctly becausethe attacker is assumed to not be in the possession of the key$K_{AB}$; so is not able to generate this message. It couldalso not have been the case that it is an old messagereplayed, because $A$ would send out each time a fresh nonce.So with this protocol you can ensure also for $A$ that ittalks to $B$. I leave you to argue that $B$ can be sure totalk to $A$. Of course these arguments will depend on theassumptions that only $A$ and $B$ know the key $K_{AB}$ andthat nobody can break the encryption unless they have this keyand that the nonces are fresh each time the protocol is run.The purpose of the nonces, the random numbers that are sentaround, might be a bit opaque. Because they are unpredictablethey fulfil an important role in protocols. 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 have sent 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 we canglean from such an exchange, it is in fact the basic buildingblock in protocols for establishing some secret or forachieving some security goal (like authentication). This iswhat I meant by magic: we send around ``just'' some randomnumbers, but actually can use them to make some meaningfulinferences.While the mutual challenge-response protocol solves theauthentication problem, there are some limitations. 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 awhistleblower (say Snowden) and want to talk to a journalist(say Greenwald) then I might not have a secret pre-shared key.Another limitation is that such mutual challenge-responsesystems often work in the same system in the ``challengemode'' but also in the ``response mode''. For example if twoservers want to talk to each other---they would need theprotocol in response mode, but also if they want to talk toother servers in challenge mode. Similarly if you are in anmilitary aircraft you have to challenge everybody you see, incase there is a friend amongst the targets you like to shoot,but you also have to respond to any of your own anti-aircraftguns on the ground, lest they shoot you. In these situationsyou have to be careful to not decode, or answer, your ownchallenge. 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 the protocol works in response and in challenge mode, then$A$ will be $A$ in one instance, but $B$ in the other. I hopethis makes sense. Let us look at the details and let us assumeour adversary is $E$ who just deflects our messages back tous. \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 ina fighter aircraft we 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---namely challenging and responding. They better hadused two different keys. This would have averted this attackand would have saved me a lot of inconvenience.\subsubsection*{Trusted Third Parties}One limitation the protocols we discussed so far have is thatthey pre-suppose a secret shared key. As already mentioned,this is a convenience we cannot always assume. How toestablish a secret key then? Well, if both parties, say $A$and $B$, mutually trust a third party, say $S$, then they canuse 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_{AS}$ 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$ twomessages instead of contacting $B$ instead? Well, there can bea time-delay between the second and third step in theprotocol. At some point in the past $A$ and $S$ need to havecome together to share a key, similarly $B$ and $S$. Afterthat $B$ does not need to be ``online'' anymore until $A$actually starts sending messages to $B$. $A$ and $S$ cancompletely on their own negotiate a new 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 and does not solve the authenticationproblem completely.\subsubsection*{Averting Person-in-the-Middle Attacks}The idea of public-private key encryption is that one canpublish the key $K^{pub}$ which people can use to encryptmessages for me and I can use my private key $K^{priv}$ to bethe only one that can decrypt them. While this sounds allgood, it relies on the ability that people can associate mewith my public key. That is not as trivial as it sounds. Forexample, if I would be the government, say Cameron, and try tofind out who are the trouble makers in the country, I wouldpublish an innocent looking webpage and say I am The Guardiannewspaper (or alternatively The Sun for all the juicystories), publish a public key on it, and then just wait forincoming 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 tosimple person-in-the-middle attacks. Consider the followingprotocol where $A$ and $B$ attempt to exchange secret messagesusing public-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 them and repackage them with new content. $A$ and $B$have no idea that they talking to an attacker. To them allmessages look legit. Because $E$ can modify messages, it seemsvery difficult to defend against this attack. But there is a clever trick\ldots{}dare I say some magic whichmakes this attack very difficult to perform on people who knoweach other---but not necessarily have a shared key. Modify theprotocol above so that $A$ and $B$ send their messages in twohalves, 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,let's try to be 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 let's 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. It can 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 one 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 $A$ and $B$ will find out thatsomething strange is going on and probably not talk on thischannel anymore? I leave you to think about it.\footnote{\rotatebox{180}{\begin{minipage}{10cm}Consider the case where $A$ sends the message ``How is your grandmother?'' to $B$, and $B$send the message ``How is the weather in London today'' to $A$.\end{minipage}}}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 if this protocol is immune fromperson-in-the-middle attacks. \subsubsection*{Further Reading}\begin{itemize}\item A blogpost that describes the first few milliseconds of an HTTPS connection is at\begin{center}\url{http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html}\end{center}It disentangles every message sent between a client and aserver.\item 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}is quite amusing to read. Obviously an even more amusing paperwould ``Dismantling Megamos Crypto: Wirelessly Lockpicking aVehicle Immobilizer'' by the same authors, but because of thecourt injunction by VW, we are denied this entertainment.UPDATE: This paper is now in the public domain.\item Man-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}The conclusion in this post is that man-in-the-middle-attackscan be launched from any place on Earth---it is not requiredthat you sit in the ``middle'' of the communication of twopeople. You just have to route their traffic through a nodeyou own.\item An article in The Guardian from 2013 reveals how GCHQ and the NSA at a G20 Summit in 2009 sniffed emails from Internet cafes, monitored phone calls from delegates and attempted to listen on phone calls which were made by Russians and which were transmitted via satellite links:\begin{center}\url{http://www.theguardian.com/uk/2013/jun/16/gchq-intercepted-communications-g20-summits}\end{center}\ldots all in the name of having a better position fornegotiations. Hmmm\ldots\item A paper guessing how the NSA can decrypt so much of theencrypted Internet traffic:\begin{center}\url{https://weakdh.org/imperfect-forward-secrecy.pdf}\end{center}\end{itemize}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: