\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 you have asimple formula which you just iterate and then you testwhether a point is inside or outside a region, and voilasomething 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. The problem with magicis of course it is poorly understood and even experts oftengot, and get, it wrong with protocols. To have an idea what kind of protocols we are interested, 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. So we must achieve securityby exchanging certain messages between the key fob on one sideand doors and engine on the other. Clearly what we like toachieve is that I can get into my car and start it, but thatthieves are kept out. The problem is that everybody can``overhear'' or skim the exchange of messages between the keyfob and car. In this scenario the simplest attack you need todefend against is a person-in-the-middle attack. Imagine youpark your car in front of a supermarket. One thief follows youwith a strong transmitter. A second thief ``listens'' to thesignal from the car and wirelessly transmits it to the``colleague'' who followed you and who silently enquires aboutthe answer from the key fob. The answer is then send back tothe thief at the car, which then dutifully opens and possiblystarts. No need to steal your key anymore.But there are many more such protocols we like to consider.Other examples are wifi---you might sit at a Starbucks andtalk wirelessly to the free access point there and from theretalk with your bank, for example. Also even if your have totouch your Oyster card at the reader each time you enter andexit the Tube, it actually operates wirelessly and withappropriate equipment over some quite large distance. Butthere are many many more examples (Bitcoins, mobilephones,\ldots). The common characteristics of the protocols weare interested in here is that an adversary or attacker isassumed to be in complete control over the network or channelover which you exchanging messages. An attacker can install apacket sniffer on a network, inject packets, modify packets,replay old messages, or fake pretty much everything. In thishostile environment, the purpose of protocols (that isexchange of messages) is to achieve some security goal, forexample only allow the owner of the car in but everybody elseshould be kept out.The protocols we are interested here are generic descriptionsof how to exchange messages in order to achieve a goal, be itestablishing a mutual secure connection or being able toauthenticate to a system. Unlike the distant past where forexample we had to meet a person in order to authenticate himor her (via a passport for example), the problem we are facingon the Internet is that we cannot easily be sure who we are``talking'' to. The obvious reason is that only some electronsarrive at our computer; we do not see 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 andsuspect, erroneously, that an idiot must have leaked thesecret key. I followed in both cases the protocol to theletter, but somehow $E$, with my help, managed to disguise asa friend. As a pilot, I would rather prefer the designer ofthis challenge-response protocol were a tad smarter. For onething they violated the best practice in protocol design ofusing 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 \rightarrow S :$ & $A, B$\\$S \rightarrow A :$ & $\{K_{AB}\}_{K_{AS}}$ and $\{\{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$\\$A \rightarrow B :$ & $\{K_{AB}\}_{K_{BS}}$\\$A \rightarrow 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. \subsubsection*{Averting Person-in-the-Middle Attacks}\bigskip\bigskipKeyfobs - protocol\subsubsection*{Further Reading}{\small\url{http://www.cs.ru.nl/~rverdult/Gone_in_360_Seconds_Hijacking_with_Hitag2-USENIX_2012.pdf}}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: