[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Restore the Leuchtfeuer sections to the Echolot pape...
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv12228
Modified Files:
echolot.tex echolot.bib
Log Message:
Restore the Leuchtfeuer sections to the Echolot paper, fix typos.
Index: echolot.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/echolot.tex,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- echolot.tex 14 Mar 2006 09:56:05 -0000 1.10
+++ echolot.tex 6 Dec 2006 19:40:19 -0000 1.11
@@ -33,22 +33,21 @@
\setlength{\rightmargin}{0in}} \small \item}{\end{list}}
-\title{Echolot}
+\title{Echolot and Leuchtfeuer}
\subtitle{Measuring the Reliability of Unreliable Mixes}
% Blinded for submission
-
-\author {Peter Palfrader\inst{1} and Len Sassaman\inst{2}}
+\author {Klaus Kursawe\inst{1} and Peter Palfrader\inst{2} and Len Sassaman\inst{1}}
%foo
-\institute{Paris Lodron Universit\"at Salzburg\\
+\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}
-\and
-Katholieke Universiteit Leuven\\
-Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium\\
-\email{len.sassaman@xxxxxxxxxxxxxxxx}
}
%foo
@@ -66,14 +65,20 @@
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.
+publishes results for the mix clients to evaluate.
-We evaluate the security concerns regarding an pingers, including the
+We discuss the security concerns regarding 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.
+To address a serious anonymity weakness potentially introduced by the
+careless deployment of pingers, we present \emph{Leuchtfeuer}, a new
+protocol enhancement for mix-nets. Leuchtfeuer eliminates the active and
+passive intersection attacks that are possible when different users obtain
+conflicting reliability statistics about the mix-net.
+
\end{abstract}
@@ -104,7 +109,12 @@
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.
+the problem of reliability monitoring than the other pingers. Finally, we
+explain the problem of pinger inconsistency, an issue which poses
+significant security implications and is shared by all existing pingers
+and mix clients. To solve this, we present the pinger agreement protocol
+Leuchtfeuer.
+
\section{Related work}
@@ -168,6 +178,24 @@
% 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}
+
+Mixminion\cite{mixminion} generalized the concept of pingers, defining a
+directory server component of the Mixminion system, 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
+servers be synchronized as well as redundant.
+
+%FIXME [Does Mixminion have any details on calculation stategy? Not sure,
+%but I should check the source.]
+%
+% Apparently, Mixminion doesn't do any actual pinging. Scratch that.
+%
+Mixminion publishes signed \emph{capability blocks} in the directory
+server, consisting of the supported mix protocol versions, mix's address,
+long-term (signing) public key, short-term (message decryption) public
+key, remixing capability, and batching strategy.
\section{Veracity attacks}
\label{section:gaming}
@@ -196,7 +224,7 @@
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
+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
@@ -395,6 +423,310 @@
%%%% END ECHOLOT
+\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
+attacks~\cite{trickle02} against the users, based on differences in the mix
+selection based on the results of the different pingers. In a system of
+entirely honest pingers, this attack is feasible for an adversary
+operating in the passive observer model.
+
+Suppose Alice retrieved her network health information from pinger 1, and
+Bob retrieved his information from pinger 2. An observer watching the
+network local to Alice or Bob would know which pinger the user under
+observation chose. If the information provided by both pingers differed in
+some manner, the delta would contain mixes that, if chosen by Alice or
+Bob, would betray which pinger had been used to obtain this information. A
+message processed by a mix contained only in the results provided by
+pinger 1 could not have been sent by Bob, who obtains his results from a
+pinger lacking that information.
+
+Additionally, differences in pinger results for mix latency could lead to
+more subtle variations in mix path selection, which may aid an attacker.
+
+If a pinger is operated by an attacker, it becomes possible to
+specifically target individual users by providing them with unique
+information about the network in order to partition them into an
+anonymity set of size 1. Users can attempt to prevent against this attack
+by obtaining their pinger results from a widely-published location, such
+as Usenet, though this does not completely solve the partitioning attack
+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.
+
+
+% More attacks? FIXME
+% - most users also fetch keys with the stats
+% -> an attacker could not just give Alice a different list of nodes, but
+% could give her the same list only with a different key for his
+% remailers, so he can easily distinguish her messages when he seems them
+% at his node
+
+\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
+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
+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
+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
+request to the {\em 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.
+
+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
+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.
+
+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 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
+survival is questionable.
+
+\subsection{The Tools}
+
+In this section, we introduce the basic building blocks needed for our
+protocol. Due to lack of space, we do not give a formal model here. The
+protocols we choose were mostly developed within the MAFTIA
+project~\cite{maftiad26}; using new randomization techniques, these protocols
+are the first practical protocols that can deal with the maximum possible
+number of corruptions, and do not require any timing assumptions.
+
+\subsubsection{Binary Byzantine Agreement.}
+
+The basic protocol behind our consensus protocols is a binary Byzantine
+agreement protocol~\cite{lashpe82,cakush00}, which allows parties to
+agree on a simple binary value. In addition to agreement, the output
+value also must depend on the input values; in our case, this means it
+must be proposed by at least one non-corrupted pinger. We also want to
+obtain a proof of the outcome, so one single pinger can prove to an
+external party what the outcome of a particular protocol instance was.
+
+
+\subsubsection{Verifiable Multivalued Byzantine Agreement.}
+
+A multivalued Byzantine agreement protocol~\cite{ckps01} allows the pingers
+to agree on any bit-string, rather than only a binary value. As there is a
+(potentially) infinite universe of possible values, a multivalued
+Byzantine agreement protocol can no longer guarantee that the output of
+the protocol is the input of some honest party -- this would only be
+possible if all honest parties propose the same value. It is, however,
+possible to enforce that all honest parties verify the value prior to
+agreement, and thus guarantee that it satisfies some properties, e.g.,
+that it has the expected format, or contains proper signatures that
+certify its validity.
+
+\subsubsection{Broadcast protocols.}
+
+Broadcast protocols~\cite{ckps01} are used to send messages from one
+sender to a number of receivers. In the simplest version, the sender
+simply sends the message to every other party (Note that in the Mixminion
+protocol, the receivers poll the messages, rather than the sender pushing
+them; for our purpose, this does not pose a significant difference). This
+simple protocol does not give any guarantees to the receivers, however;
+some may receive different messages, or no message at all.
+
+A {\em consistent broadcast}, or {c-broadcast}, guarantees that all
+parties that do receive a particular broadcast receive the same
+value~\cite{malrei98a}. It does not, however, guarantee that all parties
+on the group receive anything in the first place.
+
+A {\em reliable broadcast}, or {\em r-broadcast}, additionally guarantees
+that all parties receive the broadcast~\cite{bracha84}. Our model being
+asynchronous, there is no guarantee about the time; the only guarantee is
+that if one honest party receives the broadcast, eventually all other ones
+will.
+
+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,
+it is possible to build the entire database on top of such a protocol; for
+this paper, however, we have chosen dedicated protocols.
+
+\subsubsection{Threshold signatures.}
+
+Threshold signatures~\cite{shoup00a} allow parties to issue shares of a
+signature, which then -- given enough shares are available -- can be
+combined into one single signature. The nice property is that a threshold
+signature outputs the same constant length signature, independent of the
+actual number of parties or the subset of parties that did the actual
+signing. This not only preserves space and bandwidth, but also solves the
+key distribution system. A client does not need to know the public key of
+any individual pinger, nor the identity of the set of pingers, but can
+verify that a certain message was signed by a certain number of pingers by
+verifying against one, 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.
+
+
+
+\subsection{The database update functions}
+
+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.
+
+\subsubsection{Update set of mixes.}
+
+The main functionality of our protocols is to maintain a consistent
+set of mixes. Furthermore, a client should easily be able to obtain
+that set, i.e., each pinger can prove that he gives out the correct
+set. This is where the threshold signatures are used; there is only
+one signature for all pingers, but a minimum of two thirds are needed
+to generate the signature. Thus, a client only needs one public key
+to verify she got a correct set of mixes, without needing to know
+which parties are in the actual set of pingers.
+
+
+\begin{algorithm}
+{\bf Protocol UpdateMixes}
+
+\begin{revpar}
+ \item r-broadcast new list ${\cal L}$ of mixes
+ \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 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
+ 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 combine the shares to retrieve $\sigma$
+\end{revpar}
+\end{algorithm}
+
+\subsubsection{Update set of pingers.}
+
+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
+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} ;
+
+\subsubsection{Update database (externally).}
+
+With this function, the pingers can update information about a mix, most
+prominently its performance data. In the simplest case, this data is
+binary; in this case, a simple binary Byzantine agreement can be performed
+to determine a common value that has been proposed by at least one honest
+party. To avoid communication overhead, the agreements needed for all data
+on all mixes can be bundled; this leads to a protocol with message size
+linear in the total number of data items, and a running time logarithmic
+in the number of pingers.
+
+
+\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
+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
+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
+parties can be assured to receive all updates in the same order. Note that
+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.
+
+\subsection{Attack Model}
+
+It is known that
+a simple problem such as agreement is quite hard in an asynchronous
+environment if some parties crash or otherwise do not follow the protocol.
+The only way around is to either rely on timing assumptions, or to use a
+randomized algorithm.
+
+Our choice 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
+attacks on the network, which timing based protocols have difficulties
+dealing with.
+
+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 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
+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.
+
+
+\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.
+
+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.
+
+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.
+
+% \subsubsection{Protocols run by mixes:}
+% \paragraph{become\_mix:}
+% With this protocol, a new server tells the pingers that he would like
+ % to become a mix
+
+% Parameters: pub\_key
+% \paragraph{renounce\_mix:}
+% With this protocol, a mix announces he does not want to be a server
+% any more.
+
+% Parameters: signature on the message
+% \paragraph{update\_pubkey:}
+% This protocol is used by a mix to define a new public key.
+
+% \subsubsection{Protocols run by clients:}
+% \paragraph{get\_mix\_list:}
+
+% \subsubsection{Protocols run by pingers:}
+% \paragraph{suggest\_mix:}
+% \paragraph{output\_mix\_list:}
+% \paragraph{make\_pinger:}
+
+
\section{Conclusions and future work}
\label{conclusions}
@@ -411,9 +743,7 @@
techniques, and as a result has become the dominant pinger solution in use
on the Mixmaster network.
-In this paper we have not addressed the effects multiple independent pingers operating
-in the same mix-net can have on users' anonymity. This is an area in need of further
-evaluation.
+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.
Index: echolot.bib
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/echolot.bib,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- echolot.bib 14 Mar 2006 10:05:26 -0000 1.8
+++ echolot.bib 6 Dec 2006 19:40:19 -0000 1.9
@@ -14329,19 +14329,15 @@
}
@inproceedings{CachinKLS02,
- author = {Christian Cachin and
- Klaus Kursawe and
- Anna Lysyanskaya and
- Reto Strobl},
- title = {Asynchronous verifiable secret sharing and proactive cryptosystems.},
- booktitle = {ACM Conference on Computer and Communications Security},
- year = {2002},
- pages = {88-97},
- ee = {http://doi.acm.org/10.1145/586110.586124},
- crossref = {DBLP:conf/ccs/2002},
- bibsource = {DBLP, http://dblp.uni-trier.de}
+ author = {Christian Cachin and Klaus Kursawe and Anna Lysyanskaya and Reto Strobl},
+ title = {Asynchronous verifiable secret sharing and proactive cryptosystems.},
+ booktitle = {ACM Conference on Computer and Communications Security},
+ year = {2002},
+ pages = {88-97},
+ ee = {http://doi.acm.org/10.1145/586110.586124},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
}
-
+% crossref = {DBLP:conf/ccs/2002},
@misc{MAFTIA,
link = "http://www.maftia.org";
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/