[freehaven-cvs] r1785: Include a solution for the edge-case of an evil validator/co (doc/trunk/pynchon-gate)

[rabbi@xxxxxxxx]

Author: rabbi
Date: 2007-06-10 15:54:21 -0400 (Sun, 10 Jun 2007)
New Revision: 1785

Modified:
   doc/trunk/pynchon-gate/byzantine-fix.tex
Log:
Include a solution for the edge-case of an evil 
validator/collator/nym-server coalition which attempts a partitioning 
attack by framing honest distributors as Byzantine.




Modified: doc/trunk/pynchon-gate/byzantine-fix.tex
===================================================================
--- doc/trunk/pynchon-gate/byzantine-fix.tex	2007-06-10 18:20:08 UTC (rev 1784)
+++ doc/trunk/pynchon-gate/byzantine-fix.tex	2007-06-10 19:54:21 UTC (rev 1785)
@@ -149,12 +149,24 @@
 
 Upon receiving these bit vectors, the distributor performs the operations as described in Subsection \ref{subsec:PIR}, and then returns two responses, in the same order which the requests were received (or otherwise in such a manner that the responses are linkable to the requests which generated them). The client caches the response for the $\{\vec{\eta}\}$ request, then performs the PIR operation as previously described using the $\{\vec{\alpha}\}$ results from all distributors.
 
+\subsubsection{The Validator:}
+
 We now introduce a new component in the Pynchon Gate architecture, known as the \emph{validator}. This component is essentially a distributor, except that it only exists to confirm that the other distributors are not Byzantine. This specialized distributor validates the ``cut-and-chosen'' responses as being correct, deterring the operation of Byzantine nodes and probabilistically uncovering them should they exist. 
 
-To ensure that additional trust is not required of this new component to the system, the validator \textbf{must} be operated by the same entity who operates the collator. The operator of the collator is already empowered to perform a denial of service attack by simply unplugging the power cord of the server running the collator. Ergo, the balance of power in this distributed trust system is maintained by placing the validator (whose operator could also force a denial of service attack, though not as easily) under the control of the same entity.\footnote{The validator is never provided the contents of $\{\vec{\alpha}\}$ queries, since the validator, collator, and nym server are \emph{not} considered trusted with regard to a user's privacy, and knowledge of the contents of $\{\vec{\alpha}\}$ queries (or responses) could provide information about the user's identity.} Note that communication with the validator occurs over an encrypted link, just as with normal distributors.  
+To ensure that additional trust is not required of this new component to the system, the validator \textbf{must} be operated by the same entity who operates the collator. The operator of the collator is already empowered to perform a denial of service attack by simply unplugging the power cord of the server running the collator. Ergo, the balance of power in this distributed trust system is maintained by placing the validator (whose operator could also force a denial of service attack, though not as easily) under the control of the same entity.\footnote{The validator is never provided the contents of $\{\vec{\alpha}\}$ queries, since the validator, collator, and nym server are \emph{not} considered trusted with regard to a user's privacy, and knowledge of the contents of $\{\vec{\alpha}\}$ queries (or responses) could provide information about the user's identity.} Note that communication with the validator occurs over an encrypted link, just as with normal distributors. 
 
-The responses from set $\{\vec{\eta}\}$ (while possibly able to return a valid mailbox) are not of interest to the client for their contents. Instead, these responses are cached by the client, along with the corresponding request that was sent to the distributor to generate them as well as an identifier for the distributor which returned the responses. To verify that a distributor is not attempting to behave in a Byzantine manner, the same bit vectors in $\{\vec{\eta}\}$ that had been submitted to each distributor can subsequently be submitted to the validator, and the validator should return a response identical to that which the original distributor returned for each request. (The entire $\{\vec{\eta}\}$ needs to be submitted, as there may be multiple Byzantine servers acting simultaneously.) Should the validator return a response that differs from the one received by the client from a given distributor, that distributor should be suspected of being Byzantine.\footnote{Strictly speaking, the $\{\vec{\eta}\}$ vectors should always be sent to the validator, regardless of the outcome of the PIR operation using the $\{\vec{\alpha}\}$ results, to guard against the scenario where an additional adversary not in collusion with the Byzantine server might learn additional information about the state of the network. However, this level of paranoia may not be affordable until bandwidth and computation become less expensive.}
+\subsubsection{Auditing the Distributors:}
 
+The requests comprising set $\{\vec{\eta}\}$ are crafted such that they return a specific \emph{validation block} when the PIR algorithm is performed. Under normal circumstances, the contents of this block are of no interest to the user. The individual responses are cached by the client, along with the corresponding request that was sent to the distributor to generate them as well as an identifier for the distributor which returned the responses. To verify that a distributor is not attempting to behave in a Byzantine manner, the same bit vectors in $\{\vec{\eta}\}$ that had been submitted to each distributor can subsequently be submitted to the validator, and the validator should return a response identical to that which the original distributor returned for each request. (The entire $\{\vec{\eta}\}$ needs to be submitted, as there may be multiple Byzantine servers acting simultaneously.) Should the validator return a response that differs from the one received by the client from a given distributor, that distributor should be suspected of being Byzantine.\footnote{Strictly speaking, the $\{\vec{\eta}\}$ vectors should always be sent to the validator, regardless of the outcome of the PIR operation using the $\{\vec{\alpha}\}$ results, to guard against the scenario where an additional adversary not in collusion with the Byzantine server might learn additional information about the state of the network. However, this level of paranoia may not be affordable until bandwidth and computation become less expensive.}
+
+\subsubsection{Auditing the Validator:}
+
+The addition of the validator component does raise the concern that a corrupt nym-server/collator/validator coalition may attempt to mount an attack on a user's anonymity by systematically framing honest distributors as Byzantine nodes so that the user selects only nodes operated by the coalition. As one of the main premises behind the security of the Pynchon Gate design is that the nym-server operator not be trusted to preserve the user's anonymity, a way to confirm that the validator is honest is needed. This confirmation procedure is simple:
+
+If the $\{\vec{\eta}\}$ responses from the distributors differ from the $\{\vec{\eta}\}$ responses from the validator, the client should first attempt to verify the correctness of the $\{\vec{\eta}\}$ response by performing the PIR protocol and comparing the result to the known validation block. If the correct block is returned, there is nothing to be learned by querying the validator. If the responses to the $\{\vec{\eta}\}$ requests yield an incorrect validation block, the presence of at least one Byzantine distributor is verified. The client then proceeds as described above, submitting each $\{\vec{\eta}\}$ query to the distributor \emph{one query at a time} and recording the results. When a differing result is received for a given query, it should be swapped in for the original result, and the PIR protocol performed. The substitution of the validator's response for the original response should yield the correct validation block if the validator is honest. In cases where the validator's responses differ for more than one query, this challenge should be performed for each differing response both individually, and as a whole.
+
+\subsubsection{Probability of Byzantine detection:}
+
 %The client should avoid sending the entire set at once, however. Instead, each element should be submitted at a metered pace to avoid excessive load on the valiator.
 As proposed above, this protocol gives a Byzantine server a 50\% chance of being discovered each time it attempts to behave in a Byzantine manner. That threshold can be increased at the expense of greater bandwidth overhead; however, we feel that a 50\% detection rate is sufficient to deter this sort of attack, due to the inherent reputation system involved with the distributor network.\footnote{A Byzantine server's chances of successfully providing a Byzantine response of unidentified origin decreases in an manner inversely proportional to its probabilty of detection.} This probability of detection is based on the assumption that the Byzantine server considers it acceptable that its Byzantine action may be \emph{ineffective}. If the server wishes to \emph{guarantee} a successful Byzantine operation, it can do so by providing Byzantine answers to all the client's requests, but the probability of detection in that case is 100\%. 
 
@@ -210,6 +222,10 @@
 
 % The resource requirements for the new architectural component validator need to be more fully investigated, and won't truly be known until the system is tested in a live environment with actual Byzantine nodes. It is conceivable that the validator might actually be multiple validators in a 
 
+%FIXME 
+% Byzantine attack posted to LJ
+% Ref. Tech report on tau-resistance.
+% Send Bart this paper and the reviewer comments.
 
 \section{Acknowledgements}
 

***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/