[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Added first-pass at the agreement protocol.
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv2537
Modified Files:
pingers.tex
Log Message:
Added first-pass at the agreement protocol.
Index: pingers.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/pingers.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- pingers.tex 27 Oct 2005 09:04:14 -0000 1.1
+++ pingers.tex 27 Oct 2005 15:45:59 -0000 1.2
@@ -148,8 +148,7 @@
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.]
+FIXME [Does Mixminion have any details on calculation stategy? Not sure, but I should check the source.]
\section{Gaming the data}
@@ -220,8 +219,144 @@
availability, and provides every client with a consistent information with
which to calculate message paths.
-%[FIXME Klaus's protocol goes here]
+[FIXME Klaus's protocol goes here]
+
+
+To recap:
+
+Remailer network monitoring problems:
+
+All users must have one view of the network.
+
+There's no fixed number of mixes or pingers.
+
+Anyone can announce themselves as a mix.
+
+Users should have to query no more than three pingers to get the network
+view.
+
+The pinger results (the directory contains:
+
+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)
+
+
+
+
+
+\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 anymore.
+
+ 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}
+
+\subsection{The basic building blocks}
+
+ 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.
+ \subsubsection{Binary Byzantine Agreement}
+
+ The basic Byzantine agreement protocol allows the parties to agree on a binary value, with the
+ property that at least one honest party must have proposed this value initially~\cite{Blah}.
+
+
+ \subsection{Verifiable Multivalued Byzantine Agreement}
+
+ 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 is signed by someone.
+
+ \subsection{Broadcast protocols}
+ Broadcast protocols are used to
+
+ A {\em consistend broadcast}, or {c-broadcast}, guarantees that all parties that do receive a particular
+ broadcast recieve the same value. 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. 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.
+
+
+ \subsection{Threshold signatures}
+ A threshold signature scheme\cite[shoup] is a special signature scheme in which individual parties
+ issue shares of a signature, which then can be combined to the full 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 actuiall 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 still can verify that a certain
+ message was signed by the pingers.
+ 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.
+
+ \subsubsection{Key Update Protocols}
+ Both the agreement protocol and the threshold signatures require keys shared between participants. Thus,
+ modifying the set of participants is relatively complex; old key shares need to be invalidated, and new
+ ones created. While the corresponding update protocols are relatively expensive, they only need to be
+ executed when the set of pingers changes. Protocols suitable for this task have been described in
+ \cite{Proactive}.
+
+
+\subsection{Protocol Implementation}
+
+ The following protocol, executed by the pingers, can be used to update the mix list
+
+ r-broadcast new list ${\cal L} of mixes \\
+ wait for $n-t$ r-broadcasts. \\
+ ==> a set ${\cal L}'$ of mixes \\
+ run multivalued BA protocol, using ${\cal L}'$ as an input\\
+ ==> a set ${\cal L}''$ of n-t lists\\
+ let ${\cal L}'''$ be the set of mixes that have been proposed by $t+1$ parties in the set.\\
+ threshold-sign (\em date, ${\cal L}'''$) using an (n,n-t) threshold signature scheme\\
+ ==> $\sigma_i}\\
+ r-broadcast the signature share $\sigma_i}\\
+ wait for $n-t$ such shares\\
+ combine the shares to retrieve $\sigma}\\
\section{Conclusions and future work}
\label{conclusions}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/