31 \end{center} |
38 \end{center} |
32 |
39 |
33 \end{frame} |
40 \end{frame} |
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
35 |
42 |
36 |
43 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
44 \begin{frame}[c] |
38 \begin{frame}[c] |
45 \frametitle{Topical Slide} |
39 \frametitle{Hashes for History} |
46 |
40 |
47 \begin{itemize} |
41 Q: What is the hash for? |
48 \item DoS attack agains some US webpages (hijacked IoT devives, like |
42 |
49 cameras,\ldots) |
43 \begin{center} |
50 |
44 \includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png} |
51 \item funny cow attack (privilege escalation attack) |
45 \end{center} |
52 \end{itemize} |
46 |
53 |
47 \end{frame} |
54 \end{frame} |
48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
49 |
56 |
50 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
51 \begin{frame}[t] |
58 \begin{frame}[c] |
52 \frametitle{Checking Solutions} |
59 \frametitle{Protocols} |
53 |
60 |
54 How can you check somebody's solution without revealing the solution?\pause\bigskip |
61 \begin{center} |
55 |
62 \includegraphics[scale=0.11]{../pics/keyfob.jpg} |
56 Alice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't |
63 \quad |
57 want to tell Bob.\medskip |
64 \includegraphics[scale=0.3025]{../pics/startstop.jpg} |
58 |
65 \end{center} |
59 You use an English dictionary: |
66 |
60 |
67 \begin{itemize} |
61 \begin{itemize} |
68 \item Other examples: Wifi, Http-request, TCP-request, |
62 \item folio \onslide<4->{$\stackrel{1}{\rightarrow}$ individual } |
69 card readers, RFID (passports)\ldots\medskip\pause |
63 \onslide<5->{$\stackrel{2}{\rightarrow}$ human} |
70 |
64 \onslide<6->{$\stackrel{3}{\rightarrow}$ or \ldots} |
71 \item The point is that we cannot control the network: An attacker |
65 \only<3>{ |
72 can install a packet sniffer, inject packets, modify packets, |
66 \begin{quote} |
73 replay messages\ldots{}fake pretty much everything. |
67 ``an \alert{individual} leaf of paper or parchment, either loose as one of a series or |
74 \end{itemize} |
68 forming part of a bound volume, which is numbered on the recto or front side only.'' |
75 |
69 \end{quote}} |
76 \end{frame} |
70 \only<4>{ |
77 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
71 \begin{quote} |
78 |
72 ``a single \alert{human} being as distinct from a group'' |
79 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
73 \end{quote}} |
80 \begin{frame}[c] |
74 \only<5>{ |
81 \frametitle{Keyless Car Transponders} |
75 \begin{quote} |
82 |
76 ``relating to \alert{or} characteristic of humankind'' |
83 \begin{center} |
77 \end{quote}} |
84 \includegraphics[scale=0.1]{../pics/keyfob.jpg} |
78 \end{itemize}\bigskip\bigskip |
85 \quad |
79 |
86 \includegraphics[scale=0.27]{../pics/startstop.jpg} |
80 \only<7->{ |
87 \end{center} |
81 this is essentially a hash function...but Bob can only check once he has also found the solution |
88 |
82 } |
89 \begin{itemize} |
83 |
90 \item There are two security mechanisms: one remote central |
84 \end{frame} |
91 locking system and one passive RFID tag (engine immobiliser). |
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
92 \item How can I get in? How can thieves be kept out? |
86 |
93 How to avoid MITM attacks? |
87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
94 \end{itemize}\medskip |
88 \begin{frame}[c] |
95 |
89 \frametitle{Zero-Knowledge Proofs} |
96 \footnotesize |
90 |
97 \hfill Papers: Gone in 360 Seconds: Hijacking with Hitag2,\\ |
91 Two remarkable properties of \alert{Zero-Knowledge |
98 \hfill Dismantling Megamos Crypto: Wirelessly Lockpicking\\ |
92 Proofs}:\bigskip |
99 \hfill a Vehicle Immobilizer |
93 |
100 |
94 \begin{itemize} |
101 \end{frame} |
95 |
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
96 \item Alice only reveals the fact that she knows a secret, not |
103 |
97 the secret itself (meaning she can convince Bob that she |
104 |
98 knows the secret, but does not give it to him).\bigskip |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
99 \item Having been convinced, Bob cannot use the evidence in |
106 \begin{frame}[c] |
100 order to convince Carol that Alice knows the secret. |
107 \frametitle{Public-Key Infrastructure} |
101 |
108 |
102 \end{itemize} |
109 \begin{itemize} |
103 |
110 \item the idea is to have a certificate authority (CA) |
104 \end{frame} |
111 \item you go to the CA to identify yourself |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
112 \item CA: ``I, the CA, have verified that public key \bl{$P^{pub}_{Bob}$} belongs to Bob''\bigskip |
106 |
113 \item CA must be trusted by everybody |
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
114 \item What happens if CA issues a false certificate? Who pays in case of loss? (VeriSign |
108 \begin{frame}[c] |
115 explicitly limits liability to \$100.) |
109 \frametitle{Interactive Protocols} |
116 \end{itemize} |
110 |
117 |
111 Q: How to cut a cake into two equal slices? |
118 \end{frame} |
112 |
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
113 \begin{center} |
120 |
114 \includegraphics[scale=0.15]{../pics/cake.jpg} |
121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
122 \begin{frame}[c] |
|
123 \frametitle{Man-in-the-Middle} |
|
124 |
|
125 ``Normal'' protocol run:\bigskip |
|
126 |
|
127 \begin{itemize} |
|
128 \item \bl{$A$} sends public key to \bl{$B$} |
|
129 \item \bl{$B$} sends public key to \bl{$A$} |
|
130 \item \bl{$A$} sends message encrypted with \bl{$B$}'s public key, \bl{$B$} decrypts it |
|
131 with its private key |
|
132 \item \bl{$B$} sends message encrypted with \bl{$A$}'s public key, \bl{$A$} decrypts it |
|
133 with its private key |
|
134 \end{itemize} |
|
135 |
|
136 \end{frame} |
|
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
138 |
|
139 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
140 \begin{frame}[c] |
|
141 \frametitle{Man-in-the-Middle} |
|
142 |
|
143 Attack: |
|
144 |
|
145 \begin{itemize} |
|
146 \item \bl{$A$} sends public key to \bl{$B$} --- \bl{$C$} intercepts this message and send his own public key |
|
147 \item \bl{$B$} sends public key to \bl{$A$} --- \bl{$C$} intercepts this message and send his own public key |
|
148 \item \bl{$A$} sends message encrypted with \bl{$C$}'s public key, \bl{$C$} decrypts it |
|
149 with its private key, re-encrypts with \bl{$B$}'s public key |
|
150 \item similar for other direction |
|
151 \end{itemize} |
|
152 |
|
153 \end{frame} |
|
154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
155 |
|
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
157 \begin{frame}[c] |
|
158 \frametitle{Man-in-the-Middle} |
|
159 |
|
160 Potential Prevention? |
|
161 |
|
162 \begin{itemize} |
|
163 \item \bl{$A$} sends public key to \bl{$B$} |
|
164 \item \bl{$B$} sends public key to \bl{$A$} |
|
165 \item \bl{$A$} encrypts message with \bl{$B$}'s public key, send's {\bf half} of the message |
|
166 \item \bl{$B$} encrypts message with \bl{$A$}'s public key, send's {\bf half} of the message |
|
167 \item \bl{$A$} sends other half, \bl{$B$} can now decrypt entire message |
|
168 \item \bl{$B$} sends other half, \bl{$A$} can now decrypt entire message |
|
169 \end{itemize}\pause |
|
170 |
|
171 %\bl{$C$} would have to invent a totally new message |
|
172 \alert{Under which circumstances does this protocol prevent |
|
173 MiM-attacks, or does it?} |
|
174 |
|
175 \end{frame} |
|
176 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
177 |
|
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
179 \begin{frame}[c] |
|
180 \frametitle{Car Transponder (HiTag2)} |
|
181 |
|
182 \begin{enumerate} |
|
183 \item \bl{$C$} generates a random number \bl{$N$} |
|
184 \item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$} |
|
185 \item \bl{$C \to T$}: \bl{$N, F$} |
|
186 \item \bl{$T$} calculates \bl{$(F',G') = \{N\}_K$} |
|
187 \item \bl{$T$} checks that \bl{$F = F'$} |
|
188 \item \bl{$T \to C$}: \bl{$N, G'$} |
|
189 \item \bl{$C$} checks that \bl{$G = G'$} |
|
190 \end{enumerate}\pause |
|
191 |
|
192 \small |
|
193 This process means that the transponder believes the car knows |
|
194 the key \bl{$K$}, and the car believes the transponder knows |
|
195 the key \bl{$K$}. They have authenticated themselves |
|
196 to each other, or have they? |
|
197 |
|
198 \end{frame} |
|
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
200 |
|
201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
202 \begin{frame}[c] |
|
203 |
|
204 A Man-in-the-middle attack in real life: |
|
205 |
|
206 \begin{itemize} |
|
207 \item the card only says yes to the terminal if the PIN is correct |
|
208 \item trick the card in thinking transaction is verified by signature |
|
209 \item trick the terminal in thinking the transaction was verified by PIN |
|
210 \end{itemize} |
|
211 |
|
212 \begin{minipage}{1.1\textwidth} |
|
213 \begin{center} |
|
214 \mbox{}\hspace{-6mm}\includegraphics[scale=0.5]{../pics/chip-attack.png} |
|
215 \includegraphics[scale=0.3]{../pics/chipnpinflaw.png} |
|
216 \end{center} |
|
217 \end{minipage} |
|
218 |
|
219 \end{frame} |
|
220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
221 |
|
222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
223 \begin{frame}[c] |
|
224 \frametitle{Problems with EMV} |
|
225 |
|
226 \begin{itemize} |
|
227 \item it is a wrapper for many protocols |
|
228 \item specification by consensus (resulted unmanageable complexity) |
|
229 \item its specification is 700 pages in English plus 2000+ pages for testing, additionally some |
|
230 further parts are secret |
|
231 \item other attacks have been found |
|
232 \end{itemize} |
|
233 |
|
234 \end{frame} |
|
235 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
236 |
|
237 |
|
238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
239 \begin{frame}[c] |
|
240 \frametitle{Protocols are Difficult} |
|
241 |
|
242 \begin{itemize} |
|
243 \item even the systems designed by experts regularly fail\medskip |
|
244 \item the one who can fix a system should also be liable for the losses\medskip |
|
245 \item cryptography is often not the problem\bigskip\bigskip |
|
246 \end{itemize} |
|
247 |
|
248 \end{frame} |
|
249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
250 |
|
251 |
|
252 |
|
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
254 \begin{frame}[c] |
|
255 \frametitle{A Simple PK Protocol} |
|
256 |
|
257 |
|
258 \begin{center} |
|
259 \begin{tabular}{ll@{\hspace{2mm}}l} |
|
260 1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\smallskip\\ |
|
261 2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\smallskip\\ |
|
262 3. & \bl{$A \to B :$} & \bl{$\{A,m\}_{K^{pub}_B}$}\smallskip\\ |
|
263 4. & \bl{$B \to A :$} & \bl{$\{B,m'\}_{K^{pub}_A}$} |
|
264 \end{tabular} |
115 \end{center}\pause\bigskip |
265 \end{center}\pause\bigskip |
116 |
266 |
117 \small |
267 unfortunately there is a simple man-in-the- middle-attack |
118 Solves the problem of communication when both parties |
268 \end{frame} |
119 distrust each other. |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
120 |
270 |
121 \end{frame} |
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
272 \begin{frame}[c] |
123 |
273 \frametitle{A MITM Attack} |
124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
274 |
125 \begin{frame}[t] |
275 |
126 \frametitle{The Idea} |
276 \begin{center} |
127 |
277 \begin{tabular}{ll@{\hspace{2mm}}l} |
128 \begin{center} |
278 1. & \bl{$A \to E :$} & \bl{$K^{pub}_A$}\smallskip\\ |
129 \begin{tabular}{l@{\hspace{10mm}}r} |
279 2. & \bl{$E \to B :$} & \bl{$K^{pub}_E$}\smallskip\\ |
130 \\[-10mm] |
280 3. & \bl{$B \to E :$} & \bl{$K^{pub}_B$}\smallskip\\ |
131 \raisebox{10mm}{\large 1.} & \includegraphics[scale=0.1]{../pics/alibaba1.png}\\ |
281 4. & \bl{$E \to A :$} & \bl{$K^{pub}_E$}\smallskip\\ |
132 \raisebox{10mm}{\large 2.} & \includegraphics[scale=0.1]{../pics/alibaba2.png}\\ |
282 5. & \bl{$A \to E :$} & \bl{$\{A,m\}_{K^{pub}_E}$}\smallskip\\ |
133 \raisebox{10mm}{\large 3.} & \includegraphics[scale=0.1]{../pics/alibaba3.png} |
283 6. & \bl{$E \to B :$} & \bl{$\{E,m\}_{K^{pub}_B}$}\smallskip\\ |
|
284 7. & \bl{$B \to E :$} & \bl{$\{B,m'\}_{K^{pub}_E}$}\smallskip\\ |
|
285 8. & \bl{$E \to A :$} & \bl{$\{E,m'\}_{K^{pub}_A}$} |
134 \end{tabular} |
286 \end{tabular} |
135 \end{center} |
287 \end{center}\pause\medskip |
136 |
288 |
137 \begin{textblock}{7}(1,2) |
289 and \bl{$A$} and \bl{$B$} have no chance to detect it |
138 The Alibaba cave protocol: |
290 \end{frame} |
139 \end{textblock} |
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
140 |
292 |
141 \small |
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
142 \only<2>{ |
294 \begin{frame}[c] |
143 \begin{textblock}{12}(2,13.3) |
295 \frametitle{Interlock Protocol} |
144 Even if Bob has a hidden camera, a recording will not be |
296 |
145 convincing to anyone else (Alice and Bob could have made it |
297 The interlock protocol (``best bet'' against MITM): |
146 all up). |
298 |
147 \end{textblock}} |
299 \begin{center} |
148 \only<3>{ |
300 \begin{tabular}{ll@{\hspace{2mm}}l} |
149 \begin{textblock}{12}(2,13.3) |
301 1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\\ |
150 Even worse, an observer present at the experiment would not be |
302 2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\\ |
151 convinced. |
303 3. & & \bl{$\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$}\\ |
152 \end{textblock}} |
304 & & \bl{$\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$}\\ |
153 |
305 4. & \bl{$A \to B :$} & \bl{$H_1$}\\ |
154 \end{frame} |
306 5. & \bl{$B \to A :$} & \bl{$\{H_1, M_1\}_{K^{pub}_A}$}\\ |
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
307 6. & \bl{$A \to B :$} & \bl{$\{H_2, M_1\}_{K^{pub}_B}$}\\ |
156 |
308 7. & \bl{$B \to A :$} & \bl{$M_2$} |
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
309 \end{tabular} |
158 \begin{frame}[c] |
310 \end{center} |
159 \frametitle{Applications of ZKPs} |
311 |
160 |
312 \end{frame} |
161 \begin{itemize} |
313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
162 \item authentication, where one party wants to prove its |
314 |
163 identity to a second party via some secret information, |
315 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
164 but doesn't want the second party to learn anything |
316 \begin{frame}[c] |
165 about this secret\bigskip |
317 \frametitle{Splitting Messages} |
166 \item to enforce honest behaviour while maintaining privacy: |
318 |
167 the idea is to force users to prove, using a |
319 \begin{center} |
168 zero-knowledge proof, that their behaviour is correct |
320 $\underbrace{\texttt{\Grid{0X1peUVTGJK+H70mMjAM8p}}}_{\bl{\{A,m\}_{K^{pub}_B}}}$ |
169 according to the protocol |
321 \end{center} |
170 \end{itemize}\bigskip |
322 |
171 |
323 \begin{center} |
172 \small |
324 $\underbrace{\texttt{\Grid{0X1peUVTGJK}}}_{\bl{H_1}}$\quad |
173 digital currencies, smart cards, id cards |
325 $\underbrace{\texttt{\Grid{+H70mMjAM8p}}}_{\bl{H_2}}$ |
174 \end{frame} |
326 \end{center} |
175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
327 |
176 |
328 \begin{itemize} |
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
329 \item you can also use the even and odd bytes |
178 \mode<presentation>{ |
330 \item the point is you cannot decrypt the halves, even if you |
179 \begin{frame}[c] |
331 have the key |
180 \frametitle{Central Properties} |
332 \end{itemize} |
181 |
333 |
182 Zero-knowledge proof protocols should satisfy:\bigskip |
334 |
183 |
335 \end{frame} |
184 \begin{itemize} |
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
185 \item \alert{\bf Completeness} If Alice knows the secret, Bob |
337 |
186 accepts Alice's ``proof'' for sure.\bigskip |
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
187 \item \alert{\bf Soundness} If Alice does not know the secret, |
339 \begin{frame}[c] |
188 Bob accepts her ``proof'' with a very small probability. |
340 |
189 |
341 \begin{center} |
190 \item \alert{\bf Zero-Knowledge} Even if Bob accepts |
342 \begin{tabular}{l@{\hspace{9mm}}l} |
191 the proof by Alice, he cannot convince anybody else. |
343 \begin{tabular}[t]{@{}l@{}} |
192 |
344 \bl{$A \to C : K^{pub}_A$}\\ |
193 \end{itemize} |
345 \bl{$C \to B : K^{pub}_C$}\\ |
194 \end{frame}} |
346 \bl{$B \to C : K^{pub}_B$}\\ |
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
347 \bl{$C \to A : K^{pub}_C$}\medskip\\ |
196 |
348 \bl{$\{A,m\}_{K^{pub}_C} \;\mapsto\; H_1,H_2$}\\ |
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
349 \bl{$\{B,m'\}_{K^{pub}_C} \;\mapsto\; M_1,M_2$}\bigskip\\ |
198 \begin{frame}[c] |
350 \bl{$\{C,a\}_{K^{pub}_B} \;\mapsto\; C_1,C_2$}\\ |
199 \frametitle{Graph Isomorphism} |
351 \bl{$\{C,b\}_{K^{pub}_A} \;\mapsto\; D_1,D_2$} |
200 \mbox{}\\[-20mm]\mbox{} |
352 \end{tabular} & |
201 |
353 \begin{tabular}[t]{@{}l@{}} |
202 \begin{center} |
354 \bl{$A \to C : H_1$}\\ |
203 \begin{tabular}{@{}ccc} |
355 \bl{$C \to B : C_1$}\\ |
204 \raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple.png}} & |
356 \bl{$B \to C : \{C_1, M_1\}_{K^{pub}_C}$}\\ |
205 \raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}& |
357 \bl{$C \to A : \{H_1, D_1\}_{K^{pub}_A}$}\\ |
206 |
358 \bl{$A \to C : \{H_2, D_1\}_{K^{pub}_C}$}\\ |
207 \footnotesize |
359 \bl{$C \to B : \{C_2, M_1\}_{K^{pub}_B}$}\\ |
208 \begin{tabular}{rl} |
360 \bl{$B \to C : M_2$}\\ |
209 Graph A & Graph B\\ |
361 \bl{$C \to A : D_2$} |
210 Graph $G_1$ & Graph $G_2$\\ |
|
211 a & 1\\ |
|
212 b & 6\\ |
|
213 c & 8\\ |
|
214 d & 3\\ |
|
215 g & 5\\ |
|
216 h & 2\\ |
|
217 i & 4\\ |
|
218 j & 7\\ |
|
219 \end{tabular} |
362 \end{tabular} |
220 \end{tabular} |
363 \end{tabular} |
221 \end{center} |
364 \end{center}\pause |
222 |
365 |
223 Finding an isomorphism between two graphs is an NP problem. |
366 \footnotesize |
224 |
367 \bl{$m$} = How is your grandmother? \bl{$m'$} = How is the |
225 \end{frame} |
368 weather today in London? |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
369 |
227 |
370 \end{frame} |
228 |
371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
372 |
230 \begin{frame}[c] |
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
231 \begin{center} |
374 \begin{frame}[c] |
232 \includegraphics[scale=0.8]{../pics/graphs.png} |
375 |
233 \end{center} |
376 \begin{itemize} |
234 |
377 \item you have to ask something that cannot be imitated |
235 Creating a new isomorphic graph is easy; finding an |
378 (requires \bl{$A$} and \bl{$B$} know each other) |
236 isomorphism is hard; checking an isomorphism is easy again |
379 \item what happens if \bl{$m$} and \bl{$m'$} are voice |
237 |
380 messages?\bigskip\pause |
238 \end{frame} |
381 |
239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
382 \item So \bl{$C$} can either leave the communication unchanged, |
240 |
383 or invent a complete new conversation |
241 |
384 |
242 |
385 \end{itemize} |
243 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
386 |
244 \begin{frame}[c] |
387 \end{frame} |
245 \frametitle{\Large Graph Isomorphism Protocol} |
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
246 |
389 |
247 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
248 |
391 \begin{frame}[c] |
249 \begin{enumerate} |
392 |
250 \item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob |
393 \begin{itemize} |
251 \item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or |
394 \item the moral: establishing a secure connection from |
252 \bl{$G_2$} and \bl{$H$} |
395 ``zero'' is almost impossible---you need to rely on some |
253 \item Alice and Bob repeat this procedure \bl{$n$} times |
396 established trust\medskip |
254 \end{enumerate}\pause |
397 |
255 |
398 \item that is why PKI relies on certificates, which however are |
256 these are called commitment algorithms |
399 badly, badly realised |
257 |
400 |
258 \end{frame} |
401 \end{itemize} |
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
402 |
|
403 \end{frame} |
|
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
405 |
|
406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
407 \begin{frame}[c] |
|
408 \frametitle{Trusted Third Parties} |
|
409 |
|
410 Simple protocol for establishing a secure connection via a |
|
411 mutually trusted 3rd party (server): |
|
412 |
|
413 \begin{center} |
|
414 \begin{tabular}{r@ {\hspace{1mm}}l} |
|
415 \bl{$A \rightarrow S :$} & \bl{$A, B$}\\ |
|
416 \bl{$S \rightarrow A :$} & \bl{$\{K_{AB}, \{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$}\\ |
|
417 \bl{$A \rightarrow B :$} & \bl{$\{K_{AB}\}_{K_{BS}} $}\\ |
|
418 \bl{$A \rightarrow B :$} & \bl{$\{m\}_{K_{AB}}$}\\ |
|
419 \end{tabular} |
|
420 \end{center} |
|
421 |
|
422 \end{frame} |
|
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
424 |
|
425 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
426 \begin{frame}[c] |
|
427 \frametitle{PKI: The Main Idea} |
|
428 |
|
429 \begin{itemize} |
|
430 \item the idea is to have a certificate authority (CA) |
|
431 \item you go to the CA to identify yourself |
|
432 \item CA: ``I, the CA, have verified that public key |
|
433 \bl{$P^{pub}_{Bob}$} belongs to Bob''\bigskip |
|
434 \item CA must be trusted by everybody\medskip |
|
435 \item certificates are time limited, and can be revoked |
|
436 |
|
437 \item What happens if CA issues a false certificate? Who pays in case of loss? (VeriSign |
|
438 explicitly limits liability to \$100.) |
|
439 \end{itemize} |
|
440 |
|
441 \end{frame} |
|
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
443 |
|
444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
445 \begin{frame}[c] |
|
446 \frametitle{PKI: Chains of Trust} |
|
447 |
|
448 \begin{center} |
|
449 \begin{tikzpicture}[scale=1, |
|
450 node/.style={ |
|
451 rectangle,rounded corners=3mm, |
|
452 very thick,draw=black!50,minimum height=18mm, minimum width=23mm, |
|
453 top color=white,bottom color=black!20}] |
|
454 |
|
455 \node (A) at (0,0) [node] {}; |
|
456 \node [below right] at (A.north west) |
|
457 {\small\begin{tabular}{@{}l}CA\\Root Cert.\end{tabular}}; |
|
458 |
|
459 \node (B) at (4,0) [node] {}; |
|
460 \node [below right=1mm] at (B.north west) |
|
461 {\mbox{}\hspace{-1mm}\small |
|
462 \begin{tabular}{@{}l}Subordinate\\ CA\end{tabular}}; |
|
463 |
|
464 \node (C) at (8,0) [node] {}; |
|
465 \node [below right] at (C.north west) |
|
466 {\small\begin{tabular}{@{}l}Server\\ Bank.com\end{tabular}}; |
|
467 |
|
468 \draw [->,line width=4mm] (A) -- (B); |
|
469 \draw [->,line width=4mm] (B) -- (C); |
|
470 |
|
471 \node (D) at (6,-3) [node] {}; |
|
472 \node [below right] at (D.north west) |
|
473 {\small\begin{tabular}{@{}l}Browser\\ Root Store\end{tabular}}; |
|
474 |
|
475 \node (E) at (2,-3) [node] {}; |
|
476 \node [below right] at (E.north west) |
|
477 {\small\begin{tabular}{@{}l}Browser\\ Vendor\end{tabular}}; |
|
478 |
|
479 \draw [->,line width=4mm] (E) -- (D); |
|
480 \end{tikzpicture} |
|
481 \end{center} |
|
482 |
|
483 \begin{itemize} |
|
484 \item CAs make almost no money anymore, because of stiff |
|
485 competition |
|
486 \item browser companies are not really interested in security; |
|
487 only in market share |
|
488 \end{itemize} |
|
489 |
|
490 \end{frame} |
|
491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
492 |
|
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
494 \begin{frame}[c] |
|
495 \frametitle{PKI: Weaknesses} |
|
496 |
|
497 CAs just cannot win (make any profit):\medskip |
|
498 |
|
499 \begin{itemize} |
|
500 \item there are hundreds of CAs, which issue millions of |
|
501 certificates and the error rate is small |
|
502 |
|
503 \item users (servers) do not want to pay or pay as little as |
|
504 possible\bigskip |
|
505 |
|
506 \item a CA can issue a certificate for any domain not needing |
|
507 any permission (CAs are meant to undergo audits, |
|
508 but\ldots DigiNotar) |
|
509 |
|
510 \item if a CA has issued many certificates, it ``becomes too |
|
511 big to fail'' |
|
512 |
|
513 \item Can we be sure CAs are not just frontends of some |
|
514 government organisation? |
|
515 |
|
516 \end{itemize} |
|
517 |
|
518 \end{frame} |
|
519 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
520 |
|
521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
522 \begin{frame}[c] |
|
523 \frametitle{PKI: Weaknesses} |
|
524 |
|
525 \begin{itemize} |
|
526 |
|
527 \item many certificates are issued via Whois, whether you own |
|
528 the domain\ldots if you hijacked a domain, it is easy to |
|
529 obtain certificates\medskip |
|
530 |
|
531 \item the revocation mechanism does not work (Chrome has given |
|
532 up on general revocation lists)\medskip |
|
533 |
|
534 \item lax approach to validation of certificates |
|
535 (Have you ever bypassed certification warnings?)\medskip |
|
536 |
|
537 \item sometimes you want to actually install invalid |
|
538 certificates (self-signed) |
260 |
539 |
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
540 \end{itemize} |
262 \begin{frame}[c] |
541 |
263 \frametitle{\Large Graph Isomorphism Protocol (2)} |
542 \end{frame} |
264 |
543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
265 If Alice knows the isomorphism, she can always calculate |
544 |
266 \bl{$\sigma$}.\bigskip |
545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
267 |
546 \begin{frame}[c] |
268 If she doesn't, she can only correctly respond if Bob's choice |
547 \frametitle{PKI: Attacks} |
269 of index is the same as the one she used to form \bl{$H$}. The |
548 |
270 probability of this happening is \bl{$\frac{1}{2}$}, so after |
549 \begin{itemize} |
271 \bl{$n$} rounds the probability of her always responding |
550 |
272 correctly is only \bl{$\frac{1}{2}^n$}. |
551 \item Go directly after root certificates |
273 |
552 \begin{itemize} |
274 \end{frame} |
553 \item governments can demand private keys\smallskip |
275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
554 \item 10 years ago it was estimated that breaking a 1024 bit |
|
555 key takes one year and costs 10 - 30 Mio \$; this is now |
|
556 reduced to 1 Mio \$ |
|
557 \end{itemize} |
|
558 |
|
559 \item Go after buggy implementations of certificate |
|
560 validation\smallskip |
|
561 |
|
562 \item Social Engineering |
|
563 \begin{itemize} |
|
564 \item in 2001 somebody pretended to be |
|
565 from Microsoft and asked for two code-signing |
|
566 certificates |
|
567 \end{itemize}\bigskip |
|
568 \end{itemize} |
|
569 |
|
570 \small The eco-system is completely broken (it relies on |
|
571 thousands of entities to do the right thing). Maybe DNSSEC |
|
572 where keys can be attached to domain names is a way out. |
|
573 |
|
574 \end{frame} |
|
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
576 |
|
577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
578 \begin{frame}[c] |
|
579 \frametitle{Real Attacks} |
|
580 |
|
581 \begin{itemize} |
|
582 |
|
583 \item In 2011, DigiNotar (Dutch company) was the first CA that |
|
584 got compromised comprehensively, and where many |
|
585 fraudulent certificates were issued to the wild. It |
|
586 included approximately 300,000 IP addresses, mostly |
|
587 located in Iran. The attackers (in Iran?) were likely |
|
588 interested ``only'' in collecting gmail passwords.\medskip |
|
589 |
|
590 \item The Flame malware piggy-bagged on this attack by |
|
591 advertising malicious Windows updates to some targeted |
|
592 systems (mostly in Iran, Israel, Sudan). |
|
593 |
|
594 \end{itemize} |
|
595 |
|
596 \end{frame} |
|
597 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
598 |
|
599 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
600 \begin{frame}[c] |
|
601 \frametitle{PKI is Broken} |
|
602 |
|
603 \begin{itemize} |
|
604 |
|
605 \item PKI and certificates are meant to protect you against |
|
606 MITM attacks, but if the attack occurs your are |
|
607 presented with a warning and you need to decide whether |
|
608 you are under attack.\medskip |
|
609 |
|
610 \item Webcontent gets often loaded from 3rd-party servers, |
|
611 which might not be secured\medskip |
|
612 |
|
613 \item Misaligned incentives: browser vendors are not |
|
614 interested in breaking webpages with invalid |
|
615 certificates |
|
616 |
|
617 \end{itemize} |
|
618 |
|
619 \end{frame} |
|
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
621 |
|
622 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
623 \begin{frame}[c] |
|
624 |
|
625 Why are there so many invalid certificates?\bigskip |
|
626 |
|
627 \begin{itemize} |
|
628 |
|
629 \item insufficient name coverage (www.example.com should |
|
630 include example.com) |
|
631 |
|
632 \item IoT: many appliances have web-based admin interfaces; |
|
633 the manufacturer cannot know under which IP and domain name |
|
634 the appliances are run (so cannot install a valid certificate) |
|
635 |
|
636 \item expired certificates, or incomplete chains of trust |
|
637 (servers are supposed to supply them) |
|
638 |
|
639 \end{itemize} |
|
640 |
|
641 \end{frame} |
|
642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
643 |
|
644 % |
|
645 % |
|
646 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
647 %\begin{frame}[c] |
|
648 %\frametitle{Best Practices} |
|
649 % |
|
650 %{\bf Principle 1:} Every message should say what it means: the |
|
651 %interpretation of a message should not depend on the |
|
652 %context.\bigskip\pause |
|
653 % |
|
654 %{\bf Principle 2:} If the identity of a principal is essential |
|
655 %to the meaning of a message, it is prudent to mention the |
|
656 %principal’s name explicitly in the message (though |
|
657 %difficult).\bigskip |
|
658 % |
|
659 %\end{frame} |
|
660 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
661 % |
|
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
663 %\begin{frame}[c] |
|
664 %\frametitle{Best Practices} |
|
665 % |
|
666 %{\bf Principle 3:} Be clear about why encryption is being |
|
667 %done. Encryption is not wholly cheap, and not asking precisely |
|
668 %why it is being done can lead to redundancy. Encryption is not |
|
669 %synonymous with security. |
|
670 % |
|
671 % |
|
672 %\small |
|
673 %\begin{center} |
|
674 %Possible Uses of Encryption |
|
675 % |
|
676 % |
|
677 %\begin{itemize} |
|
678 %\item Preservation of confidentiality: \bl{$\{X\}_K$} only those that have \bl{$K$} may recover \bl{$X$}. |
|
679 %\item Guarantee authenticity: The partner is indeed some particular principal. |
|
680 %\item Guarantee confidentiality and authenticity: binds two parts of a message --- |
|
681 %\bl{$\{X,Y\}_K$} is not the same as \bl{$\{X\}_K$} and \bl{$\{Y\}_K$}. |
|
682 %\end{itemize} |
|
683 %\end{center} |
|
684 % |
|
685 %\end{frame} |
|
686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
687 % |
|
688 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
689 %\begin{frame}[c] |
|
690 %\frametitle{Best Practices} |
|
691 % |
|
692 %{\bf Principle 4:} The protocol designers should know which |
|
693 %trust relations their protocol depends on, and why the |
|
694 %dependence is necessary. The reasons for particular trust |
|
695 %relations being acceptable should be explicit though they will |
|
696 %be founded on judgment and policy rather than on |
|
697 %logic.\bigskip |
|
698 % |
|
699 % |
|
700 %Example Certification Authorities: CAs are trusted to certify |
|
701 %a key only after proper steps have been taken to identify the |
|
702 %principal that owns it. |
|
703 % |
|
704 %\end{frame} |
|
705 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
706 % |
|
707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
708 %\begin{frame}[c] |
|
709 %\frametitle{Formal Methods} |
|
710 % |
|
711 %Ross Anderson about the use of Logic:\bigskip |
|
712 % |
|
713 %\begin{quote} |
|
714 %Formal methods can be an excellent way of finding |
|
715 %bugs in security protocol designs as they force the designer |
|
716 %to make everything explicit and thus confront difficult design |
|
717 %choices that might otherwise be fudged. |
|
718 %\end{quote} |
|
719 % |
|
720 %\end{frame} |
|
721 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
722 % |
|
723 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
724 \begin{frame}[c] |
|
725 \frametitle{Mid-Term} |
|
726 |
|
727 \begin{itemize} |
|
728 \item homework, handouts, programs\ldots |
|
729 \end{itemize}\bigskip\bigskip\bigskip |
|
730 |
|
731 \begin{center} |
|
732 {\huge\bf\alert{Any Questions?}} |
|
733 \end{center} |
|
734 |
|
735 \end{frame} |
|
736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
737 |
|
738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
739 \begin{frame}[c] |
|
740 \frametitle{Security Engineering} |
|
741 |
|
742 \begin{center} |
|
743 \begin{tabular}{cc} |
|
744 \raisebox{-0.8mm}{\includegraphics[scale=0.28]{../pics/flight.jpg}} & |
|
745 \includegraphics[scale=0.31]{../pics/airbus.jpg}\\ |
|
746 \small Wright brothers, 1901 & \small Airbus, 2005 \\ |
|
747 \end{tabular} |
|
748 \end{center} |
|
749 |
|
750 \end{frame} |
|
751 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
752 |
|
753 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
754 \begin{frame}[c] |
|
755 \frametitle{1st Lecture} |
|
756 |
|
757 \begin{itemize} |
|
758 \item chip-and-pin, banks vs.~customers |
|
759 \begin{quote}\small\rm |
|
760 the one who can improve security should also be |
|
761 liable for the losses |
|
762 \end{quote}\pause\bigskip |
|
763 |
|
764 \item hashes and salts to guarantee data integrity\medskip |
|
765 \item storing passwords (you should know the difference between |
|
766 brute force attacks and dictionary attacks; how do salts help?) |
|
767 \end{itemize} |
|
768 |
|
769 \end{frame} |
|
770 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
771 |
|
772 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
773 \begin{frame}[c] |
|
774 \frametitle{1st Lecture: Cookies} |
|
775 |
|
776 \begin{itemize} |
|
777 \item good uses of cookies?\medskip |
|
778 |
|
779 \item bad uses of cookies: snooping, tracking, profiling\ldots |
|
780 the ``disadvantage'' is that the user is in |
|
781 \alert{control}, because you can delete them |
|
782 |
|
783 \begin{center} ``Please track me using cookies.'' |
|
784 \end{center}\bigskip\pause |
|
785 |
|
786 \item fingerprinting beyond browser cookies |
|
787 \begin{quote}\small\rm |
|
788 Pixel Perfect: Fingerprinting Canvas in HTML5\\ |
|
789 (a research paper from 2012)\\ |
|
790 \footnotesize |
|
791 \url{http://cseweb.ucsd.edu/~hovav/papers/ms12.html} |
|
792 \end{quote} |
|
793 \end{itemize} |
|
794 |
|
795 \end{frame} |
|
796 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
797 |
|
798 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
799 \begin{frame}[c] |
|
800 \frametitle{1st Lecture: Cookies} |
|
801 |
|
802 \begin{itemize} |
|
803 \item a bit of JavaScript and HTML5 + canvas\medskip |
|
804 \begin{center} |
|
805 \begin{tabular}{cc} |
|
806 Firefox & Safari\\ |
|
807 \includegraphics[scale=0.31]{../pics/firefox1.png} & |
|
808 \includegraphics[scale=0.31]{../pics/safari1.png} \\ |
|
809 \tiny |
|
810 \pcode{55b2257ad0f20ecbf927fb66a15c61981f7ed8fc} & |
|
811 \tiny |
|
812 \pcode{17bc79f8111e345f572a4f87d6cd780b445625d3} |
|
813 \end{tabular} |
|
814 \end{center}\bigskip |
|
815 |
|
816 \item\small no actual drawing needed\pause |
|
817 \item\small in May 2014 a crawl of 100,000 popular |
|
818 webpages revealed 5.5\% already use canvas |
|
819 fingerprinting\smallskip |
|
820 \begin{center}\scriptsize |
|
821 \url{https://securehomes.esat.kuleuven.be/~gacar/persistent/the_web_never_forgets.pdf} |
|
822 \end{center} |
|
823 \end{itemize} |
|
824 |
|
825 \end{frame} |
|
826 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
827 |
|
828 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
829 \begin{frame}[c] |
|
830 \frametitle{1st Lecture: Cookies} |
|
831 |
|
832 Remember the small web-app I showed you where a cookie |
|
833 protected a counter?\bigskip |
|
834 |
|
835 \begin{itemize} |
|
836 \item NYT, the cookie looks the ``resource'' - harm\medskip |
|
837 \item imaginary discount unlocked by cookie - no harm |
|
838 \end{itemize} |
|
839 |
|
840 \end{frame} |
|
841 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
842 |
276 |
843 |
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
844 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
278 \begin{frame}[t] |
845 \begin{frame}[t] |
279 \frametitle{Plot of $\frac{1}{2}^n$} |
846 \frametitle{2nd Lecture: E-Voting} |
|
847 |
|
848 Where are paper ballots better than voice voting?\bigskip |
|
849 |
|
850 \begin{itemize} |
|
851 \item Integrity |
|
852 \item \alert{Ballot Secrecy} |
|
853 \item Voter Authentication |
|
854 \item Enfranchisement |
|
855 \item Availability |
|
856 \end{itemize} |
|
857 |
|
858 \end{frame} |
|
859 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
860 |
|
861 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
862 \begin{frame}[t] |
|
863 \frametitle{2nd Lecture: E-Voting} |
|
864 |
|
865 \begin{itemize} |
|
866 \item recently an Australian parliamentary committee |
|
867 found: e-voting is highly vulnerable to hacking and Australia |
|
868 will not use it any time soon\bigskip\pause |
|
869 \item Alex Halderman, Washington D.C.~hack |
|
870 \begin{center} |
|
871 \scriptsize |
|
872 \url{https://jhalderm.com/pub/papers/dcvoting-fc12.pdf} |
|
873 \end{center}\medskip |
|
874 |
|
875 \item PDF-ballot tampering at the wireless router (the modification |
|
876 is nearly undetectable and leaves no traces; MITM attack with firmware |
|
877 updating) |
|
878 \begin{center} |
|
879 \scriptsize |
|
880 \url{http://galois.com/wp-content/uploads/2014/11/technical-hack-a-pdf.pdf} |
|
881 \end{center} |
|
882 |
|
883 \end{itemize} |
|
884 |
|
885 \end{frame} |
|
886 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
887 |
|
888 |
|
889 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
890 \tikzset{alt/.code args={<#1>#2#3#4}{% |
|
891 \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path |
|
892 }} |
|
893 |
|
894 \begin{frame}[t] |
|
895 \frametitle{\begin{tabular}{c}3rd Lecture:\\ Buffer Overflow Attacks\end{tabular}} |
|
896 |
|
897 \begin{itemize} |
|
898 \item the problem arises from the way C/C++ organises its function calls\\[-8mm]\mbox{} |
|
899 \end{itemize} |
|
900 |
|
901 \begin{center} |
|
902 \begin{tikzpicture}[scale=1] |
|
903 %\draw[black!10,step=2mm] (0,0) grid (9,4); |
|
904 %\draw[black!10,thick,step=10mm] (0,0) grid (9,4); |
|
905 |
|
906 \node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}}; |
|
907 \draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8); |
|
908 \draw[line width=0mm, white, alt=<9->{fill=red}{fill=blue}] (0,0.2) rectangle (1,0.5); |
|
909 \draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5); |
|
910 \draw[line width=1mm, alt=<6->{fill=red}{fill=blue}] (0,1.0) rectangle (1,2.0); |
|
911 \draw[line width=1mm, alt=<7->{fill=yellow}{fill=blue}] (0,0.5) rectangle (1,1.0); |
|
912 \draw[line width=1mm] (0,0) -- (0,4); |
|
913 \draw[line width=1mm] (1,0) -- (1,4); |
|
914 |
|
915 \node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}}; |
|
916 \draw[line width=1mm, alt=<{4-5,8}>{fill=red}{fill=blue}] (3,1.0) rectangle (4,3.0); |
|
917 |
|
918 \onslide<3-4>{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);} |
|
919 \onslide<5>{\draw[<-, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {res=24} (3,1);} |
|
920 |
|
921 \onslide<7-8>{\draw[->, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {n=3} (3,3);} |
|
922 \onslide<9>{\draw[<-, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {res=6} (3,1);} |
|
923 |
|
924 |
|
925 \node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}}; |
|
926 \draw[line width=1mm] (7,3.5) -- (7,0.5) -- (8.5,0.5) -- (8.5,3.5); |
|
927 |
|
928 \onslide<3,4,7,8>{ |
|
929 \node at (7.75, 1.4) {ret}; |
|
930 \draw[line width=1mm] (7,1.1) -- (8.5,1.1); |
|
931 \node at (7.75, 2.0) {sp}; |
|
932 \draw[line width=1mm] (7,2.3) -- (8.5,2.3); |
|
933 } |
|
934 \onslide<3,4>{ |
|
935 \node at (7.75, 0.8) {4}; |
|
936 \draw[line width=1mm] (7,1.7) -- (8.5,1.7); |
|
937 } |
|
938 \onslide<7,8>{ |
|
939 \node at (7.75, 0.8) {3}; |
|
940 \draw[line width=1mm] (7,1.7) -- (8.5,1.7); |
|
941 } |
|
942 |
|
943 |
|
944 \end{tikzpicture} |
|
945 \end{center} |
|
946 |
|
947 \end{frame} |
|
948 |
|
949 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
950 \begin{frame}[t] |
|
951 |
|
952 \begin{center} |
|
953 \begin{tikzpicture}[scale=1] |
|
954 %\draw[black!10,step=2mm] (0,0) grid (9,4); |
|
955 %\draw[black!10,thick,step=10mm] (0,0) grid (9,4); |
|
956 |
|
957 \node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}}; |
|
958 \draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8); |
|
959 \draw[line width=1mm, white, fill=blue] (0,1.0) rectangle (1,2.0); |
|
960 \draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5); |
|
961 \draw[line width=1mm] (0,0) -- (0,4); |
|
962 \draw[line width=1mm] (1,0) -- (1,4); |
|
963 |
|
964 \node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}}; |
|
965 \draw[line width=0mm, alt=<{4-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,3.0); |
|
966 \draw[line width=0mm, alt=<{5-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,2.0); |
|
967 \draw[line width=0mm, alt=<{7-}>{red, fill=red}{blue, fill=blue}] (3,2.0) rectangle (4,1.0); |
|
968 \draw[line width=1mm] (3,1.0) rectangle (4,3.0); |
|
969 |
|
970 \onslide<3->{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);} |
|
971 \onslide<5->{\draw[<-, line width=2mm,red] (4,2) to node [above,sloped,midway] |
|
972 {\begin{tabular}{l}user\\[-1mm] input\end{tabular}} (6,2);} |
|
973 \onslide<8->{\draw[<-, line width=1mm,red] (1,-2) to (3,1);} |
|
974 |
|
975 \node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}}; |
|
976 \draw[line width=1mm] (7,3.5) -- (7,-0.1) -- (8.5,-0.1) -- (8.5,3.5); |
|
977 |
|
978 \onslide<3->{ |
|
979 \node at (7.75, 0.2) {4}; |
|
980 \draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,0.5) rectangle (8.5,1.1); |
|
981 \node at (7.75, 0.8) {\alt<6->{@a\#}{ret}}; |
|
982 \draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,1.1) rectangle (8.5,1.7); |
|
983 \node at (7.75, 1.4) {\alt<6->{!?w;}sp}; |
|
984 } |
|
985 |
|
986 \onslide<4->{ |
|
987 \draw[line width=1mm,fill=red] (7,1.7) rectangle (8.5,3.0); |
|
988 \node[white] at (7.75, 2.4) {buffer}; |
|
989 } |
|
990 |
|
991 \end{tikzpicture} |
|
992 \end{center} |
|
993 |
|
994 \end{frame} |
|
995 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
996 |
|
997 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
998 \begin{frame}[t] |
|
999 \frametitle{\begin{tabular}{c}3rd Lecture:\\[-3mm] |
|
1000 Buffer Overflow Attacks\end{tabular}} |
|
1001 |
|
1002 US National Vulnerability Database\\ |
|
1003 \small(636 out of 6675 in 2014) |
280 |
1004 |
281 \begin{center} |
1005 \begin{center} |
282 \begin{tikzpicture} |
1006 \begin{tikzpicture} |
283 \begin{axis}[ |
1007 \begin{axis}[ |
284 enlargelimits=true, |
1008 xlabel={year}, |
285 xtick={0,1,...,10}, |
1009 ylabel={\% of total attacks}, |
286 xmax=11, |
1010 ylabel style={yshift=0em}, |
287 ymax=1.1, |
1011 enlargelimits=false, |
288 ytick={0,0.1,...,1.1}, |
1012 xtick={1997,1999,...,2015}, |
|
1013 xmin=1996.5, |
|
1014 xmax=2016, |
|
1015 ymax=21, |
|
1016 ytick={0,5,...,20}, |
289 scaled ticks=false, |
1017 scaled ticks=false, |
290 axis lines=left, |
1018 axis lines=left, |
291 width=11cm, |
1019 width=11cm, |
292 height=7cm] |
1020 height=5cm, |
293 \addplot[blue,mark=*, mark options={fill=white}] |
1021 ybar, |
294 coordinates { |
1022 nodes near coords= |
295 (0, 1) (1, 0.5) (2, 0.25) (3, 0.125) |
1023 {\footnotesize |
296 (4, 0.0625) (5, 0.03125) (6, 0.015625) |
1024 $\pgfmathprintnumber[fixed,fixed zerofill,precision=1,use comma]{\pgfkeysvalueof{/data point/y}}$}, |
297 (7, 0.0078125) (8, 0.00390625) |
1025 x tick label style={font=\scriptsize,/pgf/number format/1000 sep={}}] |
298 (9, 0.001953125) (10, 0.0009765625) |
1026 \addplot |
299 }; |
1027 table [x=Year,y=Percentage] {../handouts/bufferoverflows.data}; |
300 \end{axis} |
1028 \end{axis} |
301 \end{tikzpicture} |
1029 \end{tikzpicture} |
302 \end{center} |
1030 \end{center} |
303 |
1031 |
304 \end{frame} |
1032 \scriptsize |
305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1033 \url{http://web.nvd.nist.gov/view/vuln/statistics} |
306 |
1034 \end{frame} |
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1035 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
308 \begin{frame}[c] |
1036 |
309 \frametitle{\Large Graph Isomorphism Protocol (3)} |
1037 |
310 |
1038 |
311 Why is the GI-protocol zero-knowledge?\bigskip\pause |
1039 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
312 |
1040 \begin{frame}[t] |
313 A: We can generate a fake transcript of a conversation, which |
1041 \frametitle{\begin{tabular}{c}4th Lecture:\\ Unix Access Control\end{tabular}} |
314 cannot be distinguished from a ``real'' conversation.\bigskip |
1042 |
315 |
1043 \begin{itemize} |
316 Anything Bob can compute using the information obtained from |
1044 \item privileges are specified by file access permissions (``everything is a file'') |
317 the transcript can be computed using only a forged transcript |
1045 \end{itemize}\medskip |
318 and therefore participation in such a communication does not |
1046 |
319 increase Bob's capability to perform any computation. |
1047 \begin{center} |
320 |
1048 \begin{tikzpicture}[scale=1] |
321 \end{frame} |
1049 |
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1050 \draw[line width=1mm] (-.3, 0) rectangle (1.5,2); |
323 |
1051 \draw (4.7,1) node {Internet}; |
324 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1052 \draw (-2.7,1.7) node {\footnotesize Application}; |
325 \begin{frame}[c] |
1053 \draw (0.6,1.7) node {\footnotesize Interface}; |
326 \frametitle{Non-Interactive ZKPs} |
1054 \draw (0.6,-0.4) node {\footnotesize \begin{tabular}{c}unprivileged\\[-1mm] process\end{tabular}}; |
327 |
1055 \draw (-2.7,-0.4) node {\footnotesize \begin{tabular}{c}privileged\\[-1mm] process\end{tabular}}; |
328 This is amazing: This can all be done ``offline'': |
1056 |
329 \bigskip |
1057 \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); |
330 |
1058 |
331 Alice can publish some data that contains no data about her |
1059 \draw[white] (1.7,1) node (X) {}; |
332 secret, but this data can be used to convince anyone of the |
1060 \draw[white] (3.7,1) node (Y) {}; |
333 secret's existence (whether Alice knows it, must be |
1061 \draw[red, <->, line width = 2mm] (X) -- (Y); |
334 established my other means). |
|
335 |
|
336 \end{frame} |
|
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
338 |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 \begin{frame}[c] |
|
341 \frametitle{Non-Interactive ZKPs (2)} |
|
342 |
|
343 Alice starts with knowing an isomorphism \bl{$\sigma$} between |
|
344 graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
|
345 |
|
346 \begin{enumerate} |
|
347 \item Alice generates \bl{$n$} isomorphic graphs |
|
348 \bl{$H_{1..n}$} which she makes public |
|
349 \item she feeds the \bl{$H_{1..n}$} into a hashing function |
|
350 (she has no control over what the output will be) |
|
351 \item Alice takes the first \bl{$n$} bits of the output: |
|
352 whenever output is \bl{$0$}, she shows an isomorphism |
|
353 with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism |
|
354 with \bl{$G_2$} |
|
355 \end{enumerate} |
|
356 |
|
357 \end{frame} |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 |
|
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
361 \begin{frame}[c] |
|
362 \frametitle{Problems of ZKPs} |
|
363 |
|
364 \begin{itemize} |
|
365 \item ``grand chess master problem''\\ (person in the |
|
366 middle again)\bigskip |
|
367 |
|
368 \item Alice can have multiple identities; once she committed a |
|
369 fraud with one, she stops using one |
|
370 \end{itemize} |
|
371 |
|
372 \end{frame} |
|
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
374 |
|
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
376 \mode<presentation>{ |
|
377 \begin{frame}[c] |
|
378 \frametitle{Other Methods for ZKPs} |
|
379 |
|
380 Essentially every NP-problem can be used for ZKPs |
|
381 |
|
382 \begin{itemize} |
|
383 \item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} |
|
384 |
|
385 \begin{center} |
|
386 \bl{$A^x \equiv B\; mod\; p$} |
|
387 \end{center} |
|
388 \end{itemize} |
|
389 |
|
390 \end{frame}} |
|
391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
392 |
|
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
394 \mode<presentation>{ |
|
395 \begin{frame}[c] |
|
396 \frametitle{Commitment Stage} |
|
397 |
|
398 \begin{enumerate} |
|
399 \item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}. |
|
400 \item Alice sends Bob for all \bl{$1..z$} |
|
401 \begin{center} |
|
402 \bl{$h_i = A^{r_i} \;mod\; p$} |
|
403 \end{center} |
|
404 \item Bob generates random bits \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin |
|
405 \item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where |
|
406 |
|
407 \begin{center} |
|
408 \begin{tabular}{ll} |
|
409 \bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\ |
|
410 \bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\ |
|
411 \end{tabular} |
|
412 \end{center} |
|
413 where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$} |
|
414 |
1062 |
415 \end{enumerate} |
1063 \draw[red, <->, line width = 1mm] (-0.6,1) -- (-1.6,1); |
416 |
1064 \end{tikzpicture} |
417 \end{frame}} |
1065 \end{center} |
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1066 |
419 |
1067 \begin{itemize} |
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1068 \item the idea is to make the attack surface smaller and |
421 \mode<presentation>{ |
1069 mitigate the consequences of an attack |
422 \begin{frame}[c] |
1070 \end{itemize} |
423 \frametitle{Confirmation Stage} |
1071 |
424 |
1072 \end{frame} |
425 \begin{enumerate} |
1073 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
426 \item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol |
1074 |
427 |
1075 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
428 \begin{center} |
1076 \begin{frame}[fragile,t] |
429 \begin{tabular}{ll} |
1077 \frametitle{\begin{tabular}{c}4th Lecture:\\ Unix Access Control\end{tabular}} |
430 \bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv h_i\;mod\;p$}\\ |
1078 |
431 \bl{$b_i = 1$}: & \bl{$A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p$}\\ |
1079 \begin{itemize} |
432 \end{tabular} |
1080 \item when a file with setuid is executed, the resulting process will assume the |
433 \end{center}\bigskip |
1081 UID given to the owner of the file |
434 |
1082 \end{itemize} |
435 Bob was sent |
1083 |
436 |
1084 \footnotesize\tt |
437 \begin{center} |
1085 \begin{center} |
438 \bl{$r_j - r_j$}, \bl{$r_m - r_j$}, \ldots, \bl{$r_p - r_j \;mod \;p - 1$} |
1086 \begin{verbatim} |
439 \end{center} |
1087 $ ls -ld . * */* |
440 |
1088 drwxr-xr-x 1 ping staff 32768 Apr 2 2010 . |
441 where the corresponding bits were |
1089 -rw----r-- 1 ping students 31359 Jul 24 2011 manual.txt |
442 \bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$} |
1090 -r--rw--w- 1 bob students 4359 Jul 24 2011 report.txt |
443 \end{enumerate} |
1091 -rwsr--r-x 1 bob students 141359 Jun 1 2013 microedit |
444 |
1092 dr--r-xr-x 1 bob staff 32768 Jul 23 2011 src |
445 \end{frame}} |
1093 -rw-r--r-- 1 bob staff 81359 Feb 28 2012 src/code.c |
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1094 -r--rw---- 1 emma students 959 Jan 23 2012 src/code.h |
447 |
1095 \end{verbatim} |
448 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1096 \end{center} |
449 \begin{frame}[c] |
1097 |
450 \frametitle{Proving Stage} |
1098 |
451 |
1099 \end{frame} |
452 \begin{enumerate} |
1100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
453 \item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\ |
1101 |
454 she sends |
1102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
455 |
1103 \begin{frame}[t] |
456 \begin{center} |
1104 \frametitle{\begin{tabular}{c}4th Lecture:\\ Unix Access Control\end{tabular}} |
457 \bl{$s_{z+1} = (x - r_j)$} |
1105 |
458 \end{center} |
1106 \begin{itemize} |
459 |
1107 \item Alice wants to have her files readable, |
460 \item Bob confirms |
1108 \alert{except} for her office mates.\bigskip |
461 |
1109 |
462 \begin{center} |
1110 \item make sure you understand the setuid and setgid bits; |
463 \bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$} |
1111 why are they necessary for login and passwd |
464 \end{center} |
1112 \end{itemize} |
465 \end{enumerate}\bigskip\pause |
1113 |
466 |
1114 |
467 In order to cheat, Alice has to guess all bits in advance. She |
1115 \end{frame} |
468 has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\ |
1116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
469 |
|
470 \small\hspace{7mm} |
|
471 \textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})} |
|
472 |
|
473 \end{frame} |
|
474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
475 |
|
476 |
|
477 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
478 \begin{frame}[c] |
|
479 \frametitle{Take Home Points} |
|
480 |
|
481 \begin{itemize} |
|
482 \item this is pretty old work (in theory); seems |
|
483 little used in practice (surprising)\bigskip |
|
484 |
|
485 \item for use in privacy, the incentives are |
|
486 not yet right\bigskip |
|
487 |
|
488 \item most likely applied with digital cash |
|
489 (Bitcoins are not yet good enough, Zerocoins) |
|
490 |
|
491 \end{itemize} |
|
492 |
|
493 \end{frame} |
|
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
495 |
|
496 |
|
497 |
1117 |
498 |
1118 |
499 \end{document} |
1119 \end{document} |
500 |
1120 |
501 %%% Local Variables: |
1121 %%% Local Variables: |