\documentclass[landscape]{slides}
\usepackage{color}
%\usepackage{times}
\usepackage{epsfig}
\newif\ifpdf
\ifx\pdfoutput\undefined
   \pdffalse
\else
   \pdfoutput=1
   \pdftrue
\fi

\newenvironment{tightlist}{\begin{list}{$\bullet$}{
  \setlength{\itemsep}{0mm}
    \setlength{\parsep}{0mm}
    %  \setlength{\labelsep}{0mm}
    %  \setlength{\labelwidth}{0mm}
    %  \setlength{\topsep}{0mm}
    }}{\end{list}}

%\special{! @fedspecial end /bop-hook { .2 .2 1 setrgbcolor 0 0 moveto 792 0 rlineto 0 612 rlineto -792 0 rlineto closepath fill } bind def TeXDict begin @defspecial }
\pagecolor{blue}
\color{yellow}

\begin{document}
\ifpdf
  \pdfcompresslevel=9
  \pdfpagewidth=\the\paperwidth
  \pdfpageheight=\the\paperheight
\fi

 \newcommand\slidetitle[1]{\begin{center} \huge #1 \end{center}}

\begin{slide}
\begin{center}
\Huge
Mixminion:\\
Design of a Type III Anonymous Remailer Protocol\\
\vspace{1in}
Roger Dingledine\\
The Free Haven Project\\
\end{center}
\end{slide}


\begin{slide}
\large
\slidetitle{Threat Model (what we aim to defend against)}
\begin{itemize}
\item Global passive adversary -- can observe \emph{everything}
\item Owns half the nodes
\end{itemize}
We are not real-time, packet-based, or steganographic
\end{slide}


\begin{slide}
\large
\slidetitle{Direct Forwarder}
\vspace{1in}
\epsfbox{F1}
\vspace{0.5in}
\\But: an observer of Alice can just read M and know it's going to Bob
\end{slide}


\begin{slide}
\large
\slidetitle{Add Encryption}
\vspace{1in}
\epsfbox{F2}
\vspace{0.5in}
\\But: \textbf{1} still knows Alice sent \textbf{M} to Bob 
\end{slide}

 
\begin{slide}
\large
\slidetitle{Multiple Hops}
\vspace{0.5in}
\epsfbox{F3}
\vspace{0.5in}
\\Assume: Not all hops will collude and reveal \textbf{A}
\\But: How do you know what the servers are? 
\end{slide}

\begin{slide}
\slidetitle{Statistics servers}
\begin{center}
\begin{large}
(directory servers)
\end{large}
\end{center}
\begin{verbatim}
Mixmaster    Latent-Hist   Latent  Uptime-Hist   Uptime  Options
----------------------------------------------------------------
winter       111032010010    :42   ++++++++++++  100.0%   PR  O  
xganon       000000000000    :03   ++++++++++++  100.0%   PR   
green        00000000000?    :09   +++++++++++0   97.8%    2  O
lcs          151231221221   1:30   +++++++++7++   97.8%    M   
\end{verbatim}
\begin{itemize}
\item Have several servers to avoid single point of failure
\item They can send test messages and tell users which nodes are up
\end{itemize}
\end{slide}

\begin{slide}
\slidetitle{Direct Reply}
\begin{center}
\begin{Large}
(Trying to hide A's location)
\end{Large}
\end{center}
\epsfbox{R1}\\
``alice''=an4691@anon.penet.fi (\textbf{A} has told \textbf{1} her location.)\\
This and the direct forward gets you type 0 remailers (anon.penet.fi)\\
But: observers still know it goes to \textbf{A}.\\
And \textbf{1} knows where \textbf{A} lives.
\end{slide}

\begin{slide}
\slidetitle{Reply Blocks}
\epsfbox{R2}\\
\begin{tightlist}
\item ``alice'' $= 1, E_1(2, ...E_n(A))$
\item Hard for B to get a reply block from A.
\end{tightlist}
\end{slide}

\begin{slide}
\large
\slidetitle{Nymserver}
\epsfbox{R3}
\vspace{0.5in}
\\ \textbf{NS} knows \textbf{A}'s reply block but not her location.
\end{slide}

\begin{slide}
\slidetitle{Anonymized Reply}
\epsfbox{R4}\\
\begin{tightlist}
\item \textbf{NS} doesn't know \textbf{A} or \textbf{B} 
\item If you stop here you get type 1 (cypherpunk) remailers. 
\end{tightlist}
\end{slide}

\begin{slide}
\slidetitle{Batching and Mixing}
Encryption doesn't matter if there's only one message.\\
\epsfbox{F5}\\
But: Different-sized messages can still be distinguished.
\end{slide}

\begin{slide}
\begin{center}
\begin{Large}
Fixed length messages by re-padding
\end{Large}
\end{center}
\begin{center}
\epsfsize=200mm
\epsfbox{F6}
\end{center}
\begin{tightlist}
\item Add random junk to the bottom to replace the header you strip off
\item Everything's encrypted, so it looks ok.
\end{tightlist}
But: Replay attacks -- a given message always decrypts the same way!
\end{slide}

\begin{slide}
\large
\slidetitle{Replay cache}
\begin{itemize}
\item When a message comes in, hash it and add it to the replay cache.
\item If it's already in the cache, \underline{drop it}.
\end{itemize}
But: you have to remember all the hashes forever!
\end{slide}

\begin{slide}
\large
\slidetitle{Expiration dates}
\begin{tightlist}
\item Exp date is chosen randomly between 3 days ago and 3 days from now.
\item Each node checks exp date; if more than 7 days old, drop.
\item Now adversary can't tell when the message was sent from its exp
date; and servers can forget hashes that are $> 7$ days old.
\end{tightlist}
\end{slide}

\begin{slide}
\slidetitle{Flooding attack}
But you can flood a node so you know all but one message in the batch.\\
\epsfbox{F8b}
\end{slide}

\begin{slide}
\large
\slidetitle{Pooling}
\begin{center}
\epsfsize=100mm
\epsfbox{F9}
\end{center}
\begin{tightlist}
\item Not all messages come out at each flush. Keep a minimum number in
the pool, always.
\item Now it's harder to target an individual message.
\end{tightlist}
\end{slide}

\begin{slide}
\large
\begin{tightlist}
\item But: Trickle attack -- what if you're the only one who sends a
message into the node in a given \\interval?\\
\item More broadly,  what if you're the only one who sends a message into
the whole network, in that interval?
\end{tightlist}
\end{slide}

\begin{slide}
\large
\slidetitle{Dummy messages}
\begin{tightlist}
\item Users sometimes send decoy messages even if they have nothing to
send.
\item Hopefully there will be enough messages that the adversary will be
confused.
\item Dummies go several hops and stop (hard to decide convincing destinations).
\item If you stop here, you get type 2 (Mixmaster) \\remailers.
\end{tightlist}
\end{slide}

\begin{slide}
\large
\slidetitle{Passive subpoena attack}
\begin{itemize}
\item Eve can record messages for later subpoena \\
She can also recognize her own messages, which helps with flooding attacks
\item Fix: Link encryption with ephemeral keys \\
(rekeyed every message / few minutes)
\end{itemize}
\end{slide}

\begin{slide}
\large
\slidetitle{Active subpoena attack}
\begin{itemize}
\item Mallory can still record messages from the node she runs, and arrive later
with a subpoena.
\item Fix: Periodic key rotation
\end{itemize}
\end{slide}

\begin{slide}
\large
\slidetitle{Partition attack on client knowledge (1)}
\begin{itemize}
\item Adversary can distinguish between clients that use static node
lists and clients that frequently update from the directory servers.
\item Fix: Clients must all use the same algorithm for \\updating from
the directory servers. Directory servers must be part of the spec!
\end{itemize}
\end{slide}

\begin{slide}
\large
\slidetitle{Partition attack on client knowledge (2)}
\begin{itemize}
\item Directory servers can be out of sync; evil directory servers
can give out rigged subsets to trace clients.
\item Fix: DSs must successively sign directory bundles; a threshold of
servers is assumed good.
\end{itemize}
\end{slide}

\begin{slide}
\large
\slidetitle{Partition attack on message expiration date}
\begin{itemize}
\item Delaying a message a few days will push its exp date to one end
of the valid window -- so they won't be uniformly distributed.
\item Fix: No expiration dates. Keep all hashes until key rotates.
\end{itemize}
\end{slide}

\begin{slide}
\large
\slidetitle{Tagging attack on headers}
\begin{tightlist}
\item Mixmaster headers have a hash to integrity-check the fields for
that hop. But it doesn't check the rest of the header.
\item So we can flip some bits later in the header, and if we own the
node later in the path that corresponds to the header we just broke, we can
recognize the message.
\item We must make the hash cover the entire header.
\end{tightlist}
\end{slide}

\begin{slide}
\large
\slidetitle{Tagging attack on payload}
\begin{itemize}
\item Flip some bits in the payload, and try to recognize altered messages
when they're delivered.
\item Fix: Make the hash cover the payload too.
\end{itemize}
\end{slide}

\begin{slide}
\large
\slidetitle{We're still using Cypherpunk replies}
\begin{tightlist}
\item No replay detection, no batching, messages change length at each
hop, etc.
\item Fix: Do all this stuff for replies too.
\end{tightlist}
Since we want to \emph{encrypt} replies at each hop, use a
cryptosystem where decrypt is as strong as encrypt.
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
But you can't write a reply block without knowing the payload!
\end{Large}
\end{center}
\begin{itemize}
\item Since the author of the reply block can't guess the right hashes
for the payload, we've reintroduced the payload tagging attack.
\item Actually, that's ok. Since we're \emph{encrypting} at each hop,
only the recipient can recognize the tag.
\end{itemize}
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
But forward messages and replies must now be distinguishable
\end{Large}
\end{center}
\begin{itemize}
\item Forward messages need hashes, and replies can't have them.
\item Assuming replies are rare relative to forwards, replies are easy
to track.
\end{itemize}
\end{slide}

% here the talk shifts into a "let me describe the design" format.
% no time to go through the intuition.

\begin{slide}
\large
\begin{center}
\begin{Large}
We support three delivery types
\end{Large}
\end{center}
\begin{tightlist}
\item Forward messages, only Alice remains anonymous
\item Direct replies, only Bob remains anonymous
\item Anonymized reply messages where Alice \emph{and} Bob remain anonymous
\end{tightlist}
Parties that get anonymity must run our software.
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Messages have two headers and a payload
\end{Large}
\end{center}
Divide the path into two legs, one for each header
\begin{tightlist}
\item For forward messages, Alice chooses both legs
\item For direct replies, Alice can use the reply block directly
\item For anonymized replies, Alice chooses the first leg and uses Bob's
reply block for the second.
\end{tightlist}
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Legs are connected by the Crossover Point
\end{Large}
\end{center}
\begin{itemize}
\item One of the hops in the first header is marked as a \emph{crossover point}
\item At the crossover point, we decrypt the second header with a hash
of the payload, and then swap the headers.
\end{itemize}
\end{slide}

\begin{slide}
\large
Forward messages are anonymous:
\begin{tightlist}
\item If the second header or the payload are tagged in the first leg,
then the second header is unrecoverable.
\item If tagged in the second leg, we've already gotten anonymity from
the first.
\end{tightlist}
\end{slide}

\begin{slide}
\large
Replies are anonymous:
\begin{tightlist}
\item The adversary can never recognize his tag.
\end{tightlist}
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Multiple-message tagging attacks
\end{Large}
\end{center}
\begin{itemize}
\item If Alice sends multiple messages along the same path, Mallory
can tag some, recognize the pattern at the crossover point, and follow
the rest.
\item Only works if Mallory owns the crossover point.
\item Fix: Alice picks $k$ crossover points \\
(and hopes Mallory doesn't own most of them)
\end{itemize}
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Nymservers and single-use reply blocks
\end{Large}
\end{center}
\begin{itemize}
\item Work like imap servers
\item User anonymously sends a bunch of reply blocks to receive the mail
that's waiting for him.
\end{itemize}
\end{slide}

\begin{slide}
\Large
If you stop here, you get the current \\Mixminion remailer design.
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Open problem: reputation on the directory servers
\end{Large}
\end{center}
How do we let clients learn which nodes are good, without:\\
Letting the adversary do partitioning attacks on clients\\
Letting the adversary get more traffic by behaving well
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Open problem: trickle attack on directory servers
\end{Large}
\end{center}
\begin{itemize}
\item Malicious nodes can hold a message and release it later, when
circumstances are different.
\item More broadly, we're still in an arms race against flooding and
trickle attacks
\end{itemize}
\end{slide}

\begin{slide}
\large
\begin{center}
\begin{Large}
Open problem: long-term intersection attack
\end{Large}
\end{center}
\begin{tightlist}
\item The fact that not all users are sending messages all the
time leaks information.
\item By observing these patterns over time, we can learn more and more
confidently who is sending mail, to whom, when, etc.
\item Major unsolved problem in anonymity systems.
\end{tightlist}
\end{slide}

\begin{slide}
\Large
\begin{center}
Privacy Enhancing Technologies workshop
\end{center}
\vspace{1in}
\begin{center}
March 26-28, 2003\\
Dresden, Germany\\
http://petworkshop.org/
\end{center}
\end{slide}

\begin{slide}
\Large
\begin{center}
Play with our code
\end{center}
\vspace{1in}
\begin{center}
http://mixminion.net/
\end{center}
\end{slide}

\end{document}