Hi Stefanie, My apologies, I missed that you were talking about a different attack.
Regardless, I agree that the presented solutions are not ideal. Thanks, Michael On Wed, Apr 20, 2016 at 2:48 PM, Michael Grube <[email protected]> wrote: > Hi Stefanie, > > I'm just clarifying for my own sake - you're talking about pitch black, > correct? There are some implications which may involve capturing routing > requests, but essentially the attack destroys the small world routing > efficiency of Sandberg's work by propagating fixed locations throughout the > network by lying about the locations of neighbors. It does not matter > terribly much if the attacker is highly connected or not - 2 attackers can > cripple a network of about 1000 or so nodes given adequate time. > > For the record I agree completely that the solutions demonstrated by my > simulation work are not ideal. I'm still working on some countermeasures > which I hope to release the code for soon. > > Let me know if you have any questions, I'd be happy to answer them. > > Thanks! > Michael > > > On Wed, Apr 20, 2016 at 2:31 PM, Stefanie Roos < > [email protected]> wrote: > >> 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} >> >>> } >> >>> >> >>> >> > >> >> >> >> _______________________________________________ >> 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
