[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] r1762: @techreport{cosic-2007-001, author = {Len Sassaman and Bart (doc/trunk/pynchon-gate)
Author: rabbi
Date: 2007-02-25 13:25:19 -0500 (Sun, 25 Feb 2007)
New Revision: 1762
Added:
doc/trunk/pynchon-gate/byzantine-faults.bib
doc/trunk/pynchon-gate/byzantine-faults.pdf
doc/trunk/pynchon-gate/byzantine-faults.tex
Log:
@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},
url = {http://www.cosic.esat.kuleuven.be/publications/article-880.pdf},
}
Added: doc/trunk/pynchon-gate/byzantine-faults.bib
===================================================================
--- doc/trunk/pynchon-gate/byzantine-faults.bib 2007-02-10 03:37:53 UTC (rev 1761)
+++ doc/trunk/pynchon-gate/byzantine-faults.bib 2007-02-25 18:25:19 UTC (rev 1762)
@@ -0,0 +1,745 @@
+@inproceedings{CPIR,
+ author = {Benny Chor and Niv Gilboa},
+ title = {Computationally private information retrieval (extended abstract)},
+ booktitle = {STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of Computing},
+ year = {1997},
+ isbn = {0-89791-888-6},
+ pages = {304--313},
+ location = {El Paso, Texas, United States},
+ doi = {http://doi.acm.org/10.1145/258533.258609},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
+
+@article{RSA,
+ author = {R. L. Rivest and A. Shamir and L. Adleman},
+ title = {A method for obtaining digital signatures and public-key cryptosystems},
+ journal = {Communications of the ACM},
+ volume = {21},
+ number = {2},
+ year = {1978},
+ issn = {0001-0782},
+ pages = {120--126},
+ doi = {http://doi.acm.org/10.1145/359340.359342},
+ publisher = {ACM Press},
+ address = {New York, NY, USA},
+ }
+
+@article{diffie76new,
+ author = {Whitfield Diffie and Martin E. Hellman},
+ title = {New Directions in Cryptography},
+ journal = {IEEE Transactions on Information Theory},
+ volume = {IT-22},
+ number = {6},
+ pages = {644--654},
+ date = {November 1976},
+ year = {1976},
+ url = {citeseer.ist.psu.edu/diffie76new.html},
+}
+
+@Article{remailer-history,
+ author = {Sameer Parekh},
+ title = {Prospects for Remailers},
+ journal = {First Monday},
+ volume = {1},
+ number = {2},
+ month = {August},
+ year = {1996},
+ note = {\url{http://www.firstmonday.dk/issues/issue2/remailers/}},
+}
+
+@Article{Szabo97,
+ author = {Nick Szabo},
+ title = {Formalizing and securing relationships on public networks},
+ journal = {First Monday},
+ volume = {2},
+ number = {9},
+ month = {September},
+ year = {1997},
+ note = {\url{http://www.firstmonday.org/issues/issue2_9/szabo/index.html}},
+}
+
+@article{invasive,
+author = {George Lawton},
+title = {Invasive Software: Who's Inside Your Computer?},
+journal = {Computer},
+volume = {35},
+number = {7},
+year = {2002},
+issn = {0018-9162},
+pages = {15-18},
+doi = {http://doi.ieeecomputersociety.org/10.1109/MC.2002.1016895},
+publisher = {IEEE Computer Society},
+address = {Los Alamitos, CA, USA},
+}
+
+@article{kissner04private,
+ author = {L. Kissner and A. Oprea and M. Reiter and D. Song and K. Yang},
+ title = {Private keywordbased push and pull with applications to anonymous communication},
+ journal = {Applied Cryptography and Network Security},
+ year = {2004},
+ url = {citeseer.ist.psu.edu/kissner04private.html},
+ }
+
+
+@article{chaum-mix,
+ title = {Untraceable electronic mail, return addresses, and digital pseudonyms},
+ author = {David Chaum},
+ journal = {Communications of the ACM},
+ volume = {4},
+ number = {2},
+ year = {1981},
+ month = {February},
+ www_txt_url = {http://www.eskimo.com/~weidai/mix-net.txt},
+ www_pdf_url = {http://www.ovmj.org/GNUnet/papers/p84-chaum.pdf},
+ www_html_url = {http://world.std.com/~franl/crypto/chaum-acm-1981.html},
+ www_section = {Anonymous communication},
+}
+
+@article{wagner,
+ author = {Robyn Wagner},
+ title = {{Don't Shoot the Messenger: Limiting the Liability of Anonymous Remailer Operators}},
+ journal = {New Mexico Law Review},
+ volume = {32},
+ number = {Winter},
+ pages = {99--142},
+ year = {2002},
+}
+
+@article{elgamal,
+ title = {{A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms}},
+ author = {Taher ElGamal},
+ journal = {{IEEE} Transactions on Information Theory},
+ volume = {IT-31},
+ number = {4},
+ pages = {469--472},
+ year = {1985},
+}
+
+@article{jap-backdoor,
+ title = {Net anonymity service back-doored},
+ author = {Thomas C. Greene},
+ journal = {The Register},
+ year = {2003},
+ note = {\url{http://www.theregister.co.uk/2003/08/21/net_anonymity_service_backdoored/}},
+}
+
+@misc{jap-pr,
+ author = {Independent Centre for Privacy Protection},
+ title = {{AN.ON} still guarantees anonymity},
+ year = {2003},
+ howpublished = {\url{http://www.datenschutzzentrum.de/material/themen/presse/anonip_e.htm}},
+}
+
+
+@phdthesis{ian-thesis,
+ title = {A Pseudonymous Communications Infrastructure for the Internet},
+ author = {Ian Goldberg},
+ school = {UC Berkeley},
+ year = {2000},
+ month = {December},
+ www_pdf_url = {http://www.isaac.cs.berkeley.edu/~iang/thesis-final.pdf},
+ www_section = {Anonymous communication},
+}
+
+@phdthesis{gd-thesis,
+ title = {Better Anonymous Communications},
+ author = {George Danezis},
+ school = {University of Cambridge},
+ year = {2004},
+}
+
+@inproceedings{freehaven-berk,
+ title = {The {Free Haven Project}: Distributed Anonymous Storage Service},
+ author = {Roger Dingledine and Michael J. Freedman and David Molnar},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_important = {1},
+ www_ps_url = {http://freehaven.net/doc/berk/freehaven-berk.ps},
+ www_section = {Anonymous publication},
+}
+
+@inproceedings{universal,
+ title = {Universal Re-Encryption for Mixnets},
+ author = {Philippe Golle and Markus Jakobsson and Ari Juels and Paul Syverson},
+ booktitle = {Proceedings of the 2004 RSA Conference, Cryptographer's track},
+ year = {2004},
+ month = {February},
+ address = {San Francisco, CA, USA},
+ www_section = {Anonymous communication},
+ www_pdf_url = {http://www.syverson.org/univrenc-ctrsa.pdf},
+}
+
+@inproceedings{bleichenbacher,
+ title = {Generating {E}l{G}amal signatures without knowing the secret key},
+ author = {Daniel Bleichenbacher},
+ booktitle = {Eurocrypt 96},
+ year = {1996},
+ month = {May},
+ address = {Zaragoza, Spain},
+ ftp_ps_url = {ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/ElGamal.ps},
+}
+
+@inproceedings{mixmaster-reliable,
+ title = {Comparison between two practical mix designs},
+ author = {Claudia D\'{\i}az and Len Sassaman and Evelyne Dewitte},
+ booktitle = {Proceedings of 9th European Symposium on Research in Computer Security
+ (ESORICS)},
+ year = {2004},
+ month = {September},
+ address = {France},
+ series = {LNCS},
+ www_ps_gz_url = {http://www.esat.kuleuven.ac.be/~cdiaz/papers/cdiaz_esorics.ps.gz},
+ www_section = {Traffic analysis},
+}
+
+@inproceedings{jap,
+ title = {Web {MIX}es: A system for anonymous and unobservable {I}nternet access},
+ author = {Oliver Berthold and Hannes Federrath and Stefan K\"opsell},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ pages = {115--129},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_pdf_url = {http://www.inf.fu-berlin.de/~feder/publ/2001/BeFK2001BerkeleyLNCS2009.pdf},
+ www_section = {Anonymous communication},
+}
+
+@misc{nguyen,
+ title = {{Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3}},
+ author = {Phong Q. Nguyen},
+ booktitle = {Eurocrypt 04},
+ year = {2004},
+ month = {May},
+ address = {Interlaken, Switzerland},
+ editor = {C. Cachin},
+ ftp_ps_url = {ftp://ftp.di.ens.fr/pub/users/pnguyen/Eurocrypt04.ps},
+}
+
+
+@inproceedings{fiveyearslater,
+ title = {{Privacy-enhancing technologies for the Internet, II: Five years later}},
+ author = {Ian Goldberg},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2002)},
+ year = {2002},
+ month = {April},
+ editor = {Roger Dingledine and Paul Syverson},
+ publisher = {Springer-Verlag, LNCS 2482},
+ www_section = {Misc},
+}
+
+@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{minx,
+ title = {Minx: A Simple and Efficient Anonymous Packet Format},
+ author = {George Danezis and Ben Laurie},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2004)}},
+ year = {2004},
+ month = {October},
+ address = {Washington, DC, USA},
+}
+
+@inproceedings{nym-alias-net,
+ title = {{The Design, Implementation and Operation of an Email Pseudonym Server}},
+ author = {David Mazi\`eres and M. Frans Kaashoek},
+ booktitle = {Proceedings of the 5th ACM Conference on Computer and Communications
+ Security (CCS'98)},
+ year = {1998},
+ month = {November},
+ publisher = {ACM Press},
+ www_pdf_url = {ftp://cag.lcs.mit.edu/pub/dm/papers/mazieres:pnym.pdf},
+ www_section = {Pseudonymity},
+}
+
+@inproceedings{mixminion,
+ title = {{Mixminion: Design of a Type III Anonymous Remailer Protocol}},
+ author = {George Danezis and Roger Dingledine and Nick Mathewson},
+ booktitle = {Proceedings of the 2003 IEEE Symposium on Security and Privacy},
+ year = {2003},
+ month = {May},
+ www_pdf_url = {http://mixminion.net/minion-design.pdf},
+ www_important = {1},
+ www_section = {Anonymous communication},
+}
+
+@inproceedings{disad-free-routes,
+ title = {The disadvantages of free {MIX} routes and how to overcome them},
+ author = {Oliver Berthold and Andreas Pfitzmann and Ronny Standtke},
+ booktitle = {Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design
+ Issues in Anonymity and Unobservability},
+ year = {2000},
+ month = {July},
+ pages = {30--45},
+ editor = {H. Federrath},
+ publisher = {Springer-Verlag, LNCS 2009},
+ www_important = {1},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.tik.ee.ethz.ch/~weiler/lehre/netsec/Unterlagen/anon/disadvantages_berthold.pdf},
+}
+
+@inproceedings{goldschlag96,
+ author = {David M. Goldschlag and Michael G. Reed and Paul F. Syverson},
+ title = {Hiding Routing Information},
+ booktitle = {Information Hiding},
+ pages = {137-150},
+ year = {1996},
+ www_pdf_url = {http://www.onion-router.net/Publications/IH-1996.pdf},
+}
+
+@inproceedings{berthold,
+ author = {Oliver Berthold and Sebastian Clau\ss and Stefan K\"opsell and Andreas Pfitzmann},
+ title = {Efficiency Improvements of the Private Message Service},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2001)},
+ year = {2001},
+ month = {April},
+ editor = {Ira S. Moskowitz},
+ publisher = {Springer-Verlag, LNCS 2137},
+ pages = {112-125},
+}
+
+@inproceedings{cooper,
+ title = {Preserving Privacy in a Network of Mobile Computers},
+ author = {David A. Cooper and Kenneth P. Birman},
+ booktitle = {Proceedings of the 1995 IEEE Symposium on Security and Privacy},
+ year = {1995},
+ month = {May},
+}
+
+@inproceedings{back01,
+ title = {Traffic Analysis Attacks and Trade-Offs in Anonymity Providing Systems},
+ author = {Adam Back and Ulf M\"oller and Anton Stiglic},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2001)},
+ year = {2001},
+ month = {April},
+ pages = {245--257},
+ editor = {Ira S. Moskowitz},
+ publisher = {Springer-Verlag, LNCS 2137},
+ www_important = {1},
+ www_section = {Traffic analysis},
+ www_pdf_url = {http://www.cypherspace.org/adam/pubs/traffic.pdf},
+}
+
+@inproceedings{reusable-channels,
+ title = {Reusable Anonymous Return Channels},
+ author = {Philippe Golle and Markus Jakobsson},
+ booktitle = {{Proceedings of the Workshop on Privacy in the Electronic Society (WPES
+ 2003)}},
+ year = {2003},
+ month = {October},
+ address = {Washington, DC, USA},
+ www_pdf_url = {http://crypto.stanford.edu/~pgolle/papers/return.pdf},
+ www_remarks = {Reencryption mix-nets can allow users to use a single reply channel even
+ when they maintain multiple separate nyms (think of it like a reply block but it
+ looks different each time you give it to somebody).},
+ www_ps_url = {http://crypto.stanford.edu/~pgolle/papers/return.ps},
+ www_section = {Anonymous communication},
+}
+
+@conference{bh-us-03-sassaman-dingledine,
+ title = {{Attacks on Anonymity Systems: Theory and Practice}},
+ author = {Roger Dingledine and Len Sassaman},
+ booktitle = {{Black Hat USA 2003 Briefings}},
+ year = {2003},
+ month = {July},
+ address = {Las Vegas, NV, USA},
+ www_pdf_url = {http://www.blackhat.com/presentations/bh-usa-03/bh-us-03-sassaman-dingledine/bh-us-03-sassaman.pdf},
+}
+
+@inproceedings{trickle02,
+ title = {From a Trickle to a Flood: Active Attacks on Several Mix Types},
+ author = {Andrei Serjantov and Roger Dingledine and Paul Syverson},
+ booktitle = {Proceedings of Information Hiding Workshop (IH 2002)},
+ year = {2002},
+ month = {October},
+ editor = {Fabien Petitcolas},
+ publisher = {Springer-Verlag, LNCS 2578},
+ www_pdf_url = {http://freehaven.net/doc/batching-taxonomy/taxonomy.pdf},
+ www_ps_url = {http://freehaven.net/doc/batching-taxonomy/taxonomy.ps},
+ www_section = {Traffic analysis},
+}
+
+@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},
+}
+
+@inproceedings{bittorrent,
+ author = {Bram Cohen},
+ title = {{Incentives Build Robustness in BitTorrent}},
+ booktitle = {Workshop on Economics of Peer-to-Peer Systems},
+ year = {2003},
+ month = {May},
+ address = {Berkeley, CA, USA},
+ note = {\url{http://www.sims.berkeley.edu/research/conferences/p2pecon/papers/s4-cohen.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},
+}
+
+@inproceedings{whittenwhy,
+ author = "Alma Whitten and J. D. Tygar",
+ title = "Why {J}ohnny can't encrypt: {A} usability evaluation of {PGP} 5.0",
+ booktitle = "8th USENIX Security Symposium",
+ year = "1999",
+ url = "citeseer.ist.psu.edu/whitten99why.html",
+ url = "citeseer.nj.nec.com/whitten99why.html" }
+
+@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_pdf_url = {http://www.cl.cam.ac.uk/users/sjm217/papers/oakland05torta.pdf},
+ www_section = {Traffic analysis},
+}
+
+@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{freedom2-arch,
+ title = {Freedom Systems 2.0 Architecture},
+ author = {Philippe Boucher and Adam Shostack and Ian Goldberg},
+ institution = {Zero Knowledge Systems, {Inc.}},
+ year = {2000},
+ month = {December},
+ type = {White Paper},
+ www_pdf_url = {http://osiris.978.org/~brianr/crypto-research/anon/www.freedom.net/products/whitepapers/Freedom_System_2_Architecture.pdf},
+ www_section = {Anonymous communication},
+ day = {18},
+}
+
+@techreport{freedom2-mail,
+ title = {Freedom 2.0 Mail System},
+ author = {Roger McFarlane and Adam Back and Graydon Hoare and Serge Chevarie-Pelletier and Bill Heelan and Christian Paquin and Deniz Sarikaya},
+ institution = {Zero Knowledge Systems, {Inc.}},
+ year = {2000},
+ month = {December},
+ type = {White Paper},
+ www_pdf_url = {http://www.cypherspace.org/~adam/pubs/freedom2-mail.pdf},
+ www_section = {Anonymous communication},
+ day = {19},
+}
+
+@misc{kidnap-len,
+ author = {Roger Dingledine},
+ title = {Remop inbreeding, or, the 'kidnap {L}en' attack},
+ year = {2003},
+ month = {March},
+ howpublished = {Mailing list post},
+ note = {\url{http://archives.seul.org/mixminion/dev/Mar-2003/msg00007.html}},
+}
+
+@misc{hal-remailer,
+ author = {Hal Finney},
+ title = {New remailer...},
+ year = {1992},
+ month = {October},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1992/10/msg00082.html}},
+}
+
+@misc{harmful,
+ author = {Anonymous},
+ title = {alt.anonymous.messages Considered Harmful},
+ year = {1995},
+ month = {November},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1995/11/msg00089.html}},
+}
+
+@misc{aam,
+ author = {Rick Busdiecker},
+ title = {Message pool: alt.anonymous.messages},
+ year = {1994},
+ month = {August},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1994/08/msg00185.html}},
+}
+
+@misc{remailer-attacks,
+ author = {Lance Cottrell},
+ title = {Mixmaster and Remailer Attacks},
+ note = {\url{http://www.obscura.com/~loki/remailer/remailer-essay.html}},
+}
+
+@misc{replay,
+ author = {Lance Cottrell},
+ title = {Re: Strengthening Remailer Protocols},
+ year = {1996},
+ month = {September},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1996/09/msg00730.html}},
+}
+
+@misc{surb,
+ author = {Mike Ingle},
+ title = {Interoperability, One-use Remailer Tickets},
+ year = {1994},
+ month = {December},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1994/12/msg00245.html}},
+}
+
+@misc{pop-mix,
+ author = {Andrew Loewenstern},
+ title = {Re: Strengthening Remailer Protocols},
+ year = {1996},
+ month = {September},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1996/09/msg00898.html}},
+}
+
+@misc{tcmay,
+ author = {Tim May},
+ title = {Re: Strengthening Remailer Protocols},
+ year = {1996},
+ month = {September},
+ howpublished = {Mailing list post},
+ note = {\url{http://cypherpunks.venona.com/date/1996/09/msg00167.html}},
+}
+
+@misc{pipenet,
+ title = {PipeNet 1.1},
+ author = {Wei Dai},
+ year = {1996},
+ month = {August},
+ howpublished = {Usenet post},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.eskimo.com/~weidai/pipenet.txt}},
+}
+
+@misc{alpha-faq,
+ title = {{FAQ} for the {ALPHA.C2.ORG} {R}emailer},
+ author = {Andre Bacard},
+ year = {1995},
+ month = {October},
+ howpublished = {Usenet post},
+ note = {\url{http://groups.google.com/groups?selm=4q4tsr%248ui%40crl14.crl.com&output=gplain}},
+}
+
+@misc{prng-back,
+ title = {Personal Communication},
+ author = {Adam Back},
+ year = {2003},
+ month = {April},
+}
+
+@misc{sassaman-lisa,
+ title = {The Promise of Privacy},
+ author = {Len Sassaman},
+ year = {2002},
+ month = {November},
+ howpublished = {Invited talk, LISA XVI},
+ organization = {USENIX}
+}
+
+@inproceedings{danezis-pet2004,
+ title = {The Traffic Analysis of Continuous-Time Mixes},
+ author = {George Danezis},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2004)},
+ year = {2004},
+ month = {May},
+ series = {LNCS},
+ www_pdf_url = {http://www.cl.cam.ac.uk/users/gd216/cmm2.pdf},
+ www_section = {Traffic analysis},
+}
+
+@misc{pgp5-elgamal,
+ title = {{Re: ElGamal signature encoding}},
+ author = {Hal Finney},
+ year = {1998},
+ month = {April},
+ howpublished = {Mailing list post},
+ note = {\url{http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-04/0050.html}},
+}
+
+@misc{gpg-compromised,
+ title = {{GnuPG's ElGamal signing keys compromised}},
+ author = {Werner Koch},
+ year = {2003},
+ month = {November},
+ howpublished = {Mailing list post},
+ note = {\url{http://lists.gnupg.org/pipermail/gnupg-announce/2003q4/000276.html}},
+}
+
+@misc{mixmaster-spec,
+ title = {Mixmaster {P}rotocol --- {V}ersion 2},
+ author = {Ulf M\"oller and Lance Cottrell and Peter Palfrader and Len Sassaman},
+ year = {2003},
+ month = {July},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.abditum.com/mixmaster-spec.txt}},
+}
+
+@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/}},
+}
+
+@misc{underhill-spec,
+ title = {Underhill: A Proposed Type 3 Nymserver Protocol Specification},
+ author = {Nick Mathewson},
+ year = {2004},
+ month = {August},
+ www_section = {Anonymous communication},
+ note = {\url{http://www.mixminion.net/nym-spec.txt}},
+}
+
+@misc{rfc-1036,
+ title = {{Standard for Interchange of USENET Messages}},
+ author = {M. Horton and R. Adams},
+ year = {1987},
+ month = {December},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 1036},
+ www_txt_url = {http://www.ietf.org/rfc/rfc1036.txt},
+}
+
+@misc{rfc-2246,
+ title = {{The TLS Protocol}},
+ author = {T. Dierks and C. Allen},
+ year = {1999},
+ month = {January},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 2246},
+ www_txt_url = {http://www.ietf.org/rfc/rfc2246.txt},
+}
+
+@misc{rfc-2440,
+ title = {{OpenPGP Message Format}},
+ author = {J. Callas and L. Donnerhacke and H. Finney and R. Thayer},
+ year = {1998},
+ month = {November},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 2440},
+ www_txt_url = {http://www.ietf.org/rfc/rfc2440.txt},
+}
+
+@misc{rfc-2779,
+ title = {{Instant Messaging / Presence Protocol Requirements}},
+ author = {M. Day and S. Aggarwal and G. Mohr and J. Vincent},
+ year = {2000},
+ month = {February},
+ organization = {Internet Engineering Task Force},
+ howpublished = {Request for Comments: 2779},
+ www_txt_url = {http://www.ietf.org/rfc/rfc2779.txt},
+}
+
+@inproceedings{tor-design,
+ title = {Tor: The Second-Generation Onion Router},
+ author = {Roger Dingledine and Nick Mathewson and Paul Syverson},
+ booktitle = {Proceedings of the 13th USENIX Security Symposium},
+ year = {2004},
+ month = {August},
+ www_pdf_url = {http://freehaven.net/tor/tor-design.pdf},
+ www_section = {Anonymous communication},
+}
+
+@misc{echolot,
+ author = {Peter Palfrader},
+ title = {Echolot: a pinger for anonymous remailers},
+ note = {\url{http://www.palfrader.org/echolot/}},
+}
+
+@misc{helsingius,
+ author = {Johan Helsingius},
+ title = {press release announcing closure of anon.penet.fi},
+ howpublished = {\url{http://www.penet.fi/press-english.html}},
+}
+
+@misc{mccoy,
+ author = {Jim McCoy},
+ title = {Anonymous Mailbox Servers},
+ year = {1997},
+ month = {August},
+ howpublished = {Presentation, HIP'97},
+}
+
+
+
+
+@inproceedings{econymics,
+ title = {{On the Economics of Anonymity}},
+ author = {Alessandro Acquisti and Roger Dingledine and Paul Syverson},
+ booktitle = {Financial Cryptography},
+ year = {2003},
+ editor = {Rebecca N. Wright},
+ publisher = {Springer-Verlag, LNCS 2742},
+}
+
+@InProceedings{e2e-traffic,
+ author = {Nick Mathewson and Roger Dingledine},
+ title = {Practical Traffic Analysis: Extending and Resisting Statistical Disclosure},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2004)},
+ year = {2004},
+ month = {May},
+ series = {LNCS},
+ www_section = traffic,
+ www_pdf_url = "http://freehaven.net/doc/e2e-traffic/e2e-traffic.pdf";,
+}
+
+@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/byzantine-faults.pdf
===================================================================
(Binary files differ)
Property changes on: doc/trunk/pynchon-gate/byzantine-faults.pdf
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: doc/trunk/pynchon-gate/byzantine-faults.tex
===================================================================
--- doc/trunk/pynchon-gate/byzantine-faults.tex 2007-02-10 03:37:53 UTC (rev 1761)
+++ doc/trunk/pynchon-gate/byzantine-faults.tex 2007-02-25 18:25:19 UTC (rev 1762)
@@ -0,0 +1,208 @@
+%\documentclass{acm_proc_article-sp}
+%\documentclass{sig-alternate}
+%\documentclass{sig-alt-full}
+\documentclass{llncs}
+
+
+\usepackage{url}
+\usepackage{graphics}
+\usepackage{amsmath}
+\usepackage{subfigure}
+\usepackage{epsfig}
+
+\setcounter{page}{1}
+
+\begin{document}
+
+%\balancecolumns
+\title{The Byzantine Postman Problem}
+\subtitle{A Trivial Attack Against PIR-based Nym Servers}
+
+%\numberofauthors{2}
+%\author{
+%\alignauthor Len Sassaman\\
+% \affaddr{Katholieke Universiteit Leuven}\\
+% \email{len.sassaman@xxxxxxxxxxxxxxxx}
+%\alignauthor Bart Preneel\\
+% \affaddr{Katholieke Universiteit Leuven}\\
+% \email{bart.preneel@xxxxxxxxxxxxxxxx}
+%}
+
+\author{Len Sassaman\inst{1} \and Bart Preneel\inst{1}}
+\institute{K. U. Leuven ESAT-COSIC \\
+Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium
+\email{\{len.sassaman,bart.preneel\}@esat.kuleuven.be}}
+
+
+\maketitle
+
+\begin{abstract}
+Over the last several decades, there have been numerous proposals for systems which can preserve the anonymity of the recipient of some data. Some have involved trusted third-parties or trusted hardware; others have been constructed on top of link-layer anonymity systems or mix-nets.
+
+In this paper, we evaluate a pseudonymous message system which takes the different approach of using Private Information Retrieval (PIR) as its basis. We expose a flaw in the system as presented: it fails to identify Byzantine servers. We provide suggestions on correcting the flaw, while observing the security and performance trade-offs our suggestions require.
+\end{abstract}
+
+
+\section{Introduction}
+Several proposals have been made for the use of private information
+retrieval (PIR)~\cite{pir} primitives to build secure, fault-tolerant
+pseudonymous mail retrieval systems~\cite{cooper,berthold,kissner04private,pynchon}.
+
+PIR-based pseudonym (or \emph{nym}) servers have several significant advantages over nym servers based on other technologies. PIR protocols can be designed to offer \emph{information-theoretic security}, i.e., assuming that the system is correct, an attacker with unlimited computational power cannot defeat the system merely by virtue of being able to perform calculations which reveal the private information. Other PIR protocols merely offer computational security: in Computational PIR systems~\cite{CPIR}, the privacy of the PIR query is protected only against an adversary restricted to polynomial-time computational capability.
+
+The most recent proposal for a nym server based on PIR with information-theoretic security, the Pynchon Gate~\cite{pynchon}, offers greater robustness, stronger anonymity assurances, and better traffic analysis resistance than previously proposed pseudonym systems. However, it contains a serious flaw in its protocol which can be used to launch a denial of service attack against the system, rendering it unusable. Furthermore, the attack is not merely limited to decreased utility of the system; due to the network-effects properties of anonymity systems, denying service to one set of users can effectively weaken the anonymity provided to a different set of users~\cite{econymics}.
+We identify this denial of service attack, evaluate the extent of the problem, and briefly consider solutions which may be considered as a means of making the protocol immune to the attack.
+
+\section{Background on Nym Servers}
+Pseudonymous messaging services allow users to send
+messages that originate at a pseudonymous address (or ``nym'') unlinked to
+the user, and to receive messages sent to that address, without allowing
+an attacker to deduce which users are associated with which pseudonyms.
+These systems can be used for parties to communicate without revealing their
+identities, or as a
+building-block for other systems that need a bi-directional anonymous
+communication channel, such as Free Haven~\cite{freehaven-berk}.
+
+%In the last twenty-five years, numerous approaches have been taken to developing secure
+%pseudonym servers (or ``nym servers''), and widely-varying definitions of security have been used when referring to such systems. The simplest, and perhaps most widely used pseudonym server of all time, was {\tt anon.penet.fi}~\cite{helsingius}. This system provided users with an easy, reliable way to receive mail while hiding their true identities and email addresses.
+
+%Sadly, this system relied on the integrity of the system operator (and host server) for the security of the pseudonyms in question. There existed a one-to-one mapping of true email address to nym address, which left the {\tt anon.penet.fi} system susceptible to attempts to coerce the operators (through lawsuits or other means~\cite{nym-alias-net,wagner,helsingius,jap-backdoor,jap-pr}) or surreptitiously compromise the security of the host server operating the pseudonym service~\cite{invasive}. Attacks which rely on sensitive information being stored in a retrievable location, such that an attacker can seize the data or coerce it out of the operator, are referred to alternatively as \emph{Legal Attacks, Hacking Attacks,} or \emph{Rubber Hose Attacks}~\cite{Szabo97,kidnap-len}, depending on the methods employed.
+
+%Clearly, solutions that do not rely on the frail integrity of a single network server, or its operators, were needed. The next widely discussed and implemented approach to nym servers were based on the anonymous communication primitive known as a \emph{mix}~\cite{chaum-mix}. Originally proposed by Chaum in 1981, mixes allow for anonymous communication from a sender to a recipient by means of nested, encrypted messages. In a mix network, there exist numerous nodes operated by independent entities. These nodes make their public encryption keys~\cite{diffie76new,RSA} public, and users select a path of nodes through which their anonymous message will travel, and then encrypt their messages in a nested fashion, starting with the last node, and progressing to the first node in the path. The sender then delivers the encrypted message to the first node in the path, which strips off its layer of encryption to reveal an encrypted blob addressed to the next node in the path. Thus the process continues, until the recipient receives the message, and the anonymity of the user is preserved as long as the nodes in his chosen path do not collude.\footnote{In reality, the security of a mix network depends on many factors. We have chosen to simplify the issue in our explanation, as direct attacks on mixes are not within the scope of this paper. See~\cite{trickle02, mixminion, pynchon} for more details on general mix security properties and attacks.}
+
+%In Chaum's seminal paper on mixes, he described a method of using \emph{return addresses}
+%in mix-nets: recipients encode a reply path, and allow senders to affix
+%messages to the encoded path. As the message moves through the network, the
+%path is decoded and the message encoded at each hop, until an encoded message
+%reaches its eventual recipient. This system relies upon all selected
+%component nodes of the chosen path remaining operational in order for mail to be
+%delivered, which can make the system too unreliable for practical
+%use if significant time elapses between path generation and message
+%origination.
+
+%Aside from fatal security flaws in early implementations of ``return address'' based nym servers~\cite{nym-alias-net} which lead to replay attacks against the mix network~\cite{replay}, even modern mix-net-based nym servers quickly fall victim to statistical disclosure attacks~\cite{statistical-disclosure,e2e-traffic}, which permit an attacker to observe the correlation over time between messages sent to a nym, and messages received by a user. In recent simulations of these attacks, Sassaman et al. show that a user's anonymity is compromised after receiving an average of 1775 messages~\cite{pynchon}. For an active user, this is well within a month's expected traffic.
+
+\section{The Pynchon Gate}
+
+To address the reliability problems of silent node failure, as well as the serious security problems of statistical disclosure and end-to-end traffic analysis, Sassaman et al. propose a complete architectural design of a PIR-based pseudonym service offering information-theoretic protection, called the Pynchon Gate~\cite{pynchon}.
+
+\subsection{Architecture overview}
+The architecture consists of an Internet-facing component referred to as the ``nym-server'', which receives messages addressed to users of the system and acts as a gateway between the pseudonym service and other Internet services such as email. Behind the nym-server is a component known as the ``collator'', which structures the incoming messages in the form of a three-level hash tree, which is then replicated to a series of mutually untrusted distribution databases referred to as ``distributors''.
+
+Email addressed to a specific pseudonym is stored in a specific location in the database, such that the owner of the pseudonym knows what information to request to obtain his message. Using the PIR protocol described in Section~\ref{subsec:PIR}, the user submits a PIR query to $\ell$ distributors, and his message is returned with none of the distributors able to deduce any information about the user's query unless all $\ell$ distributors collude.
+
+
+
+%Known parameters:
+%$\ell$: number of servers chosen by the client
+%$b$: number of discrete blocks in the database
+
+%Client operations (retrieving block number $\beta$):
+%\begin{equation}
+%Let $e_{"\beta"}$ be a bit string of length $b$ consisting entirely of 0s except for position $\beta$.
+%\end{equation}
+%\begin{equation}
+%Generate $\ell-1$ random bit strings $S_{"1"},\ldots,S_{"\ell"}-1$, each of length $b$
+%\end{equation}
+%\begin{equation}
+%Compute $S_{"\ell"} = S_{"1"} \oplus \ldots \oplus S_{"\ell"}-1 \oplus e_{"\beta"}$
+%\end{equation}
+\subsection {The Pynchon Gate PIR Protocol}
+\label{subsec:PIR}
+
+The protocol runs as follows: after choosing distributors, the client
+establishes an encrypted connection to each
+(e.g., using TLS~\cite{rfc-2246}). These connections must be unidirectionally authenticated
+to prevent man-in-the-middle attacks, and can be made sequentially or in
+parallel.
+
+The client sends a different ``random-looking'' bit vector
+$\nu_{s\beta}$ to each distributor $s$ for each message block $\beta$ to be retrieved. Each
+bit vector has a length equal to the number of message blocks in the database. Each
+distributor $s$ then
+computes $R(\nu_{s\beta})$ as the exclusive-OR of all message blocks whose positions is set to $1$
+in $\nu_{s\beta}$. The resulting value is then returned to the client.
+
+Thus, in order to retrieve the $\beta$'th message block, the client need only choose
+the values of $\nu_{s\beta}$ so that their XOR is 0 at every position
+except $\beta$. (For security, $\ell-1$ of the vectors should be generated
+randomly.) When the client receives the corresponding $R(\nu_{s\beta})$ values, she
+can XOR them to compute the message block's contents.
+
+
+\subsection{Byzantine Server Protection}
+
+In a distributed-trust anonymity system such as the Pynchon Gate, there exists the possibility that some servers may be \emph{Byzantine}, i.e., they may behave incorrectly, either due to intentional malice or simple error.\footnote{This concern is present in many other anonymity systems, including Chaumian mix-nets~\cite{chaum-mix,mixmaster-spec,mixminion} and systems built on top of them~\cite{nym-alias-net,underhill-spec}.} In the case of the Pynchon Gate, the Byzantine behavior we are concerned with is the incorrect response to a PIR query of a distributor's database.
+
+All $n$ distributors in the system have the exact same copy of the database, and the system is designed such that any attempt by a Byzantine server to modify its response to the PIR query will be detected by the user when he verifies the root of the hash tree. This is crucial to preserving the anonymity properties of the system, for if an attacker may alter a message or observe the cleartext of a message, he may potentially be able to later link an input message with a given output retrieved by the nym holder.
+
+The Pynchon Gate's message and link encryption prevents an attacker from observing the cleartext of a message. Active attacks that are dependent upon the attacker's ability to alter some of the data being transmitted to the user such that the attacker may later link the user to his pseudonym based either on a variance in the user's response to altered versus unaltered data, or by simply recognizing the product of the altered data as it is processed by the system (collectively known as \emph{tagging attacks}~\cite{bh-us-03-sassaman-dingledine}) are ineffective, as TLS protects data integrity on the wire. Thus, any tagging attacks an attacker wished to attempt against a user would have to occur through the use of a corrupt distributor. To protect against the case where a distributor provides (intentionally or otherwise) an incorrect response to the PIR query, the client verifies that the hash of the message block it has received can be authenticated through the hash tree with the verified hash root.
+
+\subsection{A Remaining Byzantine Server Attack}
+
+There exists a remaining attack not prevented with the hash tree verification system. A corrupt distributor can, through malice or error, create a denial of service attack on the system by responding with incorrect data to a client's query. While the client will detect that the message block is invalid after performing the final step of the PIR protocol in Subsection \ref{subsec:PIR}, and thus can conclude that \emph{some} server was Byzantine, the client cannot determine \emph{which} server or servers returned the incorrect response. The client cannot safely pass the message block contents (assuming they consist of anything other than garbage) to the user, lest tagging attacks become possible.
+
+Furthermore, if attacks on portions of the pseudonymity infrastructure
+affect some users differently than others, an attacker may exploit such
+attacks on components of the system to facilitate an intersection attack
+against a user of the system as a whole. In the Pynchon Gate, if a Byzantine distributor selectively performed denial of service attacks against certain users by returning garbage results to their queries, but correctly responded to other users' queries, the attacker would increase his chances of learning the identity of certain users, based on which users responded to messages that were successfully delivered.
+
+%For instance, in a reply-block
+%system, an attacker could disable certain mixes, and observe which nyms
+%ceased receiving traffic. If the nym holder has a fixed-route reply block,
+%this would enable the attacker to identify the mixes used in the
+%nym holder's reply-block path, and increase his chances of successfully
+%linking the nym with the nym holder's true name.
+
+
+\section{Byzantine Server Detection}
+
+Ideally, there would exist a way to identify a Byzantine server, without modifying the existing threat model or positive security properties of the Pynchon Gate. This is a challenging problem to solve with the existing XOR-based PIR protocol, which makes verifying the results of a PIR query to a distributor impossible. (The client does not know what a ``correct'' response $R(\nu_{s\beta})$ from any given distributor should look like; only that $$R(\nu_{s_1\beta}) \oplus R(\nu_{s_2\beta}) \oplus \cdots \oplus R(\nu_{s_\ell\beta}) = \beta'th~\text{message block}$$ and thus, cannot identify which of the responses were invalid.)
+
+\subsection{Checksums on each message block}
+
+Applying traditional hashes or checksums to each message block is not a viable approach, for it is not the message blocks themselves, but the XOR of all the blocks requested from a given distributor that is returned by that distributor.
+
+If there exists a commitment verification function $g$ such that $g(f(A),f(B)) = g'(A \oplus B)$ (and $g$ can take an arbitrary number of arguments, and $g'$ is predictable based on $g$), it may be possible for the collator (already trusted with the creation and signing of the hash root) to perform the commitment $f$ on each block, and publish that value. When encountering a corrupt message block, the client could obtain all $f$'s corresponding to the 1's in the bit vectors it sent to the distributors, calculate $g(f(A),f(B),\cdots, f(n))$ for each bit vector sent to each distributor in turn, and identify which distributor was Byzantine by observing which calculation of $g$ did not match the corresponding calculation of $g'$.
+
+We know of no such function, nor do we know if such a function would increase the cost of operating the Pynchon Gate system prohibitively, either through excess computation, bandwidth, or storage.
+
+\subsection{Alternative PIR schemes}
+
+There exist PIR schemes that incorporate Byzantine recovery as part of the protocol, such as the scheme presented by Beimel and Stahl~\cite{beimel-robust}. Such protocols could theoretically be used in lieu of the XOR-based scheme in the Pynchon Gate and the other PIR-based pseudonym systems referenced. These protocols have the additional property of \emph{Byzantine recovery}, where a user can still reconstruct a message block from the responses he has received, as long as some threshold of servers are not Byzantine.
+
+These alternate protocols we have considered are $k$-out-of-$\ell$
+ polynomial interpolation based schemes, and therefore have a
+significant drawback in that the security offered by the Pynchon Gate
+must be weakened. In these schemes, the threshold of nodes which must
+collude to break the security of the system decreases compared to the
+simple XOR scheme in the Pynchon Gate. In a $k$-out-of-$\ell$
+ scheme, if \emph{any} $k$ servers collude, the privacy of the user is
+lost. As the difference of $\ell - k$ must be at least 1 in order to
+provide any Byzantine robustness, the best assurance the system can
+offer the user is protection as long as two of the distributors are
+honest (and this is in the weakest configuration for Byzantine
+robustness!) Therefore, the threat of Byzantine servers must be weighed
+against the probability that an adversary may control a large enough
+coalition of servers to satisfy $k$ in a polynomial interpolation based
+PIR scheme, and the protocol parameters chosen accordingly.
+
+Furthermore, these, like most PIR protocols, have only been evaluated for security and privacy-preserving properties. Additional considerations apply when selecting a primitive for use in an anonymity system; considerations which may not have been part of the design criteria for these protocols. Before implementing an alternate PIR-scheme as the basis for a pseudonymity service, one must consider possible attacks on the protocol which are only of concern when it is used for anonymity purposes.
+
+\section{Conclusions and Future Work}
+
+We have evaluated the security of the Pynchon Gate, a PIR-based pseudonymous message system, and identified a weakness in its protocol which prevents users from identifying Byzantine servers. We have described how this limitation in the system can lead to a denial of service attack or potentially be used to compromise the anonymity of the system's users.
+
+We have offered suggestions on potential solutions to the problems in the existing system; however, we have not provided a known solution which maintains the other security properties of the original scheme. Additional work must be done on the development of Private Information Retrieval protocols as anonymity primitives.
+
+\section{Acknowledgements}
+
+We would like to thank Brian Warner and Bryce Wilcox-O'Hearn for their helpful early discussions of the Byzantine Postman Problem; Elena Andreeva, David Chaum, Markulf Kohlweiss and Brian Warner for insightful comments on specialized commitment functions; Ian Goldberg for suggesting the potential of polynomial interpolation-based PIR solutions; Elena Andreeva, Ian Goldberg and David Molnar for assistance in searching the literature for pertinent work; and David Chaum, Bram Cohen and Meredith L. Patterson for inspirational discussion of the future work directions.
+
+We would like to thank Nikita Borisov and Bram Cohen for their comments on an earlier draft of this technical report which significantly improved its presentation, and Meredith L. Patterson for proofreading and bibliography assistance with the final version.
+
+Len Sassaman's work was supported in part by the EU within the PRIME Project under contract IST-2002-507591.
+
+\bibliographystyle{plain}
+\bibliography{byzantine-faults}
+\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/