[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] checkpointing patches from paul, modulo patches from...
Update of /home/freehaven/cvsroot/doc/batching-taxonomy
In directory moria.seul.org:/home/arma/work/freehaven/doc/batching-taxonomy
Modified Files:
taxonomy.bib taxonomy.tex
Log Message:
checkpointing patches from paul, modulo patches from me
Index: taxonomy.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.bib,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- taxonomy.bib 22 Aug 2002 08:47:26 -0000 1.4
+++ taxonomy.bib 31 Aug 2002 02:12:02 -0000 1.5
@@ -1,34 +1,44 @@
% Note that this file requires a \usepackage{url} which seems to be
% one of the standard latex packages
-
@InProceedings{flash-mix,
author = {Markus Jakobsson},
- title = {Flash {M}ixing},
+ title = {{Flash Mixing}},
booktitle = {Principles of Distributed Computing - {PODC} '99},
- year = {1999},
+ year = 1999,
publisher = {ACM},
note = {\url{http://citeseer.nj.nec.com/jakobsson99flash.html}},
}
-@Misc{mix-acc,
- author = {Roger Dingledine and Michael J. Freedman and David Hopwood and David Molnar},
- title = {A {R}eputation {S}ystem to {I}ncrease {MIX}-net {R}eliability},
- howpublished = {Proceedings of the Information Hiding Workshop 2001},
- note = {\url{http://www.freehaven.net/papers.html}},
+@InProceedings{mix-acc,
+ author = {Roger Dingledine and Michael J. Freedman and David
+ Hopwood and David Molnar},
+ title = {{A Reputation System to Increase MIX-net
+ Reliability}},
+ booktitle = {Information Hiding, 4th International Workshop (IH 2001)},
+ pages = {126--141},
+ year = 2001,
+ editor = {Ira Moskowitz},
+ publisher = {Springer-Verlag, LNCS 2137},
+ note = {\url{http://www.freehaven.net/papers.html}},
}
-@Misc{casc-rep,
+
+
+@InProceedings{casc-rep,
author = {Roger Dingledine and Paul Syverson},
- title = {Reliable {MIX} {C}ascade {N}etworks through {R}eputation},
- howpublished = {Proceedings of Financial Cryptography 2002},
- note = {\newline \url{http://www.freehaven.net/papers.html}},
- year = {2002}
+ title = {{Reliable MIX Cascade Networks through Reputation}},
+ booktitle = {Financial Cryptography (FC '02)},
+ year = 2002,
+ editor = {Matt Blaze},
+ publisher = {Springer Verlag, LNCS (forthocoming)},
+ note = {\newline \url{http://www.freehaven.net/papers.html}}
}
@article{chaum81untraceable,
author = "David Chaum",
- title = "Untraceable electronic mail, return addresses and digital pseudonyms",
- journal = "Communications of the A.C.M.",
+ title = "Untraceable electronic mail, return addresses and digital
+ pseudonyms",
+ journal = "Communications of the ACM",
volume = "24",
number = "2",
pages = "84--88",
@@ -38,79 +48,40 @@
@Misc{Cott94,
author = {L. Cottrell},
title = {Mixmaster and Remailer Attacks},
- OPThowpublished = {},
- year = {1994},
- OPTmonth = {},
- note= {\url{http://www.obscura.com/~loki/remailer/remailer-essay.html}},
- OPTannote = {}
+ year = 1994,
+ note= {\url{http://www.obscura.com/~loki/remailer/remailer-essay.html}}
}
-@inproceedings{syverson99,
- author = "Paul F. Syverson and Stuart G. Stubblebine",
- title = "Group Principals and the Formalization of Anonymity",
- booktitle = "World Congress on Formal Methods (1)",
- pages = "814-833",
- year = "1999",
- note = {\url{http://citeseer.nj.nec.com/syverson99group.html}}
-}
-
@Misc{Anonymizer,
key = {Anonymizer},
- OPTauthor = {},
title = {The Anonymizer},
- howpublished = {\url{http://www.anonymizer.com/}},
- OPTyear = {},
- OPTmonth = {},
- OPTnote = {},
- OPTannote = {}
+ howpublished = {\url{http://www.anonymizer.com/}}
}
@InProceedings{babel,
- author = {C. Gulcu and G. Tsudik},
- title = {Mixing Email with {B}abel},
- OPTcrossref = {},
- OPTkey = {},
- booktitle = {1996 Internet Society Symposium on Network and Distributed Sytem Security},
+ author = {C. G\"{u}lc\"{u} and G. Tsudik},
+ title = {{Mixing Email with \emph{Babel}}},
+ booktitle = {Internet Society Symposium on Network and
+ Distributed Sytem Security (NDSS'96)},
pages = {2--16},
- year = {1996},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
+ year = 1996,
address = {San Diego, CA},
- month = {Feb},
- OPTorganization = {},
- OPTpublisher = {},
- OPTnote = {},
- OPTannote = {}
+ month = {Feb}
}
@InProceedings{syverson_2000,
- author = {Paul F. Syverson and Gene Tsudik and Michael G. Reed and Carl E. Landwehr},
+ author = {Paul F. Syverson and Gene Tsudik and Michael G. Reed
+ and Carl E. Landwehr},
title = {Towards an Analysis of Onion Routing Security},
booktitle = {Workshop on Design Issues in Anonymity and Unobservability},
- OPTcrossref = {},
- OPTkey = {},
- OPTpublisher = {},
- year = {2000},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
- OPTchapter = {},
- OPTtype = {},
- OPTaddress = {},
- OPTedition = {},
- month = {July},
- OPTpages = {},
- OPTnote = {},
- OPTannote = {}
+ year = 2000,
+ month = {July}
}
@article{reiter98crowds,
author = "Michael K. Reiter and Aviel D. Rubin",
- title = "Crowds: anonymity for {Web} transactions",
+ title = "{Crowds: anonymity for Web transactions}",
journal = "ACM Transactions on Information and System Security",
volume = "1",
number = "1",
@@ -132,53 +103,34 @@
@InProceedings{Kesdogan98,
author = {D. Kesdogan and J. Egner and R. Buschkes},
- title = {Stop-And-Go-{MIX}es Providing Probabilistic Anonymity in an Open System},
- booktitle = {Proceedings of the International Information Hiding Workshop},
- OPTcrossref = {},
- OPTkey = {},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
- year = {1998},
- OPTorganization = {},
- OPTpublisher = {},
- OPTaddress = {},
- OPTmonth = {April},
- OPTpages = {},
- OPTnote = {},
- OPTannote = {}
+ title = {Stop-And-Go-{MIX}es Providing Probabilistic
+ Anonymity in an Open System},
+ booktitle = {Proceedings of the International Information Hiding
+ Workshop},
+ year = 1998,
+ month = {April}
}
@misc{clarke00freenet,
author = "I. Clarke and O. Sandberg and B. Wiley and T. Hong",
- title = "Freenet: A Distributed Anonymous Information Storage and Retrieval System",
- text = "In Proceedings of the ICSI Workshop on Design Issues in Anonymity and
- Unobservability, Berkeley, CA",
+ title = "Freenet: A Distributed Anonymous Information Storage and
+ Retrieval System",
+ text = "In Proceedings of the ICSI Workshop on Design Issues in
+ Anonymity and Unobservability, Berkeley, CA",
year = "2000",
note = {\url{http://citeseer.nj.nec.com/clarke00freenet.html}}
}
@Misc{Napster,
key = {Napster},
- OPTauthor = {},
title = {Napster},
- howpublished = {\url{http://www.napster.com/}},
- OPTyear = {},
- OPTmonth = {},
- OPTnote = {},
- OPTannote = {}
+ howpublished = {\url{http://www.napster.com/}}
}
@Misc{Groove,
key = {Groove},
- OPTauthor = {},
title = {Groove.net},
- howpublished = {\url{http://www.groove.net/}},
- OPTyear = {},
- OPTmonth = {},
- OPTnote = {},
- OPTannote = {}
+ howpublished = {\url{http://www.groove.net/}}
}
@Misc{Freedom,
@@ -186,30 +138,23 @@
author = {P. Boucher and I. Goldberg and A. Shostack},
title = {Freedom System 2.0 Architecture},
howpublished = {\url{http://www.freedom.net/info/whitepapers/}},
- year = {2000},
+ year = 2000,
month = {December},
- note = {Zero-Knowledge Sytems, Inc.},
- OPTannote = {}
+ note = {Zero-Knowledge Sytems, Inc.}
}
@InBook{Gnutella,
author = {Gene Kan},
- title = {Peer-to-Peer: Harnessing the Power of Disruptive Technologies},
- chapter = {8},
+ title = {Peer-to-Peer: Harnessing the Power of Disruptive
+ Technologies},
+ chapter = 8,
publisher = {O'Reilly},
- year = {2001},
- OPTkey = {},
- OPTeditor = {Andy Oram},
+ year = 2001,
+ editor = {Andy Oram},
volume = {},
- OPTnumber = {},
- OPTseries = {},
- OPTaddress = {},
- OPTedition = {},
month = {March},
pages = {94-122},
- OPTtype = {},
- note = {},
- OPTannote = {}
+ note = {}
}
@@ -223,28 +168,22 @@
@InProceedings{Raymond00,
author = {J. Raymond},
- title = {Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems},
- booktitle = {Designing Privacy Enhancing Technologies: Proceedings of the International Workshop on the Design Issues in Anonymity and Observability},
- OPTcrossref = {},
- OPTkey = {},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
- year = {2000},
- OPTorganization = {},
- OPTpublisher = {},
- OPTaddress = {},
+ title = {Traffic Analysis: Protocols, Attacks, Design Issues,
+ and Open Problems},
+ booktitle = {Designing Privacy Enhancing Technologies:
+ Proceedings of the International Workshop on the
+ Design Issues in Anonymity and Observability},
+ year = 2000,
month = {July},
- pages = {10-29},
- OPTnote = {},
- OPTannote = {}
+ pages = {10-29}
}
@article{chaum88dining,
author = "David Chaum",
- title = "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability",
- journal = "Journal of Cryptology: the journal of the International Association for Cryptologic Research",
+ title = "The Dining Cryptographers Problem: Unconditional Sender
+ and Recipient Untraceability",
+ journal = "Journal of Cryptology: the Journal of the International
+ Association for Cryptologic Research",
volume = "1",
number = "1",
pages = "65--75",
@@ -252,44 +191,29 @@
}
@InProceedings{Berthold00,
- author = {Oliver Berthold and Andreas Pfitzmann and Ronny Standtke},
- title = {The Disadvantages of Free {MIX} Routes and How to overcome them},
- booktitle = {Designing Privacy Enhancing Technologies: Proceedings of the International Workshop on the Design Issues in Anonymity and Observability},
- OPTcrossref = {},
- OPTkey = {},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
- year = {2000},
- OPTorganization = {},
- OPTpublisher = {},
- OPTaddress = {},
+ author = {Oliver Berthold and Andreas Pfitzmann and Ronny
+ Standtke},
+ title = {The Disadvantages of Free {MIX} Routes and How to
+ overcome them},
+ booktitle = {Designing Privacy Enhancing Technologies:
+ Proceedings of the International Workshop on the
+ Design Issues in Anonymity and Observability},
+ year = 2000,
month = {July},
- pages = {10-29},
- OPTnote = {},
- OPTannote = {}
+ pages = {10-29}
}
@InProceedings{Pfitzmann00,
author = {Andreas Pfitzmann and Marit Kohntopp},
- title = {Anonymity, Unobservability and Pseudonymity --- A proposal for Terminology},
- booktitle = {Designing Privacy Enhancing Technologies: Proceedings of the International Workshop on the Design Issues in Anonymity and Observability},
- OPTcrossref = {},
- OPTkey = {},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
- year = {2000},
- OPTorganization = {},
- OPTpublisher = {},
- OPTaddress = {},
+ title = {Anonymity, Unobservability and Pseudonymity --- A
+ proposal for Terminology},
+ booktitle = {Designing Privacy Enhancing Technologies:
+ Proceedings of the International Workshop on the
+ Design Issues in Anonymity and Observability},
+ year = 2000,
month = {July},
- pages = {1-9},
- OPTnote = {},
- OPTannote = {}
+ pages = {1-9}
}
@inproceedings{syverson97anonymous,
@@ -308,122 +232,74 @@
author = {Claude Shannon},
title = {The Mathematical Theory of Communication},
journal = {Bell Systems Technical Journal},
- year = {1948},
- OPTkey = {},
- volume = {30},
- OPTnumber = {},
- pages = {50--64},
- OPTmonth = {},
- OPTnote = {},
- OPTannote = {}
+ year = 1948,
+ volume = 30,
+ pages = {50--64}
}
@InProceedings{Hybrid00,
author = {Miyako Ohkubo and Masayuki Abe},
title = {A Length-Invariant Hybrid Mix},
- OPTcrossref = {},
- OPTkey = {},
booktitle = {Advances in Cryptology -- ASIACRYPT},
pages = {178 ff.},
- year = {2000},
+ year = 2000,
editor = {T. Okamoto},
- OPTvolume = {},
- number = {1976},
- series = {LNCS},
- OPTaddress = {},
- OPTmonth = {},
- OPTorganization = {},
- OPTpublisher = {},
- OPTnote = {},
- OPTannote = {}
+ number = 1976,
+ series = {LNCS}
}
@Manual{Mix_prot,
title = {Mixmaster Protocol Version 3},
- OPTkey = {},
author = {Ulf Moeller and Lance Cottrell},
- OPTorganization = {},
- OPTaddress = {},
- OPTedition = {},
- OPTmonth = {},
- year = {2000},
- note = {\url{http://www.eskimo.com/~rowdenw/crypt/Mix/draft-moeller-v3-01.txt}},
- OPTannote = {}
+ year = 2000,
+ note = {\url{http://www.eskimo.com/~rowdenw/crypt/Mix/draft-moeller-v3-01.txt}}
}
@InProceedings{Diaz02,
- author = {Claudia Diaz and Stefaan Seys and Joris Claessens and Bart Preneel},
+ author = {Claudia Diaz and Stefaan Seys and Joris Claessens
+ and Bart Preneel},
title = {Towards measuring anonymity},
booktitle = {Privacy Enhancing Technologies},
- OPTcrossref = {},
- OPTkey = {},
- OPTeditor = {},
- OPTvolume = {},
- OPTnumber = {},
- OPTseries = {},
- year = {2002},
- OPTorganization = {},
- OPTpublisher = {},
- OPTaddress = {},
+ year = 2002,
month = {April},
- pages = {},
- OPTnote = {},
- OPTannote = {}
+ pages = {}
}
-\bibitem{IT} Claude Shannon, "The Mathematical Theory of Communication," Bell Systems
-Technical Journal, 30:50--64, 1948.
@InProceedings{Serj02,
author = {Andrei Serjantov and George Danezis},
title = {Towards an Information Theoretic Metric for Anonymity},
- OPTcrossref = {},
- OPTkey = {},
booktitle = {Privacy Enhacing Technologies},
- OPTpages = {},
- year = {2002},
- OPTeditor = {Paul Syverson and Roger Dingledine},
- OPTvolume = {},
- OPTnumber = {},
+ year = 2002,
+ editor = {Paul Syverson and Roger Dingledine},
series = {LNCS},
- OPTaddress = {San Francisco, CA},
- month = {April},
- OPTorganization = {},
- OPTpublisher = {},
- OPTnote = {},
- OPTannote = {}
+ address = {San Francisco, CA},
+ month = {April}
}
-@Proceedings{FGJP98,
- title = {Comparison of Commitment Schemes Used in Mix-Mediated
- Anonymous Communication for Preventing Pool-Mode Attacks},
- year = {1998},
- OPTkey = {},
- booktitle = {3rd Australasian Conference on Information Security and Privacy (ACISP'98},
+@InProceedings{FGJP98,
+ author = {Elke Franz and Andreas Graubner and Anja Jerichow and
+ Andreas Pfitzmann},
+ title = {{Comparison of Commitment Schemes Used in
+ Mix-Mediated Anonymous Communication for Preventing
+ Pool-Mode Attacks}},
+ year = 1998,
+ booktitle = {3rd Australasian Conference on Information Security and
+ Privacy (ACISP'98},
editor = {C. Boyd and E. Dawson},
- OPTvolume = {},
- number = {1438},
+ number = 1438,
series = {LNCS},
- OPTaddress = {},
- OPTmonth = {},
- OPTorganization = {},
- publisher = {Springer-Verlag},
- OPTnote = {},
- OPTannote = {}
+ publisher = {Springer-Verlag}
}
+
@PhdThesis{Jer2000,
author = {Anja Jerichow},
- title = {Generalisation and Security Improvement of Mix-mediated Anonymous Communication},
+ title = {Generalisation and Security Improvement of
+ Mix-mediated Anonymous Communication},
school = {Technischen Universitat Dresden},
- year = {2000},
- OPTkey = {},
- OPTtype = {},
- OPTaddress = {},
- OPTmonth = {},
- OPTnote = {},
- OPTannote = {}
+ year = 2000
}
Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -d -r1.19 -r1.20
--- taxonomy.tex 22 Aug 2002 08:47:26 -0000 1.19
+++ taxonomy.tex 31 Aug 2002 02:12:02 -0000 1.20
@@ -9,6 +9,10 @@
\bibliographystyle{try1}
\newtheorem{exa}{Example}
+\newcommand{\piece} {\mathbin{\mathit{frac}}}
+\newcommand{\minf} {\mathbin{f_\mathit{min}}}
+\hyphenation{an-o-nym-i-ty}
+
\begin{document}
\pagestyle{plain}
@@ -109,8 +113,12 @@
of 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.
-%cite?
+have proved difficult to build. More importantly, source authentication
+on links would trivially defeat the very anonymity free-route mix networks
+are intended to protect.
+%i added the phrase free-route here, so we don't have people jumping
+% up and down saying "but you can do it if you have a cascade topology
+% and give out blinded tokens" -rd
Thus, the threat of the active
attacker comes from him having the power to log and manipulate
messages on the links.
@@ -126,11 +134,11 @@
It is well known that the ability to insert or delay messages may
allow the attacker to determine, for instance, the recipient of a
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, 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
+the case of a single threshold $n$ mix\footnote{The same attack can be
+ used against a mix cascade by mounting it against the first mix, 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
it. He now starts sending messages into the mix until it fires. As
soon as the mix fires, he stops all other messages from entering the
@@ -202,10 +210,22 @@
%about these definitions? Would you care to throw a few symbols in? (I
%don't want to build an entire model in this paper!))
-\section{Simple Mix Flushing Algorithms}
+\section{Simple Mixes}
-In describing the different mix flushing algorithms and working out
-their properties, we make several assumptions:
+In this section we describe various mixes divided according to
+their flushing algorithms. In particular we set out for each mix type:
+mix parameters, what the flushing algorithm is, the delay on messages
+in normal operations (i.e., when not under attack), the minimum
+anonymity provided against a passive adversary, analysis of the
+blending attacks on the mix, and finally a discussion of the
+adversaries capable of performing blending attacks. This section
+describes simple mixes, in which all of the messages in the mix are
+sent each time it fires. The more complex pool mixes are discussed in
+the next section.
+
+In describing the
+different mix flushing algorithms and working out their properties, we
+make several assumptions:
\begin{itemize}
@@ -251,7 +271,7 @@
Assuming a constant rate of arrival of messages $r$, we can calculate
the mean delay: $\frac{n}{2r}$.
-\paragraph*{Anonymity:} $n$.
+\paragraph*{Anonymity:} The minimum anonymity set is $n$.
We assume that all the messages in the batch are from different senders
(and go to different receivers).
@@ -348,7 +368,7 @@
noted, the delays could be caused by insertions.} We also note that
this ``attack'' can happen naturally in low traffic conditions, so a
dishonest mix may be able to attack the next hop of a message simply
-by holding it until the next hop is empty.
+by holding it until the next hop is empty and about to fire.
%(AAS comment: Verification comments should go here!)
\subsection{Threshold Or Timed Mix}
@@ -361,7 +381,7 @@
the mix.
\paragraph*{Message Delay:}
-The maximum message delay is $t$, the minimum is $\epsilon$.
+The maximum message delay is $t - \epsilon$, the minimum is $\epsilon$.
\paragraph*{Anonymity:}
The minimum anonymity set is $0$ -- no messages arrive during the
@@ -389,7 +409,7 @@
accumulated in the mix.
\paragraph*{Message Delay:}
-The minimum delay is $0$, and there is no maximum delay.
+The minimum delay is $\epsilon$, and there is no maximum delay.
\paragraph*{Anonymity:}
The minimum anonymity of this mix is $n$. The maximum anonymity is in
@@ -448,8 +468,13 @@
\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
-in the mix. The other $n$ are forwarded on.
+messages (chosen uniformly at random from all the messages) is
+retained in the mix. (This can be thought of as the feedback into the
+mix, hence the variable name.) The other $n$ are forwarded on. Note
+that the threshold is the threshold of messages that must be received
+to fire again during ongoing operation. For pool mixes this is
+distinct from the `threshold' of messages to fire when the mix is
+completely empty, e.g., $n+f$ for the current mix type.
\paragraph*{Message Delay:}
The minimum delay is $\epsilon$, the maximum delay is infinite --- until
@@ -591,19 +616,19 @@
potentially, a whole host of other features). Of course, in practice,
a record of only the last few rounds gives a good approximation.
-The minimum anonymity of a timed pool mix is clearly smaller
-than that of the threshold pool mix. We stress that in pool mixes the
-bulk of the anonymity comes from mixing the target message with the
-batch of incoming messages, not from mixing it with the messages in
-the pool. Because the timed mix does not always have this batch of
-messages for mixing the target message, its minimum anonymity should
-be considered to be very much worse than that of the threshold pool
-mix.
-% can we talk about this a bit more? i want some better intuition
-% here. it will let us answer questions like "for the cottrell mix,
-% when you have more than $min$ messages but less than $min*frac$,
-% do you fire, even tho you'd end up with less than $min$ in the
-% pool? or do you fire but always maintain $min$ in the pool?"
+The minimum anonymity of a timed pool mix is clearly smaller than that
+of a threshold pool mix (unless the threshold is $1$). If the pool is
+small relative to the batch size, then the bulk of the anonymity comes
+from mixing the target message with the batch of incoming messages,
+not from mixing it with the messages in the pool. Because the timed
+mix does not always have this batch of messages for mixing the target
+message, its minimum anonymity should be considered to be very much
+worse than that of the threshold pool mix unless a large pool is
+maintained. As was shown in \cite{Serj02}, the anonymity contribution
+of pool messages is quantifiably greater than those of batch messages.
+So a larger pool is always preferable from this perspective. Of course
+this would have an impact on message delay, reducing one of the
+potential advantages of having a timed mix.
\paragraph*{Blending Attack Behaviour:}
Two flavours of blending attack are possible on this mix. The adversary
@@ -641,50 +666,80 @@
based on whether he can send out many messages or delay messages to a
mix for a long time.
-\subsection{Cottrell Mix (Timed Dynamic-Pool Mix)}
+\subsection{Timed Dynamic-Pool Mix (Cottrell Mix)}
\paragraph*{Parameters:}
-$t$, period; $min$, pool; $frac$, fraction; ($0$, threshold).
+$t$, period; $\minf$ minimum pool; $\piece$, fraction of messages to be
+sent; ($n$, threshold)
+
\paragraph*{Flushing Algorithm:}
-The mix fires every $t$ seconds. A fraction $frac$ of randomly
-chosen messages inside the mix at the time remain in the mix. But if
-there are $min$ or fewer messages in the pool, it outputs no messages.
+The mix fires every $t$ seconds, provided there are $n+\minf$ messages
+in the mix; however, instead of sending $n$ messages (as in a
+timed-and-threshold constant-pool mix), the mix sends the greater of
+$1$ and $\lfloor m*\piece \rfloor$ messages, and retains the rest in
+the pool, where $m+\minf$ is the number of messages in the mix ($m
+\geq n$). If $n=1$, this is the mix that has been used in MixMaster
+remailer system for years. We will continue to use the term `Cottrell
+mix' for $n=1$ and `timed dynamic-pool mix' for the more general case
+when $n$ might be greater than one. Although the Cottrell mix has been
+used in Mixmaster, it has never been previously described or
+analyzed.\footnote{This is the Mixmaster mix design as given in
+ personal communication from Lance Cottrell, the original designer
+ and implementer of MixMaster. It is also the one used in the
+ current MixMaster network. \cite{Jer2000} describes a different mix
+ that is called ``Mixmaster'' therein.} We believe this paper is the
+first place that more general dynamic-pool mixes have been introduced.
+We have called constant-pool mixes simply `pool mix' up to now for
+consistency with the previous literature. Hereafter, `pool mix' will
+refer to either constant or dynamic pool mixes.
-%Note that if there are $min$ messages in the mix, a flush does not cause
+When messages arrive at a constant rate of $1$ per period, Cottrell
+mixes are equivalent to both timed mixes and threshold-$1$
+constant-pool mixes. Specifically, if the rate $r$ of message arrival
+is $1/t$, then the mix will forward $1$ message in every period and
+retain $\minf$ in the pool. For a general Cottrell mix, if the
+messages arrive at a constant rate of $n*\piece/t$ and $\lceil
+n*\piece \rceil = n*\piece$, then this is equivalent to a
+constant-pool mix with threshold of $\minf+n(1-\piece)$.
+%Note that if there are $min$ [now \minf-1 -PFS] messages in the mix,
+%a flush does not cause
%any messages to be put out onto the network. But it is still a logical
%flush.
% commented out for now. if we're using this to introduce dummy traffic
% later, we can say it then -RRD
-This mix has been used in the Mixmaster remailer system for a number of
-years, but has not been described or evaluated before.
-
-%Good, thank you for that!
\paragraph*{Message Delay:} Like the other pool mixes, the
-minimum delay is $\epsilon$ and there is no upper limit on the delay.
+minimum delay is $\epsilon$, and there is no upper limit on the delay.
The mean delay depends on the future rate of arrival of messages into
-the mix. If the rate is high enough that exactly $n*frac$ messages are
-getting sent out on each flush, the mean delay is $1+frac$ rounds.
-This is in general higher than that of the timed pool mix.
+the mix; it is at least as high as that of a timed constant-pool mix
+and typically higher.
\paragraph*{Anonymity:}
-The Cottrell mix has identical minimum and maximum anonymity
-properties compared to a timed pool mix. We could similarly use a log
-of the mix's activity to calculate the anonymity of a message passing
-through it (although the calculation would be slightly different).
-Also, we note that the anonymity provided by the mix would be higher
-than that provided by a timed mix (as the number of messages in the
-mix goes up, $frac$ keeps the chance of the message remaining in the
-mix constant, whereas it decreases in the case of the timed pool mix).
+The dynamic-pool mix has identical minimum and maximum anonymity
+properties compared to a timed constant-pool mix. We could similarly
+use a log of the mix's activity to calculate the anonymity of a
+message passing through it (although the calculation would be slightly
+different). Also, we note that the anonymity provided by the mix
+would be higher than that provided by either a timed or threshold
+constant-pool mix: As the number of messages in the mix goes up,
+$\piece$ keeps the chance of the message remaining in the mix
+constant, whereas it decreases in the case of the timed constant-pool
+mix. While the chance of a message remaining in a threshold
+constant-pool mix is also constant for each flush, increased
+message rate causes increased flushing, thus reducing the chance of a
+message remaining in the constant-pool threshold mix per unit time.
\paragraph*{Blending Attack Behaviour:}
-The introduction of the dynamic parameter $frac$ has several
-new consequences compared to the timed pool mix.
+The introduction of the dynamic parameter $\piece$ has several
+new consequences compared to the timed constant-pool mix.
Firstly, the maximum probability of flushing the mix of good messages
-in one flush is $frac$. Therefore there is no possibility of flushing
-the mix with high probability in one flush: the first of the two
-blending attacks on timed pool mixes is blocked.
+in one flush is $\piece$. Therefore there is no possibility of
+flushing the mix with high probability in one flush: the first of the
+two blending attacks on timed constant-pool mixes is blocked. As
+already noted, it is similarly more resistant to flooding than is a
+constant-pool threshold mix. Indeed, this greater resistance to
+blending attacks is the motivation for that design feature.
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
@@ -693,28 +748,28 @@
%FIXME can you elaborate more on this, andrei?
%Not worth putting in, IMO but:
%We can either use the number of messages the attacker put in, the
-%number that came out and, knowing frac, work out the number of good
+%number that came out and, knowing \piece, work out the number of good
%messages remaining %(trivial, think about it!)
%or just let the mix alone for a while until it outputs nothing
%in which case $min$ messages remain.
%
Finally, the number of messages inside the pool mix may be arbitrarily
-high and cannot be reduced to below $min$ in one round. Therefore, if
-we wish to send a message
-that is harder to track, we should send it at a time of higher
-traffic --- thereby increasing the cost (in terms of messages or time)
-of attempted attacks on it.\footnote{Unfortunately, an attacker capable
-of arbitrary message insertions, as we have been assuming, will make it
-hard to determine times of higher legitimate traffic.}
+high and cannot be reduced to below $\minf$ in one round. Therefore,
+if we wish to send a message that is harder to track, we should send
+it at a time of higher traffic --- thereby increasing the cost (in
+terms of messages or time) of attempted attacks on
+it.\footnote{Unfortunately, an attacker capable of arbitrary message
+ insertions, as we have been assuming, will make it hard to determine
+ times of higher legitimate traffic.}
%\footnote{At times of high traffic, the mix will contain
-%many more messages than $min$, and to flush it free of good messages
+%many more messages than $minf$, and to flush it free of good messages
%will require either more time or more messages from the attacker.}.
%
-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
-therefore for a substantial time.
+Thus timed dynamic-pool mixes requires the attacker to be able to
+delay all the traffic to the mix for a substantial number of rounds,
+and therefore for a substantial time.
\begin{exa}
A Cottrell mix with a pool of 60 messages and fraction of
@@ -744,10 +799,10 @@
%opinion could lead to a very much stronger system.
We note that the minimum anonymity of the Cottrell mix is still very
-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 believe
+much worse than that of the threshold constant-pool mix (where the
+threshold size is much larger than the pool size). Therefore, we
+propose a larger threshold timed dynamic-pool mix will have better
+minimum anonymity properties. We believe
%We shall not go into any more detail other than to say
%that it is intuitively clear that
this modification will not have
@@ -779,7 +834,7 @@
of the number of messages in the mix. Thus, it would take the attacker
several rounds to establish with any confidence the number of
good messages in the mix initially, and he can never be exactly
-sure of that figure.
+sure of that figure (unless he has the whole history).
While introducing randomness is a promising direction, note that it would
not increase the cost of the attack significantly (if at all). Thus,
@@ -854,16 +909,17 @@
prevent wholescale (unobservable!) anonymity compromise. Methods to
detect an attack afterwards, e.g. by checking for successful delivery
of test messages at the end of the cascade \cite{casc-rep}, can help
-detect misbehaving mixes --- but they still allow the adversary to
-uncover a few messages before he is noticed. As we design new
-protocols and batching approaches, we must consider this tradeoff
-between protection from blending attacks and verifiability.
+detect misbehaving mixes --- but this only works for cascades, and it
+assumes that which messages are test messages can be hidden from the
+cascade head. As we design new protocols and batching approaches, we
+must consider this tradeoff between protection from blending attacks
+and verifiability.
\subsection{Cover Traffic}
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
+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.
@@ -889,11 +945,7 @@
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 (possibly in some format that can be
-automatically discarded
-% no -- because then we make them distinguishable by the adversary
-% too. this problem is very very hard.
-). However, providing complete protection with
+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
@@ -903,11 +955,12 @@
%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).
+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).
% What if we always filled the outgoing batch up to some threshold?
% Then the issue wouldn't be orthogonal, right? Hrm. Padding question;
% hard. But I still don't buy that dummies are completely orthogonal
@@ -934,7 +987,7 @@
blending attacks; we leave its analysis for future work.
-\section{Related Work}
+\section{Limitations of Stop-and-Go Mixes}
\label{SG}
While active attacks have been widely cited in the literature and
@@ -942,26 +995,26 @@
most of these have not been rigorously analysed or evaluated
\cite{Cott94,babel,Jer2000,Kesdogan98}.
-We will concentrate our attention on one particular proposal ---
+We now concentrate our attention on one particular proposal ---
Stop-and-Go Mixes \cite{Kesdogan98}. The authors outline several
techniques that could be used to protect mix systems against active
attacks like the ones considered in this work.
The first is a scheme for an anonymity system based on a mix cascade
-that requires authentication. This is based on a stronger
-assumption --- that the attacker cannot mount a distributed $n-1$
-attack where the hostile messages come from different users.
-Unfortunately, it seems very hard to reuse this idea in free route
-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.
+that requires authentication. This is based on a stronger assumption
+--- that the attacker cannot mount a distributed $n-1$ attack where
+the hostile messages come from different users. Unfortunately, it
+seems very hard to reuse this idea in free route 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
-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. Therefore the attacker's ability to delay messages is much
-more limited, so active attacks are harder.
+The second scheme, Stop-and-Go mixes (SG 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. Therefore the attacker's ability to
+delay messages is much more limited, so active attacks are harder.
The attack is uncertain, and the authors argue that the probability of
executing the attack successfully is very low.
@@ -977,6 +1030,8 @@
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.
+(It is conceivable that combining SG mixes with reputation systems
+as in \cite{mix-acc} or \cite{casc-rep} might help.)
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
@@ -1002,8 +1057,53 @@
mixes and as a recommendation to the Mixmaster implementors to alter
the cover traffic policy and introduce thresholds into the mixes.
+\begin{center}
+\renewcommand{\arraystretch}{1.3}
+\begin{tabular}[b]{|l|c||c|c|c||c|c|c|}
+
+\hline
+\multicolumn{2}{|c||}{}&\multicolumn{3}{c||}{Delay} & \multicolumn{3}{c|}{Anonymity} \\
+\cline{3-8}
+\multicolumn{2}{|c||}{} & Avg. & Min. & Max. & Avg. & Min. & Max \\
+
+\hline
+
+ & Threshold & $\frac{n}{2r}$ & $\epsilon$ & $\infty$ & $n$ & $n$ & $n$ \\
+
+\cline{2-8}
+
+ & Timed & $\frac{t}{2}$ & $\epsilon$ & $t-\epsilon$ & $rt$ & 0 & mix capacity \\
+
+\cline{2-8}
+
+\raisebox{1.5ex}[0pt]{Simple } & Thresh.\ or Time & & $\epsilon$ & $t - \epsilon$ & & 0 & n \\
+
+\cline{2-8}
+
+ & Thresh.\ \& Time & & $\epsilon$ & $\infty$ & & $n$ & mix capacity \\
+
+\hline \hline
+Constant & Threshold & $(1+\frac{f}{n+f})\frac{n}{r}$ & $\epsilon$ & $\infty$ & & $\geq n$ & $-\left(1 - \frac{f}{n}\right) \log{(n + f)} + \frac{f}{n}\log{f}$
+ \\
+
+\cline{2-8}
+
+Pool & Timed & & $\epsilon$ & $\infty$ & & $\geq 1$ & $\infty$ \\
+
+%\cline{2-8}
+\hline
+
+Dynamic & Cottrell & & $\epsilon$ & $\infty$ & & $\geq 1$ & $\infty$ \\
+
+\cline{2-8}
+
+Pool & Thresh.\ \& Time & & $\epsilon$ & $\infty$ & & $\geq n$ & $\infty$ \\
+\hline
+
+\end{tabular}
+\end{center}
+
\bibliography{taxonomy}
\end{document}
-
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/