Hi, if I remember correctly, the thought behind i) was that the attacker has a very high probability to capture routing requests that pass one of its neighbors, so the strength of the attacker should depend on the ttl of the routing and the connectivity/degree of the attacker (=factors influencing the likelihood that a neighbor is on the route), I guess.
Yes, as stated, it is definitively an improvement over the current algorithm. Just pointing out that it might still have some issues and I am currently unsure if they are serious threats or can be disregarded :) My guess would be that the problem only arises if the attacker has a lot of neighbors, but any concrete results reinforcing that guess would of course be better. Regards, Stef On 19.04.2016 21:57, Arne Babenhauserheide wrote: > Hi Stef, > > Thank you for your answer! > > I’m sorry that it took me long to answer back. I somehow missed a lot of > messages the past three months… (I’m only now catching up bit by bit) > > i) only works when the attacker is directly connected to the target, > right? That would allow them to fix one node per active connection to > a bad position, and for that they have to be already connected via > darknet, so they have to social engineer their way to the nodes. > > I would think that both problems are much weaker in impact — though > that’s easy compared to the pitch black attack which effectively allowed > poisoning the network with negligible cost. > > Best wishes, > Arne > > Stefanie Roos writes: > >> 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} >>> } >>> >>> >
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
