5 |
5 |
6 \begin{document} |
6 \begin{document} |
7 |
7 |
8 \section*{Handout 5 (Protocols)} |
8 \section*{Handout 5 (Protocols)} |
9 |
9 |
|
10 Protocols are the computer science equivalent to fractals and |
|
11 the Mandelbrot set in mathematics. With the latter you have a |
|
12 simple formula which you just iterate and then you test |
|
13 whether a point is inside or outside a region, and voila |
|
14 something magically |
|
15 happened.\footnote{\url{http://en.wikipedia.org/wiki/Fractal}, |
|
16 \url{http://en.wikipedia.org/wiki/Mandelbrot_set}} Protocols |
|
17 are similar: they are simple exchanges of messages, but in the |
|
18 end something ``magical'' can happen---for example a secret |
|
19 channel has been established or two entities have |
|
20 authenticated themselves to each other. The problem with magic |
|
21 is of course it is poorly understood and even experts often |
|
22 got, and get, it wrong with protocols. |
|
23 |
|
24 To have an idea what kind of protocols we are interested, let |
|
25 us look at a few examples. One example are (wireless) key |
|
26 fobs which operate the central locking system and the |
|
27 ignition in a car. |
|
28 |
|
29 \begin{center} |
|
30 \includegraphics[scale=0.075]{../pics/keyfob.jpg} |
|
31 \quad |
|
32 \includegraphics[scale=0.2025]{../pics/startstop.jpg} |
|
33 \end{center} |
|
34 |
|
35 \noindent The point of these key fobs is that everything is |
|
36 done over the ``air''---there is no physical connection |
|
37 between the key, doors and engine. So we must achieve security |
|
38 by exchanging certain messages between the key fob on one side |
|
39 and doors and engine on the other. Clearly what we like to |
|
40 achieve is that I can get into my car and start it, but that |
|
41 thieves are kept out. The problem is that everybody can |
|
42 ``overhear'' or skim the exchange of messages between the key |
|
43 fob and car. In this scenario the simplest attack you need to |
|
44 defend against is a person-in-the-middle attack. Imagine you |
|
45 park your car in front of a supermarket. One thief follows you |
|
46 with a strong transmitter. A second thief ``listens'' to the |
|
47 signal from the car and wirelessly transmits it to the |
|
48 ``colleague'' who followed you and who silently enquires about |
|
49 the answer from the key fob. The answer is then send back to |
|
50 the thief at the car, which then dutifully opens and possibly |
|
51 starts. No need to steal your key anymore. |
|
52 |
|
53 But there are many more such protocols we like to consider. |
|
54 Other examples are wifi---you might sit at a Starbucks and |
|
55 talk wirelessly to the free access point there and from there |
|
56 talk with your bank, for example. Also even if your have to |
|
57 touch your Oyster card at the reader each time you enter and |
|
58 exit the Tube, it actually operates wirelessly and with |
|
59 appropriate equipment over some quite large distance. But |
|
60 there are many many more examples (Bitcoins, mobile |
|
61 phones,\ldots). The common characteristics of the protocols we |
|
62 are interested in here is that an adversary or attacker is |
|
63 assumed to be in complete control over the network or channel |
|
64 over which you exchanging messages. An attacker can install a |
|
65 packet sniffer on a network, inject packets, modify packets, |
|
66 replay old messages, or fake pretty much everything. In this |
|
67 hostile environment, the purpose of protocols (that is |
|
68 exchange of messages) is to achieve some security goal, for |
|
69 example only allow the owner of the car in but everybody else |
|
70 should be kept out. |
|
71 |
10 The protocols we are interested here are generic descriptions |
72 The protocols we are interested here are generic descriptions |
11 of how to exchange messages in order to achieve a goal, be it |
73 of how to exchange messages in order to achieve a goal, be it |
12 establishing a mutual secure connection or being able to |
74 establishing a mutual secure connection or being able to |
13 authenticate to a system. Our notion of protocol is |
75 authenticate to a system. Unlike the distant past where for |
14 deliberately quite general: it includes situations like the |
76 example we had to meet a person in order to authenticate him |
15 messages send between a key fob and a car in order to open |
77 or her (via a passport for example), the problem we are facing |
16 doors or the messages that participants need to exchange in |
78 on the Internet is that we cannot easily be sure who we are |
17 order to mine Bitcoins (which is often already called Bitcoin |
79 ``talking'' to. The obvious reason is that only some electrons |
18 \emph{protocol}). |
80 arrive at our computer; we do not see the person, or computer, |
|
81 behind the incoming electrons (messages). |
19 |
82 |
20 Unlike the distant past where for example we had to meet a |
83 To start, let us look at one of the simplest protocols that |
21 person in order to authenticate him or her (via a passport for |
84 are part of the TCP protocol (which underlies the Internet). |
22 example), the problem we are facing is that on the Internet we |
85 This protocol does not do anything security relevant, it just |
23 cannot easily be sure who we are ``talking'' to. The obvious |
86 establishes a ``hello'' from a client to a server which the |
24 reason is that only some electrons arrive at our computer; we |
87 server answers with ``I heard you'' and the client answers |
25 do not see the person, or computer, behind the incoming |
88 in turn with something like ``thanks''. This protocol |
26 electrons. Often there are is also no person behind the |
89 is often called a \emph{three-way handshake}. Graphically it |
27 messages, rather than a computer system. |
90 can be illustrated as follows |
|
91 |
|
92 \begin{center} |
|
93 \includegraphics[scale=0.5]{../pics/handshake.png} |
|
94 \end{center} |
|
95 |
|
96 \noindent On the left-hand side is a client, say Alice, on the |
|
97 right-hand side is a server, say. Time is running from top to |
|
98 bottom. Alice initial SYN message needs some time to travel to |
|
99 the server. The server answers with SYN-ACK, which will |
|
100 require some time to arrive at Alice. Her answer ACK will |
|
101 again take some time to arrive at the server. After the |
|
102 messages are exchanged Alice and the server simply have |
|
103 established a channel to communicate over. Alice does |
|
104 not know whether she is really talking to the server (somebody |
|
105 else on the network might have intercepted her message |
|
106 and replied in place of the server). Similarly, the |
|
107 server has no idea who it is talking to. That this can be |
|
108 established depends on what is exchanged next and is the |
|
109 point of the protocols we want to study in more detail. |
|
110 |
|
111 Before we start in earnest, we need to fix a more |
|
112 convenient notation for protocols. Drawing pictures like |
|
113 the one above would be awkward in the long-run. The |
|
114 notation already abstracts away from a few details we are |
|
115 not interested in: for example the time the messages |
|
116 need to travel between endpoints. What we are interested |
|
117 in is in which order the messages are sent. For the SYN-ACK |
|
118 protocol we will therefore use the notation |
|
119 |
|
120 \begin{center} |
|
121 \begin{tabular}{l@{\hspace{2mm}}l} |
|
122 $A \to S$: & $SYN$\\ |
|
123 $S \to A$: & $SYN\_ACK$\\ |
|
124 $A \to S$: & $ACK$\\ |
|
125 \end{tabular} |
|
126 \end{center} |
|
127 |
|
128 \noindent The left-hand side specifies who is the sender and |
|
129 who is the receiver of the message. On the right of the colon |
|
130 is the message that is send. The order from top to down |
|
131 specifies in which order the messages are sent. We also |
|
132 have the convention that messages like above $SYN$ are send |
|
133 in clear-text over the network. If we want that a message is |
|
134 encrypted, then we use the notation |
|
135 |
|
136 \[ |
|
137 \{msg\}_{K_{AB}} |
|
138 \] |
|
139 |
|
140 |
|
141 \noindent for messages. The curly braces indicate a kind of |
|
142 envelope which can only be opened if you know the key $K_{AB}$ |
|
143 with which the message has been encrypted. We always assume |
|
144 that an attacker, say Eve, cannot get the content of the |
|
145 message, unless she is also in the possession of the key. We |
|
146 explicitly exclude in our study that the encryption can be |
|
147 broken.\footnote{\ldots{}which of course is what a good |
|
148 protocol designer needs to ensure and more often than not |
|
149 protocols are broken. For example Oyster cards contain a very |
|
150 weak encryption mechanism which has been attacked.} It is also |
|
151 possible that an encrypted message contains several parts. In |
|
152 this case we would write something like |
|
153 |
|
154 \[ |
|
155 \{msg_1, msg_2\}_{K_{AB}} |
|
156 \] |
|
157 |
|
158 \noindent But again Eve would not be able to know |
|
159 this unless she also has the key. We also allow the |
|
160 possibility that a message is encrypted twice under |
|
161 different keys. In this case we write |
|
162 |
|
163 \[ |
|
164 \{\{msg\}_{K_{AB}}\}_{K_{BC}} |
|
165 \] |
28 |
166 |
29 |
167 |
|
168 |
|
169 Note, however, |
|
170 while an attacker cannot obtain the content of the message |
|
171 without the key, this encrypted message can be observed |
|
172 and be recorded and then replayed at another time. |
30 |
173 |
31 Keyfobs - protocol |
174 Keyfobs - protocol |
32 |
175 |
33 {\small |
176 {\small |
34 \url{http://www.cs.ru.nl/~rverdult/Gone_in_360_Seconds_Hijacking_with_Hitag2-USENIX_2012.pdf}} |
177 \url{http://www.cs.ru.nl/~rverdult/Gone_in_360_Seconds_Hijacking_with_Hitag2-USENIX_2012.pdf}} |