[freehaven-cvs] clean up section 1

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/e2e-traffic

Modified Files:
	e2e-traffic.tex 
Log Message:
clean up section 1
add some early paragraphs to section 2


Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- e2e-traffic.tex	2 Dec 2003 20:14:48 -0000	1.5
+++ e2e-traffic.tex	11 Dec 2003 05:22:15 -0000	1.6
@@ -38,31 +38,33 @@
 senders had known behavior patterns, this paper describes how an analogous
 attack can reveal sender-receiver connections, even when the eavesdropper is
 non-global, the sender behavior is unknown, the substrate is a network of
-timed dynamic-poll mixes, and senders use padding messages.  Each weakening
+timed dynamic-pool mixes, and senders use padding messages.  Each weakening
 of earlier assumptions increases the time over which the attacker must
 observe the mix-net, but has little effect on the attacker's storage or
 computational requirements.  Additionally, we describe how such an attacker
 can exploit extra information about message linkability in order to reduce
 the number of rounds required to link senders to recipients.  We present
-simulated results for each of our atttacks, focusing on the amount of
-information needed to link senders and recipientes.  Finally, we discuss
-few mechanisms for partially resisting these attacks.
+simulated results for each of our attacks, focusing on the amount of
+information needed to link senders and recipients.  Finally, we discuss
+some mechanisms for partially resisting these attacks.
 \end{abstract}
 
 %======================================================================
 \section{Introduction}
 \label{sec:intro}
 Since the introduction of mix-nets \cite{chaum-mix} in 1981, many
-attacks against such anonymity systems have been proposed and
-discussed.  While some of these attacks have been partially addressed
-by advancements in mix-net designs \cite{???}, broad classes of
-attacks remain effective against current mix-net designs.
-
-One such class of attacks are {\it long-term intersection attacks}
-wherein a passive eavesdropper observes a large volume of network traffic,
+attacks against these anonymity systems have been proposed and discussed.
+%\cite{back01,langos02,disad-free-routes,desmedt,mitkuro,raymond00,trickle02}
+While some of these attacks have been partially
+addressed by improved mix-net designs,
+%\cite{abe,babel,flash-mix,kesdogan,pfitzmann85,shuffle,hybrid-mix,mixmaster-spec,minion-design}
+% let's leave the cites until section 2 -RD
+one class of attack that remains effective against current deployable
+mix-net 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 transmitting messages.  Although
-these correlations tend to be slight, given enough time, an attacker can
+receive messages after given senders have transmitted messages.  Although
+these correlations tend to be slight, given enough time an attacker can
 use them to deduce which senders are communicating with which recipients.
 Categorical defenses against long-term intersection attacks tend to require
 either an impractically large amount of cover traffic (by requiring senders
@@ -70,11 +72,9 @@
 a single 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).
-% i would argue they require both? if you do great cover traffic but
-% aren't online much, you lose; and if you're online but not sending
-% much, you also lose.   -RD
 %
-% No.  Suppose that Alice sends a  message to every possible recipient
+% 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.
@@ -83,52 +83,66 @@
 % 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
 
-An example of a long-term intersection attack is proposed by Agrawal,
-Kesdogan, and Penz \cite{limits-open}.  Their {\it disclosure attack}
+Agrawal, Kesdogan, and Penz propose an example of a long-term intersection
+attack in \cite{limits-open}. 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 a complex NP-complete
-problem in order to reveal the connections between senders and
-recipients.
+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 on the behalf of the attacker.  This attack
-is easier to describe and implement, but it assumes the same
+less computation on the part of the attacker.  But while this attack
+is easier to describe and implement, it assumes the same
 restrictive sender and network models as the original disclosure
 attack.
 
-In this paper, we extend Danezis's original statistical disclosure attack to
+In this paper, we extend Danezis's statistical disclosure attack to
 work in more real-world circumstances.  Specifically, if a given mix-net
-sender (hereinafter called ``Alice'') maintains a fairly consistant behavior
+sender (call her Alice) maintains a fairly consistent behavior
 pattern over time, we show how an attacker can learn Alice's regular
-recipients, even in the presence of one or more of these deviations from the
-origigal disclosure attack's model:
+recipients, even when we relax the original disclosure attack's model
+in the following ways:
+%in the presence of one or more of these deviations from the
+%original disclosure attack's model:
 \begin{tightlist}
-\item Alice chooses non-uniformly among her communication partners, and sends
-  multiple messages per single batch.
+\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 the timed dynamic-pool
   algorithm \cite{trickle02} used by Mixmaster \cite{mixmaster-spec}, or the
-  generalized mix algorithm proposed by \cite{pet2003-diaz}.  (With these
-  algorithms, mixes do not relay all of the messages they hold whenever they
-  receive a batch of $b$, but instead hold messages in a ``pool'' for a
-  randomized number of rounds, based on the number of messages in the pool.)
-\item Alice uses a mix network (of any topology) relaying her messages through
-  a succession of mixes, instead of using just a single mix.
-\item Alice sends some intra-network traffic padding delivered to no particular
-  recipient, in order to disguise when she is sending real messages.
+  generalized mix algorithm proposed by \cite{pet2003-diaz}.  (Rather than
+  the normal ``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 sends some intra-network traffic padding delivered to no
+  particular recipient, to disguise when she is sending real messages.
+% XXX is 'delivered to no particular recipient' the same as 'delivered
+%     to some mix node in the network'? -RD
 \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.
 \item The cover traffic generated by other senders changes
   slowly over time.  (We do not address this case completely).
 \end{tightlist}
-Each of these variations from the original statistical disclosure attack's
-model increases the amount of traffic the attacker must observe in order to
+Each of these variations from the original statistical disclosure attack
+model increases the amount of traffic the attacker must observe to
 learn Alice's regular recipients.
 
 Additionally, we show how an attacker can exploit additional knowledge to
@@ -152,16 +166,18 @@
 \item Alice's behavior is not consistent over time.  If Alice does not
   produce enough traffic with the same group of regular recipients,
   the attacker cannot learn Alice's behavior.
+  We will quantify what `enough' means below.
+    % if it's true that we will, we should probably shout it louder
+    % in the abstract. guess we'll wait to see if we do. -RD
 \item The attacker cannot observe how the network behaves when Alice isn't
   sending messages. If Alice always sends the same number of messages, in
   every round, forever, the attacker may not be able to learn who receives
   messages in Alice's absence.
-  % Also, is it right to call this ``steady state'' behavior?  It's
-  % really `The network's behavior when Alice isn't around'.
 \item The attacker cannot tell when the sender is originating
   messages.
-  % This may be the case if the sender is running her own mix
-  %node and injecting messages into it directly.
+  % For example, the sender may be running her own mix
+  % node and injecting messages into it directly.
+  %% why leave this out? it sounds important. -RD
 \end{tightlist}
 
 We begin in section \ref{sec:previous-work} by presenting a brief
@@ -179,13 +195,82 @@
 
 \subsection{Mix-nets}
 \label{subsec:mix-nets}
-[Write something here to tell people what mix-nets are; maybe take the
-first draft from the Minion paper.]
+
+Chaum introduced the concept of using relay servers, or \emph{mixes},
+for anonymous communications \cite{chaum-mix}. Each mix has a public key
+which senders use to encrypt messages to it. The mix accumulates a batch
+of these encrypted messages, decrypts them, and delivers them. Because a
+decrypted output message looks nothing like the original encrypted input
+message, and because the mix collects a batch of messages and then sends
+out the decrypted messages in a rearranged order, an observer cannot learn
+which incoming message corresponds to which outgoing message. Chaum showed
+the security of a mix against a \emph{passive adversary} who eavesdrops
+on all communications but is unable to observe the reordering inside the
+mix. Pfitzmann fixed a weakness in Chaum's original scheme based on the
+properties of raw RSA encryption \cite{pfitzmann90how}.
+
+However, trusting a single mix is dangerous: the mix itself could
+be controlled by an adversary. Therefore users send their messages
+through a series of mixes: if some of the mixes are honest (not
+run by the adversary), anonymity may be preserved. In schemes like
+Babel \cite{babel}, Mixmaster \cite{mixmaster-spec}, or Mixminion
+\cite{minion-design}, the sender chooses the mixes that make up her
+message's path. When Alice wants to send an anonymous message to
+Bob through mixes $M_1$, $M_2$, and $M_3$, she encrypts her message
+successively with the public keys of the mixes in reverse order. She
+includes routing information at each hop, so that each mix $M_i$ receives
+the address of $M_{i+1}$ along with the message intended for $M_{i+1}$
+(all encrypted under $M_i$'s public key).
+
+A mix network where Alice chooses her route freely from all mixes is
+called a \emph{free-route} network. Another approach is a \emph{cascade}
+network, where senders choose from a set of fixed paths through the
+mix-net. Cascades can provide greater anonymity against an adversary
+who owns many mixes \cite{disad-free-routes}, but they are also more
+vulnerable to blending attacks such as trickle or flooding attacks
+\cite{trickle02}. Further, cascade networks arguably have lower
+maximum anonymity because the number of people Alice can hide among
+(her \emph{anonymity set}) is limited to the number of messages the
+weakest node in her cascade can handle. In a free-route network, larger
+anonymity sets are possible because no single mix acts as a bottleneck:
+many mixes handle traffic in parallel as messages traverse the network.
+Mix cascade research includes real-time mixes \cite{realtime-mix} and
+web mixes \cite{web-mix}.
+
+More complex designs use zero-knowledge proofs and stronger
+assumptions to guarantee delivery or to detect and exclude misbehaving
+participants.  These include flash mixes \cite{flash-mix}, hybrid
+mixes \cite{jakobsson-optimally,hybrid-mix}, and provable shuffles
+\cite{PShuffle,shuffle}. The properties of these designs are appealing,
+but they are often impractical since they assume fairly strong
+coordination and synchronization between the mixes and impose a heavy
+computational and communication overhead.
 
 \subsection{Traffic analysis}
 \label{subsec:traffic-analysis}
-[Write an overview of the general history of traffic analysis attacks.
-Remember to check out disad-freeroutes and langos02.]
+% an overview of the general history of traffic analysis attacks.
+
+Attacks against mix-nets aim to reduce the anonymity of users by
+linking anonymous senders with the messages they send, by linking
+anonymous recipients with the messages they receive, or by linking
+anonymous messages with one another \cite{raymond00}.  Attackers may
+trace messages through the network by observing network
+traffic, compromising mixes, compromising keys, delaying messages
+so they stand out from other traffic, or altering messages
+in transit.  They may learn a given message's destination
+by flooding the network with messages, replaying multiple copies
+of a message, or shaping traffic to isolate the target message from
+other unknown traffic. Attackers may discourage users from
+using honest mixes by making them unreliable. They may analyze
+intercepted message text to look for commonalities between otherwise
+unlinked senders.
+Finally, even if all other attacks are foiled, a passive adversary can
+mount a long-term \emph{intersection attack} to correlate the times at
+which senders and receivers are active \cite{disad-free-routes}.
+% Mention that no defense short of N^2 padding is known, and that N^2
+% padding doesn't work?
+
+Remember to check out disad-freeroutes and langos02.
 
 \subsection{The disclosure attack}
 \label{subsec:disclosure-attack}
@@ -413,7 +498,7 @@
 In the first case, the change is trivial: Alice's behavior vector
 $\vec{v}$ no longer adds to $1$, since there is now a probability that
 a message from Alice will not reach any recipient.  Aside from this, the
-attack can procede before, so long as Alice sends more messages (including
+attack can proceed as before, so long as Alice sends more messages (including
 dummies) in some rounds than in others.
 
 \XXXX{Is the rest of this section even vaguely germane or realistic?}

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