1 \documentclass[dvipsnames,14pt,t]{beamer} |
1 \documentclass[dvipsnames,14pt,t]{beamer} |
2 \usepackage{../slides} |
2 \usepackage{../slides} |
3 \usepackage{../graphics} |
3 \usepackage{../graphics} |
4 \usepackage{../langs} |
4 \usepackage{../langs} |
|
5 \usepackage{../data} |
5 |
6 |
6 \usetikzlibrary{shapes} |
7 \usetikzlibrary{shapes} |
7 |
8 |
8 % beamer stuff |
9 % beamer stuff |
9 \renewcommand{\slidecaption}{SEN 08, King's College London} |
10 \renewcommand{\slidecaption}{SEN 08, King's College London} |
36 \LARGE Security Engineering (8)\\[-3mm] |
37 \LARGE Security Engineering (8)\\[-3mm] |
37 \end{tabular}}\bigskip\bigskip\bigskip |
38 \end{tabular}}\bigskip\bigskip\bigskip |
38 |
39 |
39 \normalsize |
40 \normalsize |
40 \begin{center} |
41 \begin{center} |
41 \begin{tabular}{ll}Ch |
42 \begin{tabular}{ll} |
42 Email: & christian.urban at kcl.ac.uk\\ |
43 Email: & christian.urban at kcl.ac.uk\\ |
43 Office: & S1.27 (1st floor Strand Building)\\ |
44 Office: & S1.27 (1st floor Strand Building)\\ |
44 Slides: & KEATS (also homework is there)\\ |
45 Slides: & KEATS (also homework is there)\\ |
45 \end{tabular} |
46 \end{tabular} |
46 \end{center} |
47 \end{center} |
47 |
48 |
48 \end{frame} |
49 \end{frame} |
49 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
50 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
50 |
|
51 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
52 \begin{frame} |
|
53 \frametitle{Interlock Protocol} |
|
54 |
|
55 invented by Ron Rivest and Adi Shamir (198X?) |
|
56 |
|
57 \begin{center} |
|
58 \begin{tabular}{ll@{\hspace{2mm}}l} |
|
59 1. & $A \to B :$ & $K^{pub}_A$\smallskip\\ |
|
60 2. & $B \to A :$ & $K^{pub}_B$\smallskip\\ |
|
61 3. & & $\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$\\ |
|
62 & & $\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$\\ |
|
63 4. & $A \to B :$ & $H_1$\smallskip\\ |
|
64 5. & $B \to A :$ & $\{H_1, M_1\}_{K^{pub}_A}$\smallskip\\ |
|
65 6. & $A \to B :$ & $\{H_2, M_1\}_{K^{pub}_B}$\smallskip\\ |
|
66 7. & $B \to A :$ & $M_2$ |
|
67 \end{tabular} |
|
68 \end{center} |
|
69 |
|
70 \end{frame} |
|
71 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
72 |
|
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
74 \begin{frame} |
|
75 \frametitle{Car \& Transponder} |
|
76 |
|
77 \begin{enumerate} |
|
78 \item $C$ generates a random number $N$ |
|
79 \item $C$ calculates $\{N\}_K \mapsto F,G$ |
|
80 \item $C \to T$: $N, F$ |
|
81 \item $T$ calculates $\{N\}_K \mapsto F',G'$ |
|
82 \item $T$ checks that $F = F'$ |
|
83 \item $T \to C$: $N, G'$ |
|
84 \item $C$ checks that $G = G'$ |
|
85 \end{enumerate} |
|
86 |
|
87 Does the car authenticate the transponder? Does the |
|
88 transponder authenticate the car? |
|
89 |
|
90 \end{frame} |
|
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
92 |
|
93 |
51 |
94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
95 % student prticipation |
53 % student prticipation |
96 %\begin{frame} |
54 %\begin{frame} |
97 %\frametitle{Bitcoins} |
55 %\frametitle{Bitcoins} |
115 \item transaction history (ledger/blockchain) is P2P distributed (12 GB) |
73 \item transaction history (ledger/blockchain) is P2P distributed (12 GB) |
116 \item two ``mining pools'' produce\\ currently more than 50\% |
74 \item two ``mining pools'' produce\\ currently more than 50\% |
117 of bitcoins |
75 of bitcoins |
118 \item can be stolen and also lost |
76 \item can be stolen and also lost |
119 \item anonymous?\pause |
77 \item anonymous?\pause |
120 \item surely a ponzi scheme! |
78 \item surely a scam/ponzi scheme! |
121 \end{itemize} |
79 \end{itemize} |
122 |
80 |
123 \begin{textblock}{7}(11.5,10) |
81 \begin{textblock}{7}(11.5,10) |
124 \includegraphics[scale=0.21]{../pics/bitcoin_ledgers.png} |
82 \includegraphics[scale=0.21]{../pics/bitcoin_ledgers.png} |
125 \end{textblock} |
83 \end{textblock} |
139 \item cloud-based (passwords) |
97 \item cloud-based (passwords) |
140 \item paper-based |
98 \item paper-based |
141 \end{itemize} |
99 \end{itemize} |
142 and contains only the public-private key |
100 and contains only the public-private key |
143 |
101 |
144 \item Bitcoins can be stolen and lost |
102 \item Bitcoins can be stolen or lost |
145 \item Mt.~Gox: hacked $\Rightarrow$ insolvent |
103 \item Mt.~Gox: hacked $\Rightarrow$ insolvent |
146 \item no form of dispute resolution (against current |
104 \item no form of dispute resolution\\ (against current |
147 consumer laws) |
105 consumer laws) |
148 \end{itemize} |
106 \end{itemize} |
149 |
107 |
150 \end{frame} |
108 \end{frame} |
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
152 |
110 |
153 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
154 \begin{frame} |
112 \begin{frame}[c] |
155 \frametitle{Underlying Ideas} |
113 \frametitle{Underlying Ideas} |
156 |
114 |
157 It establishing trust in a completely |
115 It establishing trust in a completely |
158 untrusted environment\medskip |
116 untrusted environment\medskip |
159 |
117 |
170 |
128 |
171 \end{frame} |
129 \end{frame} |
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
173 |
131 |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
175 \begin{frame}[t] |
133 \begin{frame}[c] |
176 \frametitle{Lets Start with Infocoins} |
134 \frametitle{Lets Start with ``Infocoins''} |
177 |
135 |
178 \begin{center} |
136 \begin{center} |
179 \bl{$\{\text{I, Alice, am giving Bob one infocoin.}\}_{K^{priv}_{Alice}}$} |
137 \bl{$\{\text{I, Alice, am giving Bob one infocoin.}\}_{K^{priv}_{Alice}}$} |
180 \end{center}\bigskip |
138 \end{center}\bigskip |
181 |
139 |
242 The solution for double spend: |
200 The solution for double spend: |
243 |
201 |
244 \begin{itemize} |
202 \begin{itemize} |
245 \item make everybody the bank, everybody has the entire |
203 \item make everybody the bank, everybody has the entire |
246 transaction history --- will be called |
204 transaction history --- will be called |
247 \alert{blockchain}\medskip |
205 \alert{\bf blockchain}\medskip |
248 \item Bob checks whether infocoin belongs to Alice and then |
206 \item Bob checks whether the infocoin belongs to Alice and then |
249 broadcasts the message to anybody else |
207 broadcasts the message to everybody else\\[-10mm]\mbox{} |
250 \end{itemize} |
208 \end{itemize} |
251 |
209 |
252 \begin{center} |
210 \begin{center} |
253 \includegraphics[scale=0.21]{../pics/bitcoin_ledgers.png} |
211 \includegraphics[scale=0.21]{../pics/bitcoin_ledgers.png} |
254 \end{center} |
212 \end{center} |
286 |
244 |
287 \end{frame} |
245 \end{frame} |
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
289 |
247 |
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
291 \begin{frame}[t] |
249 \begin{frame}[squeeze] |
292 \frametitle{Double Spend Again} |
250 \frametitle{Double Spend Again} |
293 |
251 |
294 \begin{bubble}[10cm]\addtolength{\leftmargini}{5mm} |
252 \begin{bubble}[10cm] |
295 \begin{itemize} |
253 \begin{itemize} |
296 \item I , Alice, am giving Bob one infocoin, with serial |
254 \item I , Alice, am giving Bob one infocoin, with serial |
297 number 1234567. |
255 number 1234567. |
298 \item I, Alice, am giving \alt<2->{\alert{Alice}}{Charlie} |
256 \item I, Alice, am giving \alt<2->{\alert{Alice}}{Charlie} |
299 one infocoin with number 1234567. |
257 one infocoin with number 1234567. |
300 \end{itemize} |
258 \end{itemize} |
301 \end{bubble}\bigskip |
259 \end{bubble} |
302 |
260 |
303 How should other people update their blockchain (public |
261 How should other people update their blockchain (public |
304 register)?\pause |
262 register)?\\[-10mm]\mbox{}\pause |
305 |
263 |
306 |
264 \begin{center} |
307 \begin{center} |
265 \hspace{15mm}\includegraphics[scale=0.35]{../pics/bitcoindisagreement.png} |
308 \includegraphics[scale=0.3]{../pics/bitcoindisagreement.png} |
266 \end{center} |
309 \end{center} |
|
310 |
|
311 |
|
312 Once enough people have broadcast that message, everyone |
|
313 updates their block chain to show that infocoin 1234567 now |
|
314 belongs to Bob, and the transaction is complete. |
|
315 |
267 |
316 \end{frame} |
268 \end{frame} |
317 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
318 |
270 |
319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
322 |
274 |
323 \begin{bubble}[10cm] |
275 \begin{bubble}[10cm] |
324 Once \alert{enough} people have broadcast that message, |
276 Once \alert{enough} people have broadcast that message, |
325 everyone updates their block chain to show that infocoin |
277 everyone updates their block chain to show that infocoin |
326 1234567 now belongs to Bob, and the transaction is accepted. |
278 1234567 now belongs to Bob, and the transaction is accepted. |
327 \end{bubble}\bigskip\bigskip |
279 \end{bubble}\bigskip |
328 \pause |
280 \pause |
329 |
281 |
330 \small |
282 \small |
331 But what if Alice sets up a large number of separate |
283 But what if Alice sets up a large number of separate |
332 identities, let’s say a billion, on the Infocoin network. When |
284 identities, let’s say a billion, on the Infocoin network. When |
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
341 \begin{frame}[t] |
293 \begin{frame}[t] |
342 \frametitle{!! Proof-of-Work !!} |
294 \frametitle{!! Proof-of-Work !!} |
343 |
295 |
344 The idea is counterintuitive and involves a combination of two |
296 The idea is counterintuitive and involves a combination of two |
345 ideas:\bigskip |
297 ideas: |
346 |
298 |
347 \begin{bubble}[10cm] |
299 \begin{bubble}[10cm] |
348 \addtolength{\leftmargini}{5mm} |
|
349 \begin{itemize} |
300 \begin{itemize} |
350 |
301 |
351 \item to (artificially) make it computationally costly for |
302 \item to (artificially) make it computationally costly for |
352 network users to validate transactions, and |
303 network users to validate transactions, and |
353 |
304 |
354 \item to reward them for trying to help validate transactions |
305 \item to reward them for trying to help validate transactions |
355 \end{itemize} |
306 \end{itemize} |
356 \end{bubble}\pause\bigskip |
307 \end{bubble}\pause |
357 |
308 |
358 \small |
309 \small |
359 this is called mining: whoever validates a transaction will be awarded with |
310 this is called mining: whoever validates a transaction will be awarded with |
360 50 bitcoins --- this halves every 210,000 transactions or |
311 50 bitcoins --- this halves every 210,000 transactions or |
361 roughly every 4 years (currently 25 BC); no new bitcoins after 2140 -- then only |
312 roughly every 4 years (currently 25 BC); no new bitcoins after 2140 -- then only |
399 |
350 |
400 \begin{center} |
351 \begin{center} |
401 \includegraphics[scale=0.37]{../pics/blockchainsolving.png} |
352 \includegraphics[scale=0.37]{../pics/blockchainsolving.png} |
402 \end{center} |
353 \end{center} |
403 |
354 |
404 %\begin{textblock}{7}(7,10) |
355 \end{frame} |
405 %10 mins |
356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
406 %\end{textblock} |
357 |
407 |
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
408 \end{frame} |
359 \begin{frame}[t] |
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
360 \frametitle{Controlling the Hardness} |
|
361 |
|
362 \begin{itemize} |
|
363 \item every 210000 blocks the amount of bitcoins to be |
|
364 mined halves (``reward era'') |
|
365 \item every 2016 blocks the hardness is adjusted\\ (app 2 weeks) |
|
366 \end{itemize} |
|
367 |
|
368 \begin{center} |
|
369 \begin{tikzpicture} |
|
370 \begin{axis}[ |
|
371 xlabel={\footnotesize year}, |
|
372 ylabel={\footnotesize \% of total bitcoins}, |
|
373 ylabel style={yshift=0.0em}, |
|
374 enlargelimits=false, |
|
375 xtick={2009,2011,...,2025}, |
|
376 xmin=2009, |
|
377 xmax=2026, |
|
378 ymax=105, |
|
379 ymin=0, |
|
380 ytick={0,20,...,100}, |
|
381 scaled ticks=false, |
|
382 axis lines=left, |
|
383 width=9cm, |
|
384 height=6cm, |
|
385 legend entries={\footnotesize plan,\footnotesize in reality 2\% ahead}, |
|
386 legend pos=south east, |
|
387 legend cell align=left, |
|
388 y tick label style={font=\footnotesize}, |
|
389 x tick label style={font=\footnotesize,/pgf/number format/1000 sep={}} |
|
390 ] |
|
391 \addplot |
|
392 table {bitcoinestimate.data}; |
|
393 \only<2>{\addplot[red] |
|
394 table {bitcoinactual.data};} |
|
395 \end{axis} |
|
396 \end{tikzpicture} |
|
397 \end{center} |
|
398 |
|
399 \end{frame} |
|
400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
401 |
410 |
402 |
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
412 \begin{frame}[t] |
404 \begin{frame}[t] |
413 \frametitle{Order of Transactions} |
405 \frametitle{Order of Transactions} |
414 |
406 |
415 If we don’t have such an ordering at any given moment |
407 If we don’t have such an ordering at any given moment |
416 then it may not be clear who owns which infocoins. |
408 then it may not be clear who owns which Bitcoins. |
417 |
409 |
418 \begin{center} |
410 \begin{center} |
419 \includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png} |
411 \includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png} |
420 \end{center} |
412 \end{center} |
421 |
413 |
504 6 months chargeback) |
496 6 months chargeback) |
505 \end{frame} |
497 \end{frame} |
506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
498 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
507 |
499 |
508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
509 \begin{frame}[t] |
501 \begin{frame}[c] |
510 \frametitle{Mining Pools} |
502 \frametitle{Mining Pools} |
511 |
503 |
512 \begin{bubble}[10cm] |
504 \begin{bubble}[10cm] |
513 On average, it would take several years for a typical computer |
505 On average, it would take several years for a typical computer |
514 to solve a block, so an individual’s chance of ever solving |
506 to solve a block, so an individual’s chance of ever solving |
515 one before the rest of the network, which typically takes 10 |
507 one before the rest of the network, which typically takes 10 |
516 minutes, is negligibly low. |
508 minutes, is negligibly low. |
517 \end{bubble}\bigskip\pause |
509 \end{bubble}\pause |
518 |
510 |
519 \small |
511 \small |
520 Many people join groups called mining pools that collectively |
512 Many people join groups called mining pools that collectively |
521 work to solve blocks, and distribute rewards based on work |
513 work to solve blocks, and distribute rewards based on work |
522 contributed. These act somewhat like lottery pools among |
514 contributed. These act somewhat like lottery pools among |
523 co-workers, except that some of these pools are quite large, |
515 co-workers, except that some of these pools are quite large, |
524 and comprise more than 20\% of all the computers in the |
516 and comprise more than 20\% of all the computers in the |
525 network.\medskip |
517 network.\medskip |
526 |
518 |
527 \footnotesize |
519 \footnotesize |
528 BTC, the largest mining pool, has limited its members to |
520 BTCC, the largest mining pool, has limited its members to |
529 not solve more than 6 blocks in a row. |
521 not solve more than 6 blocks in a row. |
530 |
522 |
531 \end{frame} |
523 \end{frame} |
532 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
524 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
533 |
525 |
556 \small |
548 \small |
557 \lstinputlisting[language=Scala, |
549 \lstinputlisting[language=Scala, |
558 numbersep=3pt, |
550 numbersep=3pt, |
559 xleftmargin=-6mm]{msg} |
551 xleftmargin=-6mm]{msg} |
560 |
552 |
561 \DOWNarrow{2}{3.5}{1.6} |
553 \DOWNarrow{2}{3.5}{1.4} |
562 \LEFTarrow{3}{3.5}{3} |
554 \LEFTarrow{3}{3.5}{2.8} |
563 \LEFTarrow{4}{4.7}{4} |
555 \LEFTarrow{4}{4.7}{3.8} |
564 \LEFTarrow{4}{5.4}{4.8} |
556 \LEFTarrow{4}{5.4}{4.6} |
565 \LEFTarrow{5}{5.4}{5.6} |
557 \LEFTarrow{5}{5.4}{5.4} |
566 \LEFTarrow{6}{5}{6.4} |
558 \LEFTarrow{6}{5.0}{6.2} |
567 \DOWNarrow{7}{6}{8.2} |
559 \DOWNarrow{7}{6.0}{8.0} |
568 \LEFTarrow{8}{5}{9.7} |
560 \LEFTarrow{8}{5.0}{9.5} |
569 \DOWNarrow{9}{7}{9.7} |
561 \DOWNarrow{9}{7.0}{9.5} |
570 \DOWNarrow{9}{10}{9.7} |
562 \DOWNarrow{9}{10.0}{9.5} |
571 \LEFTarrow{10}{9}{12} |
563 \LEFTarrow{10}{9.0}{11.8} |
572 \DOWNarrow{11}{12.5}{12} |
564 \DOWNarrow{11}{12.5}{11.9} |
573 |
565 |
574 |
566 |
575 \begin{textblock}{0}(7,3)% |
567 \begin{textblock}{0}(7,3)% |
576 \small |
568 \small |
577 \onslide<2,4,7,8,9,10,11,12>{ |
569 \onslide<2,4,7,8,9,10,11,12>{ |