[freehaven-cvs] r1783: Remove the initial partitioning attack results. This goes in (doc/trunk/pynchon-gate)

[rabbi@xxxxxxxx]

Author: rabbi
Date: 2007-05-10 09:09:01 -0400 (Thu, 10 May 2007)
New Revision: 1783

Modified:
   doc/trunk/pynchon-gate/byzantine-fix.tex
Log:
Remove the initial partitioning attack results. This goes in a different 
paper.


Modified: doc/trunk/pynchon-gate/byzantine-fix.tex
===================================================================
--- doc/trunk/pynchon-gate/byzantine-fix.tex	2007-05-08 03:02:57 UTC (rev 1782)
+++ doc/trunk/pynchon-gate/byzantine-fix.tex	2007-05-10 13:09:01 UTC (rev 1783)
@@ -46,8 +46,8 @@
 
 
 \maketitle
-%\pagestyle{empty}
-%\centerline{\LARGE\bf DRAFT --- not for publication}
+\pagestyle{empty}
+\centerline{\LARGE\bf DRAFT --- not for publication}
 %======================================================================
 
 \begin{abstract}
@@ -58,7 +58,7 @@
 
 We show a trivial modification to the original PynGP which allows for detection and identification of Byzantine nodes, with no weakening of the security model necessary, at the relatively affordable cost of greater bandwidth requirements during certain communication operations. We demonstrate that this adequately solves the problems raised by~\cite{cosic-2007-001}, and argue that it is the most suitable method of addressing the attack in question yet proposed.
 
-We then evaluate an alternate approach to solving to the problem described in~\cite{cosic-2007-001}, proposed by Goldberg in his recent paper~\cite{goldberg-2007}. We compare the security and performance trade-offs made in that proposal, and find it less secure against anonymity attacks as compared to the original (but flawed) Pynchon Gate Protocol (PynGP)~\cite{pynchon-spec} presented in the first Pynchon Gate paper. We show that this proposal is significantly weaker than the solution offered in this paper, which retains the security properties of the original Pynchon Gate Protocol. We then examine a flaw in the novel protocol presented in~\cite{goldberg-2007} that facilitates partitioning attacks by an adversary operating two or more of the user-selected nodes.
+We then evaluate an alternate approach to solving to the problem described in~\cite{cosic-2007-001}, proposed by Goldberg in his recent paper~\cite{goldberg-2007}. We compare the security and performance trade-offs made in that proposal, and find it less secure against anonymity attacks as compared to the original (but flawed) Pynchon Gate Protocol (PynGP)~\cite{pynchon-spec} presented in the first Pynchon Gate paper. We show that this proposal is significantly weaker than the solution offered in this paper, which retains the security properties of the original Pynchon Gate Protocol. %We then examine a flaw in the novel protocol presented in~\cite{goldberg-2007} that facilitates partitioning attacks by an adversary operating two or more of the user-selected nodes.
 
 \end{abstract}
 
@@ -187,16 +187,16 @@
 
 These real-world limitations reduce Goldberg's protocol to a simple $t$-private $v$-Byzantine-robust $k$-out-of-$\ell$ PIR protocol such as that proposed in~\cite{beimel-robust}, which allows for the identification of Byzantine servers only at the cost of reduced overall security as compared to PynGP. PynGP 2.0 requires no such compromise in its security.
 
-\subsection{Partitioning attacks}
+%\subsection{Partitioning attacks}
 
-In contrast to the Beimel and Stahl protocol, the Goldberg protocol presents a two-stage Byzantine recovery procedure. An attacker controlling two or more nodes can manipulate the responses given to certain users such that some users will be able to recover from the Byzantine action using the first-stage recovery operation and other users will require the second stage recovery operation. This offers the possibility that an attacker may partition users based on their response to Byzantine actions, thus presenting a serious threat to user anonymity. Detecting which recovery step the user conducted is not trivial, but using the temperature-induced clock-skew caused by the recovery operations as an indicator of which recovery operation is being performed, an attacker can learn into which set a given host falls. (This approach is the same as that used by Murdoch to detect remote host activity in~\cite{HotOrNot}). 
+%In contrast to the Beimel and Stahl protocol, the Goldberg protocol presents a two-stage Byzantine recovery procedure. An attacker controlling two or more nodes can manipulate the responses given to certain users such that some users will be able to recover from the Byzantine action using the first-stage recovery operation and other users will require the second stage recovery operation. This offers the possibility that an attacker may partition users based on their response to Byzantine actions, thus presenting a serious threat to user anonymity. Detecting which recovery step the user conducted is not trivial, but using the temperature-induced clock-skew caused by the recovery operations as an indicator of which recovery operation is being performed, an attacker can learn into which set a given host falls. (This approach is the same as that used by Murdoch to detect remote host activity in~\cite{HotOrNot}). 
 
 \section{Conclusions}
 We have reviewed the attack as described in~\cite{cosic-2007-001}, and found that it has significant impact on the deployability and potential success of the Pynchon Gate, as well as other PIR-based nym server systems that do not account for Byzantine servers. A denial or degradation of service attack would be nearly impossible to thwart, and would likely happen soon after the system became popular among users. This vulnerability must not be present in the public system if it is to be expected to achieve and maintain any level of popularity or substantial user-base.
 
 We have presented a subtle modification to PynGP 1.0, relying on nothing more than an additional set of operations already performed by the original PynGP 1.0, to enable the detection and identification of Byzantine nodes with sufficient probability that the denial of service attack against the PynGP 1.0 is no longer feasible. This modified protocol, PynGP 2.0, requires no weakening of the original Pynchon Gate security model, and although it increases the bandwidth communication overhead, the bandwidth costs are still reasonable enough to fall within the engineering requirements of the original Pynchon Gate design goals: namely, that the system's bandwidth requirements be inexpensive enough to be reasonable for both users and system operators.
 
-We have examined the prior solution proposed by Goldberg in~\cite{goldberg-2007} to address the Byzantine server vulnerability. We show that the trade-offs made in Goldberg's proposal do not satisfy the the security requirements set forth for the Pynchon Gate in its original design paper, as Goldberg's core protocol weakens the security assumptions significantly compared to the original PynGP, and introduces new avenues of attack.
+We have examined the prior solution proposed by Goldberg in~\cite{goldberg-2007} to address the Byzantine server vulnerability. We show that the trade-offs made in Goldberg's proposal do not satisfy the the security requirements set forth for the Pynchon Gate in its original design paper, as Goldberg's core protocol weakens the security assumptions significantly compared to the original PynGP.%, and introduces new avenues of attack.
 
 With the addition of PynGP 2.0, we consider the Pynchon Gate design to be superior to any other high-latency pseudonym service offering strong privacy properties currently proposed in the literature.
 

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