[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] write a lot more. now we have more written.
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
sync-batching.pdf sync-batching.tex
Log Message:
write a lot more. now we have more written.
Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
Binary files /tmp/cvstGXMmi and /tmp/cvsIYEFrC differ
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -d -r1.11 -r1.12
--- sync-batching.tex 21 Jan 2004 00:52:25 -0000 1.11
+++ sync-batching.tex 21 Jan 2004 09:48:46 -0000 1.12
@@ -75,7 +75,7 @@
\end{tightlist}
We investigate synchronous batching in three topologies: cascade,
-systolic array (restricted route), and free-route. We find that the foo
+stratified (a restricted route), and free-route. We find that the foo
topology provides the highest expected anonymity of these three.
%Specifically, whereas
@@ -113,8 +113,8 @@
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.)
+to the attacks from \cite{disad-free-routes} described in
+Section~\ref{subsec:disad} below.
In the \emph{synchronous batching} approach,
the network has a fixed {\em batch period}, $t_\mathrm{batch}$, which
@@ -165,13 +165,8 @@
the bandwidth required through each node in this simplified case
will be $\frac{T_{batch}}{wt_{hop}} = \frac{nT_{batch}}{wt_{batch}}$.
-mix-acc review
-
\section{Related work}
-\subsection{The disadvantages of free MIX routes}
-\label{subsec:disad}
-
Which system is advantageous depends on the adversary model and the
desired security properties. Against an adversary who can observe only
a relatively small percentage of nodes, links, or mixnet entry and
@@ -187,84 +182,113 @@
can only choose a small number of points because
messages can enter and exit the network anywhere.
-go through the claims in the paper and refute them
+\subsection{Sync-batching timing model and protocol}
-\subsection{Blending attacks}
+Dingledine et al.~present in \cite{mix-acc} a mix network that uses
+synchronous batching. We refer to that paper for a detailed discussion
+of the timing model, how to handle loosely synchronized clocks, and the
+step-by-step instructions for senders and mixes to use the network and
+judge whether messages have arrived in time. The paper also describes
+a receipt and witness system by which senders and mixes can prove that
+a given mix failed to pass on a given message. These receipts allow
+a reputation system where nodes that drop messages lose reputation,
+discouraging misbehavior.
-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.
+\subsection{The Disadvantages of Free Mix Routes}
+\label{subsec:disad}
-\subsection{Currently deployed mix networks}
+% This section is based on notes from David Hopwood. Will the real
+% David Hopwood please come forward and become an author?
-Mixmaster/Mixminion: rough number of deployed nodes.
-explain the current free route node selection. motivation for loosely
-federated network.
+Berthold et al.~argue \cite{disad-free-routes} that cascades are safer
+than free-route mix networks against a strong adversary who watches all
+links and controls many of the mixes. We address each of their attacks
+below with respect to a free-route mix network that uses synchronous
+batching.
-Jap: describe overall design -- low-latency. how many cascades are
-there? how long are they? talk about web-mixes ticket design?
+{\bf{Position in mix route:}} This attack partitions messages that go
+through a given node based on how many hops each message has travelled so
+far. Because the adversary owns all nodes in the network but this node,
+he can distinguish messages at different positions in their path, and
+thus learn the sender and recipient of each message. The authors note:
+\emph{Eventually, a message is only unobservable in that group of messages
+which have this mix on the same routing position.} But in the synchronous
+design, that's not a problem because this group is large (if only one
+mix is trustworthy, $1/w$ of all messages in the batch, which is what
+it would be anyway). They conclude: \emph{If only one miX of a route is
+trustworthy, then the achievable anonymity is distinctly lower in a mix
+network compared to a synchronously working mix cascade.} The actual
+conclusion should be: If only one mix of a route is trustworthy, then
+the achievable anonymity is distinctly lower in an asynchronous mix-net
+than in a synchronous mix-net (whether it uses free routes or cascades).
-\subsection{Danezis's restricted routes paper}
+{\bf{Determining the next mix:}} An adversary owning most nodes
+in the network can attack the honest mixes: he can link senders
+to messages entering honest mixes, and he can link receivers to
+messages exiting honest mixes. Thus the target messages will only
+be mixing with other messages that enter the mix node at that time,
+rather than with other messages elsewhere in the network. If senders
+use the same path for multiple messages, the authors point out that
+\emph{the batches always generate different anonymity groups.} Again,
+the important property is whether the network uses synchronous batching,
+not whether it uses free routes. All messages in a batch exit the
+network together after the last hop, so messages cannot be partitioned
+based on when they exit the network. Free-route protocols where each
+sender fixes his path are vulnerable to attacks (e.g. tagging attacks
+\cite{disad-free-routes,raymond00}) that free-route protocols with
+randomly chosen paths can resist \cite{minion-design}, but so long
+as they use synchronous batching, they are not vulnerable to this
+particular attack.
-\subsection{S-G mixes}
+{\bf{Probability of Unobservability:}} The authors show that the cascade
+topology optimizes for the case that only one mix node is honest. They
+give an equation to calculate the chance that a user in a free-route
+system with 75\% compromised nodes will pick a length-4 path of only
+compromised mixes.
-[the sender chooses to delay at certain nodes, which improves anonymity.
-no reason why we couldn't too, really.]
+[I'm not sure what to do with this one. It's clear that we're looking at
+things as "for each node, 75\% chance compromised, and they're looking at
+it as "we know 3 of the 4 are bad". Also, I feel that comparing a 16-node
+free-route with 12 nodes bad to a 16-node cascade network with 12 nodes
+bad is more fair, and maybe also more revealing. Thoughts? This is perhaps
+a form of anonymity-robustness that Paul has been thinking about. -RD]
-Possible extension: for the purpose of discussion, let's use
-$t_\mathrm{batch}$ = 3 hours and $t_\mathrm{hop}$ = 1 hour / n. Then
-the latency is between
-1 and 4 hours, and the anonymity set is the set of messages sent in a
-3 hour period.
+{\bf{Active Attacks:}}
-We can improve this by having a "delay until next batch" option in
-the message subheader; that would delay the message by $t_\mathrm{batch}$ and
-re-introduce it at the same point in the path. If each message is either
-delayed once or not delayed, that gives us a latency of 1 to 4 hours for
-non-delayed messages, 4 to 7 hours for delayed messages, and a 6-hour
-anonymity set (unless the attacker knows that someone never sends or
-receives delayed messages, in which case the anonymity set for those
-users is still 3 hours).
+first knock down their crazy ledger notion.
-Can anyone attack the "delay until next batch" option? I don't think
-the fact that those messages can be distinguished by the node is any
-more harmful than Mixminion's "swap" operation, etc. [It seems a bit
-more harmful: in Mixminion, all messages have a swap point somewhere in
-the path. In this scheme, messages that ask to be delayed are inherently
-more interesting. -RD]
+then knock down the assumption that you can register all your users.
-A generalisation of this is a "source-timed" network: use the timing model
-from \cite{mix-acc} (with or without receipts), where $t_\mathrm{hop}$
-corresponds
-to one time unit, but in each subheader specify "drop if not received in
-period t1" and "send in period t2".
+and hey, mix-acc isn't so bad compared to the ticket scheme.
-Even more general would be "drop if not received between
-$t1_\mathrm{start}$ and $t1_\mathrm{end}$" and "send between
-$t2_\mathrm{start}$ and $t2_\mathrm{end}$, chosen uniformly at
-random". This can support almost all batching designs.
+plus there's randomized partial checking.
-\subsection{Robust mixes}
+\subsection{Blending attacks}
-flash
+In deployed mix networks like Mixmaster and Mixminion, the goal of the
+batching algorithm is to hide from the adversary when an outgoing message
+entered the mix. Mixes `pool' some messages from previous batches, to
+try to mix them as far back as possible. This technique aims to defend
+against \emph{blending attacks} such as the $n-1$ or \emph{trickle}
+attack, where the adversary submits all but one messages in a batch,
+and then learns the destination of the target message. In the synchronous
+batching design, on the other hand, the goal is to mix a message with the
+other messages in its batch. Blending attacks are somewhat mitigated by
+preventing messages from being delayed. An attacker cannot reintroduce
+the messages that he removed; he must permanently trash all the messages
+that are not in the trickle, which will hopefully be noticed.
-paul: can you explain how this approach differs from the robust mix
-designs, and why it's still reasonably practical?
-"I'm not sure it's directly
-relevant. Generally I think people do a bunch of shuffle proofs, etc.
-If the answer doesn't come out as desired, the threshold number of
-guys won't decrypt the final set of messages (i.e., the whole batch
-gets dropped). Also, I think this only applies to re-encryption mixes,
-so, e.g., current remailer networks couldn't be based on them."
+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 stratified topology.
+
+\subsection{Danezis's restricted routes paper}
-The only reason I thought to put these in here is that for some
-reason I thought of them as synchronized-batching. If this is not
-the case, then this subsection should be removed entirely. -RD
\section{Scenarios}
@@ -297,7 +321,7 @@
\hfill
\begin{minipage}[t]{3.5cm}
\mbox{\epsfig{angle=0,figure=sa-2x2,width=3.5cm}}
-\caption{A 2x2 systolic array (4 nodes)}
+\caption{A 2x2 stratified network (4 nodes)}
\label{fig:sa-2x2}
\end{minipage}
\hfill
@@ -309,8 +333,8 @@
\hfill
\end{figure}
-\subsection{Scenario 2: systolic array}
-walk us through calculating entropy for a 2x2 matrix (4 nodes)
+\subsection{Scenario 2: stratified network}
+walk us through calculating entropy for a 2x2 stratified (4 nodes)
\subsection{Scenario 3: free-route}
walk us through calculating entropy for a 4x2 free-route (4 nodes)
@@ -336,16 +360,6 @@
* compare the entropy between 16 nodes: cascade, SA, and free-route
-%\begin{figure}
-%\begin{minipage}[t]{4in}
-%\mbox{\epsfig{angle=0,figure=badnodes,width=4in}}
-%\caption{Entropy vs chance of bad node, for four topologies (16 nodes)}
-%\label{fig:badnodes}
-%\end{minipage}
-%\hfill
-%\end{figure}
-
-
\begin{figure}[ht]
\centering
@@ -364,7 +378,7 @@
\begin{figure}[ht]
\centering
\mbox{\epsfig{angle=270,figure=systhops,width=4in}}
-\caption{Entropy vs number of hops, for systolic array (16 nodes)}
+\caption{Entropy vs number of hops, for stratified network (16 nodes)}
\label{fig:systhops}
\end{figure}
@@ -379,10 +393,19 @@
\section{Other considerations}
-\subsection{Allow loops?}
-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?
+\subsection{Choose path hops with or without replacement?}
+
+Intuitively, when the adversary density is low, entropy is doing
+fine. When it's high, the difference between picking between $B$ and $B-1$
+bad nodes is slight.
+
+More formally, if there are $G$ good nodes and $B$ bad nodes, then the
+chance of selecting a bad node as your next link is $\frac{B-1}{G+B}$ if
+the current node is bad and $\frac{B}{G+B}$ if your current node is good.
+The difference between the two is only $\frac{1}{G+B}$. In particular,
+the difference does not depend on what fraction of the nodes are bad. And
+for reasonably large values of $G+B$ (total number of nodes), the shift
+in probability distribution is negligible.
\subsection{Robustness}
@@ -399,7 +422,7 @@
one percent of messages will be delivered through the network. This
makes such a network very brittle.
-A 4x4 cascade mixnet does much better. A single failed node affects
+A 4x4 cascade network does much better. A single failed node affects
only one quarter of the messages. And two failed nodes have a one in
ten chance of being no worse than a single failed node. On the other
hand there is a ninety percent chance that half the messages are
@@ -428,7 +451,7 @@
failure, since this is the most straightforward way to actively shrink
anonymity. Also, as discussed in Section~\ref{?}, there are techniques
to detect and punish more selective attacks; although a combination of
-active and passive attacks should prove the most devestating.
+active and passive attacks should prove the most devastating.
We can use the observations of the above paragraphs to note that the
16x16 free route has the worst anonymity in the face of any node
@@ -442,10 +465,6 @@
-----------------------------\\
Below was previously in robustness subsec.
-
-scenario 4 is clearly least robust. 1-3 are the same,
-maybe 3b is a bit bad.
-
Two issues: one is robustness with respect to a single message
going through. How likely is it to arrive on time?
But there's a deeper issue: in asynchronous-batching designs, a
@@ -456,6 +475,45 @@
The free-route topology can add a new batch at every hop,
increasing the anonymity everybody gets. maybe.
+\subsection{S-G mixes}
+
+[the sender chooses to delay at certain nodes, which improves anonymity.
+no reason why we couldn't too, really.]
+
+Possible extension: for the purpose of discussion, let's use
+$t_\mathrm{batch}$ = 3 hours and $t_\mathrm{hop}$ = 1 hour / n. Then
+the latency is between
+1 and 4 hours, and the anonymity set is the set of messages sent in a
+3 hour period.
+
+We can improve this by having a "delay until next batch" option in
+the message subheader; that would delay the message by $t_\mathrm{batch}$ and
+re-introduce it at the same point in the path. If each message is either
+delayed once or not delayed, that gives us a latency of 1 to 4 hours for
+non-delayed messages, 4 to 7 hours for delayed messages, and a 6-hour
+anonymity set (unless the attacker knows that someone never sends or
+receives delayed messages, in which case the anonymity set for those
+users is still 3 hours).
+
+Can anyone attack the "delay until next batch" option? I don't think
+the fact that those messages can be distinguished by the node is any
+more harmful than Mixminion's "swap" operation, etc. [It seems a bit
+more harmful: in Mixminion, all messages have a swap point somewhere in
+the path. In this scheme, messages that ask to be delayed are inherently
+more interesting. -RD]
+
+A generalisation of this is a "source-timed" network: use the timing model
+from \cite{mix-acc} (with or without receipts), where $t_\mathrm{hop}$
+corresponds
+to one time unit, but in each subheader specify "drop if not received in
+period t1" and "send in period t2".
+
+Even more general would be "drop if not received between
+$t1_\mathrm{start}$ and $t1_\mathrm{end}$" and "send between
+$t2_\mathrm{start}$ and $t2_\mathrm{end}$, chosen uniformly at
+random". This can support almost all batching designs.
+
+
\subsection{Not enough input messages}
does number of messages influence things? that is, does too few messages
screw things up more for one topology than for another?
@@ -487,9 +545,6 @@
the beginnings of a solution there.
http://freehaven.net/anonbib/\#danezis:pet2003
-
-
-
\subsection{Blending and flooding attacks}
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
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/