Am Samstag, 22. Dezember 2012, 02:17:24 schrieb Matthew Toseland: > Hmmm, what about DoS attacks against the pre-insert cache? Maybe we should > use the store; we do want to free up the slots when we've inserted > successfully though (in spite of random replacement this still makes the > store more efficient).
wouldn’t the pre-insert keys never be requested, so they would drop out anyway
after 14 days on average? (following digger3’s stats)
> > I insert many chunks which go to the same part of the keyspace. When I
> > send
> > the reveal, I can start a distributed replacement attack.
> >
> > Any chance to avoid that?
>
> Ahhh, you mean you can bombard one keyspace location with lots of spam
> inserts, in the hopes of driving a single document out, and while avoiding
> the usual load management limits between you and the target?
Yes, exactly that.
It allows attacking a given location without being detectable.
Though that’s essentially a condition to being anonymous, so I don’t know if
it is fixable…
Essentially you can pretend to be many different people at the same time. If
you can orchestrate the reveal, you could create very many inserts to some
location coming in one fast burst. And that could make it possible to kill a
document with known content before anyone can download it.
> I guess it comes down to how effective will the attack be, given the
> structure of our datastores? How many keys on average do we need to send to
> a node to displace a target document, given they are close to the target
> location so will be routed to the target node, and given we don't know the
> salt value for that store? Won't that be a significant fraction of the
> datastore?
That’s a very good point.
If we want to be reasonable sure that we can kill a given file, we might have
to displace 90% of the store or so.
I think that the assumption, that normal insert behaviour is pretty random
distributed in the keyspace, so a sudden surge of inserts to a given location
could be detected as an attack.
And since that would very likely only happen with an attack, adding limits to
displacement in the store should kill those attacks but only marginally affect
regular inserts.
In my 1GiB store, I have a write rate of 0.08/s and 13,414 keys, so if I
interpret the data correctly, it takes 40h till the number of write requests
equals the number of keys.
To estimate the amount of keys displaced after 40h:
N: Number of keys in the store.
First key: 100% chance of displacing an old key.
Second: (1 - 1/N) chance of displacing an old key.
…
since I stumbled with the math, I realized it in a recursive function:
def displacedold(n, steps, step=0, nth=None):
if step == steps:
return nth
if step == 0:
return displacedold(n, steps, step=step+1, nth=1 - 1.0/n)
return displacedold(n, steps, step=step+1, nth=nth*(1 - 1.0/n))
def displacedourkey(n, steps):
dis = 1.0/n
for step in range(steps-1):
dis += displacedold(n, step+1)/n
return dis
print displacedourkey(100, 100)
→ 0.63
print displacedourkey(100, 200)
→ 0.86
print displacedourkey(100, 300)
→ 0.95
print displacedourkey(100, 400)
→ 0.98
This stays similar for bigger numbers of keys, but my algo is bad enough that
it quickly exceeds the maximum recursion depths :)
So to be 95% sure that you replaced a key, you have to create inserts of 3
times the size of the store. Which in case of my store would take about 6
days.
If you could triple the rate of writes to my store with the distributed insert
attack, you could decrease the lifetime to 2 days.
But that could be stopped by throttling the rate of change of write traffic to
the node (if that’s possible). Then an attacker would have to keep inserting
constantly and the attack would be twarted.
The attack draws its strength from being able to insert first and then using
the reveal step to force a huge number of writes to a given location in a very
short time. Essentially it allows storing up bandwidth and then releasing it
in a much shorter timespan.
And that is not possible if you have to keep up the insert traffic over a
longer timespan.
And that can be stopped by throttling the rate of change of write traffic to
the store. For example it would be possible to limit the writes per minute to
3× the daily rate.
Then displacing a key in my store with high probability (95%) would take at
least 2 days. And that is much longer than the time needed for completing an
upload, announcing the upload on Sone and someone downloading it.
And as soon as the upload has been downloaded, it is in the cache and the
attack is useless, because downloaders can heal the inserted key.
(please doublecheck my logic, though!)
> If we can quantify it, e.g. say that it's possible but you'd need to
> continually commit a significant amount of bandwidth per targeted key
> depending on its popularity, that's enough for me ...
Throttling the write rate gives that.
The attack tries to make all nodes around you send you inserts all of a
sudden, so the write rate has a massive spike. Smooth that spike and the
attack is mostly useless.
> > > chain are still connected it will prove to them that the insert has been
> >
> > How do they prove it?
>
> Forwarding a portion of the reveal request? Not all of it, we don't want
> them to be able to decode the block; X_n is probably enough?
I don’t know it well enough to say something about that. But I trust your
judgement here.
> > http://en.wikipedia.org/wiki/Dining_cryptographers_problem
>
> Right, we can use provably anonymous broadcast groups provided the message
> is very small, and provided that it can be announced all at once, before
> there is any churn in the membership of the group. The problem comes if we
> can't do the reveal for the whole file in one broadcast, or, if we do two
> stages, if a node receives both the original and the reveal so can connect
> the two broadcast groups. These sorts of things look very hard to execute
> though IMHO?
I don’t know enough to answer that.
> previous, so there should be very few such levels. And we can use anonymous
> broadcast for the bottom layer.
I’m a bit wary of broadcast, since that creates very many messages. Is it a
real broadcast (reaching all nodes in the network) or limited somehow?
But all in all, the scheme sounds pretty good to me. I don’t have sufficient
knowledge to really judge it completely, though.
Best wishes,
Arne
--
Ich hab' nichts zu verbergen – hab ich gedacht:
- http://draketo.de/licht/lieder/ich-hab-nichts-zu-verbergen
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
