[freehaven-cvs] cleaned up sections 6-8

[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:
cleaned up sections 6-8

went through and played the s/which/that/ game



Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- taxonomy.tex	7 May 2002 07:55:42 -0000	1.4
+++ taxonomy.tex	7 May 2002 08:41:07 -0000	1.5
@@ -32,15 +32,15 @@
 \maketitle
 
 \begin{abstract}
-The literature contains a variety of different mixes some of which
+The literature contains a variety of different mixes, some of which
 have also been used in deployed anonymity systems. We explore their
-anonymity and message delay properties and show how to mount active
+anonymity and message delay properties, and show how to mount active
 attacks against them by altering the traffic between the mixes. We
 show that if certain mixes are used, such attacks cannot destroy the
 anonymity of a particular message completely.  We work out the cost of
-these attacks in terms of the messages which the attacker has to
-insert into the network and the time he has to spend carrying out the
-attack. We discuss advantages and disadvantages of these mixes and the
+these attacks in terms of the messages that the attacker must
+insert into the network and the time he must spend.
+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
@@ -506,7 +506,7 @@
 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, we achieve
+history of events that 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}.
@@ -558,7 +558,7 @@
 
 \paragraph*{Analysis:} 
 Flushing out the mix: after $k$ rounds, the probability that a
-particular message which was in the mix at round $0$ is still in the
+particular message that was in the mix at round $0$ is still in the
 mix by round $k$ is
 
 \[
@@ -619,7 +619,7 @@
 be calculated from the history of the mix --- a record of the operation
 of the mix ever since it was started. Like in the threshold case, a
 mix's history includes the senders of each message and also the number
-of messages which got mixed together in each batch (and, potentially,
+of messages that got mixed together in each batch (and, potentially,
 a whole host of
 other features). Of course, in practice, a record of the only last few
 rounds gives a good approximation.
@@ -713,7 +713,7 @@
 
 Secondly, the attacker has to find out how many messages are in the
 mix.  Of course, the number of good messages in the mix is easy to
-calculate from the number of messages which come out. 
+calculate from the number of messages that come out. 
 %FIXME can you elaborate more on this, andrei?
 
 Finally, the number of messages inside the pool mix may be
@@ -757,7 +757,7 @@
 %verifiability schemes to detect very long delays of messages through
 %the mix and act appropriately. In the case of a system which needs to
 %guarantee a certain level of anonymity, all messages arising from a
-%mix which has not responded for a long time would be discarded thereby
+%mix that has not responded for a long time would be discarded thereby
 %not giving away their destination to the attacker. This, in our
 %opinion could lead to a very much stronger system.
 
@@ -846,37 +846,44 @@
 Another possible protection against the blending attacks is cover
 traffic. Indeed, in designing the Mixmaster system \cite{Cott94},
 Cottrell realised that even the timed dynamic pool mixes still leave
-the system vulnerable to attacks.  The decision was made to introduce
-cover traffic.
+the system vulnerable to attacks. He decided to introduce
+cover traffic to improve attack-resistance.
 
 At the moment, Mixmaster has the following cover traffic policy: at
 each flush one dummy is put out onto the network. The dummy message 
 generated by the mix looks like a normal message, but has a constant
 length of 5 hops and ends at a mix rather than at a receiver.
+% Have you confirmed it uses 5? Where is this from? -RRD
 
-Note that this still makes it possible for the attacker to flush the
+Note that this dummy policy still allows an attacker to flush the
 mix free of good messages and be certain about it.  However, once the
 good message is inserted into the mix, at every round at least one
 good message comes out. Naturally, when two messages come out, the
 attacker knows that the target message was one of those, but he does
 not know which one. If the attacker finishes here, he has reduced the
-anonymity of the message to $1$ (or two possible receivers). However,
+anonymity of the message to $1$ (that is, two possible receivers). However,
 he can do better. Because Mixmaster is a mix network, he can keep
-tracking both messages (and all the messages which result when these
+tracking both messages (and all the messages that result when these
 pass through more mixes) until he can detect that one message has gone
-to a recipient. That is the target message as all the dummy messages
+to a recipient. That is the target message since all the dummy messages
 end in a mix. This attack is exact, but much more expensive than
 anything we have described previously. The situation can be further
 improved by making the mix choose its route length for the dummies
-from a uniform distribution rather than always choosing $5$. The
-attack can be avoided altogether by allowing the mixes to send cover
-traffic to the users\footnote{We expect this to be unacceptable as
-each mix would have to be aware of a number of users who are happy to
-be sent dummy traffic.}  (possibly in some format which will make it
-discarded by the user).
+from a uniform distribution rather than always choosing $5$. We could
+get further protection by allowing mixes to send cover traffic to
+the users (possibly in some format that can be automatically discarded).
+However, providing complete protection with this approach is very
+hard. Each mix must know all the users in the system: if a mix only
+delivers dummies to a subset of the users, an adversary can distinguish
+with better than even probability between a dummy and a legitimate
+message.
 
-Note that this is completely orthogonal to the blending attack
-properties provided by the mixes themselves, merely magnifying the
+%if a mix doesn't
+%know about even a single user when it generates a dummy, an adversary
+%can be sure that messages arriving at that user are not dummies.
+
+Note that dummies are completely orthogonal to the blending attack
+properties provided by the mixes themselves. Dummies simply magnify the
 scale of the attack without changing the properties. For example, even
 with the Mixmaster cover traffic policy, a threshold mix network can
 be attacked in $\epsilon$ time (but a very large number of messages).
@@ -889,35 +896,41 @@
 most of these have not been rigorously analysed or evaluated.
 
 We will concentrate our attention on one particular proposal -- Stop
-and Go Mixes \cite{Kesdogan98}. The authors outline several ways which
-could be used to protect mix systems against active attacks similar to
+and Go Mixes \cite{Kesdogan98}. The authors outline several techniques
+that
+could be used to protect mix systems against active attacks %similar to
+like
 the ones considered in this work.
 
 The first is a scheme for an anonymity system based on a mix cascade
-which requires authentication. This is based on a stronger set of
+that requires authentication. This is based on a stronger set of
 assumptions -- that the attacker cannot mount a distributed $n-1$
-attack where the hostile messages come from different users. It
-cannot be used in mix networks.
+attack where the hostile messages come from different users. 
+%It cannot be used in mix networks.
+Unfortunately, it seems very hard to reuse this idea in free-route mix
+networks, since there is no centralized input location at which we can do
+authentication; compromised mixes could claim to have done authentication
+on traffic they instead generate themselves.
 
-The second scheme, Stop and Go Mixes involves the sender estimating a
+The second scheme, Stop and Go Mixes, involves the sender estimating a
 time window during which the message is allowed to arrive at each of
 the mixes making up the route of the message. If the message arrives
 during that time period it will be forwarded on, otherwise it will be
-discarded. This limits the attacker's ability to delay messages and
-therefore the possibility of an active attack.
+discarded. Therefore the attacker's ability to delay messages is much
+more limited, so active attacks are harder.
 
-The attack is uncertain, and furthermore, the authors argue that the
+The attack is uncertain, the authors argue that the
 probability of executing the attack successfully is very low. 
 
 However, the scheme relies on the users being able to accurately
-calculate a security parameter which depends on their estimate of the
-rate of arrival of messages to the mixes which the target message will
+calculate a security parameter that depends on their estimate of the
+rate of arrival of messages to the mixes that the target message will
 go through \emph{at the time it will travel through them}. In other
 words, the users need to be able to predict the traffic levels in the
-system in the future to remain anonymous. This is a weakness of the
-system which is likely to be exploited by the attacker (the exact
+system in the future to remain anonymous. This weakness
+is likely to be exploited by the attacker (the exact
 details depend, of course, on how the security parameter is
-calculated). And, an attacker able to insert arbitrary messages
+calculated). Further, an attacker able to insert arbitrary messages
 into the system will still be able to arbitrarily affect the input
 batch with which a target message enters any mix, regardless of the
 timing requirements of that message.
@@ -930,16 +943,16 @@
 In this paper we have presented a set of mixes and examined their
 anonymity, message delay and blending attack properties. In
 particular, we suggested that it is useful to partition the mixes into
-certain categories of vulnerability but emphasized that it the cost,
-as well as the worst case attack scenario is important to consider.
+certain categories of vulnerability but emphasized that the cost
+and worst case attack scenario are important qualities to consider.
 
 Although we have shown the mixes to be rather vulnerable to active
-attacks, there are possible avenues which could be explored. The first
+attacks, some avenues still have hope. The first
 of these is verification schemes.
 
-The second, and the more widely used one is cover traffic. Here we
-assess the cover traffic policy used in Mixmaster, point out
-weaknesses and show how they can be fixed.
+The second and the more widely used solution is cover traffic. Here we
+assess the cover traffic policy used in Mixmaster, point out weaknesses,
+and discuss some approaches to strengthening its dummy policy.
 
 The paper can also be treated as a tutorial on the different styles of
 mixes and as a recommendation to the Mixmaster implementors to alter

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