[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] r1773: Cleanup. (doc/trunk/pynchon-gate/bp-ringstwice)
Author: rabbi
Date: 2007-04-06 13:00:45 -0400 (Fri, 06 Apr 2007)
New Revision: 1773
Modified:
doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib
doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
Log:
Cleanup.
Modified: doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib
===================================================================
--- doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib 2007-04-05 13:42:38 UTC (rev 1772)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib 2007-04-06 17:00:45 UTC (rev 1773)
@@ -233,3 +233,19 @@
www_pdf_url = {http://www.abditum.com/pynchon/sassaman-wpes2005.pdf},
www_section = {Pseudonymity},
}
+
+@inproceedings{statistical-disclosure,
+ title = {Statistical Disclosure Attacks: Traffic Confirmation in Open Environments},
+ author = {George Danezis},
+ booktitle = {Proceedings of Security and Privacy in the Age of Uncertainty, ({SEC2003})},
+ organization = {{IFIP TC11}},
+ year = {2003},
+ month = {May},
+ address = {Athens},
+ pages = {421--426},
+ editor = {Gritzalis and Vimercati and Samarati and Katsikas},
+ publisher = {Kluwer},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.cl.cam.ac.uk/~gd216/StatDisclosure.pdf},
+}
+
Modified: doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
===================================================================
--- doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex 2007-04-05 13:42:38 UTC (rev 1772)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex 2007-04-06 17:00:45 UTC (rev 1773)
@@ -41,41 +41,54 @@
\end{abstract}
+%\section{Inter-author communication}
+%FIXME
+%(Len: Depending on just how closely the Byzantine servers can watch the
+%user they're tampering with, I think the k-Byzantine-robust
+%polynomial-interpolation protocols like Beimel's and Ian's are actually
+%*more* vulnerable to the attack than the purely XOR-based ones, because
+%the k-Byzantine-robust protocols provide (algorithmically) for dropping
+%the Byzantine server's output once it's been detected. This means that
+%the k-Byzantine-robust protocols silently recover from a Byzantine
+%action (so long as the total number of Byzantine servers in the response
+%is <k), allowing the user to recover his data and (in a bad
+%implementation, anyway) not pointing out which server sent back bad
+%data. Thus my assertion of "undetectable" above.
+
+%Now, that said, observing the critical action that turns the user into
+%an oracle -- the fact that the Byzantine server gets dropped from the
+%user's list of "servers I consider honest" for the remainder of the
+%processing of that query -- is hard, and probably requires something
+%like the ability to watch what's going on in RAM. But if that's
+%something we can handwave, then I'll be happy to play with it.)
+%
+%(Mer: Yes, there is a catch-22 for us with regard to algorithms that allow for Byzantine-recovery. On the one hand, the user doesn't get worked up that something fishy is going on, or get run off because his system doesn't work. On the other hand, the parties communicating need to be able to get their signal, and if the user doesn't react differently to a Byzantine server's use of the subliminal channel, how do they get it? Well, let's turn to our friends at Cambridge and cite \url{http://www.freehaven.net/anonbib/cache/torta05.pdf}, which observes that you can learn something about the load on a server (or client) based on the latency in its network responses. So, for instance, I'm betting that if you could observe the network traffic of a Golberg-style PIR client~\cite{goldberg-2007}, during its hard-recover step, latency goes up because CPU usage goes up, and the client gets bogged down. We can totally hand-wave this; we might be able to even demonstrate this in practice with Ian's code and some simple ping results.)
+
+%Note: we might want to cite Ishai et al.'s paper ``Cryptography from Anonymity'' which observes that anonymity systems can be used as a building-block for cryptographic protocols. There is a lot of work on the problems of subliminal channels in cryptographic protocols (the example that comes to mind is DSS~\cite{Sim93a,Sim93b}/El Gamal signatures~\cite{newtonchannel}), so we could say "this is as important as if it were a crypto primitive we were talking about, because Ishai et al. say it might as well be."
+
+%There's a good overview/retrospective by Simmons, the discoverer of the DSA subliminal channel, here:
+%\url{http://kabru.eecs.umich.edu/rtclonly/jsac/js1998/16sac04-simmons2.pdf}
+
+%Note: Does this get more interesting when we consider Bond and Danezis ``A Pact with the Devil''~\cite{pactwithdevil}?
+
\section{Introduction}
-\section{Inter-author communication}
-%FIXME
+Since the seminal paper by Chor, et al. in 1995~\cite{pir}, information-theoretic private information retrieval protocols have received considerable attention in the information theory community~\cite{beimel01informationtheoretic,beimel-barrier,beimel-robust,tau-indy,goldberg-2007}. However, comparatively little work has been done to evaluate these privacy primitives within the broader scope of a secure privacy system. We examine one consideration that designers of systems based on information-theoretic PIR may need to consider within their threat model: subliminal channels between independent PIR databases.
-(Len: Depending on just how closely the Byzantine servers can watch the
-user they're tampering with, I think the k-Byzantine-robust
-polynomial-interpolation protocols like Beimel's and Ian's are actually
-*more* vulnerable to the attack than the purely XOR-based ones, because
-the k-Byzantine-robust protocols provide (algorithmically) for dropping
-the Byzantine server's output once it's been detected. This means that
-the k-Byzantine-robust protocols silently recover from a Byzantine
-action (so long as the total number of Byzantine servers in the response
-is <k), allowing the user to recover his data and (in a bad
-implementation, anyway) not pointing out which server sent back bad
-data. Thus my assertion of "undetectable" above.
+\subsection{Background}
-Now, that said, observing the critical action that turns the user into
-an oracle -- the fact that the Byzantine server gets dropped from the
-user's list of "servers I consider honest" for the remainder of the
-processing of that query -- is hard, and probably requires something
-like the ability to watch what's going on in RAM. But if that's
-something we can handwave, then I'll be happy to play with it.)
+Explain what Information-Theoretic PIR is.
-(Mer: Yes, there is a catch-22 for us with regard to algorithms that allow for Byzantine-recovery. On the one hand, the user doesn't get worked up that something fishy is going on, or get run off because his system doesn't work. On the other hand, the parties communicating need to be able to get their signal, and if the user doesn't react differently to a Byzantine server's use of the subliminal channel, how do they get it? Well, let's turn to our friends at Cambridge and cite \url{http://www.freehaven.net/anonbib/cache/torta05.pdf}, which observes that you can learn something about the load on a server (or client) based on the latency in its network responses. So, for instance, I'm betting that if you could observe the network traffic of a Golberg-style PIR client~\cite{goldberg-2007}, during its hard-recover step, latency goes up because CPU usage goes up, and the client gets bogged down. We can totally hand-wave this; we might be able to even demonstrate this in practice with Ian's code and some simple ping results.)
+\subsection{In this paper}
-Note: we might want to cite Ishai et al.'s paper ``Cryptography from Anonymity'' which observes that anonymity systems can be used as a building-block for cryptographic protocols. There is a lot of work on the problems of subliminal channels in cryptographic protocols (the example that comes to mind is DSS~\cite{Sim93a,Sim93b}/El Gamal signatures~\cite{newtonchannel}), so we could say "this is as important as if it were a crypto primitive we were talking about, because Ishai et al. say it might as well be."
+Explain organization of the paper.
-There's a good overview/retrospective by Simmons, the discoverer of the DSA subliminal channel, here:
-\url{http://kabru.eecs.umich.edu/rtclonly/jsac/js1998/16sac04-simmons2.pdf}
+\subsection{Related work}
-Note: Does this get more interesting when we consider Bond and Danezis ``A Pact with the Devil''~\cite{pactwithdevil}?
+Mention actual PIR system designs/implementations.
-\section{Example}
+\section{Examples of Subliminal Channels in Several PIR Schemes}
\subsection{A simple subliminal channel in a Chor et al. PIR Service}
Let us examine the simple \textsc{xor}-based PIR scheme presented in the seminal paper on PIR~\cite{pir}, and observe the potential for covert communication between nodes in a multiple-server PIR system.
@@ -135,7 +148,7 @@
% I need to read the paper on how this latency stuff is detected, but I suspect the consequence of the observation above is that network traffic increases by a factor of n^2 because of all the extra pings going back and forth.
A worse problem, however, is the fact that each colluding server can only transmit a bit when its mark performs a \textsc{pir} request.
-In protocols like the Pynchon Gate~\cite{pynchon}, requests are rate-limited to a fixed number per cycle in order to reduce the effectiveness of long-term intersection attacks and other forms of traffic analysis.
+In systems like the Pynchon Gate~\cite{pynchon}, requests are rate-limited to a fixed number per cycle in order to reduce the effectiveness of long-term intersection attacks and other forms of traffic analysis~\cite{statistical-disclosure}.
If each colluding server can only transmit a few bits per day, the latency of this channel becomes so high as to be useless.
(Furthermore, since \textsc{pir} requests are user-initiated, a colluding server can be silenced if its mark goes offline for a few days.)
Fortunately, this problem is easy to address: partition the userbase into sets of marks, such that $S_i$'s set of marks, $M_{S_i}$, is disjoint with $\bigcup M_{S_j}$, $\forall j \neq i$.
@@ -154,7 +167,7 @@
Note that a colluding server only gets one chance per user to transmit a signal, as once a Byzantine-robust client detects a Byzantine action, it does not request any more blocks from that server.
Partitioning the userbase again comes into play here.
-Overall bandwidth goes down, because a server can only use a mark to transmit a 1 once, and once a server has done so, it cannot use that mark again.
+Overall bandwidth goes down, because a server can only use a mark to transmit a $1$ once, and once a server has done so, it cannot use that mark again.
However, a server can easily pass an expended mark to another colluding server; i.e., once $S_i$ has transmitted a 1 using mark $M_i$, all the colluding servers revise their list of marks, assigning $M_i$ to $S_{i+1}$ modulo $n$, the number of colluding servers.
As a final note, observe that $v$-Byzantine-robust protocols need not (and, in practice, probably should not) prearrange alternate
@@ -178,11 +191,20 @@
%(Also: What do we do about the scenario where two groups are using this channel and their set of marks overlaps? Collision becomes a problem again.)
+\section{Coercing Collusion from Users}
+In their paper ``A Pact with the Devil'', Bond and Danezis discuss ways an adversary can entice third-party users to facilitate his attacks by cooperating in exchange for incentives (and under threat of punishment for failure to cooperate)~\cite{pactwithdevil}. A clever attacker employing these methods could significantly broaden the communication channel for the covert communications of the servers; rather than simply relying on an unwitting user's side-channel leakage in the form of success-or-failure detection, users could be drafted into relaying messages encoded in the seemingly random data that PIR clients transmit to the PIR databases.
+
+
\section{Conclusion}
\paragraph{Acknowledgements}
+Meredith L. Patterson's would like to thank the COSIC group at K.U. Leuven, for its hospitality during her visit to Leuven, and for the discussions which lead in part to this work.
+Len Sassaman's work was supported in part by the EU within the PRIME Project under contract IST-2002-507591.
+
+
+
\bibliographystyle{plain}
\bibliography{byzantine-postman-rings-twice}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/