- tor-dev - lists.torproject.org

Introduction: CollecTor Improvement Project
by iwakeh 08 Apr '16

08 Apr '16

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hi there! With the first nice spring days in some parts of the Northern Hemisphere the CollecTor Improvement Project started. You probably know that CollecTor [0] is the friendly data-collecting service in the Tor network. It fetches data from various nodes and services in the public Tor network and makes it available to the world. The current project aims at making CollecTor more robust against data loss and improve its source base, development structure, as well as its installation procedure and configuration. More details can be found in the project's wiki page [1]. Further general discussion of the CollecTor Improvement Project will take place in the metrics-team mailing list [2]. So, if you're interested your can subscribe there, too. Cheers, iwakeh [0]: https://collector.torproject.org/ [1]: https://trac.torproject.org/projects/tor/wiki/doc/CollecTor/Improvements [2]: https://lists.torproject.org/cgi-bin/mailman/listinfo/metrics-team -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iF4EAREIAAYFAlcHjlgACgkQsANAxTOj/aYIVQD+KwlYx5FFXy+uiCtF8wCIAfeA SJQ3Fnk4YQC598/jo9QA/RUaZ/Z99Yjey8DsniBZTOJ/lTNlCOcKpXyXLIaOezOB =CSaG -----END PGP SIGNATURE-----

2 1

Research on Breaking reCAPTCHA
by bancfc＠openmailbox.org 08 Apr '16

08 Apr '16

While I don't understand why researchers are doing free labor for Google its still an interesting read on the innards of reCAPTCHAs and its weaknesses. Some tests were done with Tor: http://www.cs.columbia.edu/~polakis/papers/sivakorn_eurosp16.pdf

1 0

Re: [tor-dev] Update on 259
by Ola Bini 08 Apr '16

08 Apr '16

Hey, > > - OrPort vs DirPort > > ORPort is used for regular circuits, while DirPort is used when getting directory information. We need to interpret reachable stuff > > differently depending on the purpose. > > > > I'm not actually sure what the comment means here. This was more for our own benefit. The OrPort vs DirPort distinction has been a bit complicated so far. The comment basically means, when we are looking up directory information, we should use the DirPort to decide reachability and so on instead, correct? > Ensuring a min percentage of dirguards in our sampled set could work. Then, > when we need a directory guard, we could filter the sampled set and only > examine guards that can do directory requests. Yeah, we talked about this yesterday and our current thinking is to have a sampled set that contains every kind of thing, and then we dynamically filter it based on config and so on during START. > Hm, are you talking about the guardlists here? What's the question? > > BTW, if we have the ability to do "ensure a min percentage of X in our sampled > set", couldn't we just ensure a min percentage of dystopic guards in our > sampled set? And forget about the two separate guardlists? > > In this case we can have the percentage value be the actual portion of the > network that is dystopic guards. So if 20% of the total guard bandwidth is > dystopic, we could ensure that at least 20% of our sampled set is > dystopic". Well, the problem is really that the idea of dystopic doesn't necessarily make sense, since it's so dependent on the current network position of the client. Our current thinking is to do away with that concept as well. =) > > - DYSTOPIC - is there value in trying 80 and 443? > > Probably not. > > > > What does "trying" mean in this case? Falling back to guards with 80 and 443. > Restart pending guard selection algorithms on a SIGHUP? Plausible, but I don't > know how hard it would be to implement this. Well, the alternative is to just finish the running guard selections with the old settings, but use the new settings for new algorithm instances. > That's not very nice because the USED_GUARDS set that was created when > ClientsUseIPv6 or FascistFirewall were on will have reduced diversity. Then > even if we switch off those options, we are still stuck with reduced diversity. > > I'm not sure what's the right way to do this here! > > We could imagine having multiple USED_GUARDS sets, where we make a new set for > each possible filter. This might be worth considering, but I imagine there will > be technical difficulties. e.g. when a guard goes down, you need to update its > state in all the USED_GUARDS sets that it's in. Also, a person who toggles the > FascistFirewall option frequently, will end up using two different sets of > guards all the time which is suboptimal. Well, one thing you could do is hash the settings (and maybe also reachable ports) and use that as a key to differentiate the different USED_GUARDS. That would solve the problem, but might lead to a single client using lots of different guards in different locations. Might that be OK? > > - Can we make the lists smaller? > > Probably. Maybe a sampled set of 30 guards? Or 1.5%? > > > > Plausible. However, if we take the filtering approach but use a small sampled > guards list, it could happen that the list is not able to satisfy some of our > filtering restrictions. > > e.g. maybe in our 30 guards there are no IPv6 guards at all, and the user just > turned on ClientUseIPv6. What to do now? > > This is important to understand, because currently there is no mechanism to add > stuff to the sampled guards list if a restriction cannot be satisfied. So what > will Tor do, if a user enables ClientsUseIPv6 _and_ FascistFirewall but there > are no IPv6+80/443 guards in our sampled guards list? Yeah, we talked about that yesterday. Our suggestion is to do something like this: - if the filtered/reduced sample-set contains less than X (5?) guards, expand SAMPLED guards using the regular process. - If SAMPLE guards reach SAMPLED_MAX (50?) size, we fail closed with an error saying something like "your current network settings make it impossible for us to safely choose an entry guard. If you really need to connect under these circumstances, consider explicitly setting the EntryGuards configuration option" > I think it asks "What happens when guards in our sampled set drop out of the > consensus and get marked as bad?" (see bad_since in entrynodes.c) . > > This is also a great question. Especially when combined with the planned > "ensure a min percentage of X in our sampled set" logic. > > Like, what happens if suddenly most of our sampled IPv6 guards drop out of the > consensus when we have ClientsUseIPv6 on? Should we replace them? And if yes, > don't we need to replace them with other IPv6 guards to maintain the minimum > percentage? Well, I think if we replace, we should just replace randomly just like we always expand the sampled set. If most ipv6 guards drop out, we will have fewer ipv6 guards in our sampled set, but that also reflects the Tor network. I suspect a plausible thing to do is to wait a few consensus rounds with expanding the sampled set to replace "bad" guards - they might come back, and under most circumstances we shouldn't need to use the sampled set anyway. > The current proposal says the following about SAMPLED_UTOPIC_GUARDS: > > It will be filled in by the algorithm if it's empty, or if it contains > less than SAMPLE_SET_THRESHOLD guards after winnowing out older guards. > > which I think is a good suggestion. However, what should we do if we end up > going with the "ensure minimum percentage" logic? Yeah, my suggestion is not have minimum percentage of X type guards - instead just fill it randomly, and use the expanding process if we can't find enough guards for a specific purpose. > > - EntryNodes > > If this is set, never use the algorithm for regular circuits - we should still use it for directory server connections though. > > If this is set we should not use our algorithm, but we should instead pick one > of the guards in the EntryNodes list. This is for people who want to hardcode > their guard. It's used a lot by people currently. Yeah. Is the guard picked randomly from this list, or using something more complicated? > > - UseEntryGuardsAsDirGuards > > I don't understand exactly what this settings does. > > I'm not sure either. I'd just let it keep the exact same semantics it currently has. Yeah, except we don't exactly understand what does semantics are, and if we need to change something in our code to match it. =) Thanks for all the feedback! Hopefully we're getting close to the final iteration of this spec. =) Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined.

5 10

Tor debugging
by SMTP Test 07 Apr '16

07 Apr '16

Hi all, I am working on a project that needs to do some modifications on the source code of Tor, to add functionalities to Tor relay. To debug I used chutney to setup Tor network locally, and checked the logs of the relay. But it is still painful and slow: I need to restart the script, and wait the network to be up every time I make changes. My question is: is there any fast way to test/debug the functionalities of Tor relay? Thanks!

2 1

extension for chrome and mozilla
by Mukul Gupta 07 Apr '16

07 Apr '16

hello tor-dev I want to make extension which can control network in my browser. so that i can connect to my some other computer which has VPN . And after that the data is exchanged between VPN server and the user. And the intermediate nodes won't be able to identify whats going on. This is my project proposal. Can you help me in this how to initiate this project.

1 0

Re: [tor-dev] Update on 259
by tdruiva＠riseup.net 06 Apr '16

06 Apr '16

Adding tor-dev. On 04/06/2016 08:53 AM, Tania Silva wrote: > Hey, > >>>>>> Yeah, we talked about that yesterday. Our suggestion is to do >>>>>> something like this: >>>>>> - if the filtered/reduced sample-set contains less than X (5?) guards, >>>>>> expand SAMPLED guards using the regular process. >>>>>> - If SAMPLE guards reach SAMPLED_MAX (50?) size, we fail closed with >>>>>> an error saying something like "your current network settings make it >>>>>> impossible for us to safely choose an entry guard. If you really need >>>>>> to connect under these circumstances, consider explicitly setting the >>>>>> EntryGuards configuration option" >>>> >>>> Oh, wow, I don't think failing closed is a good idea. >>>> It means users that move around a lot (and clients which have a longer state history) could fail at some arbitrary time. >>>> Why not simply continue to add guards that satisfy the restrictions? >> Well, users that move around a lot will only have an expanded sampled >> set if they move between several different networks that have severe >> restrictions - but mutually exclusive such restrictions. And we would >> only ever hit this fail closed if we can't find anything in the >> sampled set that matches the current needed restrictions. If we keep >> adding guards, the idea of the sampled set as a measure to minimize >> exposure to too many guards fly out the window. >> >> The problem really comes down to this - if you have a network that is >> actively firewalling every guard that is not under their control, if >> we keep expanding we will sooner or later be forced to use a guard >> under adversary control. By failing closed, we can avoid that >> eventuality. > > We thought in to have a minimum size for this set after been filtered [1]. > > ``` > MINIMUM_FILTERED_SAMPLE_SIZE > The minimum size of the sampled set after filtering out nodes based on > client configuration (FILTERED_SAMPLED). Proposed value is ???. > ``` > > In order to expose less guards when we are expanding sample set, we > thought in to have a maximum size before to fail. > What do you think if this is a configurable value by user? (we can have > as default if not provided) > > ``` > MAXIMUM_SAMPLE_SIZE_THRESHOLD > In order to guarantee a minimum size of guards after filtering, we > expand SAMPLED_GUARDS until a limit. This fraction of GUARDS will be > used as an upper bound when expanding SAMPLED_GUARDS. Proposed value is > 0.03. > ``` > > 1 - > https://github.com/twstrike/torspec/blob/review/proposals/259-guard-selecti… >

1 0

Adding one more (optional) step to Trac's ticket work-flow
by Isabela 06 Apr '16

06 Apr '16

Hello tor-dev! tl;dr; we want to add one more step to Trac ticket work-flow called 'merge_ready' - if you don't want to use it you don't need to During Tor's Dev Meeting in Valencia, the Network Team discussed a code review process[1] for the team and we concluded that for us a two stage review process would make things much better for the team. In order to organize that on our ticket work-flow on Trac, we decided to add the step 'merge_ready'[2] that would come after either 'needs_review' or 'needs_revision' steps. For our team, what that will mean is that we have reviewed the code and believe is ready for Nick to do a second review and merge. The first review will remove load from Nick and we want to eventually have more folks helping Nick on the second review as well. But this change alone will be already a big step. What does that means for someone working on a ticket that is not part of Core Tor development flow? Well, if you don't want to use it in your team or your project flow, you can just ignore it and keep using Trac as normal. We are sending this note to make sure folks knows about it before it happens and of course, to hear any concerns or feedback. Cheers, Isabela [1] https://trac.torproject.org/projects/tor/wiki/org/meetings/2016WinterDevMee… [2] https://storm.torproject.org/shared/pt9FtdJNG_gB_afqayg9dXTJwdDFncgU0HVXJEq… -- PM at TorProject.org gpg fingerprint = 8F2A F9B6 D4A1 4D03 FDF1 B298 3224 4994 1506 4C7B @isa

3 2

Re: [tor-dev] [TOR+QUIC] Progress Update
by Xiaofan Li 05 Apr '16

05 Apr '16

Tim: Thank you for the detailed email. I've also included tor-dev on CC. Anyone is welcome to comment. To reply to your concerns: 1. All the documentation we have is basically in email correspondences as well as in the generic simple-quic codebase here: https://github.com/kku1993/simple-quic. The quicksock_t interface is in the above repo under /quicsock. There isn't much documentation because: a) our designs are still under test and large portions are not stable yet, b) we haven't gotten much time to properly document designs and changes to the Tor codebase. But the emails should be somewhat clear on some key design aspects. 2. About providing an alternative for QUIC connections: - Great idea about keeping both type of sockets in connection. I think this will give us a cleaner design. - Exit relay will speak normal TCP. This is part of our design from the start but we haven't gotten around to look into the exit connection code. - Connections to the directory authorities should be normal TCP. - While compatibility with the current system is very important, our main goal is to compare performances of the OR connections with TCP vs. QUIC. So we haven't spent much effort making things beautiful yet. After all, it is possible that QUIC is a bad idea for Tor.. 3. I was looking at chutney the other day but I couldn't find much documentation on how it works. I will play with it more and then I might ask for more help. If anyone else is expert on the SSL part of the codebase, please provide some insights about the security aspect of the design, specifically: "About SSL, we want to adopt the design where QUIC handles SSL by not using the ssl_buffer in TOR code. Any concerns at all?" (not using read_to_buf_tls() and other similar ssl functions) Another concern is the assumption on TOR_SOCKET_T in the Tor codebase. In particular, there are many call sites of fcntl, getsockname, setsockopt etc made directly on this object, assuming that it is a UNIX socket. For compatibility, after replacing UNIX socket with quicsock_t, we would use "qs_get_fd" for all those low-level calls. Note that quicsock_t holds a UDP socket internally. Without the testing system ready, we don't know the effect of these calls on a UDP socket instead of the normal TCP socket. Any other feedback also welcomed! Li. On Mon, Apr 4, 2016 at 10:43 PM, Tim Wilson-Brown - teor <teor2345(a)gmail.com > wrote: > Hi Li, > > If you're ok with emailing the tor-dev mailing list, you will likely get > better answers to some of these questions there. > All of these questions could benefit from the wider Tor developer > community. > When I know I can't fully answer a question, I'll say so below. > > Please feel free to forward my response to tor-dev. > > > On 5 Apr 2016, at 05:38, Xiaofan Li <xli2(a)andrew.cmu.edu> wrote: > > > > Hi Tim: > > I think maybe now is a good time to bother you again. In the following > email, we outlined some current progress on the TOR+QUIC project. This > weekend we booted up our first TOR node running QUIC (then of course it > failed to contact the directory authorities and hanged). We hope to move on > to testing our design while clean up some uncertain "loose-ends" in the > integration process, with your help. In particular: > > • We decided to implement a QUIC interface similar to the UNIX > socket interface. We have replaced TOR_SOCKET_T with our quicksock_t. Any > issues about this design? > > I'm not particularly familiar with this part of the tor codebase, you > might get better answers from tor-dev. > Also, without knowing the definition of quicksock_t, I can't say much more. > > Overall, I think your design has two major flaws: > * you need to provide QUIC as an alternative, not a replacement, because > Exits need to speak TCP, and so might Clients and Onion Services > * you've chosen to modify all tor sockets to speak QUIC, rather than > replacing SSL over TCP with QUIC > > Why not put your quicksock_t in connection_t (in or.h), and then choose > whether to use QUIC or a plain socket based on whether you're using an OR > connection (or_connection_t) or not? > You'd also need some logic in OR listener connections > (listener_connection_t) that creates a QUIC or plain socket from the > listener depending on whether it's an OR listener or not. > > See "Kinds of Connections" in > https://gitweb.torproject.org/user/nickm/torguts.git/tree/02-dataflow.md > And > https://gitweb.torproject.org/user/nickm/torguts.git/plain/diagrams/02/02-c… > And maybe > https://gitweb.torproject.org/user/nickm/torguts.git/plain/diagrams/02/02-d… > > Here are my concerns in detail: > > I think you need a design that enables QUIC over UDP as an alternative to > SSL over TCP sockets, like the way Tor's IPv6 support provides IPv6 as an > alternative to IPv4. (Of course, IPv6 is not the same level of the protocol > stack as QUIC.) > > If you completely replace TCP with QUIC, then Exits will also speak QUIC > to sites on the wider Internet. (As you describe below.) > Also, relays with speak QUIC to the directory authorities when downloading > descriptors, rather than using HTTP over TCP. > And you'll force the browser and Tor controllers to speak QUIC to the Tor > Client. > And Tor Onion Services to speak QUIC to the backend servers they connect > to. > (I think some parts of Tor's DNS might also be affected, but it depends on > the level of abstraction they're at.) > > This is unlikely to be what you want. And there could also be other > impacts on connections that should stay TCP. > > > • About SSL, we want to adopt the design where QUIC handles SSL by > not using the ssl_buffer in TOR code. Any concerns at all? > > You'll need to ask tor-dev for this one, I'm not familiar with this code > at all. > > > • During integration, I found many instances where TOR assumes > TOR_SOCKET_T is INT. Why can TOR make this assumption? Is the type > TOR_SOCKET_T only created to accommodate windows dev? > > I think the assumption was already there when Windows support was added. > It would appear that tor_socket_t exists for Windows compatibility. > > From the definition of tor_socket_t in compat.h: > > /* XXX Actually, this should arguably be SOCKET; we use intptr_t here so > that > * any inadvertent checks for the socket being <= 0 or > 0 will probably > * still work. */ > > > • For testing, what's the most correct (and easy enough to do in a > few weeks) way to simulate the TOR network? Right now I'm thinking using > the microdesc cache to avoid contacting any directory authorities. I will > create a cluster of about 5 nodes in server mode, all of which only know > the other nodes running QUIC. Do you think this will work? > > Tor has a TestingTorNetwork config option, which modifies a significant > number of settings to enable local testing. > If you define your own authorities, they can provide a consensus to your > clients. > This could be much more reliable than using the microdesc cache. > (Please read the TestingTorNetwork entry in the tor manual for more > details.) > > You may find this easiest to set up using chutney, which is how we test a > full tor network on a local machine. > Chutney will configure authorities, relays, and clients for you, then > launch the network. > The easiest way to set it up is to: > 1. Clone https://gitweb.torproject.org/chutney.git > 2. Clone your tor repository next to the chutney clone > 3. Run tor's ./configure > 4. Run tor's make test-network > > If this doesn't work, you might find it easiest to start with the chutney > "basic" template: > 5. Run src/test/test-network.sh --flavor basic > > If you start by running chutney on tor master, you'll get an idea of how > it works. > Then you can see what breaks when you try it with your QUIC-based tor. > > > • Anything else bad about the implementation? > > I haven't seen the implementation. > Have you sent me a link, or did you want me to give advice based on the > design issues you describe in the email you forwarded? > > As far as I can see, your major issues are getting a Tor test network > running (I strongly recommend chutney), and dealing with Exits needing > QUIC, TCP, and DNS/UDP. If you want interoperability with non-QUIC browsers > and servers, you'll need to work out similar issues with Clients and Onion > Services as well. > > Tim > > > Thank you! > > Li. > > > > > > > > > > ---------- Forwarded message ---------- > > From: Xiaofan Li <xli2(a)andrew.cmu.edu> > > Date: Mon, Apr 4, 2016 at 3:20 PM > > Subject: [TOR+QUIC] Progress Update > > To: Mashael AlSabah <malsabah(a)gmail.com> > > Cc: Srinivasan Seshan <srini(a)cs.cmu.edu>, Kevin Ku <kku(a)andrew.cmu.edu> > > > > > > Hi all, > > Before the project meetings, we want to debrief you on the recent > progress of the project so that our discussions can be more efficient. In > general, this week we made reasonable progress and now we are in the > debugging/testing phase. Particularly, we: > > • Designed and implemented the interaction between QUIC and the > libevent system inside TOR. > > • Integrating QUIC with TOR causes mismatches of > abstractions (see below). We worked hard to come up with a clean design > while not blocking development. > > • We have to pass the event_base to QUIC for it to > register an alarm callback that is required by QUIC. > > • libevent -> TOR-register callbacks -> QUIC interface -> > data -> QUIC processing -> only application data gets passed up to TOR > > • Minimum code change in TOR: we still use all the > callback mechanisms (timer + signal + async) in TOR but we modify those > callbacks. > > • Modified code paths inside TOR to accommodate QUIC. > > • We turned off Tor's SSL code path in the read/write > callbacks. We should probably also turn off the handshake inside TOR as > well. > > • TOR has a lot of implementation shortcut that make > assumptions about the TOR_SOCKET_T type. We cleaned this up. > > • Some remaining issues about direct low-level calls on > the socket (e.g. fcntl or setsockopt). The effects of these issues are > unclear right now. > > • Small hacks to make sure things ran. > > • We hardcoded the certificate and private key used by > QUIC. > > • QUIC is compiled into a shared library and it seems to > be working well. (Don't know about the SSL things right now.) > > • Tweaked the our QUIC interface to allow generality and smooth > integration with TOR. > > Some challenging problems we encountered: > > • Mismatched abstractions: This is obviously the most challenging > implementation problem. We hope our experience can perhaps suggestion some > designs for the ongoing QUIC interface design: > > • SSL/TLS: Fundamentally, QUIC is providing TLS security > on a lower level than what TOR is expecting and this is causing problems. > We should take away the TOR's SSL/TLS code to achieve the benefits of QUIC. > > • Other Implementations: Compared to the UNIX socket type, > our QUIC "socket" provides different interface and functionalities and it > is possible that there are assumptions made by TOR about the socket > interface. For example, the fact that QUIC requires an alarm system is > destroying the abstraction separation between TOR and QUIC. The alarms are > used for path discovery, handshakes, retransmission etc. We believe that > those should be internal to the lower level transport and thus hidden by > QUIC. We are unable to hide them right now because QUIC does not have the > necessary OS support to do so. The performance implication is unclear. > > • Testing: We are in the phase of testing. We are investigating > various testing methods. The key problem is that we have to basically scrap > all the systems that TOR already provides because we speak a different > protocol. Particularly, we need to: > > • Replace or disable the directory authorities. Disabling > is easier because we can hardcode the bootstrapping process and make the OP > contact our QUIC node, but this way we might not have the most accurate > (and comparable) data on the bootstrapping process. > > • We need to set up some number of circuits and > differentiate normal nodes from exit nodes. Right now the exit nodes will > also speak QUIC which is not good. > > • We will probably need 3-5 machines at least. (Some > Amazon AWS credit maybe??) > > Right now, our simple_quic interface is relatively stable and it is > located at: https://github.com/kku1993/simple-quic . It offers a purely > generic interface that does not specifically tie to TOR. Feel free to take > a look! We are thinking about giving it to the QUIC people at Google after > we polish and document it better. > > Kevin, feel free to add anything. > > > > Looking forward to the meetings! > > Li. > >

2 1

Re: [tor-dev] Yawning's CFC, web caching, and PETs
by leep＠sigaint.org 04 Apr '16

04 Apr '16

Check out CENO. Right now it runs Freenet as a back-end for distributed caching but it can gain Tahoe-LAFS support. https://censorship.no/

1 0

Proposal 259: New Guard Selection Behaviour
by George Kadianakis 04 Apr '16

04 Apr '16

Hello, proposal 259 has evolved plenty since the last time it was posted on [tor-dev]. All the technical discussion can be found in various threads, and here is a thread about the proposal itself as it is now. The current proposal is pretty much done, and it's currently being implemented for testing. We imagine that during testing we might have to slightly alter the algorithm and its parameters to improve performance and security. Here are some behaviors that are still unspecified in the current proposal based on our discussion yesterday: - What exactly should be done if a circuit has restrictred requirements? (e.g. it needs a Fast/Stable guard, but our top guard is not Fast/Stable) - How exactly should directory guards work? Should the guard lists be initialized only with directory guards? Or should we just initialize our guard lists from the set of all guards, and just skip non-V2Dir guards whenever we need to make a directory circuit? FWIW, there are currently 2076 guards, out of which 1659 support V2Dir (i.e. they are directory guards). - How should the algorithm work wrt ReachableAddresses? I wonder how the current algorithm work wrt ReachableAddresses and if it's behavior is good. --- Filename: 259-guard-selection.txt Title: New Guard Selection Behaviour Author: Isis Lovecruft, George Kadianakis, [Ola Bini] Created: 2015-10-28 Status: Draft §1. Overview Tor uses entry guards to prevent an attacker who controls some fraction of the network from observing a fraction of every user's traffic. If users chose their entries and exits uniformly at random from the list of servers every time they build a circuit, then an adversary who had (k/N) of the network would deanonymize F=(k/N)^2 of all circuits... and after a given user had built C circuits, the attacker would see them at least once with probability 1-(1-F)^C. With large C, the attacker would get a sample of every user's traffic with probability 1. To prevent this from happening, Tor clients choose a small number of guard nodes (currently 3). These guard nodes are the only nodes that the client will connect to directly. If they are not compromised, the user's paths are not compromised. But attacks remain. Consider an attacker who can run a firewall between a target user and the Tor network, and make many of the guards they don't control appear to be unreachable. Or consider an attacker who can identify a user's guards, and mount denial-of-service attacks on them until the user picks a guard that the attacker controls. In the presence of these attacks, we can't continue to connect to the Tor network unconditionally. Doing so would eventually result in the user choosing a hostile node as their guard, and losing anonymity. This proposal outlines a new entry guard selection algorithm, which addresses the following concerns: - Heuristics and algorithms for determining how and which guard(s) is(/are) chosen should be kept as simple and easy to understand as possible. - Clients in censored regions or who are behind a fascist firewall who connect to the Tor network should not experience any significant disadvantage in terms of reachability or usability. - Tor should make a best attempt at discovering the most appropriate behaviour, with as little user input and configuration as possible. §2. Design Alice, an OP attempting to connect to the Tor network, should undertake the following steps to determine information about the local network and to select (some) appropriate entry guards. In the following scenario, it is assumed that Alice has already obtained a recent, valid, and verifiable consensus document. The algorithm is divided into four components such that the full algorithm is implemented by first invoking START, then repeatedly calling NEXT while adviced it SHOULD_CONTINUE and finally calling END. For an example usage see §A. Appendix. Several components of NEXT can be invoked asynchronously. SHOULD_CONTINUE is used for the algorithm to be able to tell the caller whether we consider the work done or not - this can be used to retry primary guards when we finally are able to connect to a guard after a long network outage, for example. This algorithm keeps track of the unreachability status for guards in state global to the system, so that repeated runs will not have to rediscover unreachability over and over again. However, this state does not need to be persisted permanently - it is purely an optimization. The algorithm expects several arguments to guide its behavior. These will be defined in §2.1. The goal of this algorithm is to strongly prefer connecting to the same guards we have connected to before, while also trying to detect conditions such as a network outage or a network environment that blocks most ports. The way it does this is by keeping track of how many guards we have exposed ourselves to, and if we have connected to too many we will fall back to only retrying the ones we have already tried. The algorithm also decides on sample set that should be persisted - in order to minimize the risk of an attacker forcing enumeration of the whole network by triggering rebuilding of circuits. §2.1. The START algorithm In order to start choosing an entry guard, use the START algorithm. This takes four arguments that can be used to fine tune the workings: USED_GUARDS This is a list that contains all the guards that have been used before by this client. We will prioritize using guards from this list in order to minimize our exposure. The list is expected to be sorted based on priority, where the first entry will have the highest priority. SAMPLED_UTOPIC_GUARDS This is a set that contains all guards that should be considered for connection under utopic conditions. This set should be persisted between runs. It will be filled in by the algorithm if it's empty, or if it contains less than SAMPLE_SET_THRESHOLD guards after winnowing out older guards. It should be filled by using NEXT_BY_BANDWIDTH with UTOPIC_GUARDS as an argument. SAMPLED_DYSTOPIC_GUARDS This is a set that contains all guards that should be considered for connection under dystopic conditions. This set should be persisted between runs. It will be filled in by the algorithm if it's empty, or if it contains less than SAMPLE_SET_THRESHOLD guards after winnowing out older guards. It should be filled by using NEXT_BY_BANDWIDTH with DYSTOPIC_GUARDS as an argument. EXCLUDE_NODES A set of nodes that we should not consider using as a guard. N_PRIMARY_GUARDS The number of guards we should consider our primary guards. These guards will be retried more frequently and will take precedence in most situations. By default the primary guards will be the first N_PRIMARY_GUARDS guards from USED_GUARDS. DIR If this argument is set, we should only consider guards that can be directory guards. If not set, we will consider all guards. The primary work of START is to initialize the state machine depicted in §2.2. The initial state of the machine is defined by: GUARDS This is a set of all guards from the consensus, without EXCLUDE_NODES and potentially filtered if DIR is set. UTOPIC_GUARDS This is a set of all guards to use under utopic conditions. It will primarily be used to fill in SAMPLED_UTOPIC_GUARDS. This set will be initialized to be the same as GUARDS. DYSTOPIC_GUARDS This is a set of all guards to use under dystopic conditions (usually when we are subject to a firewall that restricts the ports we can connect to). It will primarily be used to fill in SAMPLED_DYSTOPIC_GUARDS. This set will be initialized to be the subset of GUARDS that listen to ports that are allowed by dystopic conditions. REMAINING_UTOPIC_GUARDS This is a running set of the utopic guards we have not yet tried to connect to. It should be initialized to be SAMPLED_UTOPIC_GUARDS without USED_GUARDS. REMAINING_DYSTOPIC_GUARDS This is a running set of the dystopic guards we have not yet tried to connect to. It should be initialized to be SAMPLED_DYSTOPIC_GUARDS without USED_GUARDS. STATE A variable that keeps track of which state in the state machine we are currently in. It should be initialized to STATE_PRIMARY_GUARDS. PRIMARY_GUARDS This list keeps track of our primary guards. These are guards that we will prioritize when trying to connect, and will also retry more often in case of failure with other guards. It should be initialized by calling algorithm NEXT_PRIMARY_GUARD repeatedly until PRIMARY_GUARDS contains N_PRIMARY_GUARDS elements. §2.2. The NEXT algorithm The NEXT algorithm is composed of several different possibly flows. The first one is a simple state machine that can transfer between four different states. Every time NEXT is invoked, it will resume at the state where it left off previously. In the course of selecting an entry guard, a new consensus can arrive. When that happens we need to update the data structures used, but nothing else should change. Before jumping in to the state machine, we should first check if it was at least PRIMARY_GUARDS_RETRY_INTERVAL minutes since we tried any of the PRIMARY_GUARDS. If this is the case, and we are not in STATE_PRIMARY_GUARDS, we should save the previous state and set the state to STATE_PRIMARY_GUARDS. §2.2.1. The STATE_PRIMARY_GUARDS state Return each entry in PRIMARY_GUARDS in turn. For each entry, if it was not possible to connect to it and mark the entry as unreachable [XXX defining "was not possible to connect" as "entry is not live" according to current definition of "live entry guard" in tor source code, seems to improve success rate on the flaky network scenario. See: https://github.com/twstrike/tor_guardsim/issues/1#issuecomment-187374942] If all entries have been tried, restore the previous state and go there. If there is no previous state, transition to STATE_TRY_UTOPIC. §2.2.2. The STATE_TRY_UTOPIC state Return each entry in USED_GUARDS that is not in PRIMARY_GUARDS in turn. For each entry, if it was not possible to connect to it and mark the entry as unreachable. Return each entry from REMAINING_UTOPIC_GUARDS using NEXT_BY_BANDWIDTH. For each entry, if it was not possible to connect to it, remove the entry from REMAINING_UTOPIC_GUARDS and mark it as unreachable. If no entries remain in REMAINING_UTOPIC_GUARDS, transition to STATE_TRY_DYSTOPIC. §2.2.3. The STATE_TRY_DYSTOPIC state Return each entry from REMAINING_DYSTOPIC_GUARDS using NEXT_BY_BANDWIDTH. For each entry, if it was not possible to connect to it, remove the entry from REMAINING_DYSTOPIC_GUARDS and mark it as unreachable. If no entries remain in REMAINING_DYSTOPIC_GUARDS, transition to STATE_PRIMARY_GUARDS. §2.2.5. ON_NEW_CONSENSUS First, ensure that all guard profiles are updated with information about whether they were in the newest consensus or not. If a guard is not included in the newest consensus, the guard is considered bad. If any PRIMARY_GUARDS have become bad, remove the guard from PRIMARY_GUARDS. Then ensure that PRIMARY_GUARDS contain N_PRIMARY_GUARDS entries by repeatedly calling NEXT_PRIMARY_GUARD. If any guards in USED_GUARDS have switched from being bad to being non-bad, add it back in the place it should have been in PRIMARY_GUARDS if it had been non-bad when populating PRIMARY_GUARDS. If this results in PRIMARY_GUARDS being larger than N_PRIMARY_GUARDS, truncate the list to be N_PRIMARY_GUARDS entries long. §2.3. The SHOULD_CONTINUE algorithm This algorithm takes as an argument a boolean indicating whether the circuit was successfully built or not. After the caller have tried to build a circuit with a returned guard, they should invoke SHOULD_CONTINUE to understand if the algorithm is finished or not. SHOULD_CONTINUE will always return true if the circuit failed. If the circuit succeeded, SHOULD_CONTINUE will always return false, unless the guard that succeeded was the first guard to succeed after INTERNET_LIKELY_DOWN_INTERVAL minutes - in that case it will set the state to STATE_PRIMARY_GUARDS and return true. §2.4. The END algorithm The goal of this algorithm is simply to make sure that we keep track of successful connections made. This algorithm should be invoked with the guard that was used to correctly set up a circuit. Once invoked, this algorithm will mark the guard as used, and make sure it is in USED_GUARDS, by adding it at the end if it was not there. §2.5. Helper algorithms These algorithms are used in the above algorithms, but have been separated out here in order to make the flow clearer. NEXT_PRIMARY_GUARD - Return the first entry from USED_GUARDS that is not in PRIMARY_GUARDS and that is in the most recent consensus. - If USED_GUARDS is empty, use NEXT_BY_BANDWIDTH with REMAINING_UTOPIC_GUARDS as the argument. NEXT_BY_BANDWIDTH - Takes G as an argument, which should be a set of guards to choose from. - Return a randomly select element from G, weighted by bandwidth. §3. Consensus Parameters, & Configurable Variables This proposal introduces several new parameters that ideally should be set in the consensus but that should also be possible to set or override in the client configuration file. Some of these have proposed values, but for others more simulation and trial needs to happen. PRIMARY_GUARDS_RETRY_INTERVAL In order to make it more likely we connect to a primary guard, we would like to retry the primary guards more often than other types of guards. This parameter controls how many minutes should pass before we consider retrying primary guards again. The proposed value is 3. SAMPLE_SET_THRESHOLD In order to allow us to recognize dystopic situations or a completely unreachable network, we would like to avoid connecting to too many guards before switching modes. We also want to avoid exposing ourselves to too many nodes in a potentially hostile situation. This parameter, expressed as a fraction, determines the number of guards we should keep as the sampled set of the only guards we will consider connecting to. It will be used as a fraction for both the utopic and the dystopic sampled set. If we assume there are 1900 utopic guards and of them there are 500 dystopic guards, a setting of 0.02 means we will have a sample set of 38 utopic guards and 10 dystopic guards. This limits our total exposure. Proposed value is 0.02. INTERNET_LIKELY_DOWN_INTERVAL The number of minutes since we started trying to find an entry guard before we should consider the network down and consider retrying primary guards before using a functioning guard found. Proposed value 5. §4. Security properties and behavior under various conditions Under normal conditions, this algorithm will allow us to quickly connect and use guards we have used before with high likelihood of working. Assuming the first primary guard is reachable and in the consensus, this algorithm will deterministically always return that guard. Under dystopic conditions (when a firewall is in place that blocks all ports except for potentially port 80 and 443), this algorithm will try to connect to 2% of all guards before switching modes to try dystopic guards. Currently, that means trying to connect to circa 40 guards before getting a successful connection. If we assume a connection try will take maximum 10 seconds, that means it will take up to 6 minutes to get a working connection. When the network is completely down, we will try to connect to 2% of all guards plus 2% of all dystopic guards before realizing we are down. This means circa 50 guards tried assuming there are 1900 guards in the network. In terms of exposure, we will connect to a maximum of 2% of all guards plus 2% of all dystopic guards, or 3% of all guards, whichever is lower. If N is the number of guards, and k is the number of guards an attacker controls, that means an attacker would have a probability of 1-(1-(k/N)^2)^(N * 0.03) to have one of their guards selected before we fall back. In real terms, this means an attacker would need to control over 10% of all guards in order to have a larger than 50% chance of controlling a guard for any given client. In addition, since the sampled set changes slowly (the suggestion here is that guards in it expire every month) it is not possible for an attacker to force a connection to an entry guard that isn't already in the users sampled set. §A. Appendix: An example usage In order to clarify how this algorithm is supposed to be used, this pseudo code illustrates the building of a circuit: OPEN_CIRCUIT: context = ALGO_CHOOSE_ENTRY_GUARD_START(used_guards, sampled_utopic_guards=[], sampled_dystopic_guards=[], exclude_nodes=[], n_primary_guards=3, dir=false, guards_in_consensus) while True: entryGuard = ALGO_CHOOSE_ENTRY_GUARD_NEXT(context) circuit = composeCircuitAndConnect(entryGuard) if not SHOULD_CONTINUE(isSuccessful(circuit)): ALGO_CHOOSE_ENTRY_GUARD_END(context, entryGuard) return circuit -*- coding: utf-8 -*-

5 12