[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Tweaks, tweaks, tweaks, hopefully all for the better.

To: freehaven-cvs@freehaven.net
Subject: [freehaven-cvs] Tweaks, tweaks, tweaks, hopefully all for the better.
From: syverson@seul.org
Date: Tue, 27 Jan 2004 03:58:46 -0500 (EST)
Delivered-to: archiver@seul.org
Delivered-to: freehaven-cvs-outgoing@seul.org
Delivered-to: freehaven-cvs@seul.org
Delivery-date: Tue, 27 Jan 2004 03:59:08 -0500
Reply-to: freehaven-dev@freehaven.net
Sender: owner-freehaven-cvs@freehaven.net
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/tmp/cvs-serv7664/sync-batching

Modified Files:
	model.tex sync-batching.bib sync-batching.pdf 
	sync-batching.tex 
Log Message:
Tweaks, tweaks, tweaks, hopefully all for the better.


Index: model.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/model.tex,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- model.tex	27 Jan 2004 03:52:15 -0000	1.8
+++ model.tex	27 Jan 2004 08:58:44 -0000	1.9
@@ -15,7 +15,7 @@
 and use a fully automated probabilistic model checking technique to
 compute probability distributions for different network topologies and
 configurations.  We use \emph{entropy} of each topology's respective
-distribution as our comparison metric, in the spirit of~\cite{Serj02}.
+distribution as our comparison metric, in the spirit of~\cite{Serj02,Diaz02}.
 
 
 \subsection{Mixing as permutation}

Index: sync-batching.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.bib,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- sync-batching.bib	26 Jan 2004 17:16:17 -0000	1.8
+++ sync-batching.bib	27 Jan 2004 08:58:44 -0000	1.9
@@ -60,6 +60,17 @@
 }
 
 
+
+@InProceedings{goldschlag96,
+  author = 	 {David M. Goldschlag and Michael G. Reed and Paul F. Syverson},
+  title = 	 {Hiding Routing Information},
+  booktitle = 	 {Information Hiding: First International Workshop},
+  pages =	 {137--150},
+  year =	 1996,
+  editor =	 {R. Anderson},
+  publisher =	 {Springer-Verlag, LNCS 1174}
+}
+
 @Article{chaum-mix,
    author =      {David Chaum},
    title =       {Untraceable electronic mail, return addresses, and digital
@@ -90,8 +101,9 @@
   month = {March},
   editor = {Roger Dingledine},
   publisher = {Springer-Verlag, LNCS 2760},
-  www_ps_gz_url = {http://www.esat.kuleuven.ac.be/~cdiaz/papers/DS03.ps.gz},
 }
+  www_ps_gz_url = {http://www.esat.kuleuven.ac.be/~cdiaz/papers/DS03.ps.gz},
+
 
 @inproceedings{minion-design,
   title = {Mixminion: Design of a Type {III} Anonymous Remailer Protocol},
@@ -123,7 +135,7 @@
   booktitle = {Proceedings of Information Hiding Workshop (IH 2002)},
   year = {2002},
   month = {October},
-  editor = {Fabien Petitcolas},
+  editor = {F. Petitcolas},
   publisher = {Springer-Verlag, LNCS 2578},
   www_pdf_url = {http://freehaven.net/doc/batching-taxonomy/taxonomy.pdf},
 }
@@ -137,8 +149,8 @@
   editor =	 {Roger Dingledine and Paul Syverson},
   month =     {April},
   publisher =	 {Springer-Verlag, LNCS 2482},
-  note =        {\url{http://www.freehaven.net/papers.html}}
 }
+  note =        {\url{http://www.freehaven.net/papers.html}}
 
 
 @InProceedings{Serj02,

Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
Binary files /tmp/cvsRu1iy9 and /tmp/cvsuXtkAb differ

Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.48
retrieving revision 1.49
diff -u -d -r1.48 -r1.49
--- sync-batching.tex	27 Jan 2004 04:16:26 -0000	1.48
+++ sync-batching.tex	27 Jan 2004 08:58:44 -0000	1.49
@@ -62,7 +62,7 @@
 %Synchronous mixnets are vastly superior to asynchronous mixnets in
 %many ways.
 In a synchronous batching design, each batch of messages enters the
-mix network together, and the messages proceed in lock step through
+mix network together, and the messages proceed in lockstep through
 the network. We show that a synchronous batching strategy can be used
 in various topologies, including a free-route network, in which senders
 choose paths freely, and a cascade network, in which senders choose from
@@ -119,15 +119,15 @@
 %   formally part of the topology.
 
 In Section~\ref{sec:sync-batching} we describe the synchronous batching
-model. Then in Section~\ref{sec:related} we relate previous work
-to synchronous batching, including responding to each of the arguments
+model. Section~\ref{sec:related} relates previous work
+to synchronous batching, including a response to each of the arguments
 from~\cite{disad-free-routes}. Section~\ref{sec:scenarios} presents the
-three topologies in detail, and walks through calculating their entropy
+three topologies, and describes calculating their entropy
 (average anonymity the sender expects from the network). We use a model
-checker to automatically compute entropy for networks with 16 nodes:
+checker to compute entropy for networks with 16 nodes:
 we present our results and assess the assumptions behind them in
-Section~\ref{sec:graphs}. We go on in
-Section~\ref{sec:metrics} to consider other metrics such as bandwidth
+Section~\ref{sec:graphs}.
+Section~\ref{sec:metrics} considers other metrics such as bandwidth
 requirements, latency, and robustness.
 %, and wrap up in Section~\ref{sec:conclusion}
 %with future work and possible extensions.
@@ -160,7 +160,6 @@
 exponentially with $t$, then so does the probability that
 a message leaving the network could have been sent that long
 ago \cite{Serj02}.)
-
 Also, because Mixmaster is both {\em asynchronous} (messages can enter
 and leave the network at any time) and uses free routes, it is subject
 to the attacks from \cite{disad-free-routes} described in
@@ -168,22 +167,21 @@
 
 A network that uses \emph{synchronous batching}
 has a fixed {\em batch period}, $t_\mathrm{batch}$, which
-is related to the maximum desired latency; a typical value
-could be 3 hours.  Messages entering the network in each batch
+is related to the maximum desired latency, for example 3 hours.
+Messages entering the network in each batch
 period are queued until the beginning of the next period. They are
 then sent through the mixnet synchronously, at a rate of one hop per
 {\em hop period}. All paths are a fixed length $\ell$ hops, so that if
 no messages are dropped, the messages introduced in a given batch will
-progress through their routes in lock-step, and will all be transmitted
+progress through their routes in lockstep, and will all be transmitted
 to their final destinations $\ell$ hop periods later. Each layer of a
 message, once decrypted, specifies the hop period in which it must be
 received, so that it cannot be delayed by an attacker.
 
-Define the {\em width} $w$ of a mixnet using synchronous batching to
-be the number of nodes that simultaneously process messages in each hop
+The {\em width} $w$ of a mixnet using synchronous batching
+is the number of nodes that simultaneously process messages in each hop
 period. (If this is not constant, we can still talk about the maximum,
-minimum and mean width.) Thus when $w=1$ we have a cascade.
-
+minimum, and mean width.) When $w=1$, we have a cascade.
 The latency is between $\ell t_\mathrm{hop}$ and $t_\mathrm{batch} +
 \ell t_\mathrm{hop}$, depending on when the message is submitted.
 Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/\ell$,
@@ -221,7 +219,7 @@
 links and controls many of the mixes. We consider each of their attacks
 below and find in each case that the arguments of \cite{disad-free-routes}
 do not apply if the free-route network is synchronous. Indeed, against
-some of the attacks a free-route network is substantially stronger than
+some of the attacks a free-route network is much stronger than
 the cascade network.
 
 {\bf{Position in mix route:}} This attack partitions messages that go
@@ -306,7 +304,7 @@
 receive blinded tickets \cite{chaum-blind} so the mixes cannot
 trivially link them to their messages). Mixes ensure their messages
 come from distinct senders, so Alice can expect good mixing at each
-honest node in her path~cite{web-mix}. For cascades this approach is
+honest node in her path \cite{web-mix}. For cascades this approach is
 clearly efficient, because Alice only needs tickets for her chosen
 cascade~\cite{disad-free-routes}, but her anonymity set is still
 limited to that one cascade. We conjecture that other topologies
@@ -330,9 +328,11 @@
 pool mix to commit to its choice of randomness to allow verifying
 its behavior~\cite{FGJP98}. Link encryption, as well as
 % \cite{Jer2000}
-Babel's \emph{inter-mix detours}, aim to block a limited adversary
-from knowing when his message has exited the mix~\cite{babel}. In
-stop-and-go
+Babel's \emph{inter-mix detours}~\cite{babel} and early Onion
+Routing's \emph{loose routing}~\cite{goldschlag96}, aim to block a
+limited adversary from knowing when his message has exited a mix.
+This also complicates blending because even the sender cannot always
+recognize a message he created.  In stop-and-go
 mixes~\cite{stop-and-go}, each sender specifies a time window for each
 mix in his path: as with synchronous batching designs, messages arriving
 outside the time window are dropped, so the attacker cannot arbitrarily
@@ -376,7 +376,6 @@
 the mixnet (in Section~\ref{subsec:average-actual} we argue that
 with high probability, observing these links will not yield much
 new information anyway).
-
 This paper only examines sender anonymity, though many of the advantages
 of synchronous batching carry over to receiver anonymity.
 
@@ -405,7 +404,6 @@
 being a tractable size for analysis, 16 nodes is also a fairly good
 approximation of actually deployed mixnets. (Mixminion currently has
 between 20 and 30 active nodes.)
-
 Messages proceed through all of our networks in \emph{layers}; all of the
 nodes in a layer process messages of one mixnet batch at the same time.
 In general we describe networks as $w$x$\ell$, where $w$ is the number
@@ -477,7 +475,6 @@
 To keep our model tractable, we have assumed that each node has an
 equal chance of being controlled by the adversary. A real adversary
 might prefer to control certain key nodes in the topology.
-
 To justify our assumption, we might assume that secure nodes (or
 equivalently, vulnerable nodes) are randomly distributed. That is,
 rather than letting the adversary have his pick of nodes, we instead
@@ -551,12 +548,12 @@
 information can be exploited by an adversary to reduce anonymity,
 for example by predicting the user's behavior based on reputation
 statistics, or by attracting more traffic by building a strong reputation
-or degrading the reputation of others. One approach to working within
-these constraints would be to put like-reputationed nodes in the same
-layer of the stratified network, or in the same row of the cascade
-network \cite{casc-rep}, so reputation distribution (at each hop or
-in each cascade, respectively) will be more uniform. We leave this
-investigation to future work.
+or degrading the reputation of others. Placing nodes of similar reputation
+in the same layer of a stratified or cascade network, or placing them
+in the same cascade can complicate these attacks, but employed naively,
+this can facilitate other attacks~\cite{casc-rep}. This
+topic merits further investigation.
+
 
 \subsection{Average Entropy vs Actual Entropy}
 \label{subsec:average-actual}
@@ -597,7 +594,7 @@
 we change our metric to require at least 2 messages on each link for
 $m=128$, then we find that only 1\% of the cases fall outside this value.
 Another significant question is how the number of layers affects the
-results: the more layers, the greater the chance that some of them will
+results: the more layers, the greater the chance that some of them are
 well balanced. But, the exact relation and its effect on entropy are
 open questions.
 
@@ -643,7 +640,7 @@
 mixnet. Similarly, we cannot control the latency that users will be
 willing to accept. To make the analysis more concrete, assume we choose
 $\ell=4$, that users deliver 128 messages every 3 hours, and that users
-will tolerate a latency of 3-6 hours (which is on par with the latency
+will tolerate a latency of 3--6 hours (which is on par with the latency
 experienced by a typical Mixmaster message, though
 they could be much longer in theory).
 
@@ -692,8 +689,8 @@
 in the rate of incoming messages.
 
 In the free-route network, each node needs to process 8 messages at a
-time, and it's active at each layer. The cascade and stratified networks
-require a larger capacity from each node: they must be able to handle 32
+time and is active at each layer. The cascade and stratified networks
+require a larger capacity from each node: they must handle 32
 messages at once (128/$w$), but they are idle for all but one hop in the
 batch. One could imagine a \emph{systolic network} where $t_\mathrm{batch}
 = t_\mathrm{hop}$ and 32 messages are let in every 45 minutes---in this
@@ -809,7 +806,7 @@
 adversary distribution for up to four node crashes. To further
 illustrate, if half of the nodes are bad in the 4x4 cascade topology,
 then in about 1 in 6 cases a quarter of the messages get through, and
-in exactly 6 cases of 12870 half of the messages get through the
+in exactly 6 cases of 12870, half of the messages get through the
 cascades. For all other distributions, no messages get through.  If
 half of the nodes are bad in the 4x4 stratified network, then the
 highest percentage of messages that can pass through is 6.25.
@@ -818,8 +815,9 @@
 
 Of the scenarios we have considered, a 16x4 free route has the best
 expected chance of message delivery for random adversary distribution.
-It outperforms the others unless the adversary has a
-particularly innocuous distribution, in which case cascades do better.
+It outperforms the others, unless the adversary has a particularly
+innocuous distribution. Cascades do better under favorable distributions,
+which are also much rarer for cascades than other topologies.
 Also note that the expected fraction of passed messages is the same
 for free routes regardless of which nodes fail: it is the most robust
 with respect to adversary distribution as well as adversary size.
@@ -926,12 +924,14 @@
 design may fall more quickly to long-term statistical disclosure
 attacks~\cite{statistical-disclosure}. Our design is also less robust
 to transient failures: a late Mixminion message still arrives, whereas
-in our system a node that is down during $t_\mathrm{hop}$ loses all
-messages going through it. But our design can tell the user for sure
-whether his mail was delivered in the batch (and he can resend if not),
-whereas late messages in Mixminion always leave the user wondering if
-it will come out sometime.
-
+in our system a node that is down throughout $t_\mathrm{hop}$ loses all
+messages going through it. (Stratified and cascade networks have the
+the lowest chance of being down in a hop period they are needed, but
+free-route networks lose proportionally fewer messages from a single
+down node.)  But our design can tell the user for sure whether his mail
+was delivered in the batch (and he can resend if not), whereas late
+messages in Mixminion always leave the user wondering if it will come
+out sometime.
 We leave further comparison to future work.
 
 \section{Summary}
@@ -946,7 +946,7 @@
 
 \section*{Acknowledgments}
 We acknowledge David Hopwood for the initial impetus and ideas; and
-we thank Camilla Fox, Rachel Greenstadt, LiWu Chang, Chris Laas, Ira
+we thank LiWu Chang, Camilla Fox, Rachel Greenstadt, Chris Laas, Ira
 Moskowitz, and Itamar Shtull-Trauring for probability discussions.
 
 %======================================================================
@@ -956,7 +956,7 @@
 
 \appendix
 
-\newpage
+%\newpage
 \section{Entropy vs number of hops, for each topology}
 \label{sec:entropy-per-hop}
 

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/
Prev by Author: [freehaven-cvs] Tweaks throughout. Discussion of throughput, latency...
Previous by thread: [freehaven-cvs] Fixed redundant statement in conclusion. Ugh, I rush...
Next by thread: [freehaven-cvs] Incorporate some suggestions from George
Index(es):
- Author
- Thread