[freehaven-cvs] tweaks and fixes

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/batching-taxonomy
In directory moria.seul.org:/home/arma/work/freehaven/doc/batching-taxonomy

Modified Files:
	taxonomy.tex 
Log Message:
tweaks and fixes

anonymized the first page



Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- taxonomy.tex	7 May 2002 01:16:37 -0000	1.2
+++ taxonomy.tex	7 May 2002 05:56:06 -0000	1.3
@@ -16,17 +16,18 @@
 %\title{Increasing the Cost of Active Attacks}
 \title{From a Trickle to a Flood: Active Attacks on Several Mix Types}
 
-
-\author{Andrei Serjantov\inst{1} and Roger Dingledine\inst{2} \and Paul Syverson\inst{3}}
-\institute{
-Cambridge University
-\email{(serjantov@cl.cam.ac.uk)}
-\and
-The Free Haven Project
-\email{(arma@mit.edu)}
-\and
-Naval Research Laboratory
-\email{(syverson@itd.nrl.navy.mil)}}
+%\author{Andrei Serjantov\inst{1} and Roger Dingledine\inst{2} \and Paul Syverson\inst{3}}
+%\institute{
+%Cambridge University
+%\email{(serjantov@cl.cam.ac.uk)}
+%\and
+%The Free Haven Project
+%\email{(arma@mit.edu)}
+%\and
+%Naval Research Laboratory
+%\email{(syverson@itd.nrl.navy.mil)}}
+\author{...}
+\institute{}
 
 \maketitle
 
@@ -42,21 +43,21 @@
 attack. We discuss advantages and disadvantages of these mixes and the
 settings in which their use is appropriate.  Finally, we look at dummy
 traffic and SG mixes as other promising ways of protecting against the
-attacks, point out potential weaknesses in existing design and suggest
+attacks, point out potential weaknesses in existing design, and suggest
 improvements.
 \end{abstract}
 
 % This paper was motivated by conversations with the Mixmaster
 % team (Len Sassaman + Bram Cohen), Lance Cottrell and Paul Syverson.
 
-\section{TODO}
-Ensure consistent use of flush/fire
+%\section{TODO}
+%Ensure consistent use of flush/fire
 
-Ensure blending attack is used throughout.
+%Ensure blending attack is used throughout.
 
-Ensure we use ``remain in the mix for an arbitrarily long time''
+%Ensure we use ``remain in the mix for an arbitrarily long time''
 
-Make ``good'' messages consistent
+%Make ``good'' messages consistent
 
 \section{Introduction}
 
@@ -80,7 +81,7 @@
 \cite{Cott94,Babel}.  This manipulation may involve delaying or
 dropping all other incoming messages (a \emph{trickle} attack),
 flooding the batch with its own known messages (a \emph{flooding}
-attack), some combination of the two which we call the blending attack.
+attack), or some combination of the two which we call the blending attack.
 
 %Chaff and winnow to be inserted here or elsewhere in the text?
 
@@ -112,12 +113,12 @@
 Here we consider a global \emph{active} adversary who is not only able
 to see the traffic on all the links, but also to delay (remove) and
 insert arbitrarily many messages into the system in a short (constant)
-time. This is not at all unreasonable as methods of logging per-packet
+time. These are reasonable assumptions --- methods of logging per-packet
 data on high bandwidth links exist, as does the possibility of
-building fast hardware to insert or delay messages.
-\footnote{We assume our attacker can send messages from many different
+building fast hardware to insert or delay messages. We further
+assume our attacker can send messages from many different
 source addresses; indeed, infrastructures to ensure sender authentication
-have proved difficult to build.}
+have proved difficult to build.
 
 Note that the global active attacker can be viewed as a combination of
 two separate attackers: one who can only insert messages (global
@@ -141,7 +142,7 @@
 particular message originating from a sender.  We illustrate this in
 the case of a single threshold mix\footnote{The same attack can be
 used against a mix cascade by mounting it against the first mix,
-against a mix network by repeating it $l$ (the number of mixes in the
+or against a mix network by repeating it $l$ (the number of mixes in the
 route of the message) times.}.  The attack, commonly referred to as
 the $n-1$ attack, proceeds as follows: The attacker observes the
 target message leaving the sender heading towards the mix and delays
@@ -158,7 +159,7 @@
 First of all, we note that the attack is \emph{exact} --- that is, it
 provides the adversary with the ability to determine the receiver of a
 particular message with certainty $1$ (the anonymity of a message
-passing through the mix is $0$)\footnote{In this case, one can use
+passing through the mix is $0$)\footnote{In this case, we can use
 either the information theoretic definition of \cite{Serj02} or the
 usual anonymity set definition.}. We also note that this attack does
 not depend on the rest of the mix network; that is, the attacker has
@@ -192,29 +193,27 @@
 
 Although it may appear that the ``vulnerability'' of the mixes goes up
 as you go down the list, this is not necessarily the case -- the cost
-of the attack is important to consider as well. Suppose, the anonymity
+of the attack is important to consider as well. For example, suppose
+the anonymity
 of a message going through Mix 1 under active attack is proportional
 to the inverse of the cube of the number of messages expended in the
-attack, it can be seen as ``more vulnerable'' than Mix 2 which is
+attack. This mix can be seen as ``more vulnerable'' than Mix 2 which is
 always compromised by $10^6$ attacker messages.
 %(but otherwise has the anonymity proportional to the inverse of the
 % number of attacker messages). 
 Note that Mix 1 is vulnerable only to non-exact blending attacks,
 while the Mix 2 is vulnerable to exact certain attacks.
 
-We now proceed analyze different mixes, categorise them and attempt to
+We now analyze and categorize several mixes. We
 suggest their blending attack cost functions (both of time and space)
 where necessary.  We also look at SG mixes \cite{Kesdogan98}, an
-attempt specifically designed to protect against active attacks, in
+approach specifically designed to protect against active attacks, in
 section \ref{SG}.
 
 %Actual cost functions are a massive pain because it is unclear quite
 %what the optimal attack is, say, ``given 500 messages''. On the other
 %hand, some points on the cost function are important to consider.
 
-%[this paragraph sounds fascinating. we should move it somewhere more
-%prominent. -RRD]
-
 %(AAS Comment: Ok, we are now in need of a diagram. Maybe the above is
 %better illustrated with a table. Paul, maybe we should be more formal
 %about these definitions? Would you care to throw a few symbols in? (I
@@ -229,7 +228,7 @@
 
 \item The mixes take a constant time to fire.
 
-\item The mixes have limited physical memory and can only contain a
+\item The mixes have limited physical memory and so can only contain a
 finite number of messages.
 
 
@@ -242,15 +241,8 @@
 %      viz: in a successful n-1, I can tell if the message has been
 %      sent through the mix already.}}
 
-%\item We do not assume that the messages do not arrive at a uniform
-%rate. 
-
 \item Messages might or might not arrive at a uniform rate.
 
-
-\item We do not assume that the messages do not arrive at a uniform
-rate. 
-
 \item In calculating the minimum anonymity we assume the global
 passive attacker. The vulnerability to the active attacker is
 described separately.
@@ -269,7 +261,7 @@
 
 \paragraph*{Mesage Delay:} 
 The minimum delay is $\epsilon$ (the message arrives when there are
-$n-1$ messages already in the mix). The maximum delay is can be
+$n-1$ messages already in the mix). The maximum delay can be
 infinite (when a message arrives to a mix and no more ever
 arrive). The mean delay can be calculated if we assume a constant rate
 of arrival $r$, in which case it is $\frac{n}{2r}$.
@@ -290,10 +282,10 @@
 in the mix and must delay the attacked message until the mix has
 fired. If there are sufficient other legitimate messages and the
 attacker allows them through one at a time until the mix fires, then
-the maximum number attacker messages is also $n-1$.
+the maximum number of attacker messages is also $n-1$.
 
 \paragraph*{Adversaries} 
-The above attack seemingly required both the global delaying attacker
+The above attack seemingly requires both the global delaying attacker
 capabilities and the global inserting attacker capabilities. However,
 this is not necessarily so. If the global inserting attacker is able
 to insert $n-1$ of its own messages between each of the ``good''
@@ -306,9 +298,9 @@
 right'', i.e. the mix the target message is headed for contains $n-1$
 of the attacker's messages and will fire as soon as the target message
 reaches it. Thus, he has the capability to attack the next mix in the
-route of each of the messages going through the mix he controls. (A
-consequence of this is that if the attacker own all the mixes but one
-in the mix network, he is able to compromise anonymity of any
+route of each of the messages going through the mix he controls. (As
+a result, if the attacker own all the mixes but one,
+he is able to compromise anonymity of any
 message).
 
 (AAS comment: Verification comments should go here!)
@@ -322,24 +314,26 @@
 
 \paragraph*{Message Delay:} 
 The minimum delay is $\epsilon$, which occurs if the message arrives
-just before the mix is due to be flushed, the maximum delay is
+just before the mix is due to be flushed. The maximum delay is
 $t-\epsilon$, which is the case when the message arrives just
 after. The mean delay is $\frac{t}{2}$.
 
 \paragraph*{Anonymity:} 
-The minimum anonymity set is $0$ -- no messages arrive during the
-entire time period, the maximum anonymity set is theoretically
+The minimum anonymity set is $0$ --- no messages arrive during the
+entire time period. The maximum anonymity set is theoretically
 infinite, but in practice is limited by the capacity of the mix. The
 mean anonymity set (assuming a rate of arrival of messages $r$) is
 $rt$.
 
 Note that the threshold and timed mixes are in some sense dual. If the
 goal of the anonymity system is to guarantee anonymity at the expense
-of messages getting delivered, threshold mixes should be used. (This
-is the scenario of a spy in a hostile country -- if the anonymity is
-compromised, the spy is caught). If, on the other hand, timeliness of
+of fast message delivery, threshold mixes are good. (This
+is the scenario of a spy in a hostile country --- if the anonymity is
+compromised, the spy is caught.) On the other hand, if timeliness of
 message delivery is crucial and anonymity is a bonus, the timed mix is
-ideal. The attentive reader will also notice that if the messages are
+ideal. 
+%The attentive reader will also 
+Notice that if the messages are
 assumed to arrive at a constant rate, the properties of these mixes
 are exactly equivalent.
 
@@ -354,7 +348,7 @@
 \paragraph*{Blending Attack Behaviour:} 
 The attack is exact and certain and proceeds as follows: The adversary
 delays the target message for a maximum of time $t$ until the mix
-flushes; then forwards in the target message, blocking all other
+flushes. He then forwards in the target message and blocks all other
 incoming messages.  After another $t$ seconds the mix flushes again
 producing the target message on its own. This takes a maximum of
 $2t-\epsilon$ and a minimum of $\epsilon$ seconds (when the mix was
@@ -367,9 +361,8 @@
 delaying attacker is sufficient.\footnote{However, as previously
   noted, the delays could be caused by insertions.}  We also note that
 this ``attack'' can happen naturally in low traffic conditions, so a
-compromised mix may be able to execute it on a particular target
-message by waiting until the next mix in the path of the message is
-empty.
+dishonest mix may be able to attack the next hop of a message simply
+by holding it until the next hop is empty.
 %(AAS comment: Verification comments should go here!)
 
 \subsection{Threshold Or Timed Mix}
@@ -390,8 +383,9 @@
 
 \paragraph*{Blending Attack Behaviour:} 
 This design gives the worst case of threshold and timed mixes (and
-thus still exact and certain). The adversary can choose to perform the
-trickle, the flood attack or a mixture of the two depending on whether
+thus still exact and certain). The adversary can choose to perform a
+trickle attack, a flood attack, or a mixture of the two depending
+on whether
 he prefers to wait or send messages.  It can be performed in a minimum
 of $0$ messages in somewhere between $0$ and $2t-\epsilon$ seconds or
 with a maximum of $2(n-1)$ messages, in $\epsilon$ seconds.
@@ -418,7 +412,7 @@
 the mix can hold.
 
 \paragraph{Blending Attack Behaviour:} 
-The $n-1$ attack is still exact and is a simple combination of the
+The $n-1$ attack is still exact and uses a combination of the
 attacks on the threshold and the timed mixes. It takes a maximum of
 $2t-\epsilon$ and a minimum of $\epsilon$ seconds, a maximum of
 $2(n-1)$ and a minimum of $(n-1)$ messages.
@@ -427,9 +421,9 @@
 It is clear that to mount an attack on this mix, the attacker has to
 have the capability both to delay and to insert messages.
 
-All the attacks examined so far have been exact and certain. We now go
-on to examine pool mixes which only give the adversary an uncertain
-attack.
+%All the attacks examined so far have been exact and certain. We now go
+%on to examine pool mixes which only give the adversary an uncertain
+%attack.
 
 %\subsection{Leftover Comments}
 %
@@ -482,9 +476,9 @@
 
 \section{Pool Mixes}
 
-Not only all the attacks described in the previous section been exact
-and certain, but their cost has also been low.  We now examine pool
-mixes which only give the adversary an uncertain attack and
+Not only are all the attacks described in the previous section exact
+and certain, but they are also low-cost.  We now examine pool
+mixes, which give the adversary only an uncertain attack and
 substantially increase the cost.
 
 \subsection{Threshold Pool Mix}
@@ -493,7 +487,7 @@
 
 \paragraph*{Flushing Algorithm:} 
 The mix fires when $n+f$ messages accumulate in the mix. A pool of $f$
-messages chosen uniformly at random from all the messages is retained
+messages (chosen uniformly at random from all the messages) is retained
 in the mix. The other $n$ are forwarded on.
 
 \paragraph*{Message Delay:} 
@@ -509,13 +503,13 @@
 \paragraph*{Anonymity:} 
 Here we have to resort to the information theoretic definition of
 anonymity described in \cite{Serj02} rather than the standard
-set-based definition as the probabilities of the senders (receivers)
+set-based definition, since the probabilities of the senders (receivers)
 sending (receiving) the message are unequal.  Note also that the
 anonymity of the message going through a mix depends on the entire
-history of events which have happened in this mix. Thus, the maximum
-anonymity occurs when all the messages which have ever passed through
-the mix had come from different senders.  This analysis was carried
-out by Serjantov and Danezis in \cite{Serj02}.
+history of events which have happened in this mix. Thus, we achieve
+the maximum anonymity $A_{max}$ when all of the messages that have ever
+passed through the mix came from different senders.
+Serjantov and Danezis carried out this analysis in \cite{Serj02}.
 
 \[
 A_{max} = -\left(1 - \frac{f}{n}\right) \log{(n + f)} + \frac{f}{n}
@@ -524,21 +518,22 @@
 
 The concept of minimum anonymity in pool mixes is slightly more
 elusive. In the threshold mix case we assumed that all the messages in
-the batch of the mix come from different senders. So, whatever was the
-case with past messages, the minimum anonymity of a threshold pool mix
-is at least $n$, and therefore no worse than that of a corresponging
+the batch come from different senders. So, regardless of previous
+senders, the minimum anonymity of a threshold pool mix
+is at least $n$, and therefore no worse than that of a corresponding
 threshold mix.  We could assume that all the other messages may have
-come from the same sender and thus provide no anonymity.  However,
+come from the same sender and thus provide no anonymity, but
 this would be overly pessimistic -- the entire history of the mix is
 unlikely to consist of messages from just one sender.
 
 \paragraph*{Blending Attack Behaviour:} 
-We notice that the blending attack usually consists of two parts:
+In general, the blending attack has two phases:
 flushing the mix so that no good messages remain inside it, then
-forwarding in the target message and then flushing it out onto the
-network. In the past, this was possible in two mix flushes. Clearly,
-this is no longer the case. Furthermore, there is now a small but
-non-zero probability that a particular message (including the target
+forwarding in the target message and flushing it out onto the
+network. In the past, the whole attack used two mix flushes. With pools,
+two flushes are no longer sufficient.
+Furthermore, there is now a small but
+non-zero probability that a given message (e.g. the target
 message) remains in the mix for an arbitrary length of time.
 Intuitively, the attack ceases to be certain. It proceeds as follows:
 

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