[freehaven-cvs] Integrated Paul"s latest revisions

[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:
Integrated Paul's latest revisions



Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- taxonomy.tex	6 May 2002 22:11:01 -0000	1.1
+++ taxonomy.tex	7 May 2002 01:16:37 -0000	1.2
@@ -1,17 +1,32 @@
+
 \documentclass{llncs}
 \usepackage{psfrag}
 \usepackage{url}
 %\usepackage{amsmath}
 \usepackage[dvips]{graphicx}
 
-\bibliographystyle{try1}
+\bibliographystyle{plain}
+%\bibliographystyle{try1}
+
 
 \newtheorem{exa}{Example}
 \begin{document}
 \pagestyle{plain}
 
-\title{Increasing the Cost of Active Attacks}
-\author{...}
+%\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)}}
 
 \maketitle
 
@@ -53,7 +68,7 @@
 them.
 
 In fact, some of the mixes used in well-known fielded systems such as
-Mixmaster \cite{Mixmaster} are mentioned only briefly or not at all in
+Mixmaster \cite{Cott94} are mentioned only briefly or not at all in
 the literature. We aim to start closing this gap by enumerating and
 exploring a variety of mix architectures. In particular, we consider
 the extent to which the mixes are vulnerable to active attacks such as
@@ -81,8 +96,8 @@
 protecting their users against passive adversaries. For instance,
 Crowds \cite{reiter98crowds} is secure against a local passive
 adversary while Onion Routing \cite{goldschlag99onion} protects
-against traffic analysis (but not traffic confirmation) by a global
-passive adversary.
+against traffic analysis by global passive adversaries in some
+configurations but not others.
 
 %[actually, onion routing is broken by a global passive adversary,
 %because he can trivially do traffic confirmation attacks. -RRD
@@ -106,8 +121,20 @@
 
 Note that the global active attacker can be viewed as a combination of
 two separate attackers: one who can only insert messages (global
-inserting attacker) and onw who can only delay messages (global
-delaying attacker).
+inserting attacker) and one who can only delay messages (global
+delaying attacker).\footnote{In fact, in theory only insertion of
+  messages is necessary given assumptions such as predictable bounds
+  on network link capacities. This is because the global inserting
+  adversary can insert enough messages to cause any volume or time
+  delay on any traffic.  This reduction also assumes that either no
+  two legitimate messages appear in the same network queue or that it
+  is not necessary to ever delay so as to cause a reordering of
+  legitimate messages.  It is more realistic to model attacks as a
+  combination of delays and insertions, and we will not make further
+  mention of this potential reduction.}
+
+%\framebox{\parbox{11cm}{Paul says:\\
+%    Note the footnote.}}
 
 It is well known that the ability to insert or delay messages may
 allow the attacker to determine, for instance, the recipient of a
@@ -205,6 +232,22 @@
 \item The mixes have limited physical memory and can only contain a
 finite number of messages.
 
+
+\item Mixes will not replay messages.
+  
+
+%  \framebox{\parbox{11cm}{Paul says:\\
+%      This seemed implicit in the paper, and I think was explicit in
+%      our conversation. Note that even this gives some information,
+%      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. 
 
@@ -232,7 +275,7 @@
 of arrival $r$, in which case it is $\frac{n}{2r}$.
 
 \paragraph*{Anonymity:} $n$. 
-We assume that all the messages in thebatch are from different senders
+We assume that all the messages in the batch are from different senders
 (and go to different receivers).
 
 \paragraph*{Blending Attack Behaviour:} 
@@ -243,9 +286,11 @@
 necessary). The attack takes a minimum of $n-1$ (if the attacker can
 detect that the mix is empty, he simply forwards the target message to
 the mix along with his $n-1$ messages to flush it out) and a maximum
-of $2n-2$ messages.%\footnote{The careful reader is invited to verify
-%this bound.}.
-%Paul says this is 2n-3.
+of $2n-2$ messages if the attacker cannot detect how many messages are
+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$.
 
 \paragraph*{Adversaries} 
 The above attack seemingly required both the global delaying attacker
@@ -314,15 +359,17 @@
 producing the target message on its own. This takes a maximum of
 $2t-\epsilon$ and a minimum of $\epsilon$ seconds (when the mix was
 empty and about to be flushed), and $0$ messages.  The attack is
-usually referred to as the trickle attack.
+usually referred to as the trickle attack. 
 %As opposed to the treacle attack which would just be messy!
 
 \paragraph*{Adversaries}
 This attack does not require any insertion of messages, so the global
-delaying attacker is sufficient. 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.
+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.
 %(AAS comment: Verification comments should go here!)
 
 \subsection{Threshold Or Timed Mix}
@@ -335,10 +382,11 @@
 the mix.
 
 \paragraph*{Message Delay:} 
-The maximum message delay is $t$, the minimum -- $\epsilon$.
+The maximum message delay is $t$, the minimum is $\epsilon$.
 
 \paragraph*{Anonymity:} 
-No minimum anonymity, the maximum anonymity is $n$.
+The minimum anonymity set is $0$ -- no messages arrive during the
+entire time period. The maximum anonymity is $n$.
 
 \paragraph*{Blending Attack Behaviour:} 
 This design gives the worst case of threshold and timed mixes (and
@@ -545,12 +593,14 @@
 
 \subsection{Timed Pool}
 
-\paragraph*{Parameters:} $t$, period; $f$, pool.
+\paragraph*{Parameters:} $t$, period; $f$, pool; ($f$, threshold).
 
 \paragraph*{Flushing Algorithm:} 
 A mix is flushed every $t$ seconds. A pool of $f$ messages chosen
 uniformly at random is retained in the mix. The others are forwarded
-on.
+on. If fewer then $f$ messages are in the mix, it does not fire.
+(Thus, strictly speaking, this is a threshold and timed pool mix, for
+which the threshold is $f$.)
 
 \paragraph*{Message Delay:} 
 The minimum message delay is $\epsilon$, and there is no maximum delay
@@ -577,14 +627,15 @@
 other features). Of course, in practice, only a record of the last few
 rounds gives a good approximation.
 
-The minimum anonymity of this mix is clearly smaller than that for the
-threshold pool mix. We note that in the pool mixes it is the mixing of
-the target message with the batch of incoming messages that provides
-the bulk of the anonymity, not the mixing of it with the messages in
-the pool. Because the timed mix does not always have this batch of
-messages that the target message is mixed with, its minimum anonymity
-should be considered to be very much worse than that of the threshold
-pool mix.
+Assuming a threshold pool mix has a threshold larger
+than the pool size, the minimum anonymity of a timed pool mix is
+clearly smaller than that for the threshold pool mix. We note that in
+the pool mixes it is the mixing of the target message with the batch
+of incoming messages that provides the bulk of the anonymity, not the
+mixing of it with the messages in the pool. Because the timed mix does
+not always have this batch of messages that the target message is
+mixed with, its minimum anonymity should be considered to be very much
+worse than that of the threshold pool mix.
 
 \paragraph*{Blending Attack Behaviour:}
 There are two flavours of the blending attack possible on this mix.
@@ -595,22 +646,22 @@
 The former involves the attacker adding as many messages as possible
 in one round trying to maximize the probability that after one flush
 only the attacker messages will be left in the pool\footnote{Note that
-the attacker knows he has succeeded if $f$ of his messages did not
-come out after the flush.}. This is very inefficient in terms of the
+  the attacker knows he has succeeded if $f$ of his messages did not
+  come out after the flush.}. This is very inefficient in terms of the
 number of messages added by the attacker ($b$) as the probability of
-flushing the mix by this method is $\frac{f^2}{b+f}$\footnote{As
-previously mentioned, in practice there is an upper limit on $b$ due
-to the finite memory capacity of the mix} (supposing there were $f$
-good messages in the mix initially).  However, this aims to flush the
+flushing the mix by this method is $\frac{f^2}{b+f}$ (supposing there
+were $f$ good messages in the mix initially).\footnote{As previously
+  mentioned, in practice there is an upper limit on $b$ due to the
+  finite memory capacity of the mix.}  However, this aims to flush the
 good messages out of the mix in one round, and therefore a maximum of
 $t$ seconds. This allows the entire attack to be executed in less than
 $2t$ seconds with an arbitrarily high probability of success.
 
 The latter involves the attacker adding just one message to each round
-for many rounds. This is very efficient in the number of messages $b$
-\footnote{Indeed, this is a much more efficient attack than the one on
-the threshold pool mix in terms of messages, but clearly not in terms
-of time} -- the probability of flushing the mix is
+for many rounds. This is very efficient in the number of
+messages\footnote{Indeed, this is a much more efficient attack than
+  the one on the threshold pool mix in terms of messages, but clearly
+  not in terms of time.} $b$ -- the probability of flushing the mix is
 $f\left(\frac{f}{f+1}\right)^b$, but delays all the messages to the
 mix by $tb$ seconds, which is highly observable to the users of the
 anonymity system.
@@ -621,8 +672,8 @@
 
 %Read through and corrected up to here.
 
-\subsection{Cottrell Mix (Timed Dynamic Pool Mix)} 
-\paragraph*{Parameters:} $t$, period; $min$, pool; $frac$, fraction.
+\subsection{Cottrell Mix (Timed Dynamic-Pool Mix)} 
+\paragraph*{Parameters:} $t$, period; $min$, pool; $frac$, fraction; ($min$ threshold).
 
 \paragraph*{Flushing Algorithm:} 
 A mix gets flushed every $t$ seconds.  Random fraction $frac$ of
@@ -668,10 +719,15 @@
 arbitrarily high and cannot be reduced to below $min$ in one round.
 Thus, if we wish to send a message and decrease the probability of it
 getting tracked, we should send it at the time of higher traffic
-thereby increasing the cost (in terms of messages or time) attempted
-attacks on it\footnote{At times of high traffic, the mix will contain
-many more messages than $min$, and to flush it free of good messages
-will require either more time or more messages from the attacker.}.
+thereby increasing the cost (in terms of messages or time) of attempted
+attacks on it%\footnote{At times of high traffic, the mix will contain
+%many more messages than $min$, and to flush it free of good messages
+%will require either more time or more messages from the attacker.}.
+%
+.\footnote{Of course this assumes that we can determine times of
+  higher legitimate traffic. An attacker capable of arbitrary message
+  insertions, as we have been assuming, will make that more
+  complicated.}
 
 Thus, the Cottrell mix requires the attacker to be able to delay all
 the traffic to the mix for a substantial number of rounds, and
@@ -726,8 +782,9 @@
 harder. -RRD]
 
 We note that the minimum anonymity of the Cottrell mix is still very
-much worse than that of the threshold pool mix. Therefore, we propose
-adding a threshold to a Cottrell mix to improve its minimum anonymity
+much worse than that of the threshold pool mix (where the threshold
+size is much larger than the pool size). Therefore, we propose adding
+a threshold to a Cottrell mix to improve its minimum anonymity
 properties. We shall not go into any more detail other than to say
 that it is intuitively clear that this modification will not have
 adverse effects on the blending attack properties, although will
@@ -742,7 +799,7 @@
 \section{Cover Traffic}
 
 Another possible protection against the blending attacks is cover
-traffic. Indeed, in designing the Mixmaster system \cite{Mixmaster},
+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.
@@ -815,7 +872,10 @@
 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
 details depend, of course, on how the security parameter is
-calculated).
+calculated). And, 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.
 
 Thus, we defer the evaluation of SG mixes to future work as the
 precise details of parts of the protocol crucial to the security of
@@ -843,4 +903,5 @@
 \bibliography{taxonomy}
 
 \end{document}
+
 

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