## 5 Attacks and Countermeasures
### P2P Countermeasures
#### 5.2.1 Countermeasures for P2P Routing Attacks  
As the _Incorrect Lookup Routing_ affects the routing algorithms of DHTs strongly, several countermeasures were proposed. Most of those countermeasures increase the robustness of the routing algorithm by adding redundancy to the network. The recursive routing algorithms are susceptible to routing attacks as the source of the request can not detect malicious nodes due to the recursive behavior of the routing. To overcome this drawback, the _Iterative Routing_ algorithm was proposed by [PERSON] and [PERSON] [22] as one of the first and most promising approaches. When an _Iterative Routing_ is initiated, intermediate nodes have to send routing information about the next hop back to the source node. This way, the source node is able to interact with the intermediate nodes directly. Whenever an intermediate node proposes an incorrect next hop address or does not respond to a request at all, the source node is aware of this malicious behavior due to the missing reply or as the proposed next hop node does not match the expected one. After detecting a malicious node, the source node can reroute the request and bypass this node. On the downside, the lookup delay and the data overhead is increased as the source node has to resend lookup messages whenever a intermediate node does not respond and as intermediate nodes have to reply to the source node which adds one additional message per hop in the overlay. Another prominent approach to increase the routing robustness of DHTs was introduced by [PERSON] _et al_. [23]. They proposed a redundant recursive routing algorithm. When multiple redundant requests are sent, the probability that all of them are dropped or redirected by malicious nodes is decreased. Due to this, the _Redundant Routing_ algorithm improves the delivery rate of lookup requests. On the downside, redundant routing increases lookup overhead strongly. [PERSON] and [PERSON] analyzed the importance of independent paths during redundant routing [24]. As long as the paths are not disjoint, a single malicious node may affect all sent requests. [PERSON] _et al_. [25] modified the _Redundant Routing_ algorithm and combined it with a reputation system. The resulting _Resistant Routing_ algorithm forwards lookup requests not only to the next hop, but also to \(n\) neighbors of the next hop. Those \(n+1\) nodes forward the request to the next set of \(n+1\) nodes around (and including) the next hop node. This way, the destination node and\(n\) of its neighbors receive the request after \(log(N)\) hops. As [PERSON] _et al._ propose to store the replicas around the root of an object, the source node receives \(n+1\) keys at the end of the lookup procedure as each neighbor of the destination stores a valid replica. In order to reduce the resulting routing overhead, an additional reputation system is introduced. During the routing, each node has to rate the behavior of all of its neighbors. When a node is rated malicious (_i.e._, when it does not forward lookup requests / answers lookup requests incorrectly), routing requests are not forwarded to this node anymore. Further, as neighbors could forward the requests to different next hop nodes, the lookup process has to be coordinated (e.g., by iterative routing) as otherwise the number of forwarded requests may increase strongly. Due to the parallel lookup, probability of a successful lookup increases. According to [PERSON] _et al._, the reputation system works efficiently as long as the fraction of malicious nodes is below 50 %. Combining _Redundant_ and _Iterative_ approaches, [PERSON] and [PERSON] [26] proposed a parallel and iterative routing algorithm. Whenever a request is initiated, the source node has to send \(n\) lookup request messages in parallel. Each intermediate node sends a reply message proposing a set of next hop nodes to the source of the request. Based on this information, the source node selects \(n\) next hop nodes and forwards \(n\) request to those nodes.