# HG changeset patch # User Christian Urban # Date 1478365745 0 # Node ID f5172bb6cf45d1a9bc4a08acad294c8d92813796 # Parent 88ee5959138416b82ea07a569b0070e146e5b349 updated diff -r 88ee59591384 -r f5172bb6cf45 handouts/ho04.tex --- a/handouts/ho04.tex Fri Oct 28 01:03:10 2016 +0100 +++ b/handouts/ho04.tex Sat Nov 05 17:09:05 2016 +0000 @@ -3,7 +3,7 @@ \usepackage{../langs} \begin{document} -\fnote{\copyright{} Christian Urban, 2014, 2015} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015} \section*{Handout 4 (Access Control)} diff -r 88ee59591384 -r f5172bb6cf45 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 88ee59591384 -r f5172bb6cf45 handouts/ho05.tex --- a/handouts/ho05.tex Fri Oct 28 01:03:10 2016 +0100 +++ b/handouts/ho05.tex Sat Nov 05 17:09:05 2016 +0000 @@ -3,7 +3,7 @@ \usepackage{../langs} \begin{document} -\fnote{\copyright{} Christian Urban, 2014} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2016} %% the expectation is that anything encrypted today, will be %% decrypted in 20 years time @@ -95,7 +95,7 @@ The common characteristics of the protocols we are interested in is that an adversary or attacker is assumed to be in -complete control over the network or channel over which we +complete control of the network or channel over which we exchanging messages. An attacker can install a packet sniffer on a network, inject packets, intercept packets, modify packets, replay old messages, or fake pretty much everything @@ -573,9 +573,12 @@ organisations, VeriSign, has limited its liability to \$100 in case it issues a false certificate. This is really a joke and really the wrong incentive for the certification organisations -to clean up their mess. +to clean up their mess. The problem is compounded that +browser vendors also play a crucial role for this to +work (and they might have completely different incentives +according to which they operate). -The problem we want to study closer here is that protocols +The problem we want to study closer now is that protocols based on public-private key encryption are susceptible to simple person-in-the-middle attacks. Consider the following protocol where $A$ and $B$ attempt to exchange secret messages @@ -604,8 +607,8 @@ \noindent Since we assume an attacker, say $E$, has complete control over the network, $E$ can intercept the first two -messages and substitutes her own public key. The protocol -run would therefore be +messages and substitutes her own public key. The resulting protocol +run would be \begin{center} \begin{tabular}{ll@{\hspace{2mm}}l} @@ -803,17 +806,18 @@ \end{minipage}}}\bigskip \noindent -I hope you have thought about all these questions. Maybe you noticed that -there is a way to defeat the lockstep protocol. If an attacker could only -forward the (unmodified) messages, then all would be great. Because then -it could be used to establish secret keys using the Hellman-Diffie -technique (see further reading). That $E$ was able to decrypt all messages -is of no importance for the Hellman-Diffie -technique. +I hope you have thought about all these questions. $E$ cannot modify +the received messages---$A$ and $B$ woudl find this out. To stay +undetected, $E$ can only forward the messages (unmodified) and this is +all what $A$ and $B$ need in order to establish a shared secret. For +example they can use the Hellman-Diffie key exchange protocol (see +further reading) which works, even if $E$ can decrypt all messages. -Unfortunately, $E$ can create completely fake messages. Let -us look at this possibility: $E$ intercepts again the keys from $A$ -and $B$, and substitutes its own keys. +All good? Unfortunately, there is a way to defeat this lockstep +protocol---the name of this protocol that halves the messages. The +problem is $E$ can create completely fake messages. Let us look at +this possibility: $E$ intercepts again the keys from $A$ and $B$, and +substitutes its own keys. \begin{center} \begin{tabular}{ll@{\hspace{2mm}}l} diff -r 88ee59591384 -r f5172bb6cf45 handouts/ho06.tex --- a/handouts/ho06.tex Fri Oct 28 01:03:10 2016 +0100 +++ b/handouts/ho06.tex Sat Nov 05 17:09:05 2016 +0000 @@ -2,7 +2,7 @@ \usepackage{../style} \begin{document} -\fnote{\copyright{} Christian Urban, 2014, 2015} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015} \section*{Handout 6 (Zero-Knowledge Proofs)} diff -r 88ee59591384 -r f5172bb6cf45 handouts/ho07.tex --- a/handouts/ho07.tex Fri Oct 28 01:03:10 2016 +0100 +++ b/handouts/ho07.tex Sat Nov 05 17:09:05 2016 +0000 @@ -3,7 +3,7 @@ \usepackage{../graphics} \begin{document} -\fnote{\copyright{} Christian Urban, 2014, 2015} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015} %https://www.theguardian.com/technology/2016/oct/04/yahoo-secret-email-program-nsa-fbi %https://nakedsecurity.sophos.com/2015/11/12/california-collects-owns-and-sells-infants-dna-samples/ diff -r 88ee59591384 -r f5172bb6cf45 slides/slides06-zkp-old.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides/slides06-zkp-old.tex Sat Nov 05 17:09:05 2016 +0000 @@ -0,0 +1,505 @@ +\documentclass[dvipsnames,14pt,t]{beamer} +\usepackage{../slides} +\usepackage{../graphics} + +\setmonofont[Scale=.88]{Consolas} +\newfontfamily{\consolas}{Consolas} + +\hfuzz=220pt + +% beamer stuff +\newcommand{\bl}[1]{\textcolor{blue}{#1}} +\renewcommand{\slidecaption}{SEN 06, King's College London} + +\begin{document} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{% + \begin{tabular}{@ {}c@ {}} + \\ + \LARGE Security Engineering (6)\\[-3mm] + \end{tabular}}\bigskip\bigskip\bigskip + + \normalsize + \begin{center} + \begin{tabular}{ll} + Email: & christian.urban at kcl.ac.uk\\ + Office: & S1.27 (1st floor Strand Building)\\ + Slides: & KEATS (also homework is there)\\ + \end{tabular} + \end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Hashes for History} + +Q: What is the hash for? + +\begin{center} +\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Checking Solutions} + +How can you check somebody's solution without revealing the solution?\pause\bigskip + +Alice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't +want to tell Bob.\medskip + +You use an English dictionary: + +\begin{itemize} +\item folio \onslide<4->{$\stackrel{1}{\rightarrow}$ individual } + \onslide<5->{$\stackrel{2}{\rightarrow}$ human} + \onslide<6->{$\stackrel{3}{\rightarrow}$ or \ldots} +\only<3>{ +\begin{quote} +``an \alert{individual} leaf of paper or parchment, either loose as one of a series or +forming part of a bound volume, which is numbered on the recto or front side only.'' +\end{quote}} +\only<4>{ +\begin{quote} +``a single \alert{human} being as distinct from a group'' +\end{quote}} +\only<5>{ +\begin{quote} +``relating to \alert{or} characteristic of humankind'' +\end{quote}} +\end{itemize}\bigskip\bigskip + +\only<7->{ +this is essentially a hash function...but Bob can only check once he has also found the solution +} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Zero-Knowledge Proofs} + +Two remarkable properties of \alert{Zero-Knowledge +Proofs}:\bigskip + +\begin{itemize} + +\item Alice only reveals the fact that she knows a secret, not + the secret itself (meaning she can convince Bob that she + knows the secret, but does not give it to him).\bigskip +\item Having been convinced, Bob cannot use the evidence in + order to convince Carol that Alice knows the secret. + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Interactive Protocols} + +Q: How to cut a cake into two equal slices? + +\begin{center} +\includegraphics[scale=0.15]{../pics/cake.jpg} +\end{center}\pause\bigskip + +\small +Solves the problem of communication when both parties +distrust each other. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{The Idea} + +\begin{center} +\begin{tabular}{l@{\hspace{10mm}}r} +\\[-10mm] +\raisebox{10mm}{\large 1.} & \includegraphics[scale=0.1]{../pics/alibaba1.png}\\ +\raisebox{10mm}{\large 2.} & \includegraphics[scale=0.1]{../pics/alibaba2.png}\\ +\raisebox{10mm}{\large 3.} & \includegraphics[scale=0.1]{../pics/alibaba3.png} +\end{tabular} +\end{center} + +\begin{textblock}{7}(1,2) +The Alibaba cave protocol: +\end{textblock} + +\small +\only<2>{ +\begin{textblock}{12}(2,13.3) +Even if Bob has a hidden camera, a recording will not be +convincing to anyone else (Alice and Bob could have made it +all up). +\end{textblock}} +\only<3>{ +\begin{textblock}{12}(2,13.3) +Even worse, an observer present at the experiment would not be +convinced. +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Applications of ZKPs} + +\begin{itemize} +\item authentication, where one party wants to prove its + identity to a second party via some secret information, + but doesn't want the second party to learn anything + about this secret\bigskip +\item to enforce honest behaviour while maintaining privacy: + the idea is to force users to prove, using a + zero-knowledge proof, that their behaviour is correct + according to the protocol +\end{itemize}\bigskip + +\small +digital currencies, smart cards, id cards +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{Central Properties} + +Zero-knowledge proof protocols should satisfy:\bigskip + +\begin{itemize} +\item \alert{\bf Completeness} If Alice knows the secret, Bob + accepts Alice's ``proof'' for sure.\bigskip +\item \alert{\bf Soundness} If Alice does not know the secret, + Bob accepts her ``proof'' with a very small probability. + +\item \alert{\bf Zero-Knowledge} Even if Bob accepts + the proof by Alice, he cannot convince anybody else. + +\end{itemize} +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Graph Isomorphism} +\mbox{}\\[-20mm]\mbox{} + +\begin{center} +\begin{tabular}{@{}ccc} +\raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple.png}} & +\raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}& + +\footnotesize +\begin{tabular}{rl} +Graph A & Graph B\\ +Graph $G_1$ & Graph $G_2$\\ +a & 1\\ +b & 6\\ +c & 8\\ +d & 3\\ +g & 5\\ +h & 2\\ +i & 4\\ +j & 7\\ +\end{tabular} +\end{tabular} +\end{center} + +Finding an isomorphism between two graphs is an NP problem. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\begin{center} +\includegraphics[scale=0.8]{../pics/graphs.png} +\end{center} + +Creating a new isomorphic graph is easy; finding an +isomorphism is hard; checking an isomorphism is easy again + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\Large Graph Isomorphism Protocol} + +Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip + +\begin{enumerate} +\item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob +\item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or +\bl{$G_2$} and \bl{$H$} +\item Alice and Bob repeat this procedure \bl{$n$} times +\end{enumerate}\pause + +these are called commitment algorithms + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\Large Graph Isomorphism Protocol (2)} + +If Alice knows the isomorphism, she can always calculate +\bl{$\sigma$}.\bigskip + +If she doesn't, she can only correctly respond if Bob's choice +of index is the same as the one she used to form \bl{$H$}. The +probability of this happening is \bl{$\frac{1}{2}$}, so after +\bl{$n$} rounds the probability of her always responding +correctly is only \bl{$\frac{1}{2}^n$}. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Plot of $\frac{1}{2}^n$} + +\begin{center} +\begin{tikzpicture} +\begin{axis}[ + enlargelimits=true, + xtick={0,1,...,10}, + xmax=11, + ymax=1.1, + ytick={0,0.1,...,1.1}, + scaled ticks=false, + axis lines=left, + width=11cm, + height=7cm] +\addplot[blue,mark=*, mark options={fill=white}] + coordinates { + (0, 1) (1, 0.5) (2, 0.25) (3, 0.125) + (4, 0.0625) (5, 0.03125) (6, 0.015625) + (7, 0.0078125) (8, 0.00390625) + (9, 0.001953125) (10, 0.0009765625) + }; +\end{axis} +\end{tikzpicture} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\Large Graph Isomorphism Protocol (3)} + +Why is the GI-protocol zero-knowledge?\bigskip\pause + +A: We can generate a fake transcript of a conversation, which +cannot be distinguished from a ``real'' conversation.\bigskip + +Anything Bob can compute using the information obtained from +the transcript can be computed using only a forged transcript +and therefore participation in such a communication does not +increase Bob's capability to perform any computation. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Non-Interactive ZKPs} + +This is amazing: This can all be done ``offline'': +\bigskip + +Alice can publish some data that contains no data about her +secret, but this data can be used to convince anyone of the +secret's existence (whether Alice knows it, must be +established my other means). + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Non-Interactive ZKPs (2)} + +Alice starts with knowing an isomorphism \bl{$\sigma$} between +graphs \bl{$G_1$} and \bl{$G_2$}\medskip + +\begin{enumerate} +\item Alice generates \bl{$n$} isomorphic graphs + \bl{$H_{1..n}$} which she makes public +\item she feeds the \bl{$H_{1..n}$} into a hashing function + (she has no control over what the output will be) +\item Alice takes the first \bl{$n$} bits of the output: + whenever output is \bl{$0$}, she shows an isomorphism + with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism + with \bl{$G_2$} +\end{enumerate} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Problems of ZKPs} + +\begin{itemize} +\item ``grand chess master problem''\\ (person in the + middle again)\bigskip + +\item Alice can have multiple identities; once she committed a + fraud with one, she stops using one +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{Other Methods for ZKPs} + +Essentially every NP-problem can be used for ZKPs + +\begin{itemize} +\item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} + +\begin{center} +\bl{$A^x \equiv B\; mod\; p$} +\end{center} +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{Commitment Stage} + +\begin{enumerate} +\item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}. +\item Alice sends Bob for all \bl{$1..z$} +\begin{center} +\bl{$h_i = A^{r_i} \;mod\; p$} +\end{center} +\item Bob generates random bits \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin +\item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where + +\begin{center} +\begin{tabular}{ll} +\bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\ +\bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\ +\end{tabular} +\end{center} +where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$} + +\end{enumerate} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{Confirmation Stage} + +\begin{enumerate} +\item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol + +\begin{center} +\begin{tabular}{ll} +\bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv h_i\;mod\;p$}\\ +\bl{$b_i = 1$}: & \bl{$A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p$}\\ +\end{tabular} +\end{center}\bigskip + +Bob was sent + +\begin{center} +\bl{$r_j - r_j$}, \bl{$r_m - r_j$}, \ldots, \bl{$r_p - r_j \;mod \;p - 1$} +\end{center} + +where the corresponding bits were +\bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$} +\end{enumerate} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Proving Stage} + +\begin{enumerate} +\item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\ +she sends + +\begin{center} +\bl{$s_{z+1} = (x - r_j)$} +\end{center} + +\item Bob confirms + +\begin{center} +\bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$} +\end{center} +\end{enumerate}\bigskip\pause + +In order to cheat, Alice has to guess all bits in advance. She +has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\ + +\small\hspace{7mm} +\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Take Home Points} + +\begin{itemize} +\item this is pretty old work (in theory); seems + little used in practice (surprising)\bigskip + +\item for use in privacy, the incentives are + not yet right\bigskip + +\item most likely applied with digital cash + (Bitcoins are not yet good enough, Zerocoins) + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: + diff -r 88ee59591384 -r f5172bb6cf45 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 88ee59591384 -r f5172bb6cf45 slides/slides06.tex --- a/slides/slides06.tex Fri Oct 28 01:03:10 2016 +0100 +++ b/slides/slides06.tex Sat Nov 05 17:09:05 2016 +0000 @@ -1,6 +1,12 @@ -\documentclass[dvipsnames,14pt,t]{beamer} +\PassOptionsToPackage{bookmarks=false}{hyperref} +\documentclass[dvipsnames,14pt,t,hyperref={bookmarks=false}]{beamer} +\usepackage{../style} \usepackage{../slides} \usepackage{../graphics} +\usepackage{../langs} +\usepackage{../data} +\usetikzlibrary{arrows} +\usetikzlibrary{shapes} \setmonofont[Scale=.88]{Consolas} \newfontfamily{\consolas}{Consolas} @@ -9,7 +15,8 @@ % beamer stuff \newcommand{\bl}[1]{\textcolor{blue}{#1}} -\renewcommand{\slidecaption}{SEN 06, King's College London} +\renewcommand{\slidecaption}{SEN 05, King's College London} + \begin{document} @@ -33,71 +40,556 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Topical Slide} + +\begin{itemize} +\item DoS attack agains some US webpages (hijacked IoT devives, like + cameras,\ldots) + +\item funny cow attack (privilege escalation attack) +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Hashes for History} +\frametitle{Protocols} + +\begin{center} +\includegraphics[scale=0.11]{../pics/keyfob.jpg} +\quad +\includegraphics[scale=0.3025]{../pics/startstop.jpg} +\end{center} + +\begin{itemize} +\item Other examples: Wifi, Http-request, TCP-request, +card readers, RFID (passports)\ldots\medskip\pause -Q: What is the hash for? +\item The point is that we cannot control the network: An attacker +can install a packet sniffer, inject packets, modify packets, +replay messages\ldots{}fake pretty much everything. +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Keyless Car Transponders} \begin{center} -\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png} +\includegraphics[scale=0.1]{../pics/keyfob.jpg} +\quad +\includegraphics[scale=0.27]{../pics/startstop.jpg} \end{center} +\begin{itemize} +\item There are two security mechanisms: one remote central +locking system and one passive RFID tag (engine immobiliser). +\item How can I get in? How can thieves be kept out? +How to avoid MITM attacks? +\end{itemize}\medskip + +\footnotesize +\hfill Papers: Gone in 360 Seconds: Hijacking with Hitag2,\\ +\hfill Dismantling Megamos Crypto: Wirelessly Lockpicking\\ +\hfill a Vehicle Immobilizer + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Public-Key Infrastructure} + +\begin{itemize} +\item the idea is to have a certificate authority (CA) +\item you go to the CA to identify yourself +\item CA: ``I, the CA, have verified that public key \bl{$P^{pub}_{Bob}$} belongs to Bob''\bigskip +\item CA must be trusted by everybody +\item What happens if CA issues a false certificate? Who pays in case of loss? (VeriSign +explicitly limits liability to \$100.) +\end{itemize} + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Checking Solutions} +\begin{frame}[c] +\frametitle{Man-in-the-Middle} + +``Normal'' protocol run:\bigskip -How can you check somebody's solution without revealing the solution?\pause\bigskip +\begin{itemize} +\item \bl{$A$} sends public key to \bl{$B$} +\item \bl{$B$} sends public key to \bl{$A$} +\item \bl{$A$} sends message encrypted with \bl{$B$}'s public key, \bl{$B$} decrypts it +with its private key +\item \bl{$B$} sends message encrypted with \bl{$A$}'s public key, \bl{$A$} decrypts it +with its private key +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -Alice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't -want to tell Bob.\medskip +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Man-in-the-Middle} + +Attack: -You use an English dictionary: +\begin{itemize} +\item \bl{$A$} sends public key to \bl{$B$} --- \bl{$C$} intercepts this message and send his own public key +\item \bl{$B$} sends public key to \bl{$A$} --- \bl{$C$} intercepts this message and send his own public key +\item \bl{$A$} sends message encrypted with \bl{$C$}'s public key, \bl{$C$} decrypts it +with its private key, re-encrypts with \bl{$B$}'s public key +\item similar for other direction +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Man-in-the-Middle} + +Potential Prevention? \begin{itemize} -\item folio \onslide<4->{$\stackrel{1}{\rightarrow}$ individual } - \onslide<5->{$\stackrel{2}{\rightarrow}$ human} - \onslide<6->{$\stackrel{3}{\rightarrow}$ or \ldots} -\only<3>{ -\begin{quote} -``an \alert{individual} leaf of paper or parchment, either loose as one of a series or -forming part of a bound volume, which is numbered on the recto or front side only.'' -\end{quote}} -\only<4>{ -\begin{quote} -``a single \alert{human} being as distinct from a group'' -\end{quote}} -\only<5>{ -\begin{quote} -``relating to \alert{or} characteristic of humankind'' -\end{quote}} -\end{itemize}\bigskip\bigskip +\item \bl{$A$} sends public key to \bl{$B$} +\item \bl{$B$} sends public key to \bl{$A$} +\item \bl{$A$} encrypts message with \bl{$B$}'s public key, send's {\bf half} of the message +\item \bl{$B$} encrypts message with \bl{$A$}'s public key, send's {\bf half} of the message +\item \bl{$A$} sends other half, \bl{$B$} can now decrypt entire message +\item \bl{$B$} sends other half, \bl{$A$} can now decrypt entire message +\end{itemize}\pause + +%\bl{$C$} would have to invent a totally new message +\alert{Under which circumstances does this protocol prevent +MiM-attacks, or does it?} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Car Transponder (HiTag2)} -\only<7->{ -this is essentially a hash function...but Bob can only check once he has also found the solution -} +\begin{enumerate} +\item \bl{$C$} generates a random number \bl{$N$} +\item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$} +\item \bl{$C \to T$}: \bl{$N, F$} +\item \bl{$T$} calculates \bl{$(F',G') = \{N\}_K$} +\item \bl{$T$} checks that \bl{$F = F'$} +\item \bl{$T \to C$}: \bl{$N, G'$} +\item \bl{$C$} checks that \bl{$G = G'$} +\end{enumerate}\pause + +\small +This process means that the transponder believes the car knows +the key \bl{$K$}, and the car believes the transponder knows +the key \bl{$K$}. They have authenticated themselves +to each other, or have they? + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +A Man-in-the-middle attack in real life: + +\begin{itemize} +\item the card only says yes to the terminal if the PIN is correct +\item trick the card in thinking transaction is verified by signature +\item trick the terminal in thinking the transaction was verified by PIN +\end{itemize} + +\begin{minipage}{1.1\textwidth} +\begin{center} +\mbox{}\hspace{-6mm}\includegraphics[scale=0.5]{../pics/chip-attack.png} +\includegraphics[scale=0.3]{../pics/chipnpinflaw.png} +\end{center} +\end{minipage} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Zero-Knowledge Proofs} +\frametitle{Problems with EMV} + +\begin{itemize} +\item it is a wrapper for many protocols +\item specification by consensus (resulted unmanageable complexity) +\item its specification is 700 pages in English plus 2000+ pages for testing, additionally some +further parts are secret +\item other attacks have been found +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Protocols are Difficult} + +\begin{itemize} +\item even the systems designed by experts regularly fail\medskip +\item the one who can fix a system should also be liable for the losses\medskip +\item cryptography is often not the problem\bigskip\bigskip +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{A Simple PK Protocol} + + +\begin{center} +\begin{tabular}{ll@{\hspace{2mm}}l} +1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\smallskip\\ +2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\smallskip\\ +3. & \bl{$A \to B :$} & \bl{$\{A,m\}_{K^{pub}_B}$}\smallskip\\ +4. & \bl{$B \to A :$} & \bl{$\{B,m'\}_{K^{pub}_A}$} +\end{tabular} +\end{center}\pause\bigskip + +unfortunately there is a simple man-in-the- middle-attack +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{A MITM Attack} + + +\begin{center} +\begin{tabular}{ll@{\hspace{2mm}}l} +1. & \bl{$A \to E :$} & \bl{$K^{pub}_A$}\smallskip\\ +2. & \bl{$E \to B :$} & \bl{$K^{pub}_E$}\smallskip\\ +3. & \bl{$B \to E :$} & \bl{$K^{pub}_B$}\smallskip\\ +4. & \bl{$E \to A :$} & \bl{$K^{pub}_E$}\smallskip\\ +5. & \bl{$A \to E :$} & \bl{$\{A,m\}_{K^{pub}_E}$}\smallskip\\ +6. & \bl{$E \to B :$} & \bl{$\{E,m\}_{K^{pub}_B}$}\smallskip\\ +7. & \bl{$B \to E :$} & \bl{$\{B,m'\}_{K^{pub}_E}$}\smallskip\\ +8. & \bl{$E \to A :$} & \bl{$\{E,m'\}_{K^{pub}_A}$} +\end{tabular} +\end{center}\pause\medskip + +and \bl{$A$} and \bl{$B$} have no chance to detect it +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Interlock Protocol} + +The interlock protocol (``best bet'' against MITM): + +\begin{center} +\begin{tabular}{ll@{\hspace{2mm}}l} +1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\\ +2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\\ +3. & & \bl{$\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$}\\ + & & \bl{$\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$}\\ +4. & \bl{$A \to B :$} & \bl{$H_1$}\\ +5. & \bl{$B \to A :$} & \bl{$\{H_1, M_1\}_{K^{pub}_A}$}\\ +6. & \bl{$A \to B :$} & \bl{$\{H_2, M_1\}_{K^{pub}_B}$}\\ +7. & \bl{$B \to A :$} & \bl{$M_2$} +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Splitting Messages} + +\begin{center} +$\underbrace{\texttt{\Grid{0X1peUVTGJK+H70mMjAM8p}}}_{\bl{\{A,m\}_{K^{pub}_B}}}$ +\end{center} + +\begin{center} +$\underbrace{\texttt{\Grid{0X1peUVTGJK}}}_{\bl{H_1}}$\quad +$\underbrace{\texttt{\Grid{+H70mMjAM8p}}}_{\bl{H_2}}$ +\end{center} + +\begin{itemize} +\item you can also use the even and odd bytes +\item the point is you cannot decrypt the halves, even if you + have the key +\end{itemize} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{center} +\begin{tabular}{l@{\hspace{9mm}}l} +\begin{tabular}[t]{@{}l@{}} +\bl{$A \to C : K^{pub}_A$}\\ +\bl{$C \to B : K^{pub}_C$}\\ +\bl{$B \to C : K^{pub}_B$}\\ +\bl{$C \to A : K^{pub}_C$}\medskip\\ +\bl{$\{A,m\}_{K^{pub}_C} \;\mapsto\; H_1,H_2$}\\ +\bl{$\{B,m'\}_{K^{pub}_C} \;\mapsto\; M_1,M_2$}\bigskip\\ +\bl{$\{C,a\}_{K^{pub}_B} \;\mapsto\; C_1,C_2$}\\ +\bl{$\{C,b\}_{K^{pub}_A} \;\mapsto\; D_1,D_2$} +\end{tabular} & +\begin{tabular}[t]{@{}l@{}} +\bl{$A \to C : H_1$}\\ +\bl{$C \to B : C_1$}\\ +\bl{$B \to C : \{C_1, M_1\}_{K^{pub}_C}$}\\ +\bl{$C \to A : \{H_1, D_1\}_{K^{pub}_A}$}\\ +\bl{$A \to C : \{H_2, D_1\}_{K^{pub}_C}$}\\ +\bl{$C \to B : \{C_2, M_1\}_{K^{pub}_B}$}\\ +\bl{$B \to C : M_2$}\\ +\bl{$C \to A : D_2$} +\end{tabular} +\end{tabular} +\end{center}\pause + +\footnotesize +\bl{$m$} = How is your grandmother? \bl{$m'$} = How is the +weather today in London? + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -Two remarkable properties of \alert{Zero-Knowledge -Proofs}:\bigskip +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{itemize} +\item you have to ask something that cannot be imitated + (requires \bl{$A$} and \bl{$B$} know each other) +\item what happens if \bl{$m$} and \bl{$m'$} are voice + messages?\bigskip\pause + +\item So \bl{$C$} can either leave the communication unchanged, + or invent a complete new conversation + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{itemize} +\item the moral: establishing a secure connection from + ``zero'' is almost impossible---you need to rely on some + established trust\medskip + +\item that is why PKI relies on certificates, which however are + badly, badly realised + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Trusted Third Parties} + +Simple protocol for establishing a secure connection via a +mutually trusted 3rd party (server): + +\begin{center} +\begin{tabular}{r@ {\hspace{1mm}}l} +\bl{$A \rightarrow S :$} & \bl{$A, B$}\\ +\bl{$S \rightarrow A :$} & \bl{$\{K_{AB}, \{K_{AB}\}_{K_{BS}} \}_{K_{AS}}$}\\ +\bl{$A \rightarrow B :$} & \bl{$\{K_{AB}\}_{K_{BS}} $}\\ +\bl{$A \rightarrow B :$} & \bl{$\{m\}_{K_{AB}}$}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{PKI: The Main Idea} + +\begin{itemize} +\item the idea is to have a certificate authority (CA) +\item you go to the CA to identify yourself +\item CA: ``I, the CA, have verified that public key + \bl{$P^{pub}_{Bob}$} belongs to Bob''\bigskip +\item CA must be trusted by everybody\medskip +\item certificates are time limited, and can be revoked + +\item What happens if CA issues a false certificate? Who pays in case of loss? (VeriSign +explicitly limits liability to \$100.) +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{PKI: Chains of Trust} + +\begin{center} + \begin{tikzpicture}[scale=1, + node/.style={ + rectangle,rounded corners=3mm, + very thick,draw=black!50,minimum height=18mm, minimum width=23mm, + top color=white,bottom color=black!20}] + + \node (A) at (0,0) [node] {}; + \node [below right] at (A.north west) + {\small\begin{tabular}{@{}l}CA\\Root Cert.\end{tabular}}; + + \node (B) at (4,0) [node] {}; + \node [below right=1mm] at (B.north west) + {\mbox{}\hspace{-1mm}\small + \begin{tabular}{@{}l}Subordinate\\ CA\end{tabular}}; + + \node (C) at (8,0) [node] {}; + \node [below right] at (C.north west) + {\small\begin{tabular}{@{}l}Server\\ Bank.com\end{tabular}}; + + \draw [->,line width=4mm] (A) -- (B); + \draw [->,line width=4mm] (B) -- (C); + + \node (D) at (6,-3) [node] {}; + \node [below right] at (D.north west) + {\small\begin{tabular}{@{}l}Browser\\ Root Store\end{tabular}}; + + \node (E) at (2,-3) [node] {}; + \node [below right] at (E.north west) + {\small\begin{tabular}{@{}l}Browser\\ Vendor\end{tabular}}; + + \draw [->,line width=4mm] (E) -- (D); + \end{tikzpicture} +\end{center} + +\begin{itemize} +\item CAs make almost no money anymore, because of stiff + competition +\item browser companies are not really interested in security; + only in market share +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{PKI: Weaknesses} + +CAs just cannot win (make any profit):\medskip + +\begin{itemize} +\item there are hundreds of CAs, which issue millions of + certificates and the error rate is small + +\item users (servers) do not want to pay or pay as little as + possible\bigskip + +\item a CA can issue a certificate for any domain not needing + any permission (CAs are meant to undergo audits, + but\ldots DigiNotar) + +\item if a CA has issued many certificates, it ``becomes too + big to fail'' + +\item Can we be sure CAs are not just frontends of some + government organisation? + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{PKI: Weaknesses} \begin{itemize} -\item Alice only reveals the fact that she knows a secret, not - the secret itself (meaning she can convince Bob that she - knows the secret, but does not give it to him).\bigskip -\item Having been convinced, Bob cannot use the evidence in - order to convince Carol that Alice knows the secret. +\item many certificates are issued via Whois, whether you own + the domain\ldots if you hijacked a domain, it is easy to + obtain certificates\medskip + +\item the revocation mechanism does not work (Chrome has given + up on general revocation lists)\medskip + +\item lax approach to validation of certificates + (Have you ever bypassed certification warnings?)\medskip + +\item sometimes you want to actually install invalid + certificates (self-signed) + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{PKI: Attacks} + +\begin{itemize} + +\item Go directly after root certificates + \begin{itemize} + \item governments can demand private keys\smallskip + \item 10 years ago it was estimated that breaking a 1024 bit + key takes one year and costs 10 - 30 Mio \$; this is now + reduced to 1 Mio \$ + \end{itemize} + +\item Go after buggy implementations of certificate + validation\smallskip + +\item Social Engineering + \begin{itemize} + \item in 2001 somebody pretended to be + from Microsoft and asked for two code-signing + certificates + \end{itemize}\bigskip +\end{itemize} + +\small The eco-system is completely broken (it relies on +thousands of entities to do the right thing). Maybe DNSSEC +where keys can be attached to domain names is a way out. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Real Attacks} + +\begin{itemize} + +\item In 2011, DigiNotar (Dutch company) was the first CA that + got compromised comprehensively, and where many + fraudulent certificates were issued to the wild. It + included approximately 300,000 IP addresses, mostly + located in Iran. The attackers (in Iran?) were likely + interested ``only'' in collecting gmail passwords.\medskip + +\item The Flame malware piggy-bagged on this attack by + advertising malicious Windows updates to some targeted + systems (mostly in Iran, Israel, Sudan). \end{itemize} @@ -106,198 +598,391 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Interactive Protocols} - -Q: How to cut a cake into two equal slices? +\frametitle{PKI is Broken} -\begin{center} -\includegraphics[scale=0.15]{../pics/cake.jpg} -\end{center}\pause\bigskip +\begin{itemize} -\small -Solves the problem of communication when both parties -distrust each other. - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{The Idea} +\item PKI and certificates are meant to protect you against + MITM attacks, but if the attack occurs your are + presented with a warning and you need to decide whether + you are under attack.\medskip -\begin{center} -\begin{tabular}{l@{\hspace{10mm}}r} -\\[-10mm] -\raisebox{10mm}{\large 1.} & \includegraphics[scale=0.1]{../pics/alibaba1.png}\\ -\raisebox{10mm}{\large 2.} & \includegraphics[scale=0.1]{../pics/alibaba2.png}\\ -\raisebox{10mm}{\large 3.} & \includegraphics[scale=0.1]{../pics/alibaba3.png} -\end{tabular} -\end{center} - -\begin{textblock}{7}(1,2) -The Alibaba cave protocol: -\end{textblock} +\item Webcontent gets often loaded from 3rd-party servers, + which might not be secured\medskip + +\item Misaligned incentives: browser vendors are not + interested in breaking webpages with invalid + certificates -\small -\only<2>{ -\begin{textblock}{12}(2,13.3) -Even if Bob has a hidden camera, a recording will not be -convincing to anyone else (Alice and Bob could have made it -all up). -\end{textblock}} -\only<3>{ -\begin{textblock}{12}(2,13.3) -Even worse, an observer present at the experiment would not be -convinced. -\end{textblock}} +\end{itemize} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Applications of ZKPs} + +Why are there so many invalid certificates?\bigskip \begin{itemize} -\item authentication, where one party wants to prove its - identity to a second party via some secret information, - but doesn't want the second party to learn anything - about this secret\bigskip -\item to enforce honest behaviour while maintaining privacy: - the idea is to force users to prove, using a - zero-knowledge proof, that their behaviour is correct - according to the protocol -\end{itemize}\bigskip + +\item insufficient name coverage (www.example.com should +include example.com) + +\item IoT: many appliances have web-based admin interfaces; + the manufacturer cannot know under which IP and domain name + the appliances are run (so cannot install a valid certificate) + +\item expired certificates, or incomplete chains of trust + (servers are supposed to supply them) + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\small -digital currencies, smart cards, id cards -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - +% +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Best Practices} +% +%{\bf Principle 1:} Every message should say what it means: the +%interpretation of a message should not depend on the +%context.\bigskip\pause +% +%{\bf Principle 2:} If the identity of a principal is essential +%to the meaning of a message, it is prudent to mention the +%principal’s name explicitly in the message (though +%difficult).\bigskip +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Best Practices} +% +%{\bf Principle 3:} Be clear about why encryption is being +%done. Encryption is not wholly cheap, and not asking precisely +%why it is being done can lead to redundancy. Encryption is not +%synonymous with security. % +% +%\small +%\begin{center} +%Possible Uses of Encryption % +% +%\begin{itemize} +%\item Preservation of confidentiality: \bl{$\{X\}_K$} only those that have \bl{$K$} may recover \bl{$X$}. %\item Guarantee authenticity: The partner is indeed some particular principal. %\item Guarantee confidentiality and authenticity: binds two parts of a message --- +%\bl{$\{X,Y\}_K$} is not the same as \bl{$\{X\}_K$} and \bl{$\{Y\}_K$}. +%\end{itemize} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Best Practices} +% +%{\bf Principle 4:} The protocol designers should know which +%trust relations their protocol depends on, and why the +%dependence is necessary. The reasons for particular trust +%relations being acceptable should be explicit though they will +%be founded on judgment and policy rather than on +%logic.\bigskip +% +% %Example Certification Authorities: CAs are trusted to certify +%a key only after proper steps have been taken to identify the +%principal that owns it. +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Formal Methods} +% +%Ross Anderson about the use of Logic:\bigskip +% +%\begin{quote} +%Formal methods can be an excellent way of finding +%bugs in security protocol designs as they force the designer +%to make everything explicit and thus confront difficult design +%choices that might otherwise be fudged. +%\end{quote} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] -\frametitle{Central Properties} - -Zero-knowledge proof protocols should satisfy:\bigskip +\frametitle{Mid-Term} \begin{itemize} -\item \alert{\bf Completeness} If Alice knows the secret, Bob - accepts Alice's ``proof'' for sure.\bigskip -\item \alert{\bf Soundness} If Alice does not know the secret, - Bob accepts her ``proof'' with a very small probability. +\item homework, handouts, programs\ldots +\end{itemize}\bigskip\bigskip\bigskip + +\begin{center} +{\huge\bf\alert{Any Questions?}} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\item \alert{\bf Zero-Knowledge} Even if Bob accepts - the proof by Alice, he cannot convince anybody else. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Security Engineering} + + \begin{center} + \begin{tabular}{cc} + \raisebox{-0.8mm}{\includegraphics[scale=0.28]{../pics/flight.jpg}} & + \includegraphics[scale=0.31]{../pics/airbus.jpg}\\ + \small Wright brothers, 1901 & \small Airbus, 2005 \\ + \end{tabular} + \end{center} -\end{itemize} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Graph Isomorphism} -\mbox{}\\[-20mm]\mbox{} +\frametitle{1st Lecture} -\begin{center} -\begin{tabular}{@{}ccc} -\raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple.png}} & -\raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}& +\begin{itemize} +\item chip-and-pin, banks vs.~customers +\begin{quote}\small\rm + the one who can improve security should also be + liable for the losses +\end{quote}\pause\bigskip + +\item hashes and salts to guarantee data integrity\medskip +\item storing passwords (you should know the difference between +brute force attacks and dictionary attacks; how do salts help?) +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\footnotesize -\begin{tabular}{rl} -Graph A & Graph B\\ -Graph $G_1$ & Graph $G_2$\\ -a & 1\\ -b & 6\\ -c & 8\\ -d & 3\\ -g & 5\\ -h & 2\\ -i & 4\\ -j & 7\\ -\end{tabular} -\end{tabular} -\end{center} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{1st Lecture: Cookies} + +\begin{itemize} +\item good uses of cookies?\medskip -Finding an isomorphism between two graphs is an NP problem. +\item bad uses of cookies: snooping, tracking, profiling\ldots + the ``disadvantage'' is that the user is in + \alert{control}, because you can delete them + + \begin{center} ``Please track me using cookies.'' + \end{center}\bigskip\pause + +\item fingerprinting beyond browser cookies + \begin{quote}\small\rm + Pixel Perfect: Fingerprinting Canvas in HTML5\\ + (a research paper from 2012)\\ + \footnotesize + \url{http://cseweb.ucsd.edu/~hovav/papers/ms12.html} + \end{quote} +\end{itemize} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{1st Lecture: Cookies} + +\begin{itemize} +\item a bit of JavaScript and HTML5 + canvas\medskip +\begin{center} +\begin{tabular}{cc} +Firefox & Safari\\ +\includegraphics[scale=0.31]{../pics/firefox1.png} & +\includegraphics[scale=0.31]{../pics/safari1.png} \\ +\tiny +\pcode{55b2257ad0f20ecbf927fb66a15c61981f7ed8fc} & +\tiny +\pcode{17bc79f8111e345f572a4f87d6cd780b445625d3} +\end{tabular} +\end{center}\bigskip + +\item\small no actual drawing needed\pause +\item\small in May 2014 a crawl of 100,000 popular +webpages revealed 5.5\% already use canvas +fingerprinting\smallskip +\begin{center}\scriptsize +\url{https://securehomes.esat.kuleuven.be/~gacar/persistent/the_web_never_forgets.pdf} +\end{center} +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{1st Lecture: Cookies} + +Remember the small web-app I showed you where a cookie +protected a counter?\bigskip + +\begin{itemize} +\item NYT, the cookie looks the ``resource'' - harm\medskip +\item imaginary discount unlocked by cookie - no harm +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] +\frametitle{2nd Lecture: E-Voting} + +Where are paper ballots better than voice voting?\bigskip + +\begin{itemize} +\item Integrity +\item \alert{Ballot Secrecy} +\item Voter Authentication +\item Enfranchisement +\item Availability +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{2nd Lecture: E-Voting} + +\begin{itemize} +\item recently an Australian parliamentary committee +found: e-voting is highly vulnerable to hacking and Australia +will not use it any time soon\bigskip\pause +\item Alex Halderman, Washington D.C.~hack \begin{center} -\includegraphics[scale=0.8]{../pics/graphs.png} +\scriptsize +\url{https://jhalderm.com/pub/papers/dcvoting-fc12.pdf} +\end{center}\medskip + +\item PDF-ballot tampering at the wireless router (the modification +is nearly undetectable and leaves no traces; MITM attack with firmware +updating) +\begin{center} +\scriptsize +\url{http://galois.com/wp-content/uploads/2014/11/technical-hack-a-pdf.pdf} \end{center} -Creating a new isomorphic graph is easy; finding an -isomorphism is hard; checking an isomorphism is easy again +\end{itemize} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\Large Graph Isomorphism Protocol} +\tikzset{alt/.code args={<#1>#2#3#4}{% + \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path +}} + +\begin{frame}[t] +\frametitle{\begin{tabular}{c}3rd Lecture:\\ Buffer Overflow Attacks\end{tabular}} + +\begin{itemize} +\item the problem arises from the way C/C++ organises its function calls\\[-8mm]\mbox{} +\end{itemize} -Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip +\begin{center} +\begin{tikzpicture}[scale=1] +%\draw[black!10,step=2mm] (0,0) grid (9,4); +%\draw[black!10,thick,step=10mm] (0,0) grid (9,4); + +\node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}}; +\draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8); +\draw[line width=0mm, white, alt=<9->{fill=red}{fill=blue}] (0,0.2) rectangle (1,0.5); +\draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5); +\draw[line width=1mm, alt=<6->{fill=red}{fill=blue}] (0,1.0) rectangle (1,2.0); +\draw[line width=1mm, alt=<7->{fill=yellow}{fill=blue}] (0,0.5) rectangle (1,1.0); +\draw[line width=1mm] (0,0) -- (0,4); +\draw[line width=1mm] (1,0) -- (1,4); + +\node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}}; +\draw[line width=1mm, alt=<{4-5,8}>{fill=red}{fill=blue}] (3,1.0) rectangle (4,3.0); -\begin{enumerate} -\item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob -\item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or -\bl{$G_2$} and \bl{$H$} -\item Alice and Bob repeat this procedure \bl{$n$} times -\end{enumerate}\pause +\onslide<3-4>{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);} +\onslide<5>{\draw[<-, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {res=24} (3,1);} + +\onslide<7-8>{\draw[->, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {n=3} (3,3);} +\onslide<9>{\draw[<-, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {res=6} (3,1);} + + +\node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}}; +\draw[line width=1mm] (7,3.5) -- (7,0.5) -- (8.5,0.5) -- (8.5,3.5); -these are called commitment algorithms +\onslide<3,4,7,8>{ +\node at (7.75, 1.4) {ret}; +\draw[line width=1mm] (7,1.1) -- (8.5,1.1); +\node at (7.75, 2.0) {sp}; +\draw[line width=1mm] (7,2.3) -- (8.5,2.3); +} +\onslide<3,4>{ +\node at (7.75, 0.8) {4}; +\draw[line width=1mm] (7,1.7) -- (8.5,1.7); +} +\onslide<7,8>{ +\node at (7.75, 0.8) {3}; +\draw[line width=1mm] (7,1.7) -- (8.5,1.7); +} + + +\end{tikzpicture} +\end{center} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\Large Graph Isomorphism Protocol (2)} - -If Alice knows the isomorphism, she can always calculate -\bl{$\sigma$}.\bigskip - -If she doesn't, she can only correctly respond if Bob's choice -of index is the same as the one she used to form \bl{$H$}. The -probability of this happening is \bl{$\frac{1}{2}$}, so after -\bl{$n$} rounds the probability of her always responding -correctly is only \bl{$\frac{1}{2}^n$}. - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{Plot of $\frac{1}{2}^n$} \begin{center} -\begin{tikzpicture} -\begin{axis}[ - enlargelimits=true, - xtick={0,1,...,10}, - xmax=11, - ymax=1.1, - ytick={0,0.1,...,1.1}, - scaled ticks=false, - axis lines=left, - width=11cm, - height=7cm] -\addplot[blue,mark=*, mark options={fill=white}] - coordinates { - (0, 1) (1, 0.5) (2, 0.25) (3, 0.125) - (4, 0.0625) (5, 0.03125) (6, 0.015625) - (7, 0.0078125) (8, 0.00390625) - (9, 0.001953125) (10, 0.0009765625) - }; -\end{axis} +\begin{tikzpicture}[scale=1] +%\draw[black!10,step=2mm] (0,0) grid (9,4); +%\draw[black!10,thick,step=10mm] (0,0) grid (9,4); + +\node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}}; +\draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8); +\draw[line width=1mm, white, fill=blue] (0,1.0) rectangle (1,2.0); +\draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5); +\draw[line width=1mm] (0,0) -- (0,4); +\draw[line width=1mm] (1,0) -- (1,4); + +\node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}}; +\draw[line width=0mm, alt=<{4-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,3.0); +\draw[line width=0mm, alt=<{5-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,2.0); +\draw[line width=0mm, alt=<{7-}>{red, fill=red}{blue, fill=blue}] (3,2.0) rectangle (4,1.0); +\draw[line width=1mm] (3,1.0) rectangle (4,3.0); + +\onslide<3->{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);} +\onslide<5->{\draw[<-, line width=2mm,red] (4,2) to node [above,sloped,midway] +{\begin{tabular}{l}user\\[-1mm] input\end{tabular}} (6,2);} +\onslide<8->{\draw[<-, line width=1mm,red] (1,-2) to (3,1);} + +\node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}}; +\draw[line width=1mm] (7,3.5) -- (7,-0.1) -- (8.5,-0.1) -- (8.5,3.5); + +\onslide<3->{ +\node at (7.75, 0.2) {4}; +\draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,0.5) rectangle (8.5,1.1); +\node at (7.75, 0.8) {\alt<6->{@a\#}{ret}}; +\draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,1.1) rectangle (8.5,1.7); +\node at (7.75, 1.4) {\alt<6->{!?w;}sp}; +} + +\onslide<4->{ +\draw[line width=1mm,fill=red] (7,1.7) rectangle (8.5,3.0); +\node[white] at (7.75, 2.4) {buffer}; +} + \end{tikzpicture} \end{center} @@ -305,195 +990,125 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\Large Graph Isomorphism Protocol (3)} +\begin{frame}[t] +\frametitle{\begin{tabular}{c}3rd Lecture:\\[-3mm] +Buffer Overflow Attacks\end{tabular}} -Why is the GI-protocol zero-knowledge?\bigskip\pause +US National Vulnerability Database\\ +\small(636 out of 6675 in 2014) -A: We can generate a fake transcript of a conversation, which -cannot be distinguished from a ``real'' conversation.\bigskip +\begin{center} +\begin{tikzpicture} +\begin{axis}[ + xlabel={year}, + ylabel={\% of total attacks}, + ylabel style={yshift=0em}, + enlargelimits=false, + xtick={1997,1999,...,2015}, + xmin=1996.5, + xmax=2016, + ymax=21, + ytick={0,5,...,20}, + scaled ticks=false, + axis lines=left, + width=11cm, + height=5cm, + ybar, + nodes near coords= + {\footnotesize + $\pgfmathprintnumber[fixed,fixed zerofill,precision=1,use comma]{\pgfkeysvalueof{/data point/y}}$}, + x tick label style={font=\scriptsize,/pgf/number format/1000 sep={}}] +\addplot + table [x=Year,y=Percentage] {../handouts/bufferoverflows.data}; +\end{axis} +\end{tikzpicture} +\end{center} -Anything Bob can compute using the information obtained from -the transcript can be computed using only a forged transcript -and therefore participation in such a communication does not -increase Bob's capability to perform any computation. - +\scriptsize +\url{http://web.nvd.nist.gov/view/vuln/statistics} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Non-Interactive ZKPs} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -This is amazing: This can all be done ``offline'': -\bigskip -Alice can publish some data that contains no data about her -secret, but this data can be used to convince anyone of the -secret's existence (whether Alice knows it, must be -established my other means). - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Non-Interactive ZKPs (2)} - -Alice starts with knowing an isomorphism \bl{$\sigma$} between -graphs \bl{$G_1$} and \bl{$G_2$}\medskip - -\begin{enumerate} -\item Alice generates \bl{$n$} isomorphic graphs - \bl{$H_{1..n}$} which she makes public -\item she feeds the \bl{$H_{1..n}$} into a hashing function - (she has no control over what the output will be) -\item Alice takes the first \bl{$n$} bits of the output: - whenever output is \bl{$0$}, she shows an isomorphism - with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism - with \bl{$G_2$} -\end{enumerate} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Problems of ZKPs} +\begin{frame}[t] +\frametitle{\begin{tabular}{c}4th Lecture:\\ Unix Access Control\end{tabular}} \begin{itemize} -\item ``grand chess master problem''\\ (person in the - middle again)\bigskip +\item privileges are specified by file access permissions (``everything is a file'') +\end{itemize}\medskip -\item Alice can have multiple identities; once she committed a - fraud with one, she stops using one +\begin{center} + \begin{tikzpicture}[scale=1] + + \draw[line width=1mm] (-.3, 0) rectangle (1.5,2); + \draw (4.7,1) node {Internet}; + \draw (-2.7,1.7) node {\footnotesize Application}; + \draw (0.6,1.7) node {\footnotesize Interface}; + \draw (0.6,-0.4) node {\footnotesize \begin{tabular}{c}unprivileged\\[-1mm] process\end{tabular}}; + \draw (-2.7,-0.4) node {\footnotesize \begin{tabular}{c}privileged\\[-1mm] process\end{tabular}}; + + \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); + + \draw[white] (1.7,1) node (X) {}; + \draw[white] (3.7,1) node (Y) {}; + \draw[red, <->, line width = 2mm] (X) -- (Y); + + \draw[red, <->, line width = 1mm] (-0.6,1) -- (-1.6,1); + \end{tikzpicture} +\end{center} + +\begin{itemize} +\item the idea is to make the attack surface smaller and +mitigate the consequences of an attack \end{itemize} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Other Methods for ZKPs} - -Essentially every NP-problem can be used for ZKPs - -\begin{itemize} -\item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} - -\begin{center} -\bl{$A^x \equiv B\; mod\; p$} -\end{center} -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Commitment Stage} - -\begin{enumerate} -\item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}. -\item Alice sends Bob for all \bl{$1..z$} -\begin{center} -\bl{$h_i = A^{r_i} \;mod\; p$} -\end{center} -\item Bob generates random bits \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin -\item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where - -\begin{center} -\begin{tabular}{ll} -\bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\ -\bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\ -\end{tabular} -\end{center} -where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$} - -\end{enumerate} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Confirmation Stage} +\begin{frame}[fragile,t] +\frametitle{\begin{tabular}{c}4th Lecture:\\ Unix Access Control\end{tabular}} -\begin{enumerate} -\item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol +\begin{itemize} +\item when a file with setuid is executed, the resulting process will assume the +UID given to the owner of the file +\end{itemize} +\footnotesize\tt \begin{center} -\begin{tabular}{ll} -\bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv h_i\;mod\;p$}\\ -\bl{$b_i = 1$}: & \bl{$A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p$}\\ -\end{tabular} -\end{center}\bigskip - -Bob was sent - -\begin{center} -\bl{$r_j - r_j$}, \bl{$r_m - r_j$}, \ldots, \bl{$r_p - r_j \;mod \;p - 1$} +\begin{verbatim} +$ ls -ld . * */* +drwxr-xr-x 1 ping staff 32768 Apr 2 2010 . +-rw----r-- 1 ping students 31359 Jul 24 2011 manual.txt +-r--rw--w- 1 bob students 4359 Jul 24 2011 report.txt +-rwsr--r-x 1 bob students 141359 Jun 1 2013 microedit +dr--r-xr-x 1 bob staff 32768 Jul 23 2011 src +-rw-r--r-- 1 bob staff 81359 Feb 28 2012 src/code.c +-r--rw---- 1 emma students 959 Jan 23 2012 src/code.h +\end{verbatim} \end{center} -where the corresponding bits were -\bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$} -\end{enumerate} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Proving Stage} - -\begin{enumerate} -\item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\ -she sends - -\begin{center} -\bl{$s_{z+1} = (x - r_j)$} -\end{center} +\begin{frame}[t] +\frametitle{\begin{tabular}{c}4th Lecture:\\ Unix Access Control\end{tabular}} -\item Bob confirms +\begin{itemize} +\item Alice wants to have her files readable, +\alert{except} for her office mates.\bigskip -\begin{center} -\bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$} -\end{center} -\end{enumerate}\bigskip\pause +\item make sure you understand the setuid and setgid bits; + why are they necessary for login and passwd +\end{itemize} -In order to cheat, Alice has to guess all bits in advance. She -has only \bl{$\frac{1}{2}^z$} chance of doing so.\bigskip\\ - -\small\hspace{7mm} -\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Take Home Points} - -\begin{itemize} -\item this is pretty old work (in theory); seems - little used in practice (surprising)\bigskip - -\item for use in privacy, the incentives are - not yet right\bigskip - -\item most likely applied with digital cash - (Bitcoins are not yet good enough, Zerocoins) - -\end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}