[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs]
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv5061
Added Files:
leuchtfeuer.bib leuchtfeuer.tex
Log Message:
...
--- NEW FILE: leuchtfeuer.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" }
[...14975 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: leuchtfeuer.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{Leuchtfeuer}
\subtitle{A Unified Agreement Protocol for Mix-nets}
% 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}
%\and
%Paris Lodron Universit\"at Salzburg\\
%Salzburg, Austria\\
%\email{ppalfrad@xxxxxxxxxxxxxx}
%}
%foo
\date{}
\begin{document}
\maketitle
\begin{abstract}
We describe the structure of the deployed mix-net systems, and examine the security implications that arise when user behavior is influenced by the node reliability and availability data provided by independently-operated information services.
We present~\emph{Leuchtfeuer}, a protocol enhancement for distributed-trust
mix-nets which eliminates the active and passive intersection attack
vector created when multiple information services contain differing information about the mix-net.
\end{abstract}
\section{Introduction}
We begin by presenting an overview of the infrastructure components that make up the public mix-net systems in use on the Internet, and examine the information service publishers known as \emph{pingers}. We evaluate the additional security considerations present in mix-net systems featuring pingers. We explain the problem of pinger inconsistency, an issue which poses significant security implications and creates the potential for two related attacks with the potential for complete loss of anonymity. We present a solution to this problem, the pinger agreement protocol \emph{Leuchtfeuer}, which can be incorporated into the vulnerable mix-net protocols.
\section{Reliability monitoring of mix-nets}
\label{pingers}
Mix-nets are intended to protect users' anonymity and conceal their communication patterns.
In a distributed-trust anonymity system such as this, the user must trust that the \emph{system} will provide these protections, but is not required to trust all of the individual nodes themselves. Mix-nets consist of \emph{mixes} which accept input traffic in the form of messages encrypted to the mix's public key, then they delay and reorder the traffic, and forward it onward to its pre-addressed destination. Messages are sent through user-selected\footnote{Or client-selected.} chain of mixes, with each message typically encrypted and addressed, in a nested fashion, to three to five mixes in the mix-net.The security of the system is based on the premise that a user's traffic may be safely routed through nodes which the attacker controls, as long as the user's client has selected a path through the network that includes a sufficient number of honest nodes. Multiple distributed-trust mix-net variants have been deployed on the Internet since the early 1990's.
The components of the extant mix-nets are operated on a volunteer basis, often by parties unknown to the users. Since many volunteer operators lack the resources to offer the same level of high-availabilty access assurance as commercial network service providers, and individual mixes may come and go as the circumstances facilitating their volunteer operation change, it is essential that users of the mix-net be able to learn a current list of available, correctly-performing mixes, and their corresponding public keys, so that their messages will be delivered reliably and swiftly.
The first reliability servers for mix-nets to be deployed~\cite{rlist} existed to provide information about the Cypherpunk remailer network~\cite{hal-remailer}, and are known to users and operators of email-oriented mixes (or \emph{remailers}) as \emph{pingers}. While there have been multiple pingers written for the Cypherpunk and Mixmaster~\cite{mixmaster-spec} remailer networks over the last decade, more than two-thirds of the pingers currently in operation are running Echolot~\cite{echolot}.
\subsection{Echolot}
Echolot tests the ability of each Cypherpunk and Mixmaster remailer to correctly process messages and to communicate with the other remailers in the network, and records the success rates and elapsed time to completion for each test. Echolot makes the results of its monitoring available for download by mix clients. Additionally (and in contrast to some of the less-common pingers), Echolot tracks other information of concern to the mix clients, specifically the public keys and the capabilities that each remailer advertises.
\subsection{Mixminion directory server}
Mixminion~\cite{mixminion}, the eventual replacement for the Cypherpunk and Mixmaster networks, explicitly generalized the role of pingers to include the distribution of all information about remailer availability, performance, and key material, as defined in the Mixminion directory server specifications~\cite{mixminion-dirspec}. The designers of the Mixminion system considered attacks on the independent pinger model, and specified that directory servers be synchronized as well as redundant.\footnote{The Mixminion system does not, however, currently specify the means by which availability and performance metrics are calculated, and does not provide a mechanism for collecting this information}.
%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.
%
To this end, 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{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 cose. If the information provided by both pingers differend 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.
% 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{Leuchtfeuer: a unified directory view}
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
distribured 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,
thier 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
recogise they are in a bad condition and alert the aministrator, 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 where mostly developed within the MAFTIA
project~\cite{MAFTIA}; 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 imput 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 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 bitstring, rather than only a binary value. As there is a
(potentially) invinite 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 thevaule 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 simnplest 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 consistend broadcast}, or {c-broadcast}, guarantees that all
parties that do receive a particular broadcast recieve the same
value~\cite{malrei98a}. It does not, however, guarantee that all parties
on the group reveive 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 guarantere 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 powerfull synchronisation mechanism, that deals with many
uncertaincies 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
combine to one single signature. The nice property is that a threshold
signature outputs the same constant length signature, independent of the
actuall number of parties or the subset of parties that did the actuall
signing. This not only preserves space and bandwith, 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 disabeled, its key share must be invalidated. Similary, a
new pinger needs to get a new keyshare, 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 functionallity of our protocols is to maintain a consistend
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 ony 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 resharing protocol is described
in~\cite{CachinKLS02} ;
\subsubsection{Update database (externaly.}
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 bundeled; 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.
Update database (internaly)
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
functionallity, 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 savely 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
condidions, 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 the all pingers receive all
update requests in the same order; however, implementing this here may be
overkill.
\subsection{Attack Model}
Since the infamous FLP impossibility proof~\cite{FLP85}, 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 teo reasons: Firstly, the randomised
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 usefull can be done once a
third or more of all parties are corrupted. 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 Functionallity}
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.
Paramters: signature on the message
\paragraph{update\_pubkey}
This protocol is used by a mix to define a new public key.
Protocols run by clients
\paragraph{get\_mix\_list}
Protocols run by pingers
\paragraph{suggest\_mix}
\paragraph{output\_mix\_list}
\paragraph{make\_pinger}
\section{Conclusions and future work}
\label{conclusions}
% WRITE ME
\subsection*{Acknowledgments}
[Redacted]
\bibliographystyle{plain}
\bibliography{leuchtfeuer}
\end{document}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/