All, Please excuse my absence. I have been very preoccupied. I am OK with the idea that we should publish and am willing to spend time assisting with that effort.
However I should disclose that I am doing research on creating a method very similar to Snadberg's original work, except that the network would sit on top of a fractal lattice. I am investigating methods to exploit the assumption of a fractal network to detect swap proposals that are inappropriate or very out of place. The work is shoddy and incomplete at the moment but all of my free time is going into it. I will make people aware of results as I get them. Thanks On Feb 9, 2016 8:59 AM, "Stefanie Roos" <[email protected]> wrote: > Hi Arne, > > looks fine in general and seems to prevent the PitchBlack Attack in its > current form. > I am slightly worried about some modified versions of the attack, which > take the protection scheme into account. > > Does the following attack work? > Pitch Black Attack: attacker(s) always provide location l1 > In addition, they > i) pretend to have location l2, reasonably far from l1 > ii) whenever nodes route for a location loc, an attacker on the route > replies with an loc' close to loc > > i) should encourage neighbors to forward to the attacker (because it > seems to be one of the few nodes not close to l1) and ii) ensures that > nodes don't swap to random location > > => I don't think this is a probably as long as the attacker has few > connections (and is thus unlikely to be on the route) but will be a > problem for more powerful attackers, so it might be good to check how > much it changes your results and determine how strong an attacker has to > be (in terms of connections to honest nodes or so). > > A second problem might be presented by an attacker who does not perform > a PitchBlack Attack, but upon receiving a routing request for the > closest node to location loc always replies with a fake location at a > large distance to loc, in order to achieve a randomized network (since > the node changes its location to the random location loc while its > current location might actually be very good). > > However, I think both attacks are certainly less of a problem than > PitchBlack. > > Cheers, > > Stef > > > > On 08.02.2016 12:13, Arne Babenhauserheide wrote: > > Hi, > > > > ## Preface > > > > 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. > > > > 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 > > > > - > http://draketo.de/dateien/freenet/fix-pitch-black-400-mean-median-median2-peerdist.png > > - > http://draketo.de/dateien/freenet/fix-pitch-black-400-mean-median-median2-lochist.png > > > > (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 limits[1]) — 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.[3] > > > > 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 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[2] 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]: Dipl. Math Stefanie Roos > > > https://tu-dresden.de/die_tu_dresden/fakultaeten/fakultaet_informatik/sysa/ps/beschaeftigte/mitarbeiter/sro_de > > > > [3]: 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} > > } > > > > > > > > _______________________________________________ > Devl mailing list > [email protected] > https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl > _______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
