Mitigate the Pitch Black attack (the simulation works)

I fixed a small bug in the simulator of thesnark. With that, the simulator shows that the defense against the Pitch Black Attack works: A small number of attackers can no longer kill parts of the keyspace and can also no longer make certain parts of the keyspace inaccessible.

Attackers can still limit the convergence of the network towards a reproduction of the small world network, but since we know that Opennet works quite well with 30% backoff, this limited convergence should suffice for efficient routing.

peer distances under attack

I also identified two possible ways to make the algorithm more efficient.

The fix does not need to know the size of the network. The only global information it needs is routing to random locations.

In this mail I first describe simulator and Pitch Black Attack. Afterwards I describe the fix. The fix was originally proposed by Oskar Sandberg. He did all the hard work, I just describe it here.

Graphics

Peer Distances - Location histogram

(because that’s what most people really want ☺)

These show that the fix prevents complete fracturing of the keyspace: It recreates the short connections.

The simulator

Most of the simulation is the work of Michael Grube. I just fixed a small bug.

  • Michaels Repo: http://github.com/mgrube/pbsim
  • My Repo: http://github.com/ArneBab/pbsim

The network starts with a random network and then optimizes it — either with clean swapping or under attack without and with different countermeasures.

To run the simulation, run

./testfixpitchblack.py

You need pylab and networkx (links are in README.md).

The Pitch Black Attack (the problem)

Optimizing the network with swapping works pretty well without attacks (within the mathematical limits1) — as shown in the simulation ("clean swapping network"). But this can currently be broken easily, even by a single attacker, using the Pitch Black Attack.2

Swapping exchanges keys and implicitly trusts randomly selected nodes. Two nodes compare their peers, and if they determine that exchanging their locations improves the link length distribution to their respective group of peers, they swap the locations. Node A now has the former location of node B and node B has the former location of node A.

Normally that’s no problem: The probability that this trust is violated is just the proportion of attackers in the network. So some swapping will wrong, but this will only happen rarely.

There is one lasting effect however: If node B always hands out the same location when swapping, this location will stay in the network indefinitely and former location of node A will be lost. This is slow, only one key can be killed per swapping, but highly effective.

Using the Pitch Black Attack, attackers can remove selected locations From the network (which allows for censorship by making selected files with known keys inaccessible, because nodes with their content change to locations which won’t be searched for this content).

The fix for this has been pending since 2008 because “We have solutions for this but they are still being tested.” (https://freenetproject.org/about.html#papers). I consider this testing to be done with this email. The fix works (described as follows).

Approach

To fix the Pitch Black Attack nodes route to a random location and check the distance of the closest node they can reach. If this distance is much larger than expected, they consider the network to be under attack and switch to this location to fill the gap they found.

If detection and filling of gaps is faster than creation of gaps by the Pitch Black Attack, this reduces the Pitch Black Attack from a death stroke to a nuisance.

Requirements

  1. The network must be stable for (a) a random network and (b) a network with a cluster of small-world structured nodes embedded in a random network. The algorithm must not mistake (a) or (b) as attacked networks, otherwise swapping will not be able to change a random network to a small world network.

  2. In case of an attack, nodes must switch do positions inside the created gaps to fill them.

  3. When switching locations, content must be preserved close to the old location.

Information used

The simulated algorithm only uses the estimated number of peers (also known as outdegree), the distance to direct peers and actual routing. It does not need the size of the network.

The number of peers is used to calculate the expected distance to a location in a randomly structured network. More exactly: The mean distance plus two standard deviations (97.5% of random routes will find a shorter distance than this). Let’s call this expected random distance range d_er. As far as I can reconstruct it, this distance was calculated by Oskar using statistics. I just use brute force, as shown in https://github.com/ArneBab/pbsim/blob/master/bruteforcemindist.py

This is the magic number 0.037. If you choose a set of six random locations in the circular keyspace [0..1) repeatedly and stop when the closest of these locations isn’t closer to a target than on the previous try, and you re-run this experiment repeatedly, then 95% of the results will be closer than 0.037. It’s the 95% limit of the distance to a target in a random network with outdegree 6.

The basic algorithm

Before starting to swap, a freenet node first selects a random location. Let’s call it l. Then it routes towards this location and notes the distance of the node closest to this location. Lets call it d.

Now it calculates the mean distance to its direct peers. Let’s call this d_mean

If the distance d minus the mean distance to the peers d_mean is larger than the expected random distance range d_er, the node assumes that the random location l is within a gap. Instead of starting a swap request, it switches to this tested location l.

if (d - d_mean) > d_er: switch to l else: initiate swap

d - d_mean compares the routing result with the distribution of direct peers. If the gap is bigger than the mean distance to the peers, it might be a real gap, purely from local information.

(d - d_mean) > d_er ensures that even if the peers have the same location (d_mean = 0), this is only treated as gap if d is larger than the distance which would be found on 95% of routing tries in a random network, d_er. This ensures that even when there is a small optimized group within a large randomized network (for example when the network grows quickly), the nodes in the optimized group will not mistake the routing quality outside the optimized group as attacked network.

Adaptions

Median distance

During experimentation I found that using mean peer distance means that nodes with more long-distance connections are less likely to detect a gap. An attacker might be able to segment the network so that every node has a few long-distance connections to prevent detection of gaps. I tried to fix this using the median distance to peers instead of the mean distance, since the median is less sensitive to outliers.

use d_median instead of d_mean

This was the most effective adjustment, but I need help from someone with deeper knowledge about network statistics to test this.

Route to two targets

If the constant minimum distance for random networks (d_er) should prove problematic, we can reduce the value of d_er by doing two routing tries with different targets and check the shorter of the two distances but switch to the target with the larger distance. d_er would then for example be only around 0.02 instead of 0.037). But for this the simulation results have been unclear.

Avoid data loss

If a node changes its location by a large distance, this means that the content it holds cannot be found anymore. To fix this, it needs to re-insert all content in its store.

This is no large problem with basic swapping, because there the locations should stabilize, changing only in small ways. In case of an attack, it becomes important, though.

While it sounds expensive to re-insert all content in the store, it should not actually cost too much, since we can assume that most peers of the node will be close to its old location. So it could simply insert the content in its store with a HTL around 2 and still be confident to reach the right nodes.

Conclusion

This solution mitigates the Pitch Black Attack with moderate cost. Under attack the network no longer converges completely, but it still reaches a more optimized state of which I would expect that it suffices for routing.

It would be great to have more math on this, but I think it’s already ready for implementation.

Please comment!

Best wishes, Arne Babenhauserheide


  1. Stefanie Roos showed that efficient convergence is not possible under churn, but this should not affect Freenet too badly, because in friend-to-friend mode many connections are extremely long lived, often on the order of years. Therefore real churn (as in permanently lost connections) is extremely low compared to other systems which often have lifetimes on the order of hours. 

  2. This was shown by Christian Grothoff: http://grothoff.org/christian/pitchblack.pdf @conference{pitchblack, title = {Routing in the Dark: Pitch Black}, booktitle = {23rd Annual Computer Security Applications Conference (ACSAC 2007)}, year = {2007}, pages = {305{\textendash}314}, publisher = {IEEE Computer Society}, organization = {IEEE Computer Society}, abstract = {In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, direct communication between nodes is limited to specific neighbors. Often these networks have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks.

    This paper is the first independent security analysis of Clarke and Sandberg{\textquoteright}s routing algorithm. We show that a relatively weak participating adversary can render the overlay ineffective without being detected, resulting in significant data loss due to the resulting load imbalance. We have measured the impact of the attack in a testbed of 800 nodes using minor modifications to Clarke and Sandberg{\textquoteright}s implementation of their routing algorithm in Freenet. Our experiments show that the attack is highly effective, allowing a small number of malicious nodes to cause rapid loss of data on the entire network.

    We also discuss various proposed countermeasures designed to detect, thwart or limit the attack. While we were unable to find effective countermeasures, we hope that the presented analysis will be a first step towards the design of secure distributed routing algorithms for restricted-route topologies.}, keywords = {denial-of-service, Freenet, installation, routing}, url = {http://grothoff.org/christian/pitchblack.pdf}, author = {Nathan S Evans and Chis GauthierDickey and Christian Grothoff} } 

Inhalt abgleichen
Willkommen im Weltenwald!
((λ()'Dr.ArneBab))



Beliebte Inhalte

sn.1w6.org news