[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Final version.
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv22013
Added Files:
echolot.bib echolot.pdf echolot.tex
Log Message:
Final version.
--- NEW FILE: echolot.bib ---
% ----------------------------------------------------------------------------
%
% Filename : w.bib
% Comment : bibilography file of my paper library
% [ all papers here are located in my office (cabinets)
% YOU MUST leave a note if you take sth. ]
% sorted by 1. to 4. authorname and year
% (bibtool -r wsort.rsc -o w.bib w.bib)
%
% Author : Christian Cachin
% Language : BibTeX
% Created : 02-06-94
% Modified : (too many times)
%
% ----------------------------------------------------------------------------
%
%
@string{acmcs = "ACM Computing Surveys" }
@string{bstj = "Bell System Technical Journal" }
[...14961 lines suppressed...]
@inproceedings{econymics,
title = {On the Economics of Anonymity},
author = {Alessandro Acquisti and Roger Dingledine and Paul Syverson},
booktitle = {Financial Cryptography},
year = {2003},
editor = {Rebecca N. Wright},
publisher = {Springer-Verlag, LNCS 2742},
}
@InProceedings{e2e-traffic,
author = {Nick Mathewson and Roger Dingledine},
title = {Practical Traffic Analysis: Extending and Resisting Statistical Disclosure},
booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2004)},
year = {2004},
month = {May},
series = {LNCS},
www_section = traffic,
www_pdf_url = "http://freehaven.net/doc/e2e-traffic/e2e-traffic.pdf";,
}
--- NEW FILE: echolot.pdf ---
%PDF-1.4
3 0 obj <<
/Length 2701
/Filter /FlateDecode
>>
stream
xÚ?YK?ãÈ
¾Ï¯hì%2ÐVT*=??Å$?
vËÚÑ?Ç??O#²
TÝxðѽÊW¸p°Xc¯ô°hûQB?ÅØq?Ý?áÉ1Óxá?? ¦Óüm?ã
F Ã
°»ò·b EKC8?Å?FÅ![§ìa ÅK81¹?'ËYi?K?öÔ7£÷uZ`ó÷ ô¥8£è?X `e/T?<ÊdÓ²´ÓÕ?ñx/\?a?f??ì
ÑèÓµ]«R±?Ò??¤ eۥר{??»öQVFNø?ÎËô¾ªS'úÇýëGÏsGÐ9¢é6±%?ÑÁ)Hûb6^tO; Ó?:´Ø!?beèì?¯¸?ëëÛ82ÈÙ¹Ï?µ?µýä³ö:¢,eµhQ`&ðGÌpïNã?WªSA®cÝnűM ?ÅÕ?M¤ âÖäöÁS?8¼èûîÂIs/ß±|Ý˧¸¶Ge ¾6ogçu?Ö½gñÁÜÝ4?¾>;l???ƹNvá½Ê&.¸2Bý?Ù??bcâI?*?`h ?÷??5q??°4 ÿíè¦
ä$a?iC¦???Î^=ÁU±¶÷>5JĤ??8ÃÚ??Ïw?UÏo?(màÙáäçÌ'¥öQ^??²~?§Ê¾ì¨ôçEÖ$^ª©¯Wº´·ràç?m?V´?¯J
L?;?1 M´È¨(NLÊêì ? ?2íÃ*8
]Å?ùáUÝ~nÞ?§ 1Ì@?ÕaªÀûxï
,´&4 þ06y⡸É?.?/¿à7 ~?wDÆqÆ3|½_!_$GTÏÙ·G¡ñyñ?pÌÞ{Ü@!ð\~2 õl(¨b#2x?í4PƹÜÄRXù ú÷?[IÀ®Áu%îk?&?Ü[ ßÄD²X?N׳ÞÅ1>±¾nO??Úê]9Ô?t?º *^_1»uÃƧóÄ*lÚ#:*_RÑüÓ¦°Dï9e1i©ÍKU?«m9 ø¨ÄN¾»?[ØÌÈÇ?Ò$ ^ë9Þ´sC3ÈÆÙÌMYIäµ o*
?ê4àhÅ ?«a?ùn/½Ê~?(,.
Èø?0?K3&QlðoExå´9ÃÄ?¦~?t??A!Ä;®±? ·-DÚ§}%?i©?E8?0Vd?îDixç¶OÇF+¼2? ?.NZ8"ÓèÚ?»c?½ìÙùB¶ô?ß
?¿È Æ£P9/Í?/ª°~ì9?r£@ßÜcä?~µ«ô!mo_AËmºÝf{?M¬)f}b,å?Lï5²Æ C?ÛAz¸©×3ìÊ&¿¢#Ñð¦ ?¿CX vA®G Çw;
endstream
endobj
2 0 obj <<
/Type /Page
/Contents 3 0 R
[...1089 lines suppressed...]
0000065933 00000 n
0000080191 00000 n
0000079796 00000 n
0000096685 00000 n
0000096288 00000 n
0000104631 00000 n
0000104401 00000 n
0000105133 00000 n
0000105199 00000 n
0000105250 00000 n
trailer
<<
/Size 92
/Root 90 0 R
/Info 91 0 R
/ID [<37FAA3CFFF367F410A4AE038D15F7913> <37FAA3CFFF367F410A4AE038D15F7913>]
>>
startxref
105448
%%EOF
--- NEW FILE: echolot.tex ---
\documentclass[runningheads]{llncs}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{psfrag}
\usepackage{amsfonts}
%%\newenvironment{algorithm}
%%{%
%%\begin{figure}[hptb]
%%%\renewcommand{\baselinestretch}{1}
%%\small
%%}
%%{\end{figure}
%%\renewcommand{\baselinestretch}{2}
%%}
% replace bullets by dashes in itemize
\renewcommand\labelitemi{\normalfont\bfseries --}
\renewcommand\labelitemii{$\m@th\bullet$}
\newenvironment{revpar}{%
\begin{list}%
{}{\setlength{\labelwidth}{0in}%
\setlength{\itemsep}{0in}%
\setlength{\topsep}{0in}%
\setlength{\leftmargin}{4em}%
\setlength{\itemindent}{-2em}}}{\end{list}}
\newenvironment{algorithm}{%
\medbreak%
\begin{list}%
{}{\setlength{\labelwidth}{0in}%
\setlength{\listparindent}{0in}%
\setlength{\rightmargin}{0in}} \small \item}{\end{list}}
\title{Echolot}
\subtitle{Measuring the Reliability of Unreliable Mixes}
% Blinded for submission
%\author 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}
%\and
%Paris Lodron Universit\"at Salzburg\\
%Salzburg, Austria\\
%\email{ppalfrad@xxxxxxxxxxxxxx}
%}
%foo
\date{}
\begin{document}
\maketitle
\begin{abstract}
In a mix-net, information regarding the network health and operational
behavior of the individual nodes must be made available to the client
applications so they may select reliable nodes to use in each message's
path through the mix-net. We introduce the concept of a \emph{pinger}, an
agent which tests the reliability of individual mixes in the mix-net, and
publishes its results for the mix clients.
We evaluate the security concerns regarding an pingers, including the
issues regarding anonymity set preservation, information disclosure, and
node cheating. We present our software \emph{Echolot}, the most
comprehensive and widely adopted pinger for the Mixmaster anonymous
remailer network.
\end{abstract}
\section{Introduction}
Chaum\cite{chaum-mix} introduced the concept of mixes as a method of
providing secure anonymous network communication. The publicly accessible
mix networks, such as the ``Type I'' Cypherpunk remailers~\cite{hal-remailer},
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
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
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
results are downloaded and interpreted by the mix clients. Pingers track
additional information as well, such as the average latency provided by
each mix, changes in the key information and capabilities of the mixes,
and so forth.
In this paper we give an overview of the different pinger systems that
have been developed for the Mixmaster network, and describe the problems
they attempt to address, as well as their relative success at doing so. We
present Echolot, our pinger implementation which more adequately addresses
the problem of reliability monitoring than the other pingers.
\section{Related work}
\label{pingers}
\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.
Once started, rlist would run indefinitely, regularly sending simple test
messages through remailers and building statistic files.
% I haven't the slightest clue how rlist comes up with its reliability number.
% it's certainly black magic. -- weasel
\subsection{pingstats}
% - cmeclax, Dec 2000 - 2003
% - written in C and shell
% - run out of cron, uses procmail to filter mails into folders
% - pings weight decreases exponentially with age
% - pings come back in plain text but contain a random token
% so a remailer can't just make up pings if me missed a fewcontain a random token
% so a remailer can't just make up pings if me missed a few
Pingstats\cite{pingstats}, developed between 2000 and 2003 by a programmer
using the pseudonym of cmeclax, is a pinger both Cypherpunk and Mixmaster
remailers. It consists of a C program which computes the statistics and a
collection of shell scripts that manage the creation, sending, and
receiving aspect of pinging, as well as help with collecting keys of known
remailers and making a list of their capabilities. These programs are
called from Cron, a Unix daemon that executes programs at previously
specified times.
Pingstats employs random tokens in message payloads as a counter-measure
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
results are given less weight than more recent data.
\subsection{remlist}
% - Christian Mock, 2001
% - uses a RDBMS as storage backend
% - run out of Cron
% - pings come back in plain text but contain a random token
% so a remailer can't just make up pings if me missed a fewcontain a random token
% so a remailer can't just make up pings if me missed a few
Christian Mock wrote remlist\cite{remlist} at about the same time as
cmeclax developed pingstats. Mock's pinger also generated
non-deterministic ping payloads but did not do any weighting of data.
Remlist's main distinguishing feature was the use of
MySQL~\cite{mysql}, a relational database, as its storage backend.
% XXX: Maybe Reliable deserves being mentioned -- weasel
% Is it documented anywhere? I suppose you're right. While not useful as
% a remailer, it isn't a terrible pinger. -- rabbi
\section{Veracity attacks}
\label{section:gaming}
A mix which is otherwise honest (in that it correctly performs mixing
duties without breaking the anonymity of the messages transmitted through
it) may attempt to convince a pinger to provide false information
regarding the performance of the mix by identifying the source address of
pings and treating the pinger messages differently than normal messages.
While this manipulation will not change basic results such as the
operational status of a defunct mix, it could allow a mix to alter the
latency statistics reported for its operation.
We experimented in Echolot 1.x with a technique intended to discourage such
cheating by creating ping messages which originate and terminate at a local mix
that also mixes normal messages, so that the target mix cannot distinguish
between user messages and pinger messages. Unfortunately, systems such as
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
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
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
pings returned to a pinger without bearing the token of an outstanding
ping are discarded without being collated.
%%%% ECHOLOT SECTION
\section{Echolot}
The first version Echolot~\cite{echolot} was written in 2001. It sent pings
through a local Mixmaster node in order to prevent the nodes being tested
from learning that a message contained a ping. Other than that it was fairly
similar to other pinger software in existence at the time.
Echolot 2.x, a complete rewrite, followed in 2002. Instead of a
being a group of programs with order-of-execution dependencies and
potential race conditions as its predecessor was, Echolot 2.x was built as
a single daemon. In addition to the normal single hop pings, this version
also featured automated node discovery. The following year with Echolot
2.1 chain pinging was added.
Echolot is the most widely used pinger for the Types 1 and 2 remailer networks.
As of this writing, there are over a dozen Echolot pingers operating
publicly\cite{allpingers}.
\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
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
client to make general assumptions about the overall behavior of the node
being tested.
When performing a ``chain ping'' test, Echolot creates a message of path
length equal to two, for all combinations of any two remailers in the
network, and tests each of these pairings. If both remailers consistently
return single pings, but fail to return chained pings, one can deduce that
the failure is occurring at the link between the two nodes. Thus, either
remailer can be reliably used, as long as they are not selected to be
adjacent nodes in the message path.
Similarly, the latency value observed from the transmission of a chain
ping until its return at the pinger measures the combined latency of the
two nodes. If this is significantly different than the sum of the
single-ping latencies for each node, the mix-net client could make
determinations about the suitability of that pairing of nodes in a chain.
As no mix-net clients exist which make use of the latencies of chain
pings, Echolot does not currently report them.
%XXX: nothing reports or cares about latencies of chain pings -- weasel
\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
to the other nodes in the network. In the case of Mixmaster, there is no
central control structure for tracking the existence of functional nodes,
and the components in the system must devise a way of obtaining this
information. Often, the human operator of a node joining or exiting the
network will announce the status change to other node operators and users
via the ``remops'' mailing list or by posting to USENET. Just as often,
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.
%
% Therefore only a few remops have to manually add a new node and it spreads
% to everyone from there. Similarly, remailers that have not been answering any
% requests for about a week get de-listed automatically. This allows echolot
% to be zero to low maintenance, an important feature for widespread adaption.
%
% - weasel
% let's add some text for this:
Echolot regularly queries each remailer for copies of its current keys, a
report of its capabilities, and a list of the other remailers known to it.
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.
Remailers that have not responded to any requests for an extended duration
of time are also removed automatically.
Echolot's automation of most routine maintenance tasks produces a more
accurate report about the remailer network than would be possible if it
relied on intervention by the pinger operator. Additionally, as the
remailer network infrastructure is operated by volunteers, it is
especially important to minimize the effort necessary to operate
components of the network, to attract and retain volunteer operators.
While the bandwidth, disk storage, and computation resources required to
operate a pinger are negligible for most potential volunteers, even as
little as one hour a month of human administration time would likely be
too costly for many. Thus,
\subsection{Echolot algorithm}
Echolot's approach for determining remailer reliability is simple.
Distributed over the course of a day, Echolot sends several pings through
each remailer, recording the time when they were sent. For pings already
received, the time interval between the sending of the ping and its return
to the pinger is recorded.
The ``reliability'' of a remailer is basically the quotient of pings
received and pings sent, with some skewing in place to put more emphasis
on more recent data while still being fair to remailers with higher
latencies: $rel := \frac{w_i \cdot rcvd_i }{w_i}$, where $rcvd_i$ is $1$
if a ping was received and $0$ otherwise.
The weight $w_i$ of a ping is made up of two factors: $w1_i \cdot w2_i$.
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$, for older pings
$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
numbers used in the Echolot software.
\begin{table}[h]
\centering
\begin{tabular}{r||c|c|c|c|c|c|c|c|c|c|c|c}
age [days]: ~ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\
\hline
weight $w1$: ~ & 0.5 & 1.0 & 1.0 & 1.0 & 1.0 & 0.9 & 0.8 & 0.5 & 0.3 & 0.2 & 0.2 & 0.1\\
\end{tabular}
\caption{Weight of pings based on their age}
\label{table:pingweight1}
\end{table}
The second part of a ping's weight also considers this node's latency
behavior over the last 12 days. If a ping already has returned its
$w2$ is $1.0$. However, should it still be outstanding, Echolot computes
the ping's age, again with some constant skewing factors:
$ age_{skewed} := (now - send - 15 min) \cdot 0.8$. The weight $w2$ is
now the percentage of pings returned with a latency lower than
$age_{skewed}$ within the past 12 days.
To illustrate this, assume a ping was sent two hours ago, which
makes $age_{skewed}$ be 84 minutes. If all pings returned from
this node were faster than 84 minutes then $w2$ is $1.0$. If only
a third of pings were received within that time frame then $w2$ is
$0.33$. If no ping was ever faster than 84 minutes, then $w2$ is
zero.
This weighting based on past behavior was introduced to accurately
report reliability of remailers that have vastly different latencies.
There exist Mixmaster nodes which return pings within minutes of sending
while others often take days to forward a message.
In addition to reliability, Echolot also reports a node's latency. The
latency reported is simply the median of latencies of all pings received
within the last 12 days.
\paragraph{Chain-Pinging:} In addition to single-hop pings, Echolot also
performs chain pinging to uncover cases where two remailers A and B
perform well when tested individually but for obscure reasons (such as a
network device error specific to the path between the two remailers),
messages sent through A to B fail to arrive at their destinations.
Since pinging every two-hop chain on a frequent basis would put an
unnecessary load on the remailer network, Echolot contents itself with
only testing each chain once a week. Chains that warrant closer attention
(so called ``interesting chains'') are pinged more often---daily.
\vfill\eject
Echolot reports a chain to be broken if
\begin{itemize}
\item at least 3 pings were sent to test the chain, and
\item the resulting chain reliability is far smaller than could be
expected from the nodes' individual performance:
$\frac{\mbox{received pings}}{\mbox{sent pings}} <= rel_A \cdot rel_B \cdot 0.3$.
\end{itemize}
Chains are considered interesting by Echolot when
\begin{itemize}
\item less than 3 pings have been sent without any returning, or
\item the chain is currently reported broken.
\end{itemize}
Because Echolot pings chains that it considers working only once a
week, it may take a while before it realizes that a previously working
chain is now broken. Fortunately, experience with the currently deployed
Mixmaster network shows that broken chains do not change very often.
%%%% END ECHOLOT
\section{Conclusions and future work}
\label{conclusions}
We have described a device called a pinger, a necessary component of
anonymity networks based on unreliable mixes. As background, we presented
a summary of the pinger software that has been created since the inception
of the public anonymous remailer networks.
We have detailed a number of techniques used to ensure the results
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.
We have not addressed the anonymity implications of multiple independent reliability monitoring servers operating in the same mix-net system, though this is an area which deserves more research.
% WRITE ME
\subsection*{Acknowledgments}
[Redacted for blind submission.]
%Peter Palfrader would like to thank Lucky Green and Colin Tuckley for
%authoring and continuing to update Echolot's end user documentation,
%Orange admin for work on the HTML templates that make up Echolot's output,
%and BiKiKii Admin, noisebox Admin and many nameless testers for providing
%valuable feedback during Echolot's development.
%
%Len Sassaman would like to thank Bill Stewart, Nick Matthewson, and
%numerous attendees of the erstwhile San Francisco Bay Area Cypherpunks
%meetings for their insightful discussions of the mechanics of pingers.
%
%Len Sassaman's work was supported in part by the EU within the PRIME
%Project under contract IST-2002-507591.
\bibliographystyle{plain}
\bibliography{echolot}
\end{document}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/