Sybil attack

Last updated

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. [1] The name was suggested in or before 2002 by Brian Zill at Microsoft Research. [2] 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". [3]

Contents

Description

The Sybil attack in computer security is an attack wherein a reputation system is subverted by creating multiple identities. [4] 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. As of 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. [5] [6]

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. [7]

Example

A notable Sybil attack in conjunction with a traffic confirmation attack was launched against the Tor anonymity network for several months in 2014. [8] [9]

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. [10] [11] [12]

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. [13] [14]

Prevention

Known approaches to Sybil attack prevention include identity validation, social trust graph algorithms, or 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. [15]

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, [16] SybilLimit, [17] the Advogato Trust Metric, [18] SybilRank, [19] and the sparsity based metric to identify Sybil clusters in a distributed P2P based reputation system. [20]

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. [21]

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 [22] – 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. [23] [24] A variety of approaches to proof of personhood have been proposed, some with deployed implementations, although many usability and security issues remain. [25]

Application-specific defenses

A number of distributed protocols have been designed with Sybil attack protection in mind. SumUp [26] and DSybil [27] are Sybil-resistant algorithms for online content recommendation and voting. Whānau is a Sybil-resistant distributed hash table algorithm. [28] I2P's implementation of Kademlia also has provisions to mitigate Sybil attacks. [29]

See also

Related Research Articles

<span class="mw-page-title-main">Peer-to-peer</span> Type of decentralized and distributed network architecture

Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network, forming a peer-to-peer network of nodes.

An intrusion detection system is a device or software application that monitors a network or systems for malicious activity or policy violations. Any intrusion activity or violation is typically reported either to an administrator or collected centrally using a security information and event management (SIEM) system. A SIEM system combines outputs from multiple sources and uses alarm filtering techniques to distinguish malicious activity from false alarms.

<span class="mw-page-title-main">Distributed hash table</span> Decentralized distributed system with lookup service

A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. Keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

<span class="mw-page-title-main">Honeypot (computing)</span> Computer security mechanism

In computer terminology, a honeypot is a computer security mechanism set to detect, deflect, or, in some manner, counteract attempts at unauthorized use of information systems. Generally, a honeypot consists of data that appears to be a legitimate part of the site which contains information or resources of value to attackers. It is actually isolated, monitored, and capable of blocking or analyzing the attackers. This is similar to police sting operations, colloquially known as "baiting" a suspect.

<span class="mw-page-title-main">Botnet</span> Collection of compromised internet-connected devices controlled by a third party

A botnet is a group of Internet-connected devices, each of which runs one or more bots. Botnets can be used to perform Distributed Denial-of-Service (DDoS) attacks, steal data, send spam, and allow the attacker to access the device and its connection. The owner can control the botnet using command and control (C&C) software. The word "botnet" is a portmanteau of the words "robot" and "network". The term is usually used with a negative or malicious connotation.

Internet security is a branch of computer security. It encompasses the Internet, browser security, web site security, and network security as it applies to other applications or operating systems as a whole. Its objective is to establish rules and measures to use against attacks over the Internet. The Internet is an inherently insecure channel for information exchange, with high risk of intrusion or fraud, such as phishing, online viruses, trojans, ransomware and worms.

A dark net or darknet is an overlay network within the Internet that can only be accessed with specific software, configurations, or authorization, and often uses a unique customized communication protocol. Two typical darknet types are social networks, and anonymity proxy networks such as Tor via an anonymized series of connections.

Proof of work (PoW) is a form of cryptographic proof in which one party proves to others that a certain amount of a specific computational effort has been expended. Verifiers can subsequently confirm this expenditure with minimal effort on their part. The concept was invented by Moni Naor and Cynthia Dwork in 1993 as a way to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from a service requester, usually meaning processing time by a computer. The term "proof of work" was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels.

Reputation systems are programs or algorithms that allow users to rate each other in online communities in order to build trust through reputation. Some common uses of these systems can be found on E-commerce websites such as eBay, Amazon.com, and Etsy as well as online advice communities such as Stack Exchange. These reputation systems represent a significant trend in "decision support for Internet mediated service provisions". With the popularity of online communities for shopping, advice, and exchange of other important information, reputation systems are becoming vitally important to the online experience. The idea of reputation systems is that even if the consumer can't physically try a product or service, or see the person providing information, that they can be confident in the outcome of the exchange through trust built by recommender systems.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

In information security, computational trust is the generation of trusted authorities or user trust through cryptography. In centralised systems, security is typically based on the authenticated identity of external parties. Rigid authentication mechanisms, such as public key infrastructures (PKIs) or Kerberos, have allowed this model to be extended to distributed systems within a few closely collaborating domains or within a single administrative domain. During recent years, computer science has moved from centralised systems to distributed computing. This evolution has several implications for security models, policies and mechanisms needed to protect users’ information and resources in an increasingly interconnected computing infrastructure.

<span class="mw-page-title-main">Tor (network)</span> Free and open-source anonymity network based on onion routing

Tor, short for The Onion Router, is free and open-source software for enabling anonymous communication. It directs Internet traffic via a free, worldwide, volunteer overlay network that consists of more than seven thousand relays.

Cloud computing security or, more simply, cloud security, refers to a broad set of policies, technologies, applications, and controls utilized to protect virtualized IP, data, applications, services, and the associated infrastructure of cloud computing. It is a sub-domain of computer security, network security, and, more broadly, information security.

Mobile security, or mobile device security, is the protection of smartphones, tablets, and laptops from threats associated with wireless computing. It has become increasingly important in mobile computing. The security of personal and business information now stored on smartphones is of particular concern.

Internet censorship circumvention, also referred to as going over the wall or scientific browsing in China, is the use of various methods and tools to bypass internet censorship.

Proof-of-stake (PoS) protocols are a class of consensus mechanisms for blockchains that work by selecting validators in proportion to their quantity of holdings in the associated cryptocurrency. This is done to avoid the computational cost of proof-of-work (POW) schemes. The first functioning use of PoS for cryptocurrency was Peercoin in 2012, although the scheme, on the surface, still resembled a POW.

A decentralised application is an application that can operate autonomously, typically through the use of smart contracts, that run on a decentralized computing, blockchain or other distributed ledger system. Like traditional applications, DApps provide some function or utility to its users. However, unlike traditional applications, DApps operate without human intervention and are not owned by any one entity, rather DApps distribute tokens that represent ownership. These tokens are distributed according to a programmed algorithm to the users of the system, diluting ownership and control of the DApp. Without any one entity controlling the system, the application is therefore decentralised.

A blockchain is a shared database that records transactions between two parties in an immutable ledger. Blockchain documents and confirms pseudonymous ownership of all transactions in a verifiable and sustainable way. After a transaction is validated and cryptographically verified by other participants or nodes in the network, it is made into a "block" on the blockchain. A block contains information about the time the transaction occurred, previous transactions, and details about the transaction. Once recorded as a block, transactions are ordered chronologically and cannot be altered. This technology rose to popularity after the creation of Bitcoin, the first application of blockchain technology, which has since catalyzed other cryptocurrencies and applications.

Proof of personhood (PoP) is a means of resisting malicious attacks on peer to peer networks, particularly, attacks that utilize multiple fake identities, otherwise known as a Sybil attack. Decentralized online platforms are particularly vulnerable to such attacks by their very nature, as notionally democratic and responsive to large voting blocks. In PoP, each unique human participant obtains one equal unit of voting power, and any associated rewards.

Proof of identity (PoID) is a consensus protocol for permission-less blockchains, in which each uniquely identified individual receives one equal unit of voting power and associated rewards. The protocol is based on biometric identification, humanity identification parties and additional verification parties.

References

  1. ↑ Lynn Neary (20 October 2011). Real 'Sybil' Admits Multiple Personalities Were Fake. NPR. Retrieved 8 February 2017.
  2. ↑ Douceur, John R (2002). "The Sybil Attack". Peer-to-Peer Systems. Lecture Notes in Computer Science. Vol. 2429. pp.  251–60. doi:10.1007/3-540-45748-8_24. ISBN   978-3-540-44179-3.
  3. ↑ Oram, Andrew (2001). Peer-to-peer: harnessing the benefits of a disruptive technology . "O'Reilly Media, Inc.". ISBN   978-0-596-00110-0.
  4. ↑ Trifa, Zied; Khemakhem, Maher (2014). "Sybil Nodes as a Mitigation Strategy Against Sybil Attack". Procedia Computer Science. 32: 1135–40. doi: 10.1016/j.procs.2014.05.544 .
  5. ↑ Wang, Liang; Kangasharju, Jussi (2012). "Real-world sybil attacks in BitTorrent mainline DHT". 2012 IEEE Global Communications Conference (GLOBECOM). pp. 826–32. doi:10.1109/GLOCOM.2012.6503215. ISBN   978-1-4673-0921-9. S2CID   9958359.
  6. ↑ Wang, Liang; Kangasharju, Jussi (2013). "Measuring large-scale distributed systems: case of BitTorrent Mainline DHT". IEEE P2P 2013 Proceedings. pp. 1–10. doi:10.1109/P2P.2013.6688697. ISBN   978-1-4799-0515-7. S2CID   5659252.
  7. ↑ Auerbach, Benedikt; Chakraborty, Suvradip; Klein, Karen; Pascual-Perez, Guillermo; Pietrzak, Krzysztof; Walter, Michael; Yeo, Michelle (2021). "Inverse-Sybil Attacks in Automated Contact Tracing". Topics in Cryptology – CT-RSA 2021. Cham: Springer International Publishing. pp. 399–421. doi:10.1007/978-3-030-75539-3_17. ISBN   978-3-030-75538-6. ISSN   0302-9743. S2CID   220274872.
  8. ↑ Tor security advisory: "relay early" traffic confirmation attack Tor Project, 30 July 2014
  9. ↑ Dan Goodin (31 July 2014). Active attack on Tor network tried to decloak users for five months.
  10. ↑ Cimpanu, Catalin (3 December 2021). "A mysterious threat actor is running hundreds of malicious Tor relays". The Record. Retrieved 7 December 2021. ... 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.
  11. ↑ Cimpanu, Catalin (9 May 2021). "Thousands of Tor exit nodes attacked cryptocurrency users over the past year". The Record. Retrieved 7 December 2021. 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.
  12. ↑ isabela (14 August 2020). "Tor security advisory: exit relays running sslstrip in May and June 2020". Tor Blog. Retrieved 7 December 2021.
  13. ↑ Cimpanu, Catalin (3 December 2021). "A mysterious threat actor is running hundreds of malicious Tor relays". The Record. Retrieved 7 December 2021. 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.
  14. ↑ Paganini, Pierluigi (3 December 2021). "KAX17 threat actor is attempting to deanonymize Tor users running thousands of rogue relays". Cyber Security. Retrieved 7 December 2021. 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.
  15. ↑ John Maheswaran; Daniel Jackowitz; Ennan Zhai; David Isaac Wolinsky; Bryan Ford (9 March 2016). Building Privacy-Preserving Cryptographic Credentials from Federated Online Identities (PDF). 6th ACM Conference on Data and Application Security and Privacy (CODASPY).
  16. ↑ Yu, Haifeng; Kaminsky, Michael; Gibbons, Phillip B; Flaxman, Abraham (2006). SybilGuard: defending against sybil attacks via social networks. 2006 conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM '06. pp. 267–78. doi:10.1145/1159913.1159945. ISBN   978-1-59593-308-9.
  17. ↑ SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks. IEEE Symposium on Security and Privacy. 19 May 2008. doi:10.1109/SP.2008.13.
  18. ↑ O'Whielacronx, Zooko. "Levien's attack-resistant trust metric". <p2p-hackers at lists.zooko.com>. gmane.org. Archived from the original on 7 July 2014. Retrieved 10 February 2012.
  19. ↑ Cao, Qiang; Sirivianos, Michael; Yang, Xiaowei; Pregueiro, Tiago (25–27 April 2012). Aiding the Detection of Fake Accounts in Large Scale Social Online Services. USENIX Networked Systems Design and Implementation.
  20. ↑ Kurve, Aditya; Kesidis, George (2011). "Sybil Detection via Distributed Sparse Cut Monitoring". 2011 IEEE International Conference on Communications (ICC). pp. 1–6. doi:10.1109/icc.2011.5963402. ISBN   978-1-61284-232-5. S2CID   5082605.
  21. ↑ Bimal Viswanath; Ansley Post; Krishna Phani Gummadi; Alan E Mislove (August 2010). "An analysis of social network-based Sybil defenses". ACM SIGCOMM Computer Communication Review. 40 (4): 363–374. doi:10.1145/1851275.1851226.
  22. ↑ Ford, Bryan; Strauss, Jacob (1 April 2008). An Offline Foundation for Online Accountable Pseudonyms. 1st Workshop on Social Network Systems - SocialNets '08. pp. 31–6. doi:10.1145/1435497.1435503. ISBN   978-1-60558-124-8.
  23. ↑ Maria Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolas Gailly; Bryan Ford (29 April 2017). Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies. IEEE Security & Privacy on the Blockchain (IEEE S&B). doi:10.1109/EuroSPW.2017.46.
  24. ↑ Ford, Bryan (December 2020). "Technologizing Democracy or Democratizing Technology? A Layered-Architecture Perspective on Potentials and Challenges". In Lucy Bernholz; Hélène Landemore; Rob Reich (eds.). Digital Technology and Democratic Theory. University of Chicago Press. ISBN   978-0-226-74857-3.
  25. ↑ Divya Siddarth; Sergey Ivliev; Santiago Siri; Paula Berman (13 October 2020). "Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols | class cs.CR". arXiv: 2008.05300 [cs.CR].
  26. ↑ Nguyen Tran; Bonan Min; Jinyang Li; Lakshminarayanan Subramanian (22 April 2009). Sybil-Resilient Online Content Voting (PDF). NSDI '09: 6th USENIX Symposium on Networked Systems Design and Implementation.
  27. ↑ Haifeng Yu; Chenwei Shi; Michael Kaminsky; Phillip B. Gibbons; Feng Xiao (19 May 2009). DSybil: Optimal Sybil-Resistance for Recommendation Systems. 30th IEEE Symposium on Security and Privacy. doi:10.1109/SP.2009.26.
  28. ↑ Chris Lesniewski-Laas; M. Frans Kaashoek (28 April 2010). Whānau: A Sybil-proof Distributed Hash Table (PDF). 7th USENIX Symposium on Network Systems Design and Implementation (NSDI).
  29. ↑ "The Network Database - I2P".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.