Hi Stef, I am sure that the algorithm still has issues. I would not claim that it is perfect. However the Pitch Black Attack is so serious, that stopping it is a very important step forward (and one we should have done years ago, but we had a too big disconnect between those who did theory and those who actually implemented the concepts found).
We’re working on changing that (and I hope that this discussion here is a part of improving that — Freenet is an implementation of important concepts which is in actual use, and experiences actual attacks, which allow seeing the concepts in real life). Best wishes, Arne Stefanie Roos writes: > 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} >>>> } >>>> >>>> >> -- Unpolitisch sein heißt politisch sein ohne es zu merken
signature.asc
Description: PGP signature
_______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
