Secure routing (p2p) Review

Secure routing for structured peer-to-peer overlay networks Review
Review By: Troy Ronda

Structured overlays can provide a substrate required for many applications
-- they allow the look-up of objects with a probabilistic bound on the
number of hops. These overlay networks allow mutually distrusting hosts to
join and also have the possibility of malicious hosts in the system.
Robustness to attack is a key design issue for overlay networks. One
aspect is secure routing. This paper presents solutions the problems of
secure assignment of identifiers, secure routing table maintenance, and
secure message forwarding. With these techniques, secure routing is
possible with up to 25% of the nodes being malicious. P2P algorithms
depend on the underlying assumption of a random and uniform distribution
of identifiers. The solution presented in this paper is similar to the
Sybil papers approach. Centralized authorities will issue certificates for
identifiers. They will charge a fee so that large attacks become expensive
for the attacker. Two methods of compromising the routing table are
presented: controlling nodes and sending bad updates during routing table
maintenance. Attackers, for example, might forge network proximity by
intercepting probes from systems like Pastry. Systems that do not
constrain routing table content (eg. Pastry) are vulnerable to attackers
supplying bad updates. The solution presented is a backup routing table
consisting of constrained entries (more like Chord). Secure routing,
first, creates a heuristic to determine if a set of replica roots is
likely to cause a routing failure (eg. due to malicious nodes). The
heuristic is based on detecting if too many nodes exist near the root
replica as compared to the senders own space. If so, there is a good
chance that the destination is compromised. In case of compromise, the
algorithm initiates redundant routing, sending multiple copies of the
message on diverse routes. The performance reduction can be mitigated with
self-certifying data. We can resort to secure routing only when data
checks fail, inserting objects, node joins, etc.

This paper makes a strong case that relying on nodes to follow the
protocol is a bad idea for structured overlays. The performance hit is
unacceptable when the possibility of malicious nodes exist. All three
suggestions for adding a security layer are intuitive. The authors also
make a point of making the solutions general, applying them to many types
of overlay networks (such as, CAN, Chord, Tapestry and Pastry). It is also
good that the algorithms presented in this paper, first try the fast
default version routing of the protocol. These algorithms form a fall-back
in case of malicious behavior. I found the presented model acceptable,
therefore I found the results to be strong. The background material
(although redundant ([ironically]) for those in the Internet systems class
would be helpful for anyone new to the area.

I found this paper to be a bit long for the concepts presented. It seemed
that some of the message got lost due to the length and font size. As the
authors stated, redundant routing will decrease the overlay performance,
at least in-commonly. Although I think self-certifying data can also be
slow if the requester has to ask for the object multiple times, due to
malicious behavior. I dislike the solution for secure identifier
assignments. It breaks the spirit of the Internet by charging fees for an
identity certificate. Having said this, I do not have a better solution
in-mind. Another idea that comes to mind is trying to blacklist
misbehaving identities. At minimum, we should repair the routing tables if
we detect maliciousness instead of merely falling back on the slower
backup tables. The performance hits caused by these nodes will continue
until they leave the network. Perhaps the attackers objective is to merely
slow the overlay. In this case, solutions like the one presented in this
paper fail to address the problem. It would be good to read some papers
discussing the plus and minuses of a blacklist attempt in distributed
systems. Is it even possible? It would probably, again, require a
certificate authority. In the end, we must recognize that overlay networks
must, unfortunately, be resilient to attack just like any other system.
Received on Thu Nov 17 2005 - 09:00:55 EST