Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

Matthew Toseland writes:

> On 22/04/16 21:31, Arne Babenhauserheide wrote:
>> Matthew Toseland writes:
>>> On 09/02/16 08:58, Arne Babenhauserheide wrote:
 We can’t keep nodes from leaving, but we can keep swapping which spans
 large parts of the keyspace from making parts of the datastore
 inaccessible.
>>> On a hybrid network we still have the aristocracy problem: Because
>>> opennet is meritocratic, fast nodes tend to connect to fast nodes. Hence
>>> the distribution is likely to be non-uniform - slow nodes will be out on
>>> the edge and have poor connectivity i.e. possibly a different mean
>>> distance??
>> This is not connected to losing store content due to darknet swapping, right?
> No, but does it affect the Pitch Black fix?

I do not think so.

Not inserting the store content when swapping also does not become worse
with the pitch black fix.

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein
ohne es zu merken


signature.asc
Description: PGP signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Matthew Toseland]

On 22/04/16 21:31, Arne Babenhauserheide wrote:
> Matthew Toseland writes:
>
>> On 09/02/16 08:58, Arne Babenhauserheide wrote:
>>> Because in normal swapping, as soon as the network settled a bit, the
>>> changes in location should be small (though my nodestats look different:
>>> too large changes in location for my taste…). So the node data should
>>> still be reachable. When randomizing the position, however, the step is
>>> large and the node might settle into a new part of the keyspace, so the
>>> store might not be reachable anymore.
>> Not in all cases. E.g. merging several growing darknets? Is this slow
>> enough that we don't care?
>>
>> OTOH: Can this be used as some sort of DoS? Is 2 hops enough? Etc.
> Maybe this should simply be regular insertion, which however would limit
> the convergence speed.
>
>> This was likely discussed way back when darknet was first proposed,
>> maybe Oskar has an opinion about it ...
> It would be great to recover some of this, given that now more people
> seem willing to actually invest in building friend-to-friend connections
> (though I’m nut sure whether I just have that impression because it
> works for me now).
>
>>> We can’t keep nodes from leaving, but we can keep swapping which spans
>>> large parts of the keyspace from making parts of the datastore
>>> inaccessible.
>> On a hybrid network we still have the aristocracy problem: Because
>> opennet is meritocratic, fast nodes tend to connect to fast nodes. Hence
>> the distribution is likely to be non-uniform - slow nodes will be out on
>> the edge and have poor connectivity i.e. possibly a different mean
>> distance??
> This is not connected to losing store content due to darknet swapping, right?
No, but does it affect the Pitch Black fix? No, because hybrid nodes
don't swap?



signature.asc
Description: OpenPGP digital signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

Matthew Toseland writes:

> On 09/02/16 08:58, Arne Babenhauserheide wrote:
>> Because in normal swapping, as soon as the network settled a bit, the
>> changes in location should be small (though my nodestats look different:
>> too large changes in location for my taste…). So the node data should
>> still be reachable. When randomizing the position, however, the step is
>> large and the node might settle into a new part of the keyspace, so the
>> store might not be reachable anymore.
>
> Not in all cases. E.g. merging several growing darknets? Is this slow
> enough that we don't care?
>
> OTOH: Can this be used as some sort of DoS? Is 2 hops enough? Etc.

Maybe this should simply be regular insertion, which however would limit
the convergence speed.

> This was likely discussed way back when darknet was first proposed,
> maybe Oskar has an opinion about it ...

It would be great to recover some of this, given that now more people
seem willing to actually invest in building friend-to-friend connections
(though I’m nut sure whether I just have that impression because it
works for me now).

>> We can’t keep nodes from leaving, but we can keep swapping which spans
>> large parts of the keyspace from making parts of the datastore
>> inaccessible.
>
> On a hybrid network we still have the aristocracy problem: Because
> opennet is meritocratic, fast nodes tend to connect to fast nodes. Hence
> the distribution is likely to be non-uniform - slow nodes will be out on
> the edge and have poor connectivity i.e. possibly a different mean
> distance??

This is not connected to losing store content due to darknet swapping, right?

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein
ohne es zu merken


signature.asc
Description: PGP signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

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

 - 
 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Michael Grube]

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 
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 <
> stefanie.r...@tu-dresden.de> 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 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Michael Grube]

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 
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
> >>> 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Stefanie Roos]

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 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

Hi Michael,

Michael Grube writes:
> 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.

That would be great!

I finished my PhD on January 15th (but am actually only recovering now),
so I could invest some time. However coming from Physics, I’m quite far
From the field and have too little domain knowledge to really take good
publication decisions.

Maybe we could contact Oskar and Ian whether the pitch black defense
simulations suffice to try to finally get the Freenet 0.7.5 paper
published.


I think what we need for that, now that the simulation showed that the
defense works, is someone who implements the fix. And different from
what I wrote earlier, I think that going for the easiest solution (the
original proposal with mean distance) would be best for that.

> 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 don’t think anyone minds that. Many of us have other projects, and
I think it’s good to not have all our eggs in one basket, though I cannot
take care of all those baskets myself :)

> 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.

Thank you!

Best wishes,
Arne


signature.asc
Description: PGP signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

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 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

Matthew Toseland writes:

> Awesome! We need to:
> 1) Implement this.

Yepp.

> 2) Publish it.

We should… Stefanie and Michael might be able to gain something from
that. Maybe you, too?

> Why is reinserting the whole datastore important in the case of an attack?

Because in normal swapping, as soon as the network settled a bit, the
changes in location should be small (though my nodestats look different:
too large changes in location for my taste…). So the node data should
still be reachable. When randomizing the position, however, the step is
large and the node might settle into a new part of the keyspace, so the
store might not be reachable anymore.

> AFAICS we are looking for a gap much larger than the node's local
> average peer distance? In practice this is likely to vary a lot because
> of different node degrees etc?

Yes. Node degree is the core variable for that. Thanks to FOAF
information we should be able to use an average degree of all friends
for the calculation.

> On opennet, performance has a big impact;
> on darknet, a node's location on the graph and its peer count? I'm
> thinking of the problems we had around the time Pitch Black was
> published - at least some of it was due to nodes with few peers taking
> locations in big gaps and then leaving the network.

We can’t keep nodes from leaving, but we can keep swapping which spans
large parts of the keyspace from making parts of the datastore
inaccessible.

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein
ohne es zu merken


signature.asc
Description: PGP signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Michael Grube]

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"  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 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Stefanie Roos]

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 

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Matthew Toseland]

On 09/02/16 08:58, Arne Babenhauserheide wrote:
> Matthew Toseland writes:
>
>> Awesome! We need to:
>> 1) Implement this.
> Yepp.
>
>> 2) Publish it.
> We should… Stefanie and Michael might be able to gain something from
> that. Maybe you, too?
>
>> Why is reinserting the whole datastore important in the case of an attack?
> Because in normal swapping, as soon as the network settled a bit, the
> changes in location should be small (though my nodestats look different:
> too large changes in location for my taste…). So the node data should
> still be reachable. When randomizing the position, however, the step is
> large and the node might settle into a new part of the keyspace, so the
> store might not be reachable anymore.

Not in all cases. E.g. merging several growing darknets? Is this slow
enough that we don't care?

OTOH: Can this be used as some sort of DoS? Is 2 hops enough? Etc.

This was likely discussed way back when darknet was first proposed,
maybe Oskar has an opinion about it ...
>> AFAICS we are looking for a gap much larger than the node's local
>> average peer distance? In practice this is likely to vary a lot because
>> of different node degrees etc?
> Yes. Node degree is the core variable for that. Thanks to FOAF
> information we should be able to use an average degree of all friends
> for the calculation.
>
>> On opennet, performance has a big impact;
>> on darknet, a node's location on the graph and its peer count? I'm
>> thinking of the problems we had around the time Pitch Black was
>> published - at least some of it was due to nodes with few peers taking
>> locations in big gaps and then leaving the network.
> We can’t keep nodes from leaving, but we can keep swapping which spans
> large parts of the keyspace from making parts of the datastore
> inaccessible.

On a hybrid network we still have the aristocracy problem: Because
opennet is meritocratic, fast nodes tend to connect to fast nodes. Hence
the distribution is likely to be non-uniform - slow nodes will be out on
the edge and have poor connectivity i.e. possibly a different mean
distance??

Does this affect this?
>
> Best wishes,
> Arne



signature.asc
Description: OpenPGP digital signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Matthew Toseland]

On 09/02/16 14:12, Michael Grube wrote:
> 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.

That sounds great. I do think we should try to publish what we have
already though, it may have ramifications beyond Freenet itself as the
authors pointed out. Thanks for all your work making this happen!
> Thanks



signature.asc
Description: OpenPGP digital signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl

[freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Arne Babenhauserheide]

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

Re: [freenet-dev] Mitigate the Pitch Black attack (the simulation works)

[Matthew Toseland]

Awesome! We need to:
1) Implement this.
2) Publish it.

Why is reinserting the whole datastore important in the case of an attack?

AFAICS we are looking for a gap much larger than the node's local
average peer distance? In practice this is likely to vary a lot because
of different node degrees etc? On opennet, performance has a big impact;
on darknet, a node's location on the graph and its peer count? I'm
thinking of the problems we had around the time Pitch Black was
published - at least some of it was due to nodes with few peers taking
locations in big gaps and then leaving the network.



signature.asc
Description: OpenPGP digital signature
___
Devl mailing list
Devl@freenetproject.org
https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl