[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] polish 7.3, plus fixes throughout
Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching
Modified Files:
sync-batching.bib sync-batching.pdf sync-batching.tex
Log Message:
polish 7.3, plus fixes throughout
first draft of the paper is done, minus some responses from paul
Index: sync-batching.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.bib,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- sync-batching.bib 26 Jan 2004 03:55:52 -0000 1.7
+++ sync-batching.bib 26 Jan 2004 17:16:17 -0000 1.8
@@ -1,3 +1,14 @@
+
+@InProceedings{pfitzmann85,
+ author = {Andreas Pfitzmann and Michael Waidner},
+ title = {Networks Without User Observability -- Design Options},
+ booktitle = {Proc. of {EUROCRYPT} 1985},
+ year = 1985,
+ publisher = {Springer-Verlag, LNCS 219},
+ www_section = comm,
+ www_html_url = "http://www.semper.org/sirene/publ/PfWa_86anonyNetze.html";,
+}
+
@InProceedings{sybil,
author = "John Douceur",
title = {{The Sybil Attack}},
@@ -262,11 +273,11 @@
Issues in Anonymity and Unobservability},
year = {2000},
month = {July},
- pages = {30--45},
editor = {H. Federrath},
publisher = {Springer-Verlag, LNCS 2009},
www_pdf_url = {http://www.tik.ee.ethz.ch/~weiler/lehre/netsec/Unterlagen/anon/disadvantages_berthold.pdf},
}
+% pages = {30--45},
@Misc{realtime-mix,
author = {Anja Jerichow and Jan M\"uller and Andreas Pfitzmann and
@@ -408,7 +419,7 @@
@inproceedings{langos02,
title = {Dummy Traffic Against Long Term Intersection Attacks},
author = {Oliver Berthold and Heinrich Langos},
- booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2002)},
+ booktitle = {Proc. Privacy Enhancing Technologies workshop (PET 2002)},
year = {2002},
month = {April},
editor = {Roger Dingledine and Paul Syverson},
Index: sync-batching.pdf
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.pdf,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -d -r1.11 -r1.12
Binary files /tmp/cvsfrBqzj and /tmp/cvsu1734v differ
Index: sync-batching.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/sync-batching/sync-batching.tex,v
retrieving revision 1.46
retrieving revision 1.47
diff -u -d -r1.46 -r1.47
--- sync-batching.tex 26 Jan 2004 15:58:36 -0000 1.46
+++ sync-batching.tex 26 Jan 2004 17:16:17 -0000 1.47
@@ -67,7 +67,7 @@
choose paths freely, and a cascade network, in which senders choose from
a set of fixed paths. We show that free-route topologies can provide
better anonymity as well as better message reliability in the event of
-node failure.
+partial network failure.
\end{abstract}
%======================================================================
@@ -102,7 +102,8 @@
uses a particular network topology. We show that synchronous batching
prevents these attacks even when free routes are used. Further, we
explore three topologies with synchronous batching---cascade, stratified
-(a restricted route), and free-route---and find that the free-route
+(a restricted-route hybrid topology), and free-route---and find that
+the free-route
network provides the highest expected anonymity as well as the best
robustness to node failure.
@@ -126,7 +127,8 @@
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
-requirements and robustness. %, and wrap up in Section~\ref{sec:conclusion}
+requirements, latency, and robustness.
+%, and wrap up in Section~\ref{sec:conclusion}
%with future work and possible extensions.
\section{Synchronous batching}
@@ -223,7 +225,7 @@
{\bf{Position in mix route:}} This attack partitions messages that go
through a given honest node based on how many hops each message has
-travelled so far. If the adversary owns all other nodes in the network,
+traveled so far. If the adversary owns all other nodes in the network,
he can distinguish messages at different positions in their path (say,
one has passed two mixes already, and another has passed three), and
thus learn the sender and recipient of each message. The authors note:
@@ -593,7 +595,7 @@
Second, how bad is it when a link varies by half the expected volume? If
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 affect the
+Another significant question is how the number of layers affects the
results: the more layers, the greater the chance that some of them will
well balanced. But, the exact relation and its effect on entropy are
open questions.
@@ -698,10 +700,10 @@
be 8, and indeed the latency could be cut to between 3 hours and 3 hours
45 minutes---but the expected entropy would be cut by a factor of $\ell$.
-Bandwidth is acceptable. Assuming a higher load of 1280 messages per
+Bandwidth is acceptable. Assuming a higher load of 5000 messages per
batch, and 32KB per message (as in Mixminion), nodes in the free-route
-system spend less than 4KB/s on batch (nodes in the other
-topologies need 16KB/s but only 1/4 of the time). That's well within
+system use less than 4KB/s (nodes in the other
+topologies use 16KB/s but only 1/4 as often). That's well within
the capabilities of current Mixmaster nodes.
%If it were desired to
@@ -739,25 +741,29 @@
\subsection{Robustness of Message Delivery}
-Better security can be achieved by longer routes. For example, if we
-formed our 16 nodes into a 1x16
+Better entropy can be achieved by longer routes: e.g., if we
+form our 16 nodes into a 1x16
cascade or a 16x16 free-route, there is almost no falloff in entropy
until each node has a ninety
percent chance of being compromised. But this ignores robustness of
message delivery. % (We discuss robustness of anonymity to active attacks
%below.)
-For the free-route 16x16 mixnet with only a single node failure (and for
-randomly chosen routes through this mixnet) nearly two thirds of
+For the free-route 16x16 mixnet with only a single node failure,
+% (and for
+%randomly chosen routes through this mixnet)
+nearly two thirds of
messages will be undelivered (because they will need to pass through
-it at some point). Such a network is very brittle. For the 1x16 cascade, it
+it at some point).
+% Such a network is very brittle.
+The 1x16 cascade
is even worse: a single node crash blocks all message delivery.
(We might take advantage of schemes to bypass a single failed node
\cite{pfitzmann85}, but it's not clear how this works with the synchronous
approach.)
Parallel cascades can be added to the network, but unlike the
free-route, they will \emph{a priori} reduce the entropy of an input
-message for a given size mixnet batch. Robustness is an
-important question.
+message for a given size mixnet batch. We must be sure to consider
+robustness when comparing topologies.
\begin{table} \caption{Percent of messages delivered}
\label{table:expected-delivery}
@@ -820,26 +826,25 @@
\subsection{Robustness of Anonymity}
\label{subsec:anonymity-robustness}
-Robustness of anonymity against active attacks is harder to determine
-as these can take on such a variety of forms. In the simplest case
+Robustness of anonymity against active attacks is harder to determine,
+as such attacks can take on a variety of forms. In the simplest case
though, we can consider the effect on anonymity of simple node
crash, since this is the most straightforward way to actively shrink
anonymity. Also, as discussed in Section~\ref{subsec:blending}, there
are techniques
to detect and/or punish more selective attacks.
-The threat model we consider in this section is an extension of the
-one in Section~\ref{sec:scenarios}. As before, senders of messages
-input to the mixnet and receivers of messages output from the mixnet
-can be observed. But now, besides failing to mix, hostile nodes may
-also crash, failing to deliver any of their input messages. A
+The threat model we consider here is an extension of the
+one in Section~\ref{sec:scenarios}. As before, the adversary can watch
+senders and receivers. But now, besides failing to mix, hostile nodes may
+also crash---failing to deliver any of their input messages. A
combination of active attacks and observations (including some
internal observations) should prove the most devastating to anonymity.
However, we leave full examination of this for future work. Here we
concentrate on the effect of such intentional crash failures on
entropy for a mixnet periphery observer.
-Anonymity of cascades are unaffected by this threat model. Since each
+Anonymity of cascades is unaffected by this threat model. Since each
cascade batch is independent of the others, any node that crashes will wipe
out all the messages in that anonymity set. Anonymity robustness of
stratified and free-route topologies is more complex.
@@ -860,27 +865,28 @@
network given node crashes is usually better and at worst equal
to that of the cascade topology.
-For free routes, it is even more difficult to determine the anonymity
-effect of node crash. For entry layer nodes, obviously the initial
-effect of each crash is smaller. However, since nodes are used at
-multiple layers, a message that reaches a crashed node at a given
-layer could not have been routed through that node at any earlier
-layer. And, by crashing nodes in order, some additional information
-may be gained. Add to this that, as the ratio of input messages to
+Free routes are even more complex. For entry layer nodes, the initial
+effect of each crash is clearly smaller. However, since nodes are
+used at multiple layers, a message that reaches a crashed node at a
+given layer could not have been routed through that node at any earlier
+layer. Further, the attacker may gain additional information by crashing
+nodes only at certain hops! Even worse, as the ratio of input messages to
width of a layer shrinks, it becomes more likely that nodes at a given
-layer will only receive messages from a subset of nodes at the
-previous layer or, in any case, that the layer distribution will be
-unbalanced between nodes to a significant degree. On the other hand,
-because nodes are recycled for use at multiple layers, it is much
-harder to plan an attack. Crashing an entry node to reduce the
-anonymity of a message at another node may cause that message to be
-blocked when it must traverse the crashed node at a later layer. If
-nodes have the ability to crash intermittently, then this issue goes
-away. But, it will generally be hard to predict when to come up beyond
-a few layers, because the targeted message will likely be coming from
-any of the remaining nodes after that much mingling (route mixing).
+layer will only receive messages from a subset of nodes at the previous
+layer or, in any case, that the layer distribution will be unbalanced
+between nodes to a significant degree.
-To get some handle on this, we will consider a very lucky adversary.
+On the other hand, because nodes are recycled for use at multiple layers,
+it is much harder to plan an attack. If nodes can't crash and then come
+back between hops (perhaps it's hard to do undetectably), crashing an
+entry node to reduce the anonymity of a message at another node may cause
+that message to be blocked when it must traverse the crashed node at a
+later layer. But it will generally be hard to predict when to come up
+beyond a few layers, because the targeted message will likely be coming
+from any of the remaining nodes after that much mixing.
+
+To get some handle on this complex situation, we will consider a very
+lucky adversary.
The adversary controls a quarter of the nodes in a 16x4 recycling
free-route. Suppose a message enters the mixnet at a node not under
adversary control, and the adversary crashes all of its nodes.
@@ -892,21 +898,25 @@
layer-3 and layer-4. Remaining messages are down to .32 of the
original mixnet batch. In this case, despite all the luck of the
adversary, the anonymity is thus still better than that of a message
-sent into a cascade processing a quarter of the original mixnet batch. And
-this is also better than the anonymity of the stratified 4x4 network
-with just two hostilely crashed entry nodes.
+sent into a cascade processing a quarter of the original mixnet batch.
+% And
+%this is also better than the anonymity of the stratified 4x4 network
+%with just two hostilely crashed entry nodes.
+%% Paul -- how are we comparing this? Isn't two easier than four?
+%% I don't see it. And given that, it's not clear it's helpful here?
+%% Though I guess it would be useful to say that free-route is better
+%% than stratified, if we can compare accurately.
We have not considered all possible active attacks. But for those we
-have considered, the best choice for anonymity robustness of those
-topologies investigated appears to be the free route, and worst is the
-cascade.
+have considered, the best choice for anonymity robustness appears to be
+the free route, and worst is the cascade. We invite further research.
\subsection{Comparison with Asynchronous Batching Designs}
We have shown synchronous free-routes can provide good anonymity, but we
must also begin comparing this design to more traditional asynchronous
free-route designs like Mixminion. Synchronous batching does away with
-the need for a replay cache (each message is labelled with its batch),
+the need for a replay cache (each message is labeled with its batch),
removes partitioning attacks from key rotation, and generally provides
clearer anonymity guarantees.
@@ -933,7 +943,7 @@
synchronous batching compare favorably to cascade networks. We invite
further analysis of the trade-offs between each topology.
-\section*{Acknowledgements}
+\section*{Acknowledgments}
We acknowledge David Hopwood for the initial impetus and ideas; and
we thank Camilla Fox, Rachel Greenstadt, LiWu Chang, Chris Laas, Ira
Moskowitz, and Itamar Shtull-Trauring for probability discussions.
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/