[tor-talk] Scaling Tor

[isis]

Mike Fikuart transcribed 4.8K bytes:
> Thanks Virgil.  I wasn’t directly what I was after; however it was an informative read and as with this subject grows the background knowledge that will come to use in the future.  I did get an interesting link from Johan Pouweise on scalability that his students published this year http://arxiv.org/abs/1404.4818, which gives a good overview of the dilemma of decentralisation (FYI).
> 
> A question raised in Tor-Design (section 9) is, "if clients can no longer have a complete picture of the network, how can they perform discovery while preventing attackers from manipulating or exploiting gaps in their knowledge?”.  If the network were to be considered to scale up to significant number of all Internet users, could it be that the Directory Authority(Ies) release (to Directory Caches and clients) a uniform, random sample of relays/nodes from the FULL set of nodes, such that the randomness of the path selection is still maintained.  The random selection could be sampled on a per client basis with enough of a sample as is currently downloaded (6000 relays).  What this means is that each client (or possibly groupings of clients) is getting a different “view” of the network, but there would need to be a scaling down from the full set to the sample set at some point before the client.  Any thoughts on the idea?
>  
> Yours sincerely
>  
> Mike Fikuart 
> 

This is an interesting idea. Variants using random walks through nodes which
only know a random subset of other nodes have been proposed before, e.g.
MorphMix. [0]

However, it should be impossible to verify that a given sequence is, in fact,
random, rather than being a sequence in seeded such a way that it is
predictable, or an encrypted sequence, etc. The biggest concern with improving
Tor's scalability via handing out random samples of nodes from the consensus
would then be that malicious Directories (whether Authorties or simply
mirrors) could collude to hand out predictable subsets of relays to some/all
clients.

Further, even if we could verify that a given sample was truly random, and we
checked the results for some subset of clients, this would not prohibit
certain clients from being lied to. I would argue that the security of the
group of all Tor clients is only as good as the worst case scenario, i.e. any
mechanism which would allow a single client to subjet to targeted attacks is
an attack against all.

Nicholas Hopper and Nikita Borisov are two of the more significant researchers
who explore scaling specifically for Tor and/or onion routing in general.
Perhaps some of the following may help give you an idea of the extant research
in this area:

For a more detailed explanation of why random subsets of nodes cannot be used
to securely pick an unbiased path (more specifically, why we won't use most
DHT algorithms, or the Salsa/Cashmere DHT-overlays), see "Hashing it out in
Public". [1]

For an interesting proposal for using some specific DHT algorithms which claim
to keep maintain the current levels of security while providing better
scalability, see the Torsk paper. [2]

And for a Private Information Retrieval (PIR) based approach (admittedly, I
haven't read it yet, but it's been on my reading list for a while!), which,
like other PIR systems would permit DHT-like queries albeit without the
Directory being able to know what is being looked up, see the PIR-Tor
paper. [3] However, I think I recall from my skimming that the lookups
produced *routes*, not nodes... which is worrisome for another set of reasons.


[0]: M. Rennhard and B. Plattner.
 "Introducing MorphMix: Peer-to-peer based anonymous internet usage with collusion detection."
 In ACM Workshop on Privacy in the Electronic Society (WPES 2002),
 pp. 91–102. ACM, 2002.

[1]: Tran, Andrew, Nicholas Hopper, and Yongdae Kim.
  "Hashing it out in public: common failure modes of DHT-based anonymity schemes."
  In Proceedings of the 8th ACM workshop on Privacy in the electronic society,
  pp. 71-80. ACM, 2009.
  http://www.cs.umn.edu/~hopper/hashing_it_out.pdf

[2]: McLachlan, Jon, Andrew Tran, Nicholas Hopper, and Yongdae Kim.
  "Scalable onion routing with Torsk."
  In Proceedings of the 16th ACM conference on Computer and communications security,
  pp. 590-599. ACM, 2009.
  https://www-users.cs.umn.edu/~hopper/torsk-ccs.pdf

[3]: Mittal, Prateek, Femi G. Olumofin, Carmela Troncoso, Nikita Borisov, and Ian Goldberg.
  "PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval."
  In USENIX Security Symposium. 2011.
  http://cacr.uwaterloo.ca/techreports/2011/cacr2011-05.pdf


-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
GPG: 4096R/A3ADB67A2CDB8B35
Current Keys: https://blog.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1154 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20140818/d96e5f0c/attachment-0001.sig>