[p2p-hackers] About DTH rings subversion attacks

[Bryan Turner]

Jesus,

	It may appear that Kademlia [1] is more reliable than Chord [2] on the
surface, but in reality the problem is not as simple as that.  It has been
shown [3] that any non-authenticated protocol may be subverted if at least
1/3 of the participants are rogue entities.  It has also been shown [4] that
for a general P2P network, only a single rogue entitiy is needed to subvert
it by creating 'faces' which appear to be other nodes, but are actually the
same entity.

	Thus, a rogue need only join the network once, then allow other rogue
entities (or faces) to join through it until the rogue entities make up 1/3
of the nodes in the network; at which time they can bring the entire network
down.  Chord attempts to alleviate this by binding the Node ID to the IP
Address, but this is not a reliable strategy as any network admin will tell
you.  Kademlia, likewise, expects this problem to be solved outside the
protocol.

	A more direct answer to your question would be that Kademlia is capable of
surviving more individual rogue entities (each with very limited resources)
than the basic Chord protocol.  However, Chord may be fortified in the same
manner as Kademlia, bringing that difference to naught.

	Additional fortification [5] brings a byzantine-agreement like protocol
into the network during the lookup phase (called "spam-resistant lookup").
This allows you to survive any number of individual or collective rogue
entities up to the byzantine limit. (or close to it, I don't recall a proof
in the paper)

	To break the byzantine barrier you will need an entirely different security
model with an identity authority.  But this moves away from the pure-P2P
model that most DHTs aim for.  To my knowledge, there are no decentralized,
secure identity authorities in the literature. (Please correct me if I'm
wrong!)

--Bryan
bryan.turner at pobox.com

References (available via http://citeseer.ist.psu.edu):
1. "Kademlia: A Peer-to-peer Information System Based on the XOR Metric"
Petar Maymounkov, David Mazieres
2. "Chord: A Scalable Peer-to-peer Lookup Protocol for Internet
Applications" Ion Stoica, et. al.
3. "The Byzantine Generals Problem" Leslie Lamport, et. al.
4. "The Sybil Attack" John Douceur
5. "A Simple Fault Tolerant Distributed Hash Table" Moni Naor, Udi Wieder

-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org]On
Behalf Of Jesus Cea Avion
Sent: Wednesday, March 31, 2004 8:04 AM
To: Peer-to-peer development.
Subject: [p2p-hackers] About DTH rings subversion attacks


> afaik, there's not much theoretical difference in performance or
> reliability between Chord and Kadmelia.

I'm concerned about malicious nodes. That is, nodes subverting the
correct ring behaviour, like searches and joins.

Reading about Chord and Kademlia, it seems that kademlia could be more
reliable because it uses several peers for each DTH bucket. If each
kademlia node use several peers for ring operation, and the bootstrap
nodes are reliable, it should keep working with malicious nodes.

Any idea or experience?.

--
Jesus Cea Avion