The Sybil Attack

Douceur, J.R. “The Sybil attack” in First International Workshop Peer-to-Peer Systems, IPTPS, 2002 Cambridge, MA, USA, March 7-8, 2002, pp. 251-260.

The goal:

• To show that Sybil attacks are always possible without the presence of a logically centralized authority.
• The impracticality of establishing distinct identities in a large-scale distributed system.
  

Peer-to-Peer systems commonly rely on the existence of multiple independent remote entities to mitigate the threat of hostile peers. There are two methods to do so:

• Replicating computational or storage tasks among several remote sites to protect against integrity violation
• Fragmenting tasks among several remote sites to protect against privacy violation

if the local entity has no direct physical knowledge of remote entities, it perceives them only as informational abstractions that we call identities.

The forging of multiple identities is called Sybil Attack

In the absence of a trusted identification authority (or unrealistic assumptions about the resources available to an attacker), a Sybil attack can severely compromise the initial generation of identities, thereby undermining the chain of vouchers.

faulty entities (deceptive) : The entities capable of performing any arbitrary behavior except as limited by explicit resource constraints

correct entities (honest): entities abiding the rules of any protocol we define

message: an uninterpreted finite-length bit string whose meaning is determined either by an explicit protocol or by an implicit agreement among a set of entities

Each entity e attempts to present an identity i to other entities in the system. l accepts i if e is able to present identity i to l successfully.

A secure hash of a public key is a straightforward and unforgeable identity. It can also generate a symmetric key for a communication session.


Three sources of information about another entity are:

• a trusted agency
• itself
• other (untrusted) entities. (why is it considered untrusted, you can establish trust to some degree but does it still keep it untrusted?)

Direct validation:

• Even when severely resource constrained, a faulty entity can counterfeit a constant number of multiple identities.
• Each correct entity must simultaneously validate all the identities it is presented; otherwise, a faulty entity can counterfeit an unbounded number of identities.