\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usetikzlibrary{patterns,decorations.pathreplacing}

\begin{document}

\section*{Handout 5 (Protocols)}

Protocols are the computer science equivalent to fractals and

happened.\footnote{\url{http://en.wikipedia.org/wiki/Fractal},

\url{http://en.wikipedia.org/wiki/Mandelbrot_set}} Protocols

are similar: they are simple exchanges of messages, but in the

end something ``magical'' can happen---for example a secret

channel has been established or two entities have

us look at a few examples. One example are (wireless) key 

ignition 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 is

done over the ``air''---there is no physical connection

talk wirelessly to the free access point there and from there

phones,\ldots). The common characteristics of the protocols we

The protocols we are interested here are generic descriptions

To start, let us look at one of the simplest protocols that

are part of the TCP protocol (which underlies the Internet).

This protocol does not do anything security relevant, it just

establishes a ``hello'' from a client to a server which the

server answers with ``I heard you'' and the client answers 

in turn with something like ``thanks''. This protocol

is often called a \emph{three-way handshake}. Graphically it

can 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 the

right-hand side is a server, say. Time is running from top to

bottom. Alice initial SYN message needs some time to travel to

the server. The server answers with SYN-ACK, which will

require some time to arrive at Alice. Her answer ACK will

again 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 does

not know whether she is really talking to the server (somebody 

else on the network might have intercepted her message

and replied in place of the server). Similarly, the

server has no idea who it is talking to. That this can be 

established depends on what is exchanged next and is the

point of the protocols we want to study in more detail.

Before we start in earnest, we need to fix a more

convenient notation for protocols. Drawing pictures like

the one above would be awkward in the long-run. The

notation already abstracts away from a few details we are

not interested in: for example the time the messages

need to travel between endpoints. What we are interested

in is in which order the messages are sent. For the SYN-ACK

protocol 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 and

who is the receiver of the message. On the right of the colon

is the message that is send. The order from top to down

specifies in which order the messages are sent. We also

have the convention that messages like above $SYN$ are send

in 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 of

envelope which can only be opened if you know the key $K_{AB}$

with which the message has been encrypted. We always assume

that an attacker, say Eve, cannot get the content of the

message, unless she is also in the possession of the key. We

explicitly exclude in our study that the encryption can be

broken.\footnote{\ldots{}which of course is what a good

protocol designer needs to ensure and more often than not

protocols are broken. For example Oyster cards contain a very

weak encryption mechanism which has been attacked.} It is also

possible that an encrypted message contains several parts. In

this 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 the

key $K_{BC}$ she could decrypt the outer envelop, but

still do not get to the message, because it is still

encrypted with the key $K_{AB}$. Note, however,

while an attacker cannot obtain the content of the message

without the key, encrypted messages can be observed

and be recorded and then replayed at another time, or

send to another person!

Another very important point is that the notation for

protocols such as shown in \eqref{SYNACK} is a

\underline{schema} how the protocol should proceed.

It could be instantiated by an actual protocol run

between 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 to

serve many clients. So there could be the same protocol

also 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 be

running in parallel or be at different stages. So the protocol

schema 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 attacker

starts 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 the

server dutifully answers, but needs to keep track of such

protocol exchanges. So every time a little bit of memory

resource will be eaten away on the server side until all

resources are exhausted and when Alice tries to contact the

server then the server is overwhelmed and does not respond

anymore. This kind of attack are called \emph{SYN

floods}.\footnote{\url{http://en.wikipedia.org/wiki/SYN_flood}}

After reading four pages, you might be wondering where the

magic 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$ know

the key $K_{AB}$ then this should be sufficient for $B$ to

infer it is talking to $A$. But this is of course too naive,

if the message can be observed by everybody else on the

network. Eve could just record this message $A$ just send, and

next time send the same message to $B$ and $B$ would believe

it talked to $A$. But actually it talked to Eve which now

clears out $A$s back account if $B$ had been a bank.

A more sophisticated protocol which tries to avoid the

replay 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 the

purpose of this nonce? Well, if an attacker records $A$ 

answer, it will not make sense to replay this message, because

next time this protocol is run the nonce $B$ sends will be

different. So if we run this protocol, what can $B$ infer:

it has send out an (unpredictable) nonce to $A$ and

received 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 to

infer it must be talking to $A$. Of course the implicit 

assumption on this inference are that nobody else knows

about the key $K_{AB}$ and nobody else can decrypt the

message. $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 it

talks to? It dutifully answered the challenge and hopes its

bank, say, will be the only one to understand her answer. But

is this the case? No! Lets consider an attacker Eve who has

control over the network. She could have intercepted the

message $HELLO$ and just replied herself to $A$ using a random

number\ldots{} for example one which she observed in a

previous run of this protocol. Remember that if a message is

send without curly braces it is sent in clear text. Then

$A$ would encrypt the nonce with the key $K_{AB}$ and send

it back to Eve. She just throws the answer away. $A$ would

hope 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 his

own nonce, $N_B$ and encrypts it with the key $K_{AB}$. $A$

receives this message, is able to decrypt it since we assume

she 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 attacker

would just not be able to answer this challenge correctly 

because the attacker is assumed to not be in the possession of

the 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 this

protocol 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 that

only $A$ and $B$ know the key $K_{AB}$ and that nobody can

break the encryption unless they have this key and that the

nonces are fresh each time the protocol is run.

There might be something mysterious about the nonces, the

random numbers, that are sent around. They need to be

unpredictable and in this way 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 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 can

glean 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 already

the authentication problem, there are some problems. One is of

course that it requires a pre-shared secret key. That is

something that needs to be established beforehand. Not all

situations allow such an assumption. For example if I am a

whistle 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 systems

often work in the same system in the ``challenge mode'' but

also in the ``response mode''. For example if two servers want

to talk to each other---they would need the protocol in

response mode, but also if they want to talk to other servers

in challenge mode. Similarly if you in an military aircraft

you have to challenge everybody you see, in case there is a

friend amongst the targets you like to shoot, but you also

have to respond to any of your own anti-aircraft guns on the

ground lest they shoot you. In these situations you have to be

careful 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 deflects

our messages back to us. 

\begin{center}

\begin{tabular}{lllll}

& \multicolumn{2}{l}{challenge mode:} & 

\multicolumn{2}{l}{response mode:}\smallskip\\

\end{tabular}

\end{center}

\noindent In the first step we challenge $E$ with a nonce we

created. Since we also run the protocol in ``response mode'',

$E$ can now feed us the same challenge in step 2. We do not

know where it came from (it's over the air), but if we are in

an aircraft we should better quickly answer it, otherwise we

risk to be shot. So we add our own challenge $N'_A$ and

encrypt it under the secret key $K_{AB}$ (step 3). Now $E$

does not need to know this key in order to form the correct

answer for the first protocol. It will just replays this

message back to us in the challenge mode (step 4). I happily

accept this message---after all it is encrypted under the

secret key $K_{AB}$ and it contains the correct challenge from

me, namely $N_A$. So I accept that $E$ is a friend and send

even back the challenge $N'_A$. The problem is that $E$ now

starts firing at me and I have no clue what is going on. I

might suspect, erroneously, that an idiot must have leaked the

secret key. Because I followed in both cases the protocol to

the letter, but somehow $E$, unknowingly to me with my help,

managed to disguise as a friend. As a pilot, I would be a bit

peeved at that moment and would have preferred the designer of

this challenge-response protocol had been a tad smarter. For

one thing they violated the best practice in protocol design

of using the same key, $K_{AB}$, for two different

purposes---challenging and responding. They better had used

two different keys. This would have averted this attack and

would have saved me a lot of trouble.

\subsubsection*{Trusted Third Parties}

One limitation the protocols we discussed so far is

that 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 the

trusted third party). The goal is that $A$ can send $B$ a

message $m$ under a shared secret key $K_{AB}$, which at the

beginning of the protocol does not exist yet. How does this

protocol work? In the first step $A$ contacts $S$ and says

that 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 of

the second message is that it is a message intended for $B$.

So a receives both messages and can decrypt them---in the

first case it obtains the key $K_{AB}$ which $S$ suggested to

use. In the second case it obtains a message it can forward to

$B$. $B$ receives this message and since it knows the key it

shares with $S$ obtains the key $K_{AB}$. Now $A$ and $B$ can

start 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 one

there can now be a time-delay between the second and

third step in the protocol. At some point in the past

$A$ and $S$ need to have come together to share