Secure Peer-to-Peer Overlay Networks
Description:
Peer-to-peer systems have recently become extremely popular for a
variety of reasons. For example, the fact that peer-to-peer systems do not need
a central server means that individuals can cooperate without fees or an
investment in additional high-performance hardware. Also, peer-to-peer systems
allow to make use of the tremendous amount of resources (such as computation
and storage) that otherwise sit idle on individual computers when they are not
in use. Furthermore, the decentralized and distributed nature of peer-to-peer
systems makes them robust against faults.
Many peer-to-peer systems (e.g., CAN, Chord, Pastry, Tapestry, I3, etc.) have recently been suggested. Unfortunately, the
architecture of many of these systems assumes that the nodes involved can be trusted. While this may be possible to achieve with
the help of a central certification authority, in many situations it is not desirable to constrain the membership of a
peer-to-peer system. Consequently, it must be able to withstand a variety of security attacks, including malicious behavior by a
relatively large fraction of its members.
Surprisingly, essentially all of the existing systems do not qualify even for the lowest level of security, that we call
unlucky-input security. There is no need to do anything malicious to execute a major denial of service. Even if all
processors follow the protocol to the letter, it is possible for the system to run into a situation with extremely poor
connectivity (and therefore performance) or a memory overflow at some sites. Furthermore, if users leave the network at
inopportune times, they may permanently remove data or disconnect some sites. Although these bad luck events may rarely happen,
an adversary can significantly reduce the time required for such events without doing anything illegal such as altering the
protocol or sniffing at communication between other peers. These anomalies are just an exploitation of "minor theoretical
glitches" in the consistent hashing approach, and they can serve as a platform for major DOS attacks.
We consequently pursue a different approach, with the following new ideas:
- Instead of using consistent hashing with pseudo-random hash functions, we decouple the data management from
the overlay network by using separate pointer structures for them, and employing true randomness.
- In order to organize data and peers, we will use a novel dynamic overlay
network that allows to organize objects by their real names (and therefore supports range queries, closest match, etc)
while giving deterministic guarantees on the maximum degree, diameter, and expansion. In contrast, existing networks only
support exact search and provide only probabilistic guarantees, and thus are exposed to attacks.
- We will introduce novel crypto/security mechanisms, that guarantee small bias of the random choices made
in the algorithms, making it provably robust against Byzantine malicious behavior.
Faculty members:
PhD students:
Publications
- B. Awerbuch and C. Scheideler.
Group Spreading: A protocol for provably secure distributed name service.
In Proc. 31st Int. Colloquium on Automata, Languages, and Programming (ICALP), 2004.
- A. Bhargava, K. Kothapalli, C. Riley, C. Scheideler, and M. Thober.
Pagoda: A dynamic overlay network for routing, data management, and multicasting.
In Proc. 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2004.
- B. Awerbuch and C. Scheideler
Robust distributed name service.
In 3rd Internation Workshop on Peer-to-Peer Systems (IPTPS), 2004.
- B. Awerbuch and C. Scheideler
The Hyperring: A low-congestion deterministic data structure for distributed environments
In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.
- B. Awerbuch and C. Scheideler
Peer-to-peer systems for prefix search
In Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC), 2003.
Implementations:
Christian Scheideler
Last modified: Tue May 20 2003