Reading Notes: Myrmic - Secure and Robust DHT Routing

A secure and robust DHT protocol has to consider two aspects. One is environmental interference, and the other is adversarial behavior. The environmental interference includes membership churn, transient routing failures and high CPU load.

The adversarial behavior includes:

1. sybil attack: an attacker generates a large number of bogus DHT nodes to out-number the honest nodes. This attach is, in general, overcome by introducing an off-line trusted entity, such as a certificate authority (CA).

2. Message corruption, drop, and delay. A DHT node forwards message ( data as well as control) for others using its routing table. An attacker can eavesdrop on and modify overlay messages passing through it. Even if the messages are signed and encrypted, he can drop or delay them. Iterative routing can be used to prevent such attacks on routing messages.

3. Routing table poisoning (Eclipse Attack). Since a node's routing table is generated from information from other nodes, it is possible that its routing table could be corrupted(i.e. filled with attacker's IP addresses).

4. Root spoofing. Routing in a DHT is "proximity" routing. A message is routed to a key's root rather than a node specified by the querier. Without detailed knowledge of the replier's neighborhood, the querier cannot verify whether the replier is indeed the root of the key.

This paper proposes a DHT routing protocol designed to be robust against adversarial behavior. It is based on Chord DHT protocol.

Assumption:

1. the existance of an off-line certification authority (CA).

2. adversaries can not corrupt or prevent IP network layer communication between honest DHT nodes.

3. do not consider denial-of-service attacks (against arbitrary nodes) at the network level; these attacks can essentially defeat any protocol in the literature.

High-level Overview:

In the protocol, (1) the sender must be able to verify the root, (2) in case root verification fails (e.g., a malicious node impersonates the root), the message must be able to bypass malicious nodes and eventually reach the root if it is reachable, and (3) the secure routing protocol must be efficient, even under attack.

In addition to the off-line CA, Myrmic introduces a new on-line authority, called the Neighborhood Authority (NA). The NA has a public/private key pair for signing certificate and we assume that its certificate is publically available. Myrmic uses iterative routing.

Details:

1. Root verification using nCerts.

The range of node R is the interval from the predecessor of R ( p(R) ) to R, i.e., range(R) = (p(R), R].

We include serveral nodes in nCert to serve as witness to the freshness of the nCert. When a nCert is revoked, the witness are notified by the NA. Hence, by consulting with the witnesses, one can verify the freshness of a nCert. If any witness can prove that a revoked nCert is indeed revoked, the a malicous node can use a revoked nCert only if all (live) witnesses are its colluders.

nCert={nList, issueTime, expireTime}

A nCert is signed by the NA using secure digital signature with private key of the NA. The nCert also includes its issue time and its expiration time. The nList in nCert includes tuples I = (nodeId, IP), which allow direct IP connection to R's neighbors.

//verify if R is the root of key K
Q.verify_root(nCert, k)
if(nCert.expireTime <> nCert.issueTime
and is_root(nCert`, k) is false )
return false;
return true;

//verify if R is the root of k according to nCert
Q.is_root(nCert, k)
if ( k in (nodeId(p(R)), nodeId(R) )
return true;
return false;

2. Neighborhood Certificate Update
When a new node joins a Chord network, it first learns its neighborhood information from a bootstrap node.
To generate nCert for node J, NA needs to learn the (nodeId, IP) pairs of the 2L nearest neighbors, which will be in J's nList. Similarly, to update the nearest neighbors, NA nees to find out the (nodeId, IP) pairs of their nearest neighbors.

//node J joins the network, node B is used for bootstrap
J.join(B)
R = B.find_root(J);
NA.update_nCerts(R, J);
init_finger_table(B);
update_others();

//issue a nCert to the joing node and update its neighbors' nCerts
NA.update_nCerts(R, J)
if(accept(J) is true and verify_root(nCert, J) is true)
list = nil;
list = construct_neighbor_list(R, J);
generate_distribute_nCerts(list);

//NA constructs a list of the nearest neighbors of the joining node
NA.construct_neighbor_list(R, J)
list = nil;
for ( X in R.nCert )
for(Y in X.nCert)
for (Z in Y.nCert)
if (in_list(list, Z) is false) and ping(Z) is live
insert_into_list(list, Z);
insert_into_list(list, J);
while(count_live_successors(list, J) < j =" gen_nList(list," x =" gen_nList(list," x =" Sign(nList" z =" Y;" z =" find_root(X," nhos =" 0;" ring =" nil;" current =" G;" p =" find_predecessor_on_ring(ring," s =" find_successor_on_ring(ring," current =" random_select_from(nCert_S);" current =" random_select_from(nCert_P);" href="http://www.blogger.com/www.dtc.umn.edu/publications/reports/2006_20.pdf">Myrmic: Secure and Robust DHT Routing

There are two more papers need to be read in the future.
1. M.Castro, etc. " Secure routing for structured peer-to-peer overlay networks", OSDI, 2002
2. A.Singh, etc. "Defending against eclipse attacks on overlay network", EW11 2004