[freehaven-cvs] overhaul the intro, plus a bit of related work

[arma@seul.org (Roger Dingledine)]

Update of /home2/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv31071

Modified Files:
	e2e-traffic.tex e2e-traffic.bib 
Log Message:
overhaul the intro, plus a bit of related work


Index: e2e-traffic.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- e2e-traffic.tex	24 Jan 2004 03:45:07 -0000	1.21
+++ e2e-traffic.tex	24 Jan 2004 06:45:29 -0000	1.22
@@ -59,92 +59,59 @@
 %======================================================================
 \section{Introduction}
 \label{sec:intro}
-%Since the introduction of mix-nets \cite{chaum-mix} in 1981, many
-%attacks against these anonymity systems have been proposed.
-%While some of these attacks have been
-%addressed by improved mix-net designs,
 Mix networks aim to allow senders to anonymously deliver messages to
 recipients. One of the strongest attacks against current deployable
-mix network designs is the \emph{long-term intersection attack}. In this
-attack, a passive eavesdropper observes a large volume of network traffic
-and notices over time that certain recipients are more likely to
-receive messages after given senders have transmitted messages.  Although
-these correlations are slight, given enough time an attacker can
-deduce which senders are communicating with which recipients.
-Previously, researchers have believed that long-term intersection attacks
-can only be stopped by an impractically large amount of cover traffic
-(e.g.,
-senders send dummy messages to every possible recipient whenever they
-want to send a real message to anyone) or a set of senders
-with perfect uptimes who send messages continually (so that the attacker can
-never learn how the network behaves in the absence of particular senders).
-%
-% Either of these is sufficient:
-% Suppose that Alice sends a  message to every possible recipient
-% (n^2 padding) every time she sends any messages at all.  Even if
-% Alice is rarely online, all we can learn about her behavior is that
-% when she comes online, she sends a message to everybody.
-%     Conversely, suppose Alice is online sending all the time, has been
-% sending since the system went online, and will send a message every
-% day till the end of time.  In this case, even if Alice doesn't pad, the
-% attacker can't learn what the network looks like when she isn't
-% sending, and so can't deduce her contribution.  -NM
-%
-% This is subtle, but I'm not sure I buy the second part of this as much
-% as the first. In the first case, it's obvious to me that if Alice wants
-% her anonymity, she broadcasts and that's that. But in the second case,
-% if Alice is the only sender, it seems she cannot get anonymity on her
-% own. If Alice is the only sender who behaves this way, then perhaps
-% she doesn't get much help from the other senders. And thirdly, this
-% wouldn't be a categorical defense unless *all* senders, not just 'a
-% set of senders', behaved this way; the ones who didn't wouldn't be
-% protected. -RD
-%
-Here we present several variations on a version of the long-term
-intersection attack, and examine their simulated performance.  Preliminary
-results indicate that these attacks can be resisted with significantly less
-overhead than previously supposed.
+mix network designs is the \emph{long-term intersection attack}. In
+this attack, a passive eavesdropper observes a large volume of network
+traffic and notices that certain recipients are more likely to receive
+messages after given senders have transmitted messages.
+% Although these correlations are slight,
+That is, if a sender (call her Alice) maintains a fairly consistent
+behavior pattern over time, the attacker can deduce Alice's recipients.
 
-Kesdogan, Agrawal, and Penz propose an example of a long-term
-intersection attack in \cite{limits-open}, and expand on this attack in
-\cite{agrawal03}. Their {\it disclosure attack}
-assumes a fairly strict model of sender behavior and works against
-only a single batch mix.  (A batch mix waits until it receives $b$
-messages, then reorders and retransmits them all.)  Additionally, the
-disclosure attack requires an attacker to solve an NP-complete
-problem to reveal the connections between senders and recipients.
+Researchers have theorized that these attacks should be extremely
+effective in many real-world contexts, but so far it has been difficult
+to reason about when they would be successful and how long the attacks
+would take.
 
-Danezis presents an algorithmically simpler {\it statistical
-disclosure attack} \cite{statistical-disclosure} that requires far
-less computation.  But while this attack
-is easier to describe and implement, it assumes the same
-restrictive sender and network models as the original disclosure
-attack.
+%% Put this stuff in the previous work section if you want.
+%Kesdogan, Agrawal, and Penz propose an example of a long-term
+%intersection attack in \cite{limits-open}, and expand on this attack in
+%\cite{agrawal03}. Their {\it disclosure attack}
+%assumes a fairly strict model of sender behavior and works against
+%only a single batch mix.  (A batch mix waits until it receives $b$
+%messages, then reorders and retransmits them all.)  Additionally, the
+%disclosure attack requires an attacker to solve an NP-complete
+%problem to reveal the connections between senders and recipients.
+%
+%Danezis presents an algorithmically simpler {\it statistical
+%disclosure attack} \cite{statistical-disclosure} that requires far
+%less computation.  But while this attack
+%is easier to describe and implement, it assumes the same
+%restrictive sender and network models as the original disclosure
+%attack.
+
+Here we extend a version of the long-term intersection attack called the
+statistical disclosure attack \cite{statistical-disclosure} to work in
+real-world circumstances. Specifically, whereas the original model for
+this attack makes strong assumptions about sender behavior and works
+against only a single batch mix, we show how an attacker can learn
+Alice's regular recipients even when:
 
-In this paper, we extend Danezis's statistical disclosure attack to
-work in more real-world circumstances.  Specifically, if a given mix-net
-sender (call her Alice) maintains a fairly consistent behavior
-pattern over time, we show how an attacker can learn Alice's regular
-recipients, even when we relax the original disclosure attack's model
-in the following ways:
 \begin{tightlist}
 \item Alice chooses non-uniformly among her communication partners,
   and can send multiple messages in a single batch.
 \item The attacker lacks {\it a priori} knowledge of the network's
   average behavior when Alice is not sending messages.
 \item Mixes use a different batching algorithm, such as Mixmaster's
-  dynamic-pool
-  algorithm \cite{trickle02,mixmaster-spec} or its
+  dynamic-pool algorithm \cite{trickle02,mixmaster-spec} or its
   generalization \cite{pet2003-diaz}.
-%  (Rather than
-%  the ``batch'' mix behavior of relaying all messages when $b$
-%  messages have arrived, these algorithms hold messages in a ``pool'' for
-%  a random number of rounds based on the number of messages in the pool.)
 \item Alice uses a mix network (of any topology, with synchronous or
   asynchronous batching) to relay her messages through a succession of
   mixes, instead of using just a single mix.
-\item Alice disguises when she is sending real messages by sending some
-  traffic padding to be dropped by some mix node in the network.
+\item Alice disguises when she is sending real messages by sending
+  traffic padding to % be dropped by 
+  some mix node in the network.
 \item The attacker can only view a subset of the messages entering and
   leaving the network, so long as this subset includes some messages
   from Alice and some messages to Alice's recipients.
@@ -152,22 +119,18 @@
   slowly over time.  (We do not address this case completely).
 \end{tightlist}
 Each of these deviations from the original
-%%statistical disclosure attack
 model reduces the rate at which the attacker learns Alice's recipients, and
 increases the amount of traffic the attacker must observe.
 
-Additionally, we show how an attacker can exploit additional knowledge to
-speed up these attacks.  Such knowledge includes:
-\begin{tightlist}
-\item Linkability between messages. For example, the attacker can take into
-  account
-  whether messages are written in the same language or signed by the
-  same pseudonym.
-\item {\it A priori} suspicion of certain messages having originated
-  or not originated from Alice.  For example, messages written in a
-  language Alice doesn't speak are unlikely to have been written
-  by Alice.
-\end{tightlist}
+Additionally, we show how an attacker can exploit additional knowledge,
+such as linkability between messages, to speed up these attacks.
+Linkability between messages. For example, the attacker can take into
+account whether messages are written in the same language or signed by
+the same pseudonym.
+%\item {\it A priori} suspicion of certain messages having originated
+%  or not originated from Alice.  For example, messages written in a
+%  language Alice doesn't speak are unlikely to have been written
+%  by Alice.
 
 The attacks in this paper fail to work when:
 \begin{tightlist}
@@ -215,6 +178,8 @@
 Many subsequent designs have been proposed, including Babel \cite{babel},
 Mixmaster \cite{mixmaster-spec}, and Mixminion \cite{minion-design}.
 %  also \cite{shuffle} and \cite{abe}
+%  No, we shouldn't mention either of these. The long-term intersection
+%  attack is not part of their threat model. -RD
 We will not address the differences between these systems in any detail: from
 the point of view of a long-term intersection attack, the internals of the
 network are irrelevant so long as the attacker can observe messages entering
@@ -226,8 +191,8 @@
 %%learning when participannts are sending and receiving.)
 
 Another class of anonymity designs is aimed at web browsing and other
-low latency activities \cite{web-mix:pet2000,tor-design,or-jsac98},
-but we neglect them in this paper because short-term timing and packet
+low latency activities \cite{web-mix:pet2000,freedom2-arch,tor-design,or-jsac98},
+but we do not address them in this paper because short-term timing and packet
 counting attacks seem sufficient against them \cite{SS03}.
 
 Attacks against mix networks aim to reduce the anonymity of users by

Index: e2e-traffic.bib
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.bib,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- e2e-traffic.bib	22 Jan 2004 04:34:46 -0000	1.6
+++ e2e-traffic.bib	24 Jan 2004 06:45:29 -0000	1.7
@@ -1,3 +1,14 @@
+
+@techreport{freedom2-arch,
+  title = {Freedom Systems 2.0 Architecture}, 
+  author = {Philippe Boucher and Adam Shostack and Ian Goldberg}, 
+  institution = {Zero Knowledge Systems, {Inc.}}, 
+  year = {2000}, 
+  month = {December}, 
+  type = {White Paper}, 
+  day = {18}, 
+}
+
 @inproceedings{SS03,
   title = {Passive Attack Analysis for Connection-Based Anonymity Systems},
   author = {Andrei Serjantov and Peter Sewell},

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/