On Saturday 25 October 2003 02:42 pm, Martin Stone Davis wrote:
Nick Tarleton wrote:
On Thursday 16 October 2003 10:11 am, Martin Stone Davis wrote:
D'oh!!! I goofed: Node C would see that it takes node A LESS TIME to find keys K101-K1000 than to find keys K1-K100, since A is trying to hide the fact that it has K1-K100.
What if it moves them from the separate to the main store when they pass through it without client intervention? I.e., if it receives a request for K1, it goes through the network and THEN moves K1 to the regular store.
Sure, but the problem still remains: the evil AAIR would still be able to tell that I was trying to hide the fact that I had requested K1-K100, since it will detect a timing difference where it knows there would be none if I weren't trying to hide it.
Then why not put a random fraction of keys in the regular store? (Alchemy.)
I think that will help, but I think it's limited.
Just to be clear on what you're saying: If the fraction is 100%, then of course we have what freenet is now. If 0%, then we have the proposed solution (which I am now saying doesn't work). Your proposal is to make it somewhere between the two.
Here's what I see is wrong with that: The reason that setting it at 0% was problematic in the first place was that the AAIR would reasonably determine that we requested at least one of K1-K100 if we are shown to have all of K1-K100. That is, if we somehow have "enough" of the Anti-AAIR stuff on our node, then the AAIR would justifiably accuse us of being Anti-AAIR. So if we don't hide any the requested keys, we'll be discovered by the "You have too many naughty keys" attack. If we only cache, say, 50% of the requested keys, then it will take AAIR twice as long to discover us by the "You have too many naughty keys" attack. If we cache only 10%, then 10x as long. If 0%, then that attack will never work.
On the other hand, if we cache 0%, then the "You have tried to HIDE too many naughty keys" attack will work perfectly. If we cache 50%, then it take would take twice as long for this attack to work. Given that the AAIR tries both attacks, the best we can do is to cache 50% of requested keys, which only doubles the time before we are discovered.
Or, keep in mind that some of K1-K100 may be in the regular store anyway, if they passed through the node before the client requested them. They would show as "already in store" on the timing attack, and with them presumably having the same regular-store distribution as K101-K1000, it would be hard to tell.
Yes, the more popular K1-K100 are, the easier it is for us to hide. But shouldn't we consider the worst-case scenario where K1-K100 are not (yet) so popular?
-Martin
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
