[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] clean up section 2, add more outline for the rest
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
sync-batching.tex
Log Message:
clean up section 2, add more outline for the rest
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- sync-batching.tex 13 Jan 2004 10:08:36 -0000 1.2
+++ sync-batching.tex 13 Jan 2004 15:03:14 -0000 1.3
@@ -21,6 +21,8 @@
% need a better title
\author{Roger Dingledine\inst{1} and Vitaly Shmatikov\inst{2} and Paul Syverson\inst{3}}
+% XXX add a footnote here about David Hopwood, how he should be an
+% author, but we can't find him (but we'll keep trying).
\institute{The Free Haven Project, \email{arma@freehaven.net} \and
Vitaly's affiliation \and
Naval Research Lab, \email{syverson@itd.nrl.navy.mil}}
@@ -93,28 +95,27 @@
equal to the maximum network latency.
This ideal is not achieved by protocols like Mixminion that use locally
-chosen random delays: if the maximum latency of such a network is $t$,
-then the anonymity set of a message leaving the network may be much
-smaller than all messages that entered over a time $t$.
-% This is handwaving, and the problem is more that the distribution
-% isn't uniform rather than the actual size of the anonymity set.
-%In principle, the maximum latency for a message that has just been
-%sent could be infinite, but that's not a significant improvement
-%in practice: if the probability of a given latency t drops off
-%exponentially with t, for example, then so does the probability that
-%a message that is leaving the network could have been sent that long
-%ago.
+computed random delays: if the maximum latency of such a network is $t$,
+%then the anonymity set of a message leaving the network may be much
+%smaller than all messages that entered over a time $t$.
+%More precisely,
+the probability that a message leaving the network corresponds to a given
+input message might be considerably higher than for other messages that
+have entered over a time $t$.
+(In principle, the maximum latency for a message that has just been
+sent could be infinite, but that's not a significant improvement
+in practice: if the probability of a given latency $t$ drops off
+exponentially with $t$, for example, then so does the probability that
+a message that is leaving the network could have been sent that long
+ago \cite{Diaz02,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 described in Section 4 of \cite{disad-free-routes}. (See
Section \ref{subsec:disad} below.)
-Here we present a strategy called {\em synchronous batching}. This
-approach seems to prevent these attacks even when free routes are used,
-and seems to improve the trade-off between latency and anonymity.
-
-The network has a fixed {\em batch period}, $t_\mathrm{batch}$, which
+In the \emph{synchronous batching} approach,
+the network has a fixed {\em batch period}, $t_\mathrm{batch}$, which
is closely related to the maximum desired latency; a typical value
could be 3--6 hours. Messages entering the network in each batch
period are queued until the beginning of the next period. They are
@@ -122,9 +123,10 @@
{\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
-to their final destinations $\ell$ hop periods later. Each subheader of a
-message specifies the hop period in which it must be received, so that it
-cannot be delayed by an attacker (which would be fatal for this design).
+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. % (which would be fatal for this design).
%[[Explain why this prevents the attacks in [disad-free-routes], even
%for free-route networks. Also explain why we need to use a hybrid
%free-route/cascade approach (otherwise the anonymity set is limited by
@@ -132,7 +134,7 @@
The set of messages sent to a node in a given hop period is called a
mini-batch, to distinguish it from the set of messages being sent
-through the network as a whole. [[need better name?]]
+through the network as a whole. % [[need better name?]]
Define the {\em width} $w$ of a mix network using synchronous batching to
be the number of nodes that simultaneously process messages in each hop
@@ -148,11 +150,10 @@
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$, so the
-latency is at most $2t_\mathrm{batch}$ independent of the path length
-$\ell$.
+latency is at most $2t_\mathrm{batch}$, independent of the path length.
Let $T_\mathrm{batch}$ be the expected throughput in a single batch period,
-i.e. the number of messages that go through the network in a batch.
+i.e.~the number of messages that go through the network in a batch.
We can give nodes the maximum opportunity to make use of the available
bandwidth by setting $t_\mathrm{hop} \simeq t_\mathrm{batch}/\ell$.
@@ -167,39 +168,25 @@
\subsection{The disadvantages of free MIX routes}
\label{subsec:disad}
-\subsection{Blending attacks}
-
-\subsection{Mixminion}
-
-\subsection{S-G mixes}
-
-\subsection{Robust mixes}
-flash
+go through the claims in the paper and refute them
-\section{Scenarios}
+\subsection{Blending attacks}
-\section{Graphs and Analysis}
+talk about active attacks. how effective they can be on
+free-routes. and particularly on cascades. talk about
+pools, and tickets, and rgb mixes, and mix-acc. refer to a
+section later in the paper where we'll talk about active
+attacks on the matrix topology.
-\section{Extensions and Future Work}
+\subsection{Mixminion}
-In practice, several considerations have to be balanced when choosing
-a batching strategy and network structure. These include maximizing
-anonymity sets (both batch sizes through each node and the overall
-anonymity sets of users); bandwidth considerations; reliability;
-enabling users to choose nodes that they trust; and interactions with
-the reputation system.
+explain the current free route node selection. motivation for
+loosely federated network. number of nodes.
-Further analysis of the trade-offs will be needed before choosing a
-final network structure. Note that a planned structure, where each
-users' software follows the plan consistently when constructing
-routes, will generally be able to achieve stronger and more easily
-analysed security properties than less constrained approaches.
+\subsection{S-G mixes}
-Possible extension: Note that synchronous batching does not necessarily
-mean a "one latency fits all" approach. People who want a larger anonymity
-set can agree to send their messages only at intervals of k*t_batch,
-so those batches will have more messages (but at the expense of the
-other batches).
+[they do delays, which improve anonymity. no reason why we couldn't
+too, really.]
Possible extension: for the purpose of discussion, let's use
t_batch = 3 hours and t_hop = 1 hour / n. Then the latency is between
@@ -231,6 +218,97 @@
t1_end" and "send between t2_start and t2_end, chosen uniformly at random".
This can support almost all batching designs.
+
+\subsection{Robust mixes}
+
+flash
+
+paul: can you explain how this approach differs from the robust mix
+designs, and why it's still reasonably practical?
+
+\section{Scenarios}
+
+explain threat model: adversary can see all incoming and outgoing
+messages at the network edges
+and has a chance for each node of compromising it
+
+he can't control which node he gets, because we use a
+communal-randomness-based topology randomization a la casc-rep.
+(though still, some nodes will refuse to be exit nodes, and some will be
+ok with it, so compromising the ones that are ok with it will give you
+a better shot at owning an exit node in the resulting topology.)
+
+assume we have 16 or so nodes, each of which can comfortably handle
+1/4 of the traffic, but none of which can comfortably handle all of the
+traffic. so what topology is best?
+
+We use the entropy-based approach from \cite{Diaz02,Serj02}.
+
+scenario 1: cascade network (network of cascades)
+walk us through calculating entropy for a 2x2 cascade network.
+
+scenario 2: matrix
+walk us through calculating entropy for a 2x2 matrix (4 nodes)
+
+scenario 3: practical free-route
+walk us through calculating entropy for a 4x4 free-route (4 nodes)
+scenario 3b: practical free-route but message never stays at the same
+hop adjacently. this is better for high-adversary-percentage, worse
+for low-adversary-percentage? or always better?
+
+scenario 4: latin square free-route
+
+discuss robustness: scenario 4 is clearly least robust. 1-3 are the same,
+maybe 3b is a bit bad.
+
+also discuss how scenarios 3-4 make a different assumption about the
+adversary, since watching all the nodes requires more power than just
+watching the entry and exit columns.
+
+also, notice that since the batch period is large and the hop period is
+short, most of the nodes will be idle nearly all the time in scenarios
+1 and 2, whereas they get used at every hop in scenarios 3 and 4. so
+scenario 4 is not so farfetched, if we can convincing ourselves that
+the reliability issues aren't bad.
+
+\section{Graphs and Analysis}
+
+show entropy graphs. talk a bit about which one's best for which
+situation.
+
+does number of messages influence things? that is, does too few messages
+screw things up more for one topology than for another?
+
+active attacks can mess up the calculations? or is the entropy with a
+baseline network plus hostile messages the same as the entropy of the
+baseline network by itself? that would be neat.
+in any case, there's also the issue that directed floods can fill up
+nodes. this is very bad.
+
+talk about the possible uses of some minimum level of padding on each
+link.
+
+\section{Extensions and Future Work}
+
+In practice, several considerations have to be balanced when choosing
+a batching strategy and network structure. These include maximizing
+anonymity sets (both batch sizes through each node and the overall
+anonymity sets of users); bandwidth considerations; reliability;
+enabling users to choose nodes that they trust; and interactions with
+the reputation system.
+
+Further analysis of the trade-offs will be needed before choosing a
+final network structure. Note that a planned structure, where each
+users' software follows the plan consistently when constructing
+routes, will generally be able to achieve stronger and more easily
+analysed security properties than less constrained approaches.
+
+Possible extension: Note that synchronous batching does not necessarily
+mean a "one latency fits all" approach. People who want a larger anonymity
+set can agree to send their messages only at intervals of k*t_batch,
+so those batches will have more messages (but at the expense of the
+other batches).
+
%\section*{Acknowledgements}
%======================================================================
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/