[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] r1769: First check-in. (doc/trunk/pynchon-gate/bp-ringstwice)
Author: rabbi
Date: 2007-03-29 05:00:31 -0400 (Thu, 29 Mar 2007)
New Revision: 1769
Added:
doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib
doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
Log:
First check-in.
Added: doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib
===================================================================
--- doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib 2007-03-26 06:59:59 UTC (rev 1768)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.bib 2007-03-29 09:00:31 UTC (rev 1769)
@@ -0,0 +1,235 @@
+@inproceedings{simmons83,
+ author = {Gustavus J. Simmons},
+ title = {The Prisoners' Problem and the Subliminal Channel},
+ editor = {David Chaum},
+ booktitle = {Advances in Cryptology:\ Proceedings of Crypto 83},
+ year = {1984},
+ pages = {51--67},
+ publisher = {Plenum Press}
+}
+
+
+@inproceedings{Sim93a,
+ author = {Gustavus J. Simmons},
+ title = {Subliminal communication is easy using the DSA},
+ booktitle = {EUROCRYPT '93: Workshop on the theory and application of cryptographic techniques on Advances in cryptology},
+ year = {1994},
+ isbn = {3-540-57600-2},
+ pages = {218--232},
+ location = {Lofthus, Norway},
+ publisher = {Springer-Verlag New York, Inc.},
+ address = {Secaucus, NJ, USA},
+ }
+
+@inproceedings{Sim93b,
+ author = {Gustavus J. Simmons},
+ title = {The Subliminal Signatures in the U.S. Digital Signature Algorithm (DSA)},
+ booktitle = {3rd Symposium on State and Progress of Research in Cryptography},
+ year = {1993},
+ month = {February},
+ location = {Rome, Italy},
+ }
+
+@inproceedings{simmon93c,
+ author = {G.J. Simmons},
+ title = {The consequences of trust in shared secret schemes},
+ editor = {Tor Helleseth},
+ booktitle = {Advances in Cryptology:\ EUROCRYPT '93},
+ year = {1994},
+ series = lncs,
+ volume = {765},
+ pages = {448-452},
+ publisher = {Springer}
+}
+
+@article{simmon98a,
+ author = {Gustavus J. Simmons},
+ title = {Results Concerning the Bandwidth of Subliminal Channels},
+ journal = {IEEE Journal on Selected Areas in Communications},
+ year = {1998},
+ volume = {16},
+ number = {4},
+ month = may
+}
+
+
+@article{simmon98b,
+ author = {Gustavus J. Simmons},
+ title = {The History of Subliminal Channels},
+ journal = {IEEE Journal on Selected Areas in Communications},
+ year = {1998},
+ volume = {16},
+ number = {4},
+ month = {May},
+}
+
+@INPROCEEDINGS{newtonchannel,
+ author = {Ross J. Anderson and Serge Vaudenay and Bart Preneel and Kaisa Nyberg},
+ title = {The Newton Channel},
+ year = {1996},
+ pages = {151-156},
+ booktitle = {Information Hiding, 1st International Workshop},
+ editor = {Ross J. Anderson},
+ volume = {1174},
+ number = {},
+ series = {Lecture Notes in Computer Science},
+ address = {Cambridge,UK},
+ publisher = {Springer-Verlag}
+}
+
+@INPROCEEDINGS{pactwithdevil,
+ author = {Mike Bond and George Danezis},
+ title = {A Pact with the Devil},
+ year = {2006},
+ pages = {13},
+ booktitle = {New Security Paradigms Workshop (NSPW 2006)},
+ editor = { },
+ volume = {},
+ number = {},
+ series = {},
+ address = {Schloss Dagstuhl,DE},
+ publisher = {ACM}
+}
+
+@inproceedings{torta05,
+ title = {Low-Cost Traffic Analysis of {Tor}},
+ author = {Steven J. Murdoch and George Danezis},
+ booktitle = {Proceedings of the 2005 IEEE Symposium on Security and Privacy},
+ year = {2005},
+ month = {May},
+ publisher = {IEEE CS},
+ www_important = {1},
+ www_pdf_url = {http://www.cl.cam.ac.uk/users/sjm217/papers/oakland05torta.pdf},
+ www_section = {Traffic analysis},
+}
+
+@article{shamir-secret,
+ author = {A. Shamir},
+ title = {{How to Share a Secret}},
+ journal = {Communications of the ACM},
+ volume = {22},
+ number = {11},
+ year = {1979},
+ issn = {0001-0782},
+ pages = {612--613},
+ doi = {http://doi.acm.org/10.1145/359168.359176},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
+
+@article{tompa-woll,
+ author = {M. Tompa and H. Woll},
+ title = {{How to Share a Secret with Cheaters}},
+ journal = {Journal of Cryptology},
+ volume = {1},
+ number = {2},
+ year = {1988},
+ issn = {0933-2790},
+ pages = {133--138},
+ publisher = {Springer-Verlag New York, Inc.},
+ address = {Secaucus, NJ, USA},
+ }
+
+@inproceedings{pailli99,
+ author = {Pascal Paillier},
+ title = {{Public-Key Cryptosystems Based on Composite Degree
+ Residuosity Classes}},
+ editor = {Jacques Stern},
+ booktitle = {Advances in Cryptology:\ EUROCRYPT '99},
+ year = {1999},
+ series = {Lecture Notes in Computer Science},
+ volume = {1592},
+ pages = {223--238},
+ publisher = {Springer-Verlag},
+}
+
+@inproceedings{tau-indy,
+ author = {Yael Gertner and Shafi Goldwasser and Tal Malkin},
+ title = {A Random Server Model for Private Information Retrieval or How to Achieve Information Theoretic PIR Avoiding Database Replication},
+ booktitle = {RANDOM '98: Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science},
+ year = {1998},
+ isbn = {3-540-65142-X},
+ pages = {200--217},
+ publisher = {Springer-Verlag},
+ address = {London, UK},
+ }
+
+ @inproceedings{beimel-robust,
+ author = {A. Beimel and Y. Stahl},
+ title = {Robust information-theoretic private information retrieval},
+ booktitle = {3rd Conf. on Security in Communication Networks},
+ editor = {S. Cimato C. Galdi G. Persiano },
+ publisher = {Springer-Verlag},
+ series = {Lecture Notes in Computer Science},
+ pages = {326-341},
+ volume = {2576},
+ year = {2002}
+}
+
+@inproceedings{beimel-barrier,
+ title = {{Breaking the $O(n^{1/(2k-1)})$ Barrier for Information-Theoretic Private Information Retrieval}},
+ author = {Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Jean-Fran\c{c}ois Raymond},
+ booktitle = {Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS)},
+ year = {2002},
+ www_pdf_url = {http://www.cs.bgu.ac.il/~beimel/Papers/BIKR.pdf},
+}
+
+@inproceedings{goldberg-2007,
+ title = {{Improving the Robustness of Private Information Retrieval}},
+ author = {Ian Goldberg},
+ booktitle = {Proceedings of the 2007 IEEE Symposium on Security and Privacy},
+ year = {2007},
+ month = {May},
+ note = {\url{http://www.cypherpunks.ca/~iang/pubs/robustpir.pdf}},
+ www_pdf_url = {http://www.cypherpunks.ca/~iang/pubs/robustpir.pdf},
+}
+
+@inproceedings{pir,
+ title = {Private Information Retrieval},
+ author = {Benny Chor and Oded Goldreich and Eyal Kushilevitz and Madhu Sudan},
+ booktitle = {{IEEE} Symposium on Foundations of Computer Science},
+ pages = {41-50},
+ year = {1995},
+ www_ps_url = {http://theory.lcs.mit.edu/~madhu/papers/pir-journ.ps},
+}
+
+@article{beimel01informationtheoretic,
+ author = {Amos Beimel and Yuval Ishai},
+ title = {Information-Theoretic Private Information Retrieval: {A} Unified Construction},
+ journal = {Lecture Notes in Computer Science},
+ volume = {2076},
+ pages = {89--98},
+ year = {2001},
+ www_pdf_url = {http://www.cs.bgu.ac.il/~beimel/Papers/BI.pdf},
+}
+
+@techreport{cosic-2007-001,
+ author = {Len Sassaman and Bart Preneel},
+ title = {{The Byzantine Postman Problem: A Trivial Attack Against PIR-based Nym Servers}},
+ year = {2007},
+ month = {February},
+ institution = {Katholieke Universiteit Leuven},
+ number = {ESAT-COSIC 2007-001},
+ note = {\url{http://www.cosic.esat.kuleuven.be/publications/article-880.pdf}},
+}
+
+@misc{pynchon-spec,
+ title = {{P}ynchon {G}ate {P}rotocol Draft Specification},
+ author = {Nick Mathewson},
+ year = {2004},
+ month = {September},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.abditum.com/pynchon/}},
+}
+
+@inproceedings{pynchon,
+ title = {{The Pynchon Gate: A Secure Method of Pseudonymous Mail Retrieval}},
+ author = {Len Sassaman and Bram Cohen and Nick Mathewson},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2005)}},
+ year = {2005},
+ month = {November},
+ address = {Arlington, VA, USA},
+ www_pdf_url = {http://www.abditum.com/pynchon/sassaman-wpes2005.pdf},
+ www_section = {Pseudonymity},
+}
Added: doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
===================================================================
--- doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex 2007-03-26 06:59:59 UTC (rev 1768)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex 2007-03-29 09:00:31 UTC (rev 1769)
@@ -0,0 +1,124 @@
+\documentclass[a4paper]{../llncs-rabbi}
+
+\usepackage{url}
+\usepackage{graphics}
+\usepackage{amsmath}
+\usepackage{subfigure}
+\usepackage{epsfig}
+
+% Cut down on whitespace above and below figures displayed at head/foot of
+% page.
+\setlength{\textfloatsep}{3mm}
+% Cut down on whitespace above and below figures displayed in middle of page
+\setlength{\intextsep}{3mm}
+% Cut down the whitespace at the end of the page
+\setlength{\topmargin}{1mm}
+
+\begin{document}
+
+\title{Subliminal Channels in the Private Information Retrieval Protocols}
+%\subtitle{The Byzantine Postman Always Rings Twice}
+
+\author{Meredith L. Patterson\inst{1} \and Len Sassaman\inst{2}}
+
+\institute{The University of Iowa, Department of Computer Science \\
+Iowa City, Iowa \\
+\email{mlpatter@xxxxxxxxxxxx}
+\and
+Katholieke Universiteit Leuven, ESAT-COSIC \\
+Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium
+\email{len.sassaman@xxxxxxxxxxxxxxxx}}
+
+
+\maketitle
+
+
+\begin{abstract}
+Information-theoretic private information retrieval (PIR) protocols, such as those described by Chor et al.~\cite{pir}, provide a mechanism by which users can retrieve information from a database distributed across multiple servers in such a way that neither the servers nor an outside observer can determine the contents of the data being retrieved. More recent PIR protocols also provide protection against Byzantine servers, such that a user can detect when one or more servers have attempted to tamper with the data he has requested. In some cases (as in the protocols presented by Beimel and Stahl~\cite{beimel-robust}), the user can still recover his data and protect the contents of his query if the number of Byzantine servers is below a certain threshold; this property is referred to as \emph{Byzantine-recovery}.
+
+However, tampering with a user's data is not the only goal a Byzantine server might have. We present a scenario in which an arbitrarily sized coalition of Byzantine servers transforms the userbase of a PIR network into a signaling framework with varying levels of detectability by means of a subliminal channel~\cite{simmons83}. We describe several such subliminal channel techniques, illustrate several use-cases for this subliminal channel, and demonstrate its applicability to a wide variety of PIR protocols. Finally, we demonstrate methods to hinder an entity's ability to sustain long-term communication through these channels in certain PIR protocols modified to prevent this sort of activity.
+
+\end{abstract}
+
+
+
+\section{Introduction}
+
+\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{Example}
+
+\subsection{Subliminal channels 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.
+
+Suppose there are three servers: an honest server $A$ and Byzantine servers $B$ and $C$ in collusion.
+Out of $n$ buckets, the bucket to be retrieved is bucket $b_1$.
+The user sends bit vectors $\vec v_A$, $\vec v_B$, $\vec v_C$ to $A, B$ and $C$ such that $\vec v_A \oplus \vec v_B \oplus \vec v_C = \langle 1\, 0\, 0\, 0\, \ldots \rangle$, e.g.: \\
+
+\begin{tabular}[c]{|c|cccc|}
+\hline
+$A$ & 1 & 1 & 1 & 0 \\
+\hline
+$B$ & 0 & 1 & 1 & 1 \\
+\hline
+$C$ & 0 & 0 & 0 & 1 \\
+\hline
+\end{tabular} \\
+
+Thus $A$ should send the user $b_{A1} \oplus b_{A2} \oplus b_{A3}$, $B$ should send $b_{B2} \oplus b_{B3} \oplus b_{B4}$, and $C$ should send $b_{C4}$.
+However, suppose $B$ and $C$ agree to flip the same bit in the vectors they received --- in this case, bucket 3: \\
+
+\begin{tabular}[c]{|c|cccc|}
+\hline
+$A$ & 1 & 1 & 1 & 0 \\
+\hline
+$B$ & 0 & 1 & 0 & 1 \\
+\hline
+$C$ & 0 & 0 & 1 & 1 \\
+\hline
+\end{tabular} \\
+
+The \textsc{xor} of all three vectors, and thus the \textsc{xor} of the returned data, still unveils the contents of $b_1$.
+More than two servers can collude in this fashion, although an odd number of colluding servers must flip bits for at least two buckets (e.g., $B$ and $C$ flip bits for bucket $j$ while $C$ and $D$ flip bits for bucket $k$).
+
+Through this channel, colluding servers could communicate potentially sensitive information even if the network channel were monitored for such communication.
+
+\section{Conclusion}
+
+\paragraph{Acknowledgements}
+
+
+\bibliographystyle{plain}
+\bibliography{byzantine-postman-rings-twice}
+
+
+\end{document}
\ No newline at end of file
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/