[freehaven-cvs] a cover traffic subsec that isn"t too wrong

[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:
a cover traffic subsec that isn't too wrong


Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.29
retrieving revision 1.30
diff -u -d -r1.29 -r1.30
--- taxonomy.tex	9 Sep 2002 20:35:49 -0000	1.29
+++ taxonomy.tex	9 Sep 2002 21:56:09 -0000	1.30
@@ -914,56 +914,50 @@
 
 \subsection{Cover Traffic}
 
-Another possible protection against the blending attacks is cover
-traffic. Indeed, in designing the Mixmaster system \cite{Cott94},
-Cottrell realized that even the timed dynamic-pool mixes still leave
-the system vulnerable to attacks. He decided to introduce
-cover traffic to improve attack resistance.
+Cover traffic is another promising protection against blending attacks.
+Consider a simple cover traffic policy, suggested originally by Lance
+Cottrell: at each flush one dummy is put out onto the network. The
+dummy message generated by the mix looks like a normal message. Assume
+that like the current Mixmaster dummy generation algorithm, it has by
+default a constant length of $4$ hops, and it ends at a mix rather than
+at a receiver.\footnote{The current Mixmaster dummy policy suffers also
+from the fact that there \emph{is} no policy --- a user or operator
+must manually decide to send each dummy. Some people have automated
+the process with periodic cron scripts, but we strongly recommend a
+coordinated network-wide policy that all users and mixes follow.}
 
-% the remainder of this section appears to be "what lance said,
-% which has no bearing on current reality". lance is way out of
-% the loop in terms of what mixmaster has done in the past 4 years.
-%
-% andrei -- do you want to change this section and say things about
-% how cover traffic should work in general? if not, let me know
-% and i'll cut it down a lot in size.
-%
-%   -RD
+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$
+(that is, two possible receivers). However, he can do better. Assuming
+a free-route mix network, he can keep 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 since all the dummy messages end in a mix. This attack is exact,
+but much more expensive than anything we have described previously.
 
-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
-% AAS: Lance.
-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$ (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 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 since all the dummy
-messages end in a mix. This attack is exact, but much more expensive
-than anything we have described previously. We can make the adversary's
-job harder by making the mix choose its route length for the
-dummies from a uniform distribution rather than always choosing
-$5$. We can get further protection by allowing mixes to send cover
-traffic to the users.  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.
+We can make the adversary's job harder by making the mix choose its
+route length for the dummies from a uniform distribution rather than
+always choosing $4$ by default. We can get further protection by allowing
+mixes to send cover traffic to the users. 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 constant rate dummy policies do not affect the blending
-attack properties provided by the mixes themselves. Constant 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).
+Note that constant rate dummy policies do not affect the blending attack
+properties provided by the mixes themselves. Constant dummies simply
+magnify the scale of the attack without changing the properties. For
+example, even with the above cover traffic policy (a dummy added at each
+flush), a threshold mix network can be attacked in $\epsilon$ time (but
+a very large number of messages). We can provide stronger protection by
+adding a variable number of dummies to each batch --- say, by choosing
+from a geometric distribution (flip a weighted coin: if it comes up heads,
+add a dummy and flip again). Some Mixmaster remailers have begun adopting
+a similar approach. We leave its analysis to future work.
 
 \subsection{Making Messages Unrecognizable}
 

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