Abstract
Large-scale peer-to-peer systems face security threats from faulty or hostile remote computing elements. To resist these threats, many such systems employ redundancy. However, if a single faulty entity can present multiple identities, it can control a substantial fraction of the system, thereby undermining this redundancy. One approach to preventing these “Sybil attacks” is to have a trusted agency certify identities. This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.
Use of the plural pronoun is customary even in solely authored research papers; however, given the subject of the present paper, its use herein is particularly ironic.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
T. Aura, P. Nikander, J. Leiwo, “DoS-Resistant Authentication with Client Puzzles”, Cambridge Security Protocols Workshop, Springer, 2000.
M. Bellare and P. Rogaway, “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols”, 1st Conference on Computer and Communications Security, ACM, 1993, pp. 62–73.
W. J. Bolosky, J. R. Douceur, D. Ely, M. Theimer, “Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs”, SIGMETRICS 2000, 2000, pp. 34–43.
M. Castro, B. Liskov, “Practical Byzantine Fault Tolerance”, 3rd OSDI, 1999.
D. Chaum, “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms”, CACM 4 (2), 1982.
B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, “Private Information Retrieval”, 36th FOCS, 1995.
I. Clarke, O. Sandberg, B. Wiley, T. Hong, “Freenet: A Distributed Anonymous Information Storage and Retrieval System”, Design Issues in Anonymity and Unobervability, ICSI, 2000.
F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, “Wide-Area Cooperative Storage with CFS”, 18th SOSP, 2001, pp. 202–215.
D. Dean, A. Stubblefield, “Using Client Puzzles to Protect TLS”, 10th USENIX Security Symp., 2001.
R. Dingledine, M. Freedman, D. Molnar “The Free Haven Project: Distributed Anonymous Storage Service”, Design Issues in Anonymity and Unobservability, 2000.
R. Dingledine, M. J. Freedman, D. Molnar “Accountability”, Peer-to-Peer: Harnessing the Power of Disruptive Technologies, O’Reilly, 2001.
J. S. Donath, “Identity and Deception in the Virtual Community”, Communities in Cyberspace, Routledge, 1998.
C. Ellison, “Establishing Identity Without Certification Authorities”, 6th USENIX Security Symposium, 1996, pp. 67–76.
U. Feige, A. Fiat, A. Shamir, “Zero-Knowledge Proofs of Identity”, Journal of Cryptology 1 (2), 1988, pp. 77–94.
A. Fiat, A. Shamir, “How to Prove Yourself: Practical Solutions of Identification and Signature Problems”, Crypto’ 86, 1987, pp. 186–194.
Y. Gertner, S. Goldwasser, T. Malkin, “A Random Server Model for Private Information Retrieval”, RANDOM’ 98, 1998.
A. Goldberg, P. Yianilos, “Towards an Archival Intermemory”, International Forum on Research and Technology Advances in Digital Libraries, IEEE, 1998, pp. 147–156.
J. H. Hartman, I. Murdock, T. Spalink, “The Swarm Scalable Storage System”, 19th ICDCS, 1999, pp. 74–81.
A. Juels, J. Brainard, “Client Puzzles: A Cryptographic Defense against Connection Depletion Attacks”, NDSS’ 99, ISOC, 1999, pp. 151–165.
L. Lamport, R. Shostak, M. Pease, “The Byzantine Generals Problem”, TPLS 4(3), 1982.
K. R. Lefebvre, “The Added Value of EMBASSY in the Digital World”, Wave Systems Corp. white paper, http://www.wave.com, 2000.
D. Mazières, M. Kaminsky, M. F. Kaashoek, E. Witchel, “Separating Key Management from File System Security”, 17th SOSP, 1999, pp. 124–139.
A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
R. C. Merkle, “Secure Communications over Insecure Channels”, CACM 21, 1978, pp. 294–299.
T. Narten, R. Draves, “Privacy Extensions for Stateless Address Autoconfiguration in IPv6”, RFC 3041, 2001.
K. Ohta, T. Okamoto, “A Modification to the Fiat-Shamir Scheme”, Crypto ŕ88, 1990, pp. 232–243.
M. K. Reiter, A. D. Rubin, “Crowds: Anonymous Web Transactions”, Transactions on Information System Security 1 (1), ACM, 1998.
A. Rowstron, P. Druschel, “Storage Management and Caching in PAST, a Large-Scale, Persistent Peer-to-Peer Storage Utility”, 18th SOSP, 2001, pp. 188–201.
F. R. Schreiber, Sybil, Warner Books, 1973.
A. Shamir, “An Efficient Identification Scheme Based on Permuted Kernels”, Crypto ⩭9, 1990, pp. 606–609.
S. Turkle, Life on the Screen: Identity in the Age of the Internet, Simon & Schuster, 1995.
M. Waldman, A. D. Rubin, L. F. Cranor, “Publius: A Robust, Tamper-Evident Censorship-Resistant Web Publishing System”, 9th USENIX Security Symposium, 2000, pp. 59–72.
J. J. Wylie, M. W. Bigrigg, J. D. Strunk, G. R. Ganger, H. Kilite, P. K. Khosla, “Survivable Information Storage Systems”, IEEE Computer 33 (8), IEEE, 2000, pp. 61–68.
P. Zimmerman, PGP User’s Guide, MIT, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Douceur, J.R. (2002). The Sybil Attack. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds) Peer-to-Peer Systems. IPTPS 2002. Lecture Notes in Computer Science, vol 2429. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45748-8_24
Download citation
DOI: https://doi.org/10.1007/3-540-45748-8_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44179-3
Online ISBN: 978-3-540-45748-0
eBook Packages: Springer Book Archive