sen-material: comparison handouts/ho05.tex

equal deleted inserted replaced

-:71136e7964cc
+:2492b771122e
 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
-authenticated themselves to each other. Even in face of strong
+authenticated themselves to each other. This can happen even
-adversaries where we have no control over the network over
+in face of strong adversaries who have complete control over
-which our messages are exchanged. The problem with magic is of
+the network involved in the message exchange. The problem with
-course it is poorly understood and even experts often got, and
+magic is of course it is poorly understood and even experts
-get, it wrong with protocols.
+often got, and get, it wrong with protocols.
 To have an idea what kind of protocols we are interested in, let
 us look at a few examples. One example are (wireless) key
 fobs, which operate the central locking system and the
 ignition in a car.
 A second thief ``listens'' to the signals from the car and
 wirelessly transmits them to the ``colleague'' who followed
 you. This thief silently enquires what the key fob answers.
 This answer is then send back to the thief at the car. If done
 properly the car will dutifully open and possibly start. No
 need to steal your keys anymore.
+That this is an attack one needs to reckon with is
+demonstrated by the fact that certain dodgy
+websites\footnote{\url{http://autokeydevices.com/product/wave/}
+\ldots{} funnily this webpage says ``not intended for illegal
+use'', but I have a hard time finding any legal purpose for
+such a device.} sell the necessary equipment for top Ruble.
+This webpage is notable for the very helpful picture
+of 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 the
+stylish attackers Malice and Mallet.\label{rsa}}
+\end{figure}
 But there are many more such protocols we like to treat.
 Another example is Wifi---you might sit at a Starbucks and
 talk wirelessly to the free access point there and from there
-talk to your bank. Moreover, even if your have to touch your
+talk to your bank (see The Guardian article cited at the very
-Oyster card at the reader each time you enter or exit the
+end of this handout). Moreover, even if your have to touch
+your Oyster card at the reader each time you enter or exit the
 Tube, it actually operates wirelessly and with appropriate
 equipment over some quite large distance (several meters). But
 there are many, many more examples (Bitcoins, mobile
-phones,\ldots). The common characteristics of the protocols we
+phones,\ldots).
-are interested in is that an adversary or attacker is assumed
-to be in complete control over the network or channel over
+The common characteristics of the protocols we are interested
-which we exchanging messages. An attacker can install a packet
+in is that an adversary or attacker is assumed to be in
-sniffer on a network, inject packets, modify packets, replay
+complete control over the network or channel over which we
-old messages, or fake pretty much everything else. In this
+exchanging messages. An attacker can install a packet sniffer
-hostile environment, the purpose of a protocol (that is
+on a network, inject packets, intercept packets modify
-exchange of messages) is to achieve some security goal. For
+packets, replay old messages, or fake pretty much everything
-example only allow the owner of the car in, but everybody else
+else. In this hostile environment, the purpose of a protocol
-should stay out.
+(that is exchange of messages) is to achieve some security
+goal. For example only allow the owner of the car in, but
+everybody else should be kept out.
 The protocols we are interested here are generic descriptions
 of how to exchange messages in order to achieve a goal. Unlike
 the distant past where, for example, we had to meet a person in
 order to authenticate him or her (via a passport for example),
 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}
+\includegraphics[scale=0.45]{../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
+messages are exchanged, Alice and the server simply have
-established a channel to communicate over. Alice does
+established a channel to communicate over. Alice does not know
-not know whether she is really talking to the server (somebody
+whether she is really talking to the server (somebody else on
-else on the network might have intercepted her message
+the network might have intercepted her message and replied in
-and replied in place of the server). Similarly, the
+place of the server). Similarly, the server has no idea who it
-server has no idea who it is talking to. That this can be
+is talking to. Whether they can authenticate themselves
-established depends on what is exchanged next and is the
+depends on what is exchanged next and is the point of the
-point of the protocols we want to study in more detail.
+protocols we want to study in more detail.
-Before we start in earnest, we need to fix a more
+Before we start in earnest, we need to fix a more convenient
-convenient notation for protocols. Drawing pictures like
+notation for protocols. Drawing pictures like the one above
-the one above would be awkward in the long-run. The
+would be awkward in the long-run. The notation we will adopt
-notation already abstracts away from a few details we are
+abstracts away from a few details we are not interested in:
-not interested in: for example the time the messages
+for example the time the messages need to travel between
-need to travel between endpoints. What we are interested
+endpoints. What we are interested in is in which order the
-in is in which order the messages are sent. For the SYN-ACK
+messages are sent. For the SYN-ACK protocol we will therefore
-protocol we will therefore use the notation
+use the notation
 \begin{equation}
 \begin{array}{l@{\hspace{2mm}}l}
 A \to S: & SYN\\
 \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
+have the convention that messages, like $SYN$ above, 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
+that an attacker, say Eve, cannot get to 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
+protocols are broken because of a weak encryption method. For
-weak encryption mechanism which has been attacked.} It is also
+example Oyster cards contain a very weak encryption mechanism
+which has been attacked and broken.} 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}}
 \{\{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
+still does 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
+Another very important point is that our 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
 \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.
+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 cause
+Although very simple, the $SYN\_ACK$ protocol can cause
-headaches for system administrators where an attacker
+headaches for system administrators where an attacker starts
-starts the protocol, but does not complete it. This looks
+the protocol, but then 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
+server dutifully answers. But in doing so the server needs to
-protocol exchanges. So every time a little bit of memory
+keep track of such protocol exchanges. As a result every time
-resource will be eaten away on the server side until all
+the protocol is initiated a little bit of memory will be eaten
-resources are exhausted and when Alice tries to contact the
+away on the server side until all memory is exhausted. When
-server then the server is overwhelmed and does not respond
+poor Alice then tries to contact the server, it is overwhelmed
-anymore. This kind of attack are called \emph{SYN
+and does not respond anymore. This kind of attack is 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
+magic is with protocols. For this let us take a closer look at
-protocols.
+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
+\noindent It can be thought of as $A$ sends a common secret to
-$B$ like a password. The idea is that if only $A$ and $B$ know
+$B$, for example a password. The idea is that if only $A$ and
-the key $K_{AB}$ then this should be sufficient for $B$ to
+$B$ know the key $K_{AB}$ then this should be sufficient for
-infer it is talking to $A$. But this is of course too naive,
+$B$ to infer it is talking to $A$. But this is of course too
-if the message can be observed by everybody else on the
+naive in the context where the message can be observed by
-network. Eve could just record this message $A$ just send, and
+everybody else on the network. Eve, for example, could just
-next time send the same message to $B$ and $B$ would believe
+record this message $A$ just sent, and next time send the same
-it talked to $A$. But actually it talked to Eve which now
+message to $B$. $B$ has no other choice than believing it
-clears out $A$s back account if $B$ had been a bank.
+talks to $A$. But actually it talks to Eve, who now clears
+out $A$'s back account assuming $B$ had been a bank.
 A more sophisticated protocol which tries to avoid the
 replay attack is as follows
 \begin{center}
 $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$
+purpose of this nonce? Well, if an attacker records $A$'s
 answer, it will not make sense to replay this message, because
-next time this protocol is run the nonce $B$ sends will be
+next time this protocol is run, the nonce $B$ sends out will
-different. So if we run this protocol, what can $B$ infer:
+be different. So if we run this protocol, what can $B$ infer?
-it has send out an (unpredictable) nonce to $A$ and
+It has send out an (unpredictable) nonce to $A$ and received
-received this challenge back, but encoded under the key
+this challenge back, but encoded under the key $K_{AB}$. If
-$K_{AB}$. If $B$ assumes only $A$ and $B$ know the key $K_{AB}$
+$B$ assumes only $A$ and $B$ know the key $K_{AB}$ and the
-and the nonce is unpredictable, then $B$ is able to
+nonce is unpredictable, then $B$ is able to infer it must be
-infer it must be talking to $A$. Of course the implicit
+talking to $A$. Of course the implicit assumption on this
-assumption on this inference are that nobody else knows
+inference is that nobody else knows about the key $K_{AB}$
-about the key $K_{AB}$ and nobody else can decrypt the
+and nobody else can decrypt the message. $B$ of course can
-message. $B$ of course can decrypt the answer from $A$
+decrypt the answer from $A$ and check whether the answer
-and check whether the answer corresponds to the challenge
+corresponds to the challenge (nonce) $B$ has sent earlier.
-(nonce) $B$ has send earlier.
+But what about $A$? Can $A$ make any inferences about whom it
-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
+is this the case? No! Let us consider again an attacker Eve
-control over the network. She could have intercepted the
+who has control over the network. She could have intercepted
-message $HELLO$ and just replied herself to $A$ using a random
+the message $HELLO$ and just replied herself to $A$ using a
-number\ldots{} for example one which she observed in 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
+sent without curly braces it is sent in clear text. $A$ would
-$A$ would encrypt the nonce with the key $K_{AB}$ and send
+encrypt the nonce with the key $K_{AB}$ and send it back to
-it back to Eve. She just throws the answer away. $A$ would
+Eve. She just throws away the answer. $A$ would hope that she
-hope that she talked to $B$ because she followed the protocol,
+talked to $B$ because she followed the protocol, but
-but unfortunately she cannot be sure who she is talking to.
+unfortunately she cannot be sure who she is talking 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.
 \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$.
+she has the key $K_{AB}$ too, and sends back the nonce of $B$.
-Let us analyse which assumptions $A$ and $B$ can make after
+Let us analyse which inferences $A$ and $B$ can make after the
-the protocol has run. $B$ received a challenge and answered
+protocol has run. $B$ received a challenge and answered
-correctly to $A$ (in the encrypted message). An attacker
+correctly to $A$ (inside the encrypted message). An attacker
-would just not be able to answer this challenge correctly
+would not be able to answer this challenge correctly because
-because the attacker is assumed to not be in the possession of
+the attacker is assumed to not be in the possession of the key
-the key $K_{AB}$; so could not have formed this message.
+$K_{AB}$; so is not able to generate this message. It could
-It could also not have just replayed an old message, because
+also not have been that it is an old message replayed, 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$.
+protocol you can ensure also for $A$ that it talks to $B$. I
-I leave you to argue that $B$ can be sure to talk to $A$.
+leave you to argue that $B$ can be sure to talk to $A$. Of
-Of course these arguments will depend on the assumptions that
+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
+The purpose of the nonces, the random numbers that are sent
-random numbers, that are sent around. They need to be
+around, might be a bit opaque. Because they are unpredictable
-unpredictable and in this way fulfil an important role in
+they fulfil an important role in protocols. Suppose
-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
 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
+\item you could only have generated your answer after I have
-you my initial message (since my $N$ is always new, it
+sent you my initial message (since my $N$ is always new,
-could not have been a message that was generated before
+it could not have been a message that was generated
-I myself knew what $N$ is)
+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
+block in protocols for establishing some secret or for
-security goal (like authentication).
+achieving some security goal (like authentication).
-While the mutual challenge-response protocol solves already
+While the mutual challenge-response protocol solves the
-the authentication problem, there are some problems. One is of
+authentication problem, there are some limitations. 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
+whistleblower (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-response
-Another problem is that such mutual challenge-response systems
+systems often work in the same system in the ``challenge
-often work in the same system in the ``challenge mode'' but
+mode'' but also in the ``response mode''. For example if two
-also in the ``response mode''. For example if two servers want
+servers want to talk to each other---they would need the
-to talk to each other---they would need the protocol in
+protocol in response mode, but also if they want to talk to
-response mode, but also if they want to talk to other servers
+other servers in challenge mode. Similarly if you are in an
-in challenge mode. Similarly if you in an military aircraft
+military aircraft you have to challenge everybody you see, in
-you have to challenge everybody you see, in case there is a
+case there is a friend amongst the targets you like to shoot,
-friend amongst the targets you like to shoot, but you also
+but you also have to respond to any of your own anti-aircraft
-have to respond to any of your own anti-aircraft guns on the
+guns on the ground, lest they shoot you. In these situations
-ground lest they shoot you. In these situations you have to be
+you have to be careful to not decode, or answer, your own
-careful to not decode, or answer, your own challenge. Recall
+challenge. Recall the protocol is
-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
+If the protocol works in response and in challenge mode, then
-challenge mode, then $A$ will be $A$ in one instance, but $B$
+$A$ will be $A$ in one instance, but $B$ in the other. I hope
-in the other. I hope this makes sense. Let us look at the
+this makes sense. Let us look at the details and let us assume
-details and lets assume our adversary is $E$ who just deflects
+our adversary is $E$ who just deflects our messages back to
-our messages back to us.
+us.
 \begin{center}
 \begin{tabular}{lllll}
 & \multicolumn{2}{l}{challenge mode:} &
 \multicolumn{2}{l}{response mode:}\smallskip\\
 \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
+a fighter aircraft we 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
 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
+purposes---namely challenging and responding. They better had
-two different keys. This would have averted this attack and
+used two different keys. This would have averted this attack
-would have saved me a lot of trouble.
+and would have saved me a lot of inconvenience.
 \subsubsection*{Trusted Third Parties}
-One limitation the protocols we discussed so far is
+One limitation the protocols we discussed so far have is that
-that they pre-suppose a secret shared key. As already
+they pre-suppose a secret shared key. As already mentioned,
-mentioned, this is a convenience we cannot always assume.
+this is a convenience we cannot always assume. How to
-How to establish a secret key then? Well, if both parties,
+establish a secret key then? Well, if both parties, say $A$
-say $A$ and $B$, mutually trust a third party, say $S$,
+and $B$, mutually trust a third party, say $S$, then they can
-then they can use the following protocol:
+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}}$\\
 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}\}_{K_{BS}}\}_{K_{AS}}$ which is encrypted with
-$K_{AB}$ but also a second time with $K_{BS}$. The point of
+$K_{AS}$ 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
+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
+messages instead of contacting $B$ instead? Well, there can be
-there can now be a time-delay between the second and
+a time-delay between the second and third step in the
-third step in the protocol. At some point in the past
+protocol. At some point in the past $A$ and $S$ need to have
-$A$ and $S$ need to have come together to share
+come together to share a key, similarly $B$ and $S$. After
-a key, similarly $B$ and $S$. After that $B$ does not need to
+that $B$ does not need to be ``online'' anymore until $A$
-be ``online'' anymore until $A$ actually starts sending messages
+actually starts sending messages to $B$. $A$ and $S$ can
-to $B$. $A$ and $S$ can completely on their own negotiate a
+completely on their own negotiate a new key.
-new key.
 The major limitation of this protocol however is that I need
 to 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 any

changeset 285	2492b771122e
parent 283	40511897fcc4
child 286	47e06cb75837