[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Cleaned up grammar, spotted another missing citation.
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv23246
Modified Files:
echolot.tex
Log Message:
Cleaned up grammar, spotted another missing citation.
My 8th grade english teacher used to yell at me about overusing commas.
She'd be very disappointed to know I still do.
Index: echolot.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/echolot.tex,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- echolot.tex 6 Dec 2006 20:19:41 -0000 1.13
+++ echolot.tex 7 Dec 2006 00:05:59 -0000 1.14
@@ -127,7 +127,7 @@
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.
+messages through remailers and building statistics files.
% I haven't the slightest clue how rlist comes up with its reliability number.
% it's certainly black magic. -- weasel
@@ -143,7 +143,7 @@
% 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
+using the pseudonym of cmeclax, is a pinger for 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
@@ -154,7 +154,7 @@
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
+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.
@@ -181,7 +181,7 @@
\subsection{Mixminion directory server}
Mixminion\cite{mixminion} generalized the concept of pingers, defining a
-directory server component of the Mixminion system, responsible for the
+directory server component of the Mixminion system which is responsible for the
distribution of all information about remailer availability, performance,
and key material. The designers of the Mixminion system considered the
attacks on the independent pinger model, and specified that directory
@@ -236,7 +236,7 @@
\section{Echolot}
-The first version Echolot~\cite{echolot} was written in 2001. It sent pings
+The first version of 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.
@@ -245,8 +245,8 @@
being a group of programs with order-of-execution dependencies and
potential race conditions as its predecessor (and all other existing pingers) were, 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.
+also featured automated node discovery. The following year Echolot
+2.1 was released, adding the capability for chain pinging.
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
@@ -257,7 +257,7 @@
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.
+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
@@ -267,7 +267,7 @@
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
+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
@@ -349,7 +349,7 @@
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
+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
numbers used in the Echolot software.
@@ -376,14 +376,14 @@
To illustrate this, assume a ping was sent two hours ago, which
makes $age_{skewed}$ 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
+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
+report the reliability of remailers that have vastly different latencies.
+There exist Mixmaster nodes which return pings within minutes of sending,
while others often take many hours to forward a message~\cite{latencies}.
In addition to reliability, Echolot also reports a node's latency. The
@@ -412,14 +412,14 @@
Chains are considered interesting by Echolot when
\begin{itemize}
-\item less than 3 pings have been sent without any returning, or
+\item fewer 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.
+Mixmaster network shows that broken chains do not change very often.~\cite{FIXME} {\em FIXME, Peter!}
%%%% END ECHOLOT
@@ -454,7 +454,7 @@
problem, and introduces additional reliability constraints on the quality
of the pinger information.
-Additionally, many users retrieve from the pinger updated keys for the remailers at the same time they update their stats. The pinger\footnote{or an attacker performing a man-in-the-middle attack on the data retrieval session.} could manipulate the user into using keys other than those the user intended to. An attacker who controlled both the pinger used by his target, and a number of mixes in the network, could observe the target's messages moving through his mixes by performing a key-swapping attack with the pinger. By providing the target with a public key other than the one generally available for the mixes he controls, the target's messages would be easily distinguishable when processed by his mixes.
+Additionally, many users retrieve from the pinger updated keys for the remailers at the same as time they update their stats. The pinger\footnote{or an attacker performing a man-in-the-middle attack on the data retrieval session.} could manipulate the user into using keys other than those the user intended to. An attacker who controlled both the pinger used by his target and a number of mixes in the network could observe the target's messages moving through his mixes by performing a key-swapping attack with the pinger. By providing the target with a public key other than the one generally available for the mixes he controls, the target's messages would be easily distinguishable when processed by his mixes.
% More attacks? FIXME
@@ -468,19 +468,19 @@
The solution to the partitioning attacks mentioned in the previous section
involves providing all clients with the same view of the network. Each
-pinger should calculate its results for the status of the network, and
+pinger should calculate its results for the status of the network and
compare these results with those of the other pingers. The pingers then
must agree on a compromise result which reflects an accurate view of mix
-availability, and provides every client with a consistent information with
+availability and provides every client with a consistent information with
which to calculate message paths.
Since the infamous FLP impossibility proof~\cite{filypa85}, it is known
that a simple problem such as reaching consensus in the presence of faulty
parties -- even if the worst they can do is to crash -- is rather hard,
-and a significant amount of research has been put into securing a
-distributed systems against faulty parties~\cite{schnei90,deblfa91}. In the
-Mixes scenario, the main parties for the agreement protocols are the {\em
+and a significant amount of research has been put into securing distributed
+systems against faulty parties~\cite{schnei90,deblfa91}. In the
+mix-net scenario, the main parties for the agreement protocols are the {\em
pingers}, i.e., the parties that maintain a database on the active mixes,
their authentication keys and some of their properties. They need to
agree on a consistent status of the {\em mixes} and then deliver it on
@@ -491,18 +491,18 @@
Depending on the attack model, the solutions can be rather complex, and in
many implementations weaker attack models are chosen to allow for simpler
-protocols . In the Mixminion protocol, for example, the agreement protocol
+protocols. In the Mixminion protocol, for example, the agreement protocol
can easily be circumvented by one (or several) parties stopping the
communication after a while -- a condition that may be constructed even if
none of the involved pingers is actually corrupt. The honest parties may
recognize they are in a bad condition and alert the administrator, but it is
left to human interference to actually recreate consensus; as the
disagreement may be created without any party behaving obviously
-dishonest, this may place quite some burden on the administration.
+dishonestly, this may place quite some burden on the administration.
-The protocol suite presented here will guarantee consensus independent of
-timing assumptions, as long as less than a third of all pingers behave
-actively malicious. For additional security, one can still add tests along
+The protocol suite presented here will guarantee a consensus independent of
+timing assumptions, as long as fewer than a third of all pingers behave in an
+actively malicious fashion. For additional security, one can still add tests along
the lines of the Mixminion protocol to detect inconsistencies and alert
the administrators; however, if more than a third of the pingers are
actively corrupt, the system is in a sufficiently bad state that its
@@ -562,10 +562,10 @@
that if one honest party receives the broadcast, eventually all other ones
will.
-An {\em Atomic broadcast}~\cite{caslis99a,reiter94} primitive additionally
+An {\em atomic broadcast}~\cite{caslis99a,reiter94} primitive additionally
guarantees that all honest parties receive all messages in the same order.
This is a rather powerful synchronization mechanism, that deals with many
-uncertainties of the asynchronous network and the attackers. In principal,
+uncertainties of the asynchronous network and the attackers. In principle,
it is possible to build the entire database on top of such a protocol; for
this paper, however, we have chosen dedicated protocols.
@@ -591,7 +591,7 @@
Due to the different character of the data in the database,
the pingers need four different protocols to maintain
-their database in a consistent state.
+their databases in a consistent state.
\subsubsection{Update set of mixes.}
@@ -604,27 +604,28 @@
to verify she got a correct set of mixes, without needing to know
which parties are in the actual set of pingers.
-
+% 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}
\begin{revpar}
\item r-broadcast new list ${\cal L}$ of mixes
- \item wait for $n-t$ r-broadcasts.
+ \item wait for ($n-t$) r-broadcasts
\item {\bf receive} a set ${\cal L}'$ of mixes
\end{revpar}
\begin{revpar}
\item run multivalued BA protocol, using ${\cal L}'$ as an input
- \item {\bf receive} a set ${\cal L}''$ of n-t lists
+ \item {\bf receive} a set ${\cal L}''$ of ($n-t$) lists
\item let ${\cal L}'''$ be the set of mixes that have been proposed by $t+1$
- parties in the set.
- \item threshold-sign (\em date, ${\cal L}'''$) using a threshold signature
+ parties in the set
+ \item threshold-sign ({\em date}, ${\cal L}'''$) using a threshold signature
scheme, getting the signature share $\sigma_i$
\end{revpar}
\begin{revpar}
\item r-broadcast the signature share $\sigma_i$
- \item wait for $n-t$ such shares
+ \item wait for ($n-t$) such shares
\item combine the shares to retrieve $\sigma$
\end{revpar}
\end{algorithm}
@@ -633,10 +634,10 @@
The protocol that updates the set of pingers is similar to the one that
updates the set of mixes. However, for this protocol it is important to
-also update the shared keys, so that the old parties can not participate
+also update the shared keys, so that the old parties cannot participate
in any signing process anymore, while the new parties get shares that
allow them to participate. An appropriate re-sharing protocol is described
-in~\cite{CachinKLS02} ;
+in~\cite{CachinKLS02}.
\subsubsection{Update database (externally).}
@@ -653,13 +654,13 @@
\subsubsection{Update database (internally).}
This function is used to allow a mix to update database information about
-himself. Most commonly, this will be used to install a new key pair once
+itself. Most commonly, this will be used to install a new key pair once
the old one expires. It is relatively straightforward to implement this
functionality, as the mix already has a key to authenticate itself.
Assuming this is implemented properly (i.e., the signed messages are
tagged properly), this can safely be used for database updates.
-The update protocol would be a simple {\em r-broadcast} of the a signed
+The update protocol would be a simple {\em r-broadcast} of a signed
message requesting the update. This way, it is guaranteed that all pingers
receive the same request, and the database stays consistent. To avoid race
conditions, the mix also needs to maintain a serial number, so that all
@@ -667,6 +668,8 @@
there exist protocols that can also enforce that all pingers receive all
update requests in the same order; however, implementing this here may be
overkill.
+%
+% FIXME Klaus -- say something about why this is overkill?
\subsection{Attack Model}
@@ -685,10 +688,11 @@
The price to pay for the fully asynchronous network model is a lower
tolerance. It can easily be shown that nothing useful can be done once a
-third or more of all parties are corrupted.~\cite{FIXME} {\em FIXME, Klaus!} In the mixes scenario, the
-main parties for the agreement protocols are the {\em pingers}; they need
-to agree on a consistent status of the {\em mixes} and then deliver it on
-request to the {\em clients}. As the clients should not be forced to
+third or more of all parties are corrupted.~\cite{FIXME} {\em FIXME, Klaus!}
+In the mix-net scenario, the
+main parties for the agreement protocols are the pingers; they need
+to agree on a consistent status of the mixes and then deliver it on
+request to the clients. As the clients should not be forced to
contact more pingers than needed, each honest mix should be able to prove
that the result it forwards to the client is in fact the genuine outcome
of the agreement.
@@ -696,11 +700,11 @@
\subsection{The Functionality}
-The primitives we have described can be utilized by the mix-net's independent components to perform basic network maintenance operations. Mixes can announce their existence to a small selection of pingers. After the pingers perform several instances of the UpdateMixes protocol, all the pingers will have learned the address of the new mixes, and independently confirmed their validity by sending the mixes a query which will result in the automatic return of their keys. After verifying a new mix exists, adding the mix's keys (which have been obtained directly from the mix itself), and confirming that the mix is properly forwarding packets by sending pings through it, the pingers will add the new mix to their list of known mixes. Once enough pingers list the new mix and its operational details it will be included in the consensus directory. The current Echolot pingers are able to add and remove mixes without human intervention, and Leuchtfeuer has been designed to integrate with the current pinger behavior.
+The primitives we have described can be utilized by the mix-net's independent components to perform basic network maintenance operations. Mixes can announce their existence to a small selection of pingers. After the pingers perform several instances of the UpdateMixes protocol, all the pingers will have learned the address of the new mixes and independently confirmed their validity by sending the mixes a query which will result in the automatic return of their keys. After verifying a new mix exists, adding the mix's keys (which have been obtained directly from the mix itself), and confirming that the mix is properly forwarding packets by sending pings through it, the pingers will add the new mix to their list of known mixes. Once enough pingers list the new mix and its operational details, it will be included in the consensus directory. The current Echolot pingers are able to add and remove mixes without human intervention, and Leuchtfeuer has been designed to integrate with the current pinger behavior.
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 theshold 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 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.
@@ -739,7 +743,7 @@
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
+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.
@@ -757,14 +761,15 @@
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
+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.
+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.
Len Sassaman's work was supported in part by the EU within the PRIME
Project under contract IST-2002-507591.
-\vfill\eject
+%\vfill\eject
\bibliographystyle{plain}
\bibliography{echolot}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/