Sybil attack
{{short description|Network service attack performed by multiple fake identities}}
{{Use dmy dates|date=May 2021}}
A Sybil attack is a type of attack on a computer network service in which an attacker subverts the service's reputation system by creating a large number of pseudonymous identities and uses them to gain a disproportionately large influence. It is named after the subject of the book Sybil, a case study of a woman diagnosed with dissociative identity disorder.Lynn Neary (20 October 2011). [https://www.npr.org/2011/10/20/141514464/real-sybil-admits-multiple-personalities-were-fake Real 'Sybil' Admits Multiple Personalities Were Fake]. NPR. Retrieved 8 February 2017. The name was suggested in or before 2002 by Brian Zill at Microsoft Research.{{cite book |doi=10.1007/3-540-45748-8_24 |chapter=The Sybil Attack |title=Peer-to-Peer Systems |volume=2429 |pages=[https://archive.org/details/peertopeersystem0000iptp/page/251 251–60] |series=Lecture Notes in Computer Science |year=2002 |last1=Douceur |first1=John R |isbn=978-3-540-44179-3 |chapter-url=https://archive.org/details/peertopeersystem0000iptp/page/251 }} The term pseudospoofing had previously been coined by L. Detweiler on the Cypherpunks mailing list and used in the literature on peer-to-peer systems for the same class of attacks prior to 2002, but this term did not gain as much influence as "Sybil attack".{{cite book|last=Oram|first=Andrew|title=Peer-to-peer: harnessing the benefits of a disruptive technology|year=2001 |publisher="O'Reilly Media, Inc." |isbn=978-0-596-00110-0 |url=https://archive.org/details/peertopeerharnes00oram|url-access=registration}}
Description
The Sybil attack in computer security is an attack wherein a reputation system is subverted by creating multiple identities.{{cite journal |doi=10.1016/j.procs.2014.05.544 |title=Sybil Nodes as a Mitigation Strategy Against Sybil Attack |journal=Procedia Computer Science |volume=32 |pages=1135–40 |year=2014 |last1=Trifa |first1=Zied |last2=Khemakhem |first2=Maher |doi-access=free }} A reputation system's vulnerability to a Sybil attack depends on how cheaply identities can be generated, the degree to which the reputation system accepts inputs from entities that do not have a chain of trust linking them to a trusted entity, and whether the reputation system treats all entities identically. {{asof|2012}}, evidence showed that large-scale Sybil attacks could be carried out in a very cheap and efficient way in extant realistic systems such as BitTorrent Mainline DHT.{{cite book |doi=10.1109/GLOCOM.2012.6503215 |chapter=Real-world sybil attacks in BitTorrent mainline DHT |title=2012 IEEE Global Communications Conference (GLOBECOM) |pages=826–32 |year=2012 |last1=Wang |first1=Liang |last2=Kangasharju |first2=Jussi |isbn=978-1-4673-0921-9 |s2cid=9958359 }}{{cite book |doi=10.1109/P2P.2013.6688697 |chapter=Measuring large-scale distributed systems: case of BitTorrent Mainline DHT |title=IEEE P2P 2013 Proceedings |pages=1–10 |year=2013 |last1=Wang |first1=Liang |last2=Kangasharju |first2=Jussi |isbn=978-1-4799-0515-7 |s2cid=5659252 }}
An entity on a peer-to-peer network is a piece of software that has access to local resources. An entity advertises itself on the peer-to-peer network by presenting an identity. More than one identity can correspond to a single entity. In other words, the mapping of identities to entities is many to one. Entities in peer-to-peer networks use multiple identities for purposes of redundancy, resource sharing, reliability and integrity. In peer-to-peer networks, the identity is used as an abstraction so that a remote entity can be aware of identities without necessarily knowing the correspondence of identities to local entities. By default, each distinct identity is usually assumed to correspond to a distinct local entity. In reality, many identities may correspond to the same local entity.
An adversary may present multiple identities to a peer-to-peer network in order to appear and function as multiple distinct nodes. The adversary may thus be able to acquire a disproportionate level of control over the network, such as by affecting voting outcomes.
In the context of (human) online communities, such multiple identities are sometimes known as sockpuppets.
The less common term inverse-Sybil attack has been used to describe an attack in which many entities appear as a single identity.{{cite book | last1=Auerbach | first1=Benedikt | last2=Chakraborty | first2=Suvradip | last3=Klein | first3=Karen | last4=Pascual-Perez | first4=Guillermo | last5=Pietrzak | first5=Krzysztof | last6=Walter | first6=Michael | last7=Yeo | first7=Michelle | title=Topics in Cryptology – CT-RSA 2021 | chapter=Inverse-Sybil Attacks in Automated Contact Tracing | publisher=Springer International Publishing | publication-place=Cham | year=2021 | isbn=978-3-030-75538-6 | issn=0302-9743 | doi=10.1007/978-3-030-75539-3_17 | pages=399–421| s2cid=220274872 }}
Example
A notable Sybil attack in conjunction with a traffic confirmation attack was launched against the Tor anonymity network for several months in 2014. [https://blog.torproject.org/blog/tor-security-advisory-relay-early-traffic-confirmation-attack Tor security advisory: "relay early" traffic confirmation attack] Tor Project, 30 July 2014Dan Goodin (31 July 2014). [https://arstechnica.com/security/2014/07/active-attack-on-tor-network-tried-to-decloak-users-for-five-months/ Active attack on Tor network tried to decloak users for five months].
There are other examples of Sybil attacks run against Tor network users. This includes the 2020 Bitcoin address rewrite attacks. The attacker controlled a quarter of all Tor exit relays and employed SSL stripping to downgrade secure connections and divert funds to the wallet of the threat actor known as BTCMITM20.{{cite web |last1=Cimpanu |first1=Catalin |title=A mysterious threat actor is running hundreds of malicious Tor relays |url=https://therecord.media/a-mysterious-threat-actor-is-running-hundreds-of-malicious-tor-relays/ |website=The Record |access-date=7 December 2021 |date=December 3, 2021|quote=... most threat actors operating malicious Tor relays tend to focus on running exit points, which allows them to modify the user's traffic. For example, a threat actor that Nusenu has been tracking as BTCMITM20 ran thousands of malicious Tor exit nodes in order to replace Bitcoin wallet addresses inside web traffic and hijack user payments.}}{{cite web |last1=Cimpanu |first1=Catalin |title=Thousands of Tor exit nodes attacked cryptocurrency users over the past year |url=https://therecord.media/thousands-of-tor-exit-nodes-attacked-cryptocurrency-users-over-the-past-year/ |website=The Record |access-date=7 December 2021 |date=May 9, 2021 |quote=For more than 16 months, a threat actor has been seen adding malicious servers to the Tor network in order to intercept traffic and perform SSL stripping attacks on users accessing cryptocurrency-related sites.}}{{cite web |author1=isabela |title=Tor security advisory: exit relays running sslstrip in May and June 2020 |url=https://blog.torproject.org/bad-exit-relays-may-june-2020/ |website=Tor Blog |access-date=7 December 2021 |date=August 14, 2020}}
Another notable example is the 2017–2021 attack run by threat actor KAX17. This entity controlled over 900 malicious servers, primarily middle points, in an attempt to deanonymize Tor users.{{cite web |last1=Cimpanu |first1=Catalin |title=A mysterious threat actor is running hundreds of malicious Tor relays |url=https://therecord.media/a-mysterious-threat-actor-is-running-hundreds-of-malicious-tor-relays/ |website=The Record |access-date=7 December 2021 |date=December 3, 2021 |quote=Grouping these servers under the KAX17 umbrella, Nusenu says this threat actor has constantly added servers ... in industrial quantities, operating servers in the realm of hundreds at any given point.}}{{cite web |last1=Paganini |first1=Pierluigi |title=KAX17 threat actor is attempting to deanonymize Tor users running thousands of rogue relays |url=https://cybersecurityworldconference.com/2021/12/03/kax17-threat-actor-is-attempting-to-deanonymize-tor-users-running-thousands-of-rogue-relays/ |website=Cyber Security |access-date=7 December 2021 |date=December 3, 2021 |quote=Most of the Tor relay servers set up by the KAX17 actor were located in data centers all over the world and are configured as entry and middle points primarily.}}
Prevention
Known approaches to Sybil attack prevention include identity validation, social trust graph algorithms, economic costs, personhood validation, and application-specific defenses.
=Identity validation=
Validation techniques can be used to prevent Sybil attacks and dismiss masquerading hostile entities. A local entity may accept a remote identity based on a central authority which ensures a one-to-one correspondence between an identity and an entity and may even provide a reverse lookup. An identity may be validated either directly or indirectly. In direct validation the local entity queries the central authority to validate the remote identities. In indirect validation the local entity relies on already-accepted identities which in turn vouch for the validity of the remote identity in question.
Practical network applications and services often use a variety of identity proxies to achieve limited Sybil attack resistance, such as telephone number verification, credit card verification, or even based on the IP address of a client. These methods have the limitations that it is usually possible to obtain multiple such identity proxies at some cost – or even to obtain many at low cost through techniques such as SMS spoofing or IP address spoofing. Use of such identity proxies can also exclude those without ready access to the required identity proxy: e.g., those without their own mobile phone or credit card, or users located behind carrier-grade network address translation who share their IP addresses with many others.
Identity-based validation techniques generally provide accountability at the expense of anonymity, which can be an undesirable tradeoff especially in online forums that wish to permit censorship-free information exchange and open discussion of sensitive topics. A validation authority can attempt to preserve users' anonymity by refusing to perform reverse lookups, but this approach makes the validation authority a prime target for attack. Protocols using threshold cryptography can potentially distribute the role of such a validation authority among multiple servers, protecting users' anonymity even if one or a limited number of validation servers is compromised.{{cite conference|author=John Maheswaran |author2=Daniel Jackowitz |author3=Ennan Zhai |author4=David Isaac Wolinsky |author5=Bryan Ford |title=Building Privacy-Preserving Cryptographic Credentials from Federated Online Identities|conference=6th ACM Conference on Data and Application Security and Privacy (CODASPY)|conference-url=https://sites.google.com/site/codaspy20162/|url=https://dedis.cs.yale.edu/dissent/papers/cryptobook.pdf|date=9 March 2016}}
=Social trust graphs=
Sybil prevention techniques based on the connectivity characteristics of social graphs can also limit the extent of damage that can be caused by a given Sybil attacker while preserving anonymity. Examples of such prevention techniques include SybilGuard,{{cite conference |doi=10.1145/1159913.1159945 |title=SybilGuard: defending against sybil attacks via social networks |conference=2006 conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM '06 |conference-url=http://conferences.sigcomm.org/sigcomm/2006/|pages=267–78 |year=2006 |last1=Yu |first1=Haifeng |last2=Kaminsky |first2=Michael |last3=Gibbons |first3=Phillip B |last4=Flaxman |first4=Abraham |isbn=978-1-59593-308-9}} SybilLimit,{{cite conference|title=SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks|url=https://ieeexplore.ieee.org/document/4531141|conference=IEEE Symposium on Security and Privacy|conference-url=https://www.ieee-security.org/TC/SP2008/oakland08.html|date=19 May 2008|doi=10.1109/SP.2008.13}} the Advogato Trust Metric,{{cite web|last=O'Whielacronx|first=Zooko|title=Levien's attack-resistant trust metric|url=http://permalink.gmane.org/gmane.network.peer-to-peer.p2p-hackers/2092|work=
|last1=Cao |first1=Qiang |last2=Sirivianos |first2=Michael |last3=Yang |first3=Xiaowei |last4=Pregueiro |first4=Tiago}} and the sparsity based metric to identify Sybil clusters in a distributed P2P based reputation system.{{cite book |doi=10.1109/icc.2011.5963402 |chapter=Sybil Detection via Distributed Sparse Cut Monitoring |title=2011 IEEE International Conference on Communications (ICC) |pages=1–6 |year=2011 |last1=Kurve |first1=Aditya |last2=Kesidis |first2=George |isbn=978-1-61284-232-5 |s2cid=5082605 }}
These techniques cannot prevent Sybil attacks entirely, and may be vulnerable to widespread small-scale Sybil attacks. In addition, it is not clear whether real-world online social networks will satisfy the trust or connectivity assumptions that these algorithms assume.{{cite journal|title=An analysis of social network-based Sybil defenses|author1=Bimal Viswanath |author2=Ansley Post |author3=Krishna Phani Gummadi |author4=Alan E Mislove |journal=ACM SIGCOMM Computer Communication Review|date=August 2010|volume=40|issue=4|pages=363–374|url=https://dl.acm.org/doi/abs/10.1145/1851275.1851226|doi=10.1145/1851275.1851226}}
=Economic costs=
Alternatively, imposing economic costs as artificial barriers to entry may be used to make Sybil attacks more expensive. Proof of work, for example, requires a user to prove that they expended a certain amount of computational effort to solve a cryptographic puzzle. In Bitcoin and related permissionless cryptocurrencies, miners compete to append blocks to a blockchain and earn rewards roughly in proportion to the amount of computational effort they invest in a given time period. Investments in other resources such as storage or stake in existing cryptocurrency may similarly be used to impose economic costs.
=Personhood validation=
As an alternative to identity verification that attempts to maintain a strict "one-per-person" allocation rule, a validation authority can use some mechanism other than knowledge of a user's real identity – such as verification of an unidentified person's physical presence at a particular place and time as in a pseudonym party{{cite conference |doi=10.1145/1435497.1435503 |title=An Offline Foundation for Online Accountable Pseudonyms |conference=1st Workshop on Social Network Systems - SocialNets '08 |pages=31–6 |date=1 April 2008 |last1=Ford |first1=Bryan |last2=Strauss |first2=Jacob |isbn=978-1-60558-124-8 |conference-url=https://dl.acm.org/doi/proceedings/10.1145/1435497|url=https://dl.acm.org/doi/10.1145/1435497.1435503}} – to enforce a one-to-one correspondence between online identities and real-world users. Such proof of personhood approaches have been proposed as a basis for permissionless blockchains and cryptocurrencies in which each human participant would wield exactly one vote in consensus.{{cite conference|author=Maria Borge |author2=Eleftherios Kokoris-Kogias |author3=Philipp Jovanovic |author4=Linus Gasser |author5=Nicolas Gailly |author6=Bryan Ford |title=Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies|conference=IEEE Security & Privacy on the Blockchain (IEEE S&B)|conference-url=https://prosecco.gforge.inria.fr/ieee-blockchain2016/|date=29 April 2017|doi=10.1109/EuroSPW.2017.46|url=https://ieeexplore.ieee.org/document/7966966}}{{cite book|chapter=Technologizing Democracy or Democratizing Technology? A Layered-Architecture Perspective on Potentials and Challenges|last=Ford|first=Bryan|chapter-url=https://bford.info/pub/soc/dt2-chapter-abs/|title=Digital Technology and Democratic Theory|editor1=Lucy Bernholz|editor2=Hélène Landemore|editor3=Rob Reich|publisher=University of Chicago Press|isbn=978-0-226-74857-3|date=December 2020|url=https://press.uchicago.edu/ucp/books/book/chicago/D/bo68657177.html}} A variety of approaches to proof of personhood have been proposed, some with deployed implementations, although many usability and security issues remain.{{cite arXiv|author=Divya Siddarth |author2=Sergey Ivliev |author3=Santiago Siri |author4=Paula Berman |title=Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols {{! }} class cs.CR|eprint=2008.05300|date=13 October 2020|class=cs.CR }}
=Application-specific defenses=
A number of distributed protocols have been designed with Sybil attack protection in mind. SumUp{{cite conference|title=Sybil-Resilient Online Content Voting|author1=Nguyen Tran |author2=Bonan Min |author3=Jinyang Li |author4=Lakshminarayanan Subramanian |conference=NSDI '09: 6th USENIX Symposium on Networked Systems Design and Implementation|conference-url=https://www.usenix.org/legacy/events/nsdi09/|url=https://www.usenix.org/legacy/events/nsdi09/tech/full_papers/tran/tran.pdf|date=22 April 2009}} and DSybil{{cite conference|title=DSybil: Optimal Sybil-Resistance for Recommendation Systems|author=Haifeng Yu |author2=Chenwei Shi |author3=Michael Kaminsky |author4=Phillip B. Gibbons |author5=Feng Xiao |conference=30th IEEE Symposium on Security and Privacy|conference-url=http://oakland09.cs.virginia.edu|url=https://ieeexplore.ieee.org/document/5207651|date=19 May 2009|doi=10.1109/SP.2009.26}} are Sybil-resistant algorithms for online content recommendation and voting. Whānau is a Sybil-resistant distributed hash table algorithm.{{cite conference|title=Whānau: A Sybil-proof Distributed Hash Table|author1=Chris Lesniewski-Laas |author2=M. Frans Kaashoek |conference=7th USENIX Symposium on Network Systems Design and Implementation (NSDI)|conference-url=https://www.usenix.org/legacy/event/nsdi10/|url=https://www.usenix.org/legacy/events/nsdi10/tech/full_papers/lesniewski-laas.pdf|date=28 April 2010}} I2P's implementation of Kademlia also has provisions to mitigate Sybil attacks.{{cite web |url=https://geti2p.net/en/docs/how/network-database#threat |title=The Network Database - I2P}}
See also
References
{{Reflist|30em}}
External links
- {{cite book |doi=10.1109/INFCOM.2010.5462218 |chapter=Sybil Attacks Against Mobile Users: Friends and Foes to the Rescue |title=2010 Proceedings IEEE INFOCOM |pages=1–5 |year=2010 |last1=Querci |first1=Daniele |last2=Hailes |first2=Stephen |isbn=978-1-4244-5836-3 |citeseerx=10.1.1.360.8730 |s2cid=2451937 }}
- {{cite journal |doi=10.1007/s00446-006-0012-y |title=On the establishment of distinct identities in overlay networks |journal=Distributed Computing |volume=19 |issue=4 |pages=267–87 |year=2006 |last1=Bazzi |first1=Rida A |last2=Konjevod |first2=Goran |s2cid=2723075 }}
- {{cite book |doi=10.1145/1435497.1435501 |chapter=A Sybil-proof one-hop DHT |title=Proceedings of the 1st workshop on Social network systems - SocialNets '08 |pages=19–24 |year=2008 |last1=Lesniewski-Laas |first1=Chris |isbn=978-1-60558-124-8 |s2cid=5793502 }}
- {{cite book |doi=10.1145/984622.984660 |chapter=The sybil attack in sensor networks |title=Proceedings of the third international symposium on Information processing in sensor networks - IPSN'04 |pages=259–68 |year=2004 |last1=Newsome |first1=James |last2=Shi |first2=Elaine|author2-link= Elaine Shi |last3=Song |first3=Dawn |last4=Perrig |first4=Adrian |isbn=978-1-58113-846-7 |s2cid=12451248 }}
- [https://web.archive.org/web/20170129094347/https://gnunet.org/sites/default/files/Tech%20Report%20-%20A%20Survey%20of%20Solutions%20to%20the%20Sybil%20Attack.pdf A Survey of Solutions to the Sybil Attack]
- [http://dimacs.rutgers.edu/Workshops/InformationSecurity/slides/gamesandreputation.pdf On Network formation: Sybil attacks and Reputation systems]
- {{cite book |doi=10.1007/11429760_22 |chapter=Trust Transfer: Encouraging Self-recommendations Without Sybil Attack |title=Trust Management |volume=3477 |pages=321–37 |series=Lecture Notes in Computer Science |year=2005 |last1=Seigneur |first1=Jean-Marc |last2=Gray |first2=Alan |last3=Jensen |first3=Christian Damsgaard |isbn=978-3-540-26042-4 |citeseerx=10.1.1.391.5003 }}
- [https://web.archive.org/web/20170809060557/http://globule.org/publi/SDST_acmcs2009.pdf A Survey of DHT Security Techniques] by Guido Urdaneta, Guillaume Pierre and Maarten van Steen. ACM Computing surveys, 2009.
- [http://www.unibg.it/lazzari/doc/marco_lazzari_reputation_algorithms_professional_social_networks_naymz.htm An experiment on the weakness of reputation algorithms used in professional social networks: the case of Naymz] by Marco Lazzari. Proceedings of the IADIS International Conference e-Society 2010.
Category:Internet manipulation and propaganda