[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Justify!
Update of /home2/freehaven/cvsroot/doc/pingers
In directory moria:/tmp/cvs-serv19048
Modified Files:
pingers.tex
Log Message:
Justify!
Index: pingers.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pingers/pingers.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- pingers.tex 9 Mar 2006 10:50:02 -0000 1.3
+++ pingers.tex 9 Mar 2006 11:41:18 -0000 1.4
@@ -20,6 +20,8 @@
\title{Measuring Remailer Reliability}
\author{Len Sassaman\inst{1}}
+\author{Klaus Kursawe\inst{1}}
+\author{Peter Palfrader\inst{2}}
%foo
@@ -45,9 +47,9 @@
in the mix-network. We present a summary of the techniques currently in
use, and evaluate their methods.
-We evaluate the security concerns regarding an information service, including
-the issues regarding anonymity set preservation, information disclosure, and
-node cheating.
+We evaluate the security concerns regarding an information service,
+including the issues regarding anonymity set preservation, information
+disclosure, and node cheating.
\end{abstract}
@@ -239,120 +241,115 @@
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~\{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.
+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.
-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.
+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.
+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.
+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{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 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.
+\subsubsection{Verifiable Multivalued Byzantine Agreement}
- \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 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.
- 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.
+\subsubsection{Broadcast protocols}
- 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.
+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.
- 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.
+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.
+\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.
@@ -398,75 +395,79 @@
\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} ;
+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.
+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.
+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.
+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.
+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.
+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.
+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
+ 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.
+ With this protocol, a mix announces he does not want to be a server
+ any more.
Paramters: signature on the message
\paragraph{update_pubkey}
@@ -482,57 +483,70 @@
\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}
+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}.
+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}
+\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.
+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
+\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 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.
+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.
+\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}.
+\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
+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. \\
@@ -545,6 +559,8 @@
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/