[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] First pass at agreement.
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv15760
Modified Files:
pingers.tex
Log Message:
First pass at agreement.
Index: pingers.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/pingers.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- pingers.tex 27 Oct 2005 15:45:59 -0000 1.2
+++ pingers.tex 9 Mar 2006 10:50:02 -0000 1.3
@@ -4,6 +4,19 @@
\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$}
+
\title{Measuring Remailer Reliability}
\author{Len Sassaman\inst{1}}
@@ -143,12 +156,18 @@
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.
-FIXME [Does Mixminion have any details on calculation stategy? Not sure, but I should check the source.]
+
\section{Gaming the data}
@@ -219,35 +238,204 @@
availability, and provides every client with a consistent information with
which to calculate message paths.
-[FIXME Klaus's protocol goes here]
+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~\{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.
-To recap:
+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.
-Remailer network monitoring problems:
+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}
-All users must have one view of the network.
+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.
-There's no fixed number of mixes or pingers.
-Anyone can announce themselves as a mix.
+ \subsubsection{Verifiable Multivalued Byzantine Agreement}
-Users should have to query no more than three pingers to get the network
-view.
+ 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 the vaule
+ 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.
-The pinger results (the directory contains:
+ \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.
-mix address (which should be the index for the directory)
-Latency (high/low)
-mix status (valid/invalid)
-mix status (confirmed/unconfirmed)
-mix pubkeys
-mix key expiration dates
-is a pinger (y/n)
+ 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}
+
+\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}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/