[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] r1789: Final version, submitted to WPES 2007. (doc/trunk/pingers)
Author: rabbi
Date: 2007-06-11 00:08:03 -0400 (Mon, 11 Jun 2007)
New Revision: 1789
Modified:
doc/trunk/pingers/echolot.pdf
doc/trunk/pingers/echolot.tex
Log:
Final version, submitted to WPES 2007.
Modified: doc/trunk/pingers/echolot.pdf
===================================================================
(Binary files differ)
Modified: doc/trunk/pingers/echolot.tex
===================================================================
--- doc/trunk/pingers/echolot.tex 2007-06-11 02:09:53 UTC (rev 1788)
+++ doc/trunk/pingers/echolot.tex 2007-06-11 04:08:03 UTC (rev 1789)
@@ -39,8 +39,6 @@
% Blinded for submission
\author {Klaus Kursawe\inst{1} and Peter Palfrader\inst{2} and Len Sassaman\inst{1}}
-
-%foo
\institute{Katholieke Universiteit Leuven\\
Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium\\
\email{\{len.sassaman,klaus.kursawe\}@esat.kuleuven.be}
@@ -51,13 +49,24 @@
}
%foo
+% Cut down on whitespace above and below figures displayed at head/foot of
+% page.
+\setlength{\textfloatsep}{3mm}
+% Cut down on whitespace above and below figures displayed in middle of page
+\setlength{\intextsep}{3mm}
+
+
\date{}
\begin{document}
\maketitle
+%\pagestyle{empty}
+%\centerline{\LARGE\bf DRAFT --- not for publication}
+%======================================================================
+
\begin{abstract}
In a mix-net, information regarding the network health and operational
@@ -90,13 +99,15 @@
the ``Type II'' Mixmaster~\cite{mixmaster-spec} network, and the ``Type
III'' Mixminion network~\cite{mixminion}, as well as the low-latency
network anonymity service Tor~\cite{tor-design}, are operated on a volunteer basis
-and are prone to intermittent failure of individual nodes. It is therefore
+and are prone to intermittent failure of individual nodes.\footnote{Furthermore, the security of these mix-net systems is based on the principle of \emph{distributed trust}: no individual mix is considered to be trusted, but rather the set of mixes chosen by the mix-net client software is presumed to contain enough honest nodes to ensure the security of the communication.} It is therefore
necessary for mix client software to have an accurate view of the health
of the nodes in the mix network. This information is gathered by sending
test messages through each node and observing the success or failure of
the mix to successfully transmit the message. In a similar fashion, links
between mixes are examined by sending messages through every combination
-of two consecutive mixes. Since the overhead and operational complexity
+of two consecutive mixes.
+
+Since the overhead and operational complexity
involved in monitoring an entire network of mixes is too great for the
average user, reliability testing servers, or \emph{pingers}, perform this
function and publish their results in a machine-parseable format. The
@@ -117,17 +128,19 @@
-\section{Related work}
+\section{Related Work}
\label{pingers}
+A variety of pinger software has been available for many years prior to the creation of our pinger implementation, \emph{Echolot}. These pingers, as well as Echolot, fundamentally behave in the same way: they attempt to relay messages through known mixes, record the success or failure of these attempts as well as the latency of the mix, and publish their results for mix-net clients to use. In this section, we briefly describe the other pinger implementations which preceded the creation of Echolot.
+
\subsection{rlist}
Raph Levien introduced the concept of a monitoring service for anonymous
-remailers. His software rlist~\cite{rlist} was at first designed only to work with the
-Cypherpunk remailer network; support for the Mixmaster network was added later.
+remailers. His software rlist~\cite{rlist} was the first remailer reliability service to monitor the status of the system by sending test messages through each known remailer. At first designed only to work with the
+Cypherpunk remailer network, rlist later incorporated support for the Mixmaster network as it became widely deployed.
Once started, rlist would run indefinitely, regularly sending simple test
-messages through remailers and building statistics files.
+messages through remailers and building statistics files, which were obtainable via a \texttt{finger} interface.
% I haven't the slightest clue how rlist comes up with its reliability number.
% it's certainly black magic. -- weasel
@@ -152,7 +165,7 @@
specified times.
Pingstats employs random tokens in message payloads as a counter-measure
-to cheating mixes (see section \ref{section:gaming} below).
+to cheating mixes (see Section \ref{section:gaming} below).
Pingstats presents a more timely view of the state of the network by
using weighted pings for its reliability calculation. Thus, older ping
@@ -178,7 +191,7 @@
% Is it documented anywhere? I suppose you're right. While not useful as
% a remailer, it isn't a terrible pinger. -- rabbi
-\subsection{Mixminion directory server}
+\subsection{Mixminion Directory Server}
Mixminion\cite{mixminion} generalized the concept of pingers, defining a
directory server component of the Mixminion system which is responsible for the
@@ -197,7 +210,7 @@
long-term (signing) public key, short-term (message decryption) public
key, remixing capability, and batching strategy.
-\section{Veracity attacks}
+\section{Veracity Attacks}
\label{section:gaming}
A mix which is otherwise honest (in that it correctly performs mixing
@@ -216,14 +229,14 @@
Mixmaster have a minimum distance between hops which is considered when
creating a mix chain, and thus messages which consist of the mix chain
A,B,A will still be distinguishable as pinger messages, since no properly
-functioning mix client would generate this chain. If a pinger were to
+functioning mix-net client would generate this chain. If a pinger were to
create a chain of A,B,C,A, neither mixes B or C would be able to tell that
the message contained pinger information, but the results would only
indicate the combined latency of the mixes B and C, as well as the health
of both B and C and the link between those mixes. It would not provide any
useful information about B or C alone.
-The pinger message data (or \emph{pings}) itself should not be
+The pinger message data (or \emph{pings}) themselves should not be
deterministic, lest a mix attempt to ``back-fill'' the results for pings
sent during a period when the mix was offline. This can be prevented by
the inclusion of random tokens in the message payload of the ping, so that
@@ -252,17 +265,17 @@
As of this writing, there are over a dozen Echolot pingers operating
publicly~\cite{allpingers}.
-\subsection{Reliability measurement aspects}
+\subsection{Reliability Measurement Aspects}
Echolot tests multiple areas of failure in the remailer networks and
collates this data in a format the Mixmaster software can process,
-allowing the mix clients to make as much use of the available network
+allowing the mix-net clients to make as much use of the available network
resources as possible without preventable packet loss.
The most basic test of reliability is the ``single ping'' test, wherein
the known nodes of the mix-net are each periodically sent individual
messages encrypted using the network-specific packet format, and the
-response times and success rates are tallied. These results allow the mix
+response times and success rates are tallied. These results allow the mix-net
client to make general assumptions about the overall behavior of the node
being tested.
@@ -284,7 +297,7 @@
%XXX: nothing reports or cares about latencies of chain pings -- weasel
-\subsection{Node discovery}
+\subsection{Node Discovery}
Distributed mix-nets consisting of independent operators often do not
allow for a guaranteed means for nodes to communicate join and exit events
@@ -297,9 +310,6 @@
nodes will come into existence or cease operation without any warning or
notification at all.
-% unfinished -- Len's working on this, leave notes, but leave until last to write it up.
-%
-%
% Remailers publish nodes they know about in their remailer-* data.
% Echolot collects that data, and once a sufficient number of nodes list
% a new remailer an Echolot pinger starts to ping it too.
@@ -317,7 +327,7 @@
If a quorum of remailers know about a new node in the remailer network
that was previously unknown to this Echolot pinger, the pinger will
automatically add the new address to the list of remailers, request
-information about keys and capabilities, and start pinging the address.
+information about keys and capabilities, and start pinging the address.\footnote{Bootstrapping Echolot requires that an initial list of active mixes be provided to the software by the administrator, who may learn this information by participating in the aforementioned forums. Additionally, Mixmaster releases are packaged with a list of active mixes at the time of the release; if any of these mixes are still active when the Echolot administrator configures his system, Echolot can learn the identity of other, newer mixes by automatically querying the currently-known mixes.}
Remailers that have not responded to any requests for an extended duration
of time are also removed automatically.
@@ -333,7 +343,7 @@
little as one hour a month of human administration time would likely be
too costly for many.
-\subsection{Echolot algorithm}
+\subsection{Echolot Algorithm}
Echolot's approach for determining remailer reliability is as follows:
Distributed over the course of a day, Echolot sends several pings through
@@ -351,7 +361,7 @@
The first of them, $w1_i$ is strictly a function of the ping's age:
Pings younger than 24 hours have a weight of $0.5$; after 24 hours
$w1$ is $1.0$ for a while until the weight decreases to zero for pings
-older than 12 days. See table \ref{table:pingweight1} for the exact
+older than 12 days. See Table \ref{table:pingweight1} for the exact
numbers used in the Echolot software.
\begin{table}[h]
@@ -422,7 +432,7 @@
Mixmaster network shows that broken chains do not change very often.
%%%% END ECHOLOT
-\section{Anonymity set attacks based on pinger data}
+\section{Anonymity Set Attacks Based on Pinger Data}
A mix network in which users obtain their view of the network's heath and
status from multiple independent sources opens the system to partitioning
@@ -463,7 +473,7 @@
% remailers, so he can easily distinguish her messages when he seems them
% at his node
-\section{Creating a consensus directory}
+\section{Creating a Consensus Directory}
The solution to the partitioning attacks mentioned in the previous section
involves providing all clients with the same view of the network. Each
@@ -590,14 +600,14 @@
verifying against one single, static, public key. The disadvantage is that the
internal management of the group of pingers becomes more complex. If an
old pinger is disabled, its key share must be invalidated. Similarly, a
-new pinger needs to get a new key-share, and all thresholds need to adapt.
+new pinger needs to get a new key-share, and all thresholds need to adapt.\footnote{The convenience afforded by the single threshold signature verification makes the threshold signature scheme, and its corresponding key data, a strong target for attack. Care must be taken that the implementation of the threshold signature scheme is performed securely, and that the algorithm itself is not weak.}
We will denote with {\em tsign\_generate(x)} the generation of a signature share
of a threshold signature scheme, while {\em tsign\_combine($x_1,...x_n$)}
-comnines $n$ such shares into the final signature.
+combines $n$ such shares into the final signature.
-\subsection{The database update functions}
+\subsection{The Database Update Functions}
Due to the different character of the data in the database,
the pingers need four different protocols to maintain
@@ -639,30 +649,58 @@
% FIXME -- I can't seem to get the LaTeX to like a \framebox here.
% Let's put a rectangular frame around the Protocol UpdateMixes?
-\begin{algorithm}
-{\bf Protocol UpdateMixes for pinger $P_i$}
+\begin{figure*}[h]
+\centerline{\framebox[\textwidth][l]{
+\begin{minipage}{.8\textwidth}
+\begin{tabbing}
+\\
+mmmm\=mmmmm\=\kill
+{\bf Protocol UpdateMixes for pinger $P_i$}.\\
+\\
+\>r-broadcast new (signed) list ${\cal L}_i$ of mixes.\\
+\>wait for ($n-t$) valid r-broadcasts.\\
+\>let ${\cal L}'= {\cal L}_{j_1}, .... {\cal L}_{j_{n-t}}$ be a set of received $n-t$ lists.\\
+\\
+\>${\cal L}''$ = {\em mult\_BA} (${\cal L}'$).\\
+\>let ${\cal L}'''$ be the set of mixes in ${\cal L}''$ that have been proposed by $t+1$ pingers.\\
+\>$\sigma_i$ = {\em tsign\_generate}({\em date}, ${\cal L}'''$).\\
+\\
+\> r-broadcast $\sigma_i$.\\
+\>wait for ($n-t$) such shares $\sigma_{j_1,}..., \sigma{j_{n-t}}$.\\
+\>$\sigma$ = {\em tsign\_combine}($\sigma_{j_1},...,\sigma_{j_{n-t}}$).\\
+\\
+\>output ({\em date}$, {\cal L}'''$, $\sigma$)
+\end{tabbing}
+\end{minipage}
+}}
+\caption{\label{updatemixes}The update protocol used by the pingers to obtain a consistent view of the mix network.}
+\end{figure*}
-\begin{revpar}
- \item r-broadcast new (signed) list ${\cal L}_i$ of mixes
- \item wait for ($n-t$) valid r-broadcasts
- \item let ${\cal L}'= {\cal L}_{j_1}, .... {\cal L}_{j_{n-t}}$ be a set of received $n-t$ lists.
-\end{revpar}
-\begin{revpar}
- \item ${\cal L}''$ = {\em mult\_BA} (${\cal L}'$)
- \item let ${\cal L}'''$ be the set of mixes in ${\cal L}''$ that have been proposed by $t+1$ pingers
- \item $\sigma_i$ = {\em tsign\_generate}({\em date}, ${\cal L}'''$)
-\end{revpar}
+%%
+%\begin{algorithm}
+%{\bf Protocol UpdateMixes for pinger $P_i$}
+%
+%\begin{revpar}
+% \item r-broadcast new (signed) list ${\cal L}_i$ of mixes
+% \item wait for ($n-t$) valid r-broadcasts
+% \item let ${\cal L}'= {\cal L}_{j_1}, .... {\cal L}_{j_{n-t}}$ be a set of received $n-t$ lists.
+%\end{revpar}
+%\begin{revpar}
+% \item ${\cal L}''$ = {\em mult\_BA} (${\cal L}'$)
+% \item let ${\cal L}'''$ be the set of mixes in ${\cal L}''$ that have been proposed by $t+1$ pingers
+% \item $\sigma_i$ = {\em tsign\_generate}({\em date}, ${\cal L}'''$)
+%\end{revpar}
+%
+%\begin{revpar}
+% \item r-broadcast $\sigma_i$
+% \item wait for ($n-t$) such shares $\sigma_{j_1,}..., \sigma{j_{n-t}}$.
+% \item $\sigma$ = {\em tsign\_combine}($\sigma_{j_1},...,\sigma_{j_{n-t}}$).
+%\end{revpar}
+%% kku
+%output ({\em date}$, {\cal L}'''$, $\sigma$)
+%\end{algorithm}
-\begin{revpar}
- \item r-broadcast $\sigma_i$
- \item wait for ($n-t$) such shares $\sigma_{j_1,}..., \sigma{j_{n-t}}$.
- \item $\sigma$ = {\em tsign\_combine}($\sigma_{j_1},...,\sigma_{j_{n-t}}$).
-\end{revpar}
-% kku
-output ({\em date}$, {\cal L}'''$, $\sigma$)
-\end{algorithm}
-
-All subprotocols used in above protocol require a (expected) constant number of rounds
+All subprotocols used in Figure \ref{updatemixes} require a (expected) constant number of rounds
and have an overal (expected) message complexity in $O(n^2)$, i.e., $O(n)$ messages to be
send by each pinger. Consequently, the update protocol also
terminates in (expected) constant rounds with a similar message complexity.
@@ -688,7 +726,6 @@
linear in the total number of data items, and a running time and message complexity logarithmic
in the number of pingers.
-
\subsubsection{Update database (internally).}
This function is used to allow a mix to update database information about
@@ -722,7 +759,7 @@
Our choice of implementation is for randomization, for two reasons: Firstly, the randomized
model appears to be better adapted to the Byzantine setting, where the
corrupted parties actively try to disrupt the protocol. Secondly, we can
-expect realistic attacker in our scenario to launch denial of service
+expect a realistic attacker in our scenario to launch denial of service
attacks on the network, which timing based protocols have difficulties
dealing with.
@@ -744,9 +781,9 @@
Leuchtfeuer restricts the information provided by pingers in one area where Echolot and the previously deployed pingers were unconstrained: in order to achieve consensus on the data associated with a mix, latency must be represented as one of a limited set of values, as opposed to being directly reported in units of time. Pingers should categorize individual mixes as being either ``high'' or ``low'' latency, and report them as such.
-Pingers using Leuchtfeuer will record reliability and performance information about the mixes as they currently do, though the interval between publication of updates available to mix clients will increase significantly. As opposed to being updated every five minutes, as is the current default in Echolot, Leuchtfeuer pingers will create a threshold signature on the consensus directory and publish the signed directory for the clients every 12 hours. While this potentially increases the risk of lost packets due to a mix going offline immediately after a consensus directory in which it was still listed is published, it limits the ability of a passive attacker to perform intersection attacks based on short-term pinger result fluctuations.
+Pingers using Leuchtfeuer will record reliability and performance information about the mixes as they currently do, though the interval between publication of updates available to mix-net clients will increase significantly. As opposed to being updated every five minutes, as is the current default in Echolot, Leuchtfeuer pingers will create a threshold signature on the consensus directory and publish the signed directory for the clients every 12 hours. While this potentially increases the risk of lost packets due to a mix going offline immediately after a consensus directory in which it was still listed is published, it limits the ability of a passive attacker to perform intersection attacks based on short-term pinger result fluctuations.
-Current mix clients do not perform any authentication on the data obtained by pingers, while in the Leuchtfeuer protocol, clients will need to verify the threshold signature to confirm that the consensus directory is authentic. This will not add noticeable additional complexity to the user experience.
+Current mix-net clients do not perform any authentication on the data obtained by pingers, while in the Leuchtfeuer protocol, clients will need to verify the threshold signature to confirm that the consensus directory is authentic. This will not add noticeable additional complexity to the user experience.
% \subsubsection{Protocols run by mixes:}
% \paragraph{become\_mix:}
@@ -771,7 +808,7 @@
% \paragraph{make\_pinger:}
-\section{Conclusions and future work}
+\section{Conclusions and Future Work}
\label{conclusions}
We have described a device called a pinger, a necessary component of
@@ -783,16 +820,12 @@
reported by a pinger are accurate and comprehensive, and emphasized
specific technical requirements necessitated by the economic
considerations of the public anonymous remailer networks. We have
-implemented and released our own pinger software which incorporates these
-techniques, and as a result has become the dominant pinger solution in use
-on the Mixmaster network.
+implemented and released our own pinger software, Echolot, which incorporates these
+techniques and as a result has become the dominant pinger solution used with the Mixmaster network.
-We have designed an agreement protocol suitable for use in the asynchronous setting presented by the public remailer networks, which enables mutually-untrusting pingers to come to present a unified view of the state of the remailer network, including the names, network addresses, and public keys of the existing mixes, which can be authenticated by the mix client by verifying just one cryptographic signature on the consensus data. Our protocol greatly restricts an attacker's ability to exploit information about a user's information service or directory to perform intersection attacks against him, and reduces the impact that pingers operated by an adversary can have on the mix-net.
+We have designed an agreement protocol suitable for use in the asynchronous setting presented by the public remailer networks, which enables mutually-untrusting pingers to come to present a unified view of the state of the remailer network, including the names, network addresses, and public keys of the existing mixes, which can be authenticated by the mix-net client by verifying just one cryptographic signature on the consensus data. Our protocol greatly restricts an attacker's ability to exploit information about a user's information service or directory to perform intersection attacks against him, and reduces the impact that pingers operated by an adversary can have on the mix-net.
-
-% WRITE ME
-
\subsection*{Acknowledgments}
Peter Palfrader would like to thank Lucky Green and Colin Tuckley for
@@ -804,7 +837,7 @@
Len Sassaman would like to thank Bill Stewart, Nick Mathewson, and
numerous attendees of the erstwhile San Francisco Bay Area Cypherpunks
meetings for their insightful discussions of the mechanics of pingers. We also thank
-Meredith L. Patterson for reviewing a draft of this paper and for providing helpful comments.
+Meredith L. Patterson and Cat Okita for reviewing a draft version of this paper and for providing helpful comments.
This work was supported in part by the Concerted Research Action (GOA) Ambiorics 2005/11 of the Flemish Government and by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy). Len Sassaman's work was supported in part by the EU within the PRIME
Project under contract IST-2002-507591.
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/