We need to be careful here. A pitch black style attack that succeeds in causing only a minor shift in locations may have a significant impact on request success rates. Given O(1) peers per node, Freenet requires O(log^2(N)) hops to find data. If we limit HTL to O(log^2(N)), then only nodes within distance O(1/N) of the ideal node can be reliably searched. That means we need to limit the ability of the attacker to shift locations to O(1/N) at worst, and ideally something more like O(1/(n*log(n))).

The best approach for the attacker might not be to simply try to concentrate locations near one chosen region (making other regions less reliable), but instead to first concentrate slightly near one region, then shift to a different region, causing data stored during the first portion to be unreachable.

We need to quantify not only the amount of location bias an attacker can introduce, but how that bias scales with network size, both for an attacker with fixed resources and for one with O(N) resources. For example, if an attacker can introduce O(log(N)/N) location drift, then finding data requires searching roughly O(log(N)) nodes near the ideal location, which means the network goes from O(log^2(N)) route length to O(log^3(N)).

We should also investigate both with and without bloom filter sharing, though I suspect bloom filter sharing has an O(1) effect on route length regardless.

Oskar has proposed a solution involving probing and selective randomisation. He is skeptical that faster swapping algorithms on their own (or combined with throttling) will fix it.

Pick a key randomly, route for it with a special query that returns the
nearest node identifier to the key found. If the closest you can get is much
further than your distance to your neighbors, give up your current position
for the random one. The definition of "much further" needs to be determined
experimentally, but it shouldn't be an issue (since the attack in question
works by putting a neighbor thousands of times closer to you then it should
be).

To make this more failsafe, one could choose K random keys, and compare the
median distance of those keys to the nearest node with your distance to your
neighbors.

Hopefully simulations will happen now that our PETS paper was rejected partly on the grounds that our swapping security sucks. We need to simulate this potential solution and demonstrate that it fixes the attack, and get a paper out about it. And then we need to implement it.

I like the idea, but...

Consider an attacker who has already mostly successfully executed the attack and is trying to maintain it. He chooses locations for his nodes (we assume he has several, but limited resources) that are a mix of nodes in the empty space and at the borders of the empty space. The routed location-seeking requests will, with high probability, be routed to one of his nodes. He can then fake the response to make it seem correct. My hunch is he can do a fairly decent job maintaining the corrupted network. The obvious question is, can he get it there? I suspect he can, but clearly simulation work is required. (The semi-corrupted network may be a more difficult playing field for the attacker, since he can't intercept as large a fraction of the requests. I suspect this merely slows down the attack.)

Note that the use of FOAF routing makes this easier for the attacker: his fake nodes can advertise a lot more locations than he has nodes, by judicious fakery of the FOAF lists.

My best guess is that this is a step in the right direction, but something more complicated / clever is required to thwart the attack.

I’d like to propose an alternative:

• Each node has two locations.

• They are compared at regular intervals far longer than the time between location-switches.

• Only the location with the worse score does switches. The better one stays fixed.

• After every comparision, the worse location chooses a new location at random and then does regular switching. If it doesn’t get better than the other location, the interval between comparisions is increased.

• When it gets a better score, the time between comparisions is reset.

• One measure for quality could be throughput or successful requests.
ideally (after a long time) both locations could be at a global optimum.

When this gets hit by a pitch black attack, the switching node should be the worse node, so the other location would stay fixed and the switching would do optimization runs from random positions to the cluster the attacker wants, and revert at each comparision.

The worst an attacker could then do is first introducing a small bias and then using the pitch black attack to make sure that the random location doesn’t find a better spot than the slightly biased one. The bias can’t be higher, though, than the quality which can be reached when switching from a starting location.

The highest allowed bias in an attack would be an upper bound on the time between comparisions.

The critical part in this scheme is the quality evaluation of the locations. If the attacker can twarth that, the scheme breaks.

thesnark is working on this for a master's project over the summer. Hopefully he will come up with an algorithm and simulations proving that it works - or validate oskar's algorithm.

[20:59:34] <zerwas> interesting lecture: "This talk will show that the recent 0.7 release of Freenet -- marketed to solve most of the problems -- entirely fails to deliver." https://www.youtube.com/watch?v=G9fAn0QO9WQ
[21:00:21] <TheSeeker> old problems are old.
[21:00:38] <zerwas> yeah, but still.
[21:01:23] <TheSeeker> Opennet prevents pitch black from working at the moment, and there's a rudamentary workaround on darknet (periodic location randomization)
[22:07:36] <toad> TheSeeker: zerwas: is it just Pitch Black or is there anything else? is it worth my time watching it?
[22:07:56] <zerwas> just pitch black, i didn't even watch it entirely myself, too technical
[22:08:17] <toad> does it explain how pitch black works? the paper was difficult to follow to the point of actually implementing it ...
[22:08:24] <zerwas> don't waste your time on youtube, code! ;)
[22:12:10] <zerwas> it goes into details about attacks, 5 minutes of Q&A session at the end
[22:13:59] <zerwas> slides are here: https://www.defcon.org/images/defcon-15/dc15-presentations/dc-15-evans_and_grothoff.pdf

Oskar's algorithm seems to work.
thesnark will post details soon, with some stats.

Before implementing, need to fetch his code and put it somewhere.
=> Simulation in /usr/src/cvs/eclipse-workspace/pbsim, NOT REVIEWED.
From http://github.com/mgrube/pbsim
[19:45:12] <thesnark> bulk is in my painfully generic "pynetsim.py" file

[20:09:10] <toad> thesnark: did you have some summary data for me? if it takes hours to find it then I guess it isn't so summary ...
[20:09:30] <thesnark> No, I don't have any right now.
[20:09:42] <thesnark> Realistically I'll have to run the simulations again.
[20:09:59] <toad> :|
[20:10:00] <toad_> okay

=> Contacted on 05/07/2013.
=> Bug him if no sign by 19/07/2013.

Last lot of simulations were roughly:

• Current swapping (6 hops)
• Current swapping plus oskar's defensive hack
• Current swapping plus oskar's defensive hack + 1% attackers (IIRC?)
  (06/05/2013)

I'm still waiting for the final report, which apparently requires new simulations.

gerard_ may do some simulations on this. He is interested in using Freenet routing for routing packets.

Link to Wanderlust (routing packets using Freenet's darknet routing): https://github.com/gerard-/wanderlust

I'll be publishing my work there. Any simulation result will probably translate very well to Freenet as there is a lot of overlap.

A description of possible attacks on Wanderlust is available here:
https://github.com/gerard-/wanderlust/blob/master/doc/attacks.md

My take on the Pitch Black attacks:
The attacks work by reducing the entropy in the node locations. We need to make sure we keep this high enough. This can be done by periodically and randomly modifying a nodes location a little bit. The small change will not significantly impact routing but the added entropy will hopefully keep the network healthy.

We should limit the number of allowed swaps (and new nodes) so that the amount of entropy that an attacker can reduce with the attack is lower than the amount we can generate by changing the locations. Of course we still need to allow for enough swaps to self-organize the network. This is an interesting balance, and whether this is possible should be provable.

Advantages of this method over Oskars idea are that it is simpler and that it prevents big jumps in locations for a node which could lead to routing problems or in the case of Freenet data loss.

We already limit the number of swaps. It appears to be insufficient, given that the attacker can force the target to swap IIRC? I'm not sure, I never investigated Pitch Black in detail.

This is as far as thesnark's work (on Oskar's fix) got:
https://emu.freenetproject.org/pipermail/devl/2013-January/036774.html

Did anyone download those graphs?

The results sound like the pitch-black attack is effectively blocked with this approach, and given that Freenet can cope with 30% backoff, it should work with non-optimal link lengths — as long as they are not too bad. It’s not like the network really has to converge to the ideal solution to work well.

<ArneBab_> https://gnunet.org/nse-techreport-2012 Efficient and Secure Decentralized Network Size Estimation ← should allow stopping the pitch black attack.

proof that Oskars fix stops the Pitch Black Attack: http://127.0.0.1:8888/USK@sUm3oJISSEU4pl2Is9qa1eRoCLyz6r2LPkEqlXc3~oc,yBEbf-IJrcB8Pe~gAd53DEEHgbugUkFSHtzzLqnYlbs,AQACAAE/random_babcom/187/#FixedsimulationshowsthatSandbergsfixstopsthePitchBlackattack

The link length distribution stays better than what we had for Opennet before the link length fix: http://127.0.0.1:8888/CHK@6yxbJzBufElCPYc1nfkRQTmx4QaC~iAlM4pwPy4m8IQ,sUuGgCErPTn51xhImo3vYv~LYolDk4YwHbKBqh0vITc,AAMC--8/pitch-black-attack-fix-works-with-a-fix-to-the-algorithm.png

the node locations get skewed, but not unusably so: http://127.0.0.1:8888/CHK@qVziRFePFX6mziEJE6omukR0wEhO4wIB5c30-oSWyko,5Lzxn3cAVPilbMoPS8rbryBlb08QmjwvV9vab5fPK8o,AAMC--8/pitch-black-attack-fix-works-with-a-fix-to-the-algorithm-node-positions.png

Using the median peer distance to detect the pitch black attack is quite a bit more effective than using the mean peer distance.

By implementing the size estimation algorithm defined by the GNUnet folks using node-to-node messages for communication this should give good protection against the pitch black attack for darknets of any size

To avoid losing data it might be useful to actively push the data to better nodes whenever we change the location (regardless of via swapping or via randomization).

Here’s a clearnet link for the working simulation: http://www.draketo.de/light/english/freenet/mitigate-pitch-black-attack-simulation-works

We know that the suggested fix should work, acknowledged by security researchers: https://emu.freenetproject.org/pipermail/devl/2016-April/038903.html

We now need to implement it.

The pitch black attack is mitigated and the mitigation deployed. This will provide the final test that verifies that: https://github.com/freenet/fred/pull/736

Fixed thanks to support from https://nlnet.nl/project/Freenet-Routing/