Review - The Sybil Attack

It is not practically impossible to ensure that a remote entity is
identified uniquely in a distributed system without a central authority. In
order to implement integrity and confidentiality constructs in peer-to-peer
systems, the ability to determine whether two remote entities are different
is a requirement. Without a central authority, it cannot be determined that
the chain of trust is rooted securely.

Douceur defines a simple model to attempt to prove that authoritative
control of a distributed system is the only method of avoiding a Sybil
attack. His model is restricted to sets of correct and faulty entities
communicating over a broadcast media. Message delivery is guaranteed, but
consistent order may not be observed across all entities. A perfect system
will always accept messages from correct entities and reject those from
faulty entities.

Two identity validation schemes are presented in the paper. First, under
direct identity validation, a faulty entity can counterfeit many identities
and, less obviously, an entity must validate all entities simultaneously to
guarantee correctness. Second, under indirect identity validation, a large
number of faulty entities can counterfeit an even larger set of identities
and, less obviously, all validations in the system must occur concurrently
to guarantee correctness.

Although much of this observation is obvious, it is important to have a
formal reference in the academic community.
Received on Thu Nov 17 2005 - 03:02:30 EST