--- /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<presentation>{
+\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<presentation>{
+\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<presentation>{
+\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<presentation>{
+\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:
+
--- 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<presentation>{
\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<presentation>{
-\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<presentation>{
-\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<presentation>{
-\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}