- tor-dev - lists.torproject.org

Existing Tor Guard Selection Algorithm
by Chelsea Komlo 11 Feb '16

11 Feb '16

Hi George, Thanks for your help with this! We wrote up our high-level understanding of the current Tor guard selection algorithm here: https://gist.github.com/chelseakomlo/2acbe15314b5a809c6f4 This has more than our python simulation, but less than the actual Tor implementation. For example, it is missing conditions like prioritization by uptime, capacity, etc. https://github.com/twstrike/tor_guardsim/blob/develop/lib/original_client.py If you wouldn't mind taking a look at this and letting us know anything that is missing/should change, that would be really helpful. Thanks! Chelsea

2 1

Re: [tor-dev] Entry guards, primary guards, dir guards
by George Kadianakis 10 Feb '16

10 Feb '16

Ola Bini <obini(a)thoughtworks.com> writes: > Hi, > >> So maybe the simple answer here is that if prop247 is enabled (this could be a >> NumGuards=N argument to our algorithm), instead of always returning the first >> reachable guard, we instead build a list of the first N reachable guards, and >> randomly choose one of them. Could this work? (see #12466 for a weird behavior >> that will make us skip bugs if NumEntryGuards != 1) > Ah, I understand. We could definitely do that. I think the easiest way > is to just have a parameter to the existing algorithm with > ExcludeNodes. We can then repeat it N times sending in the previous > nodes chosen as ExcludeNodes. This will generate the N reachable first > guards. Then, we can just choose randomly from them. > > Does that sound reasonable? > Yes, that sounds like a reasonable way to achieve this. Maybe N_PRIMARY_GUARDS should also scale up in that case, so that N_PRIMARY_GUARDS >= N.

2 1

Re: [tor-dev] Detailed algorithm
by George Kadianakis 09 Feb '16

09 Feb '16

Ola Bini <obini(a)thoughtworks.com> writes: > OK, with your feedback and thinking a bit more about it, here is a > revision of the algorithm from yesterday. I think we are starting to > get close so we will rip out the original simulation code and > implement something that matches this now. Hopefully, the changes will > be smaller. > > - Start of algorithm (arguments: USED_GUARDS, EXCLUDE_NODES) > - If selecting directory guards, GUARDS is all guards from the consensus with the V2Flag, > otherwise GUARDS is all guards from the consensus > - Set UTOPIC_GUARDS to be all guards to use under utopic conditions from GUARDS > - Set DYSTOPIC_GUARDS to be all guards to use under dystopic conditions from GUARDS > - Set REMAINING_UTOPIC_GUARDS to be UTOPIC_GUARDS without EXCLUDE_NODES > - Set REMAINING_DYSTOPIC_GUARDS to be DYSTOPIC_GUARDS without EXCLUDE_NODES > - Create a list of PRIMARY_GUARDS that contain N_PRIMARY_GUARDS that are not bad by: > - Taking the next entry from USED_GUARDS > - If USED_GUARDS is empty: > - randomly select an entry from UTOPIC_GUARDS, weighted by bandwidth > - Set TRIED_GUARDS to be an empty set > - Set TRIED_DYSTOPIC_GUARDS to be an empty set > - Set state = STATE_PRIMARY_GUARDS > > - Each iteration of algorithm > - If a new consensus has arrived: > - Update all guard profiles with new bad/non-bad information > - If any PRIMARY_GUARDS have become bad: > - re-add to the list of PRIMARY_GUARDS using the same procedure > - If any USED_GUARDS have become non-bad: > - add it back to PRIMARY_GUARDS at the place it would have been if > it was non-bad when running the start of the algorithm. If this > results in PRIMARY_GUARDS being larger than N_PRIMARY_GUARDS, > remove from the end of the list until the list is N_PRIMARY_GUARDS long > - Ensure that UTOPIC_GUARDS and DYSTOPIC_GUARDS are updated with the changes > from the consensus > > - If it was at least 3 minutes since we tried the primary guards and we are not in STATE_PRIMARY_GUARDS: > - save previous state > - set state = STATE_PRIMARY_GUARDS > > - STATE_PRIMARY_GUARDS: > - return each entry in PRIMARY_GUARDS in turn > - mark each entry as "unreachable" if algorithm doesn't terminate > - restore previous state (or STATE_TRY_UTOPIC if no previous) > > - STATE_TRY_UTOPIC: > - for each entry in TRIED_GUARDS that was marked as unreachable more than 20 minutes ago > - add it back to REMAINING_UTOPIC_GUARDS > - return each remaining entry from USED_GUARDS in turn > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_GUARDS > - if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC > - return each entry from REMAINING_UTOPIC_GUARDS randomly selected, weighted by bandwidth > - remove the returned entry from REMAINING_UTOPIC_GUARDS > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_GUARDS > - if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC > > - STATE_TRY_DYSTOPIC: > - for each entry in TRIED_DYSTOPIC_GUARDS that was marked as unreachable more than 20 minutes ago > - add it back to REMAINING_DYSTOPIC_GUARDS > - return each remaining DYSTOPIC entry from USED_GUARDS in turn > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_DYSTOPIC_GUARDS > - if the number of entries in TRIED_GUARDS+TRIED_DYSTOPIC_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_DYSTOPIC_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of DYSTOPIC_GUARDS: > - mark all guards in PRIMARY_GUARDS, TRIED_GUARDS and TRIED_DYSTOPIC_GUARDS as not "unreachable" > - return failure from the algorithm > - return each entry from REMAINING_DYSTOPIC_GUARDS randomly selected, weighted by bandwidth > - remove the returned entry from REMAINING_DYSTOPIC_GUARDS > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_DYSTOPIC_GUARDS > - if the number of entries in TRIED_GUARDS+TRIED_DYSTOPIC_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_DYSTOPIC_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of DYSTOPIC_GUARDS: > - mark all guards in PRIMARY_GUARDS, TRIED_GUARDS and TRIED_DYSTOPIC_GUARDS as not "unreachable" > - return failure from the algorithm > > - End of algorithm > - If circuit is set up correctly, let algorithm know > - Algorithm marks the guard chosen as used and makes sure it is in USED_GUARDS > - Otherwise do another run of the algorithm > Ah great! Good improvements. I think we are going the right way. Here is another quick review. I include a second copy of the algorithm and comment inline: > > - Start of algorithm (arguments: USED_GUARDS, EXCLUDE_NODES) > - If selecting directory guards, GUARDS is all guards from the consensus with the V2Flag, > otherwise GUARDS is all guards from the consensus > - Set UTOPIC_GUARDS to be all guards to use under utopic conditions from GUARDS > - Set DYSTOPIC_GUARDS to be all guards to use under dystopic conditions from GUARDS > - Set REMAINING_UTOPIC_GUARDS to be UTOPIC_GUARDS without EXCLUDE_NODES > - Set REMAINING_DYSTOPIC_GUARDS to be DYSTOPIC_GUARDS without EXCLUDE_NODES Maybe we also need to exclude USED_GUARDS from these two lists? > - Create a list of PRIMARY_GUARDS that contain N_PRIMARY_GUARDS that are not bad by: > - Taking the next entry from USED_GUARDS > - If USED_GUARDS is empty: > - randomly select an entry from UTOPIC_GUARDS, weighted by bandwidth > - Set TRIED_GUARDS to be an empty set > - Set TRIED_DYSTOPIC_GUARDS to be an empty set > - Set state = STATE_PRIMARY_GUARDS > > - Each iteration of algorithm > - If a new consensus has arrived: > - Update all guard profiles with new bad/non-bad information > - If any PRIMARY_GUARDS have become bad: > - re-add to the list of PRIMARY_GUARDS using the same procedure > - If any USED_GUARDS have become non-bad: > - add it back to PRIMARY_GUARDS at the place it would have been if > it was non-bad when running the start of the algorithm. If this > results in PRIMARY_GUARDS being larger than N_PRIMARY_GUARDS, > remove from the end of the list until the list is N_PRIMARY_GUARDS long > - Ensure that UTOPIC_GUARDS and DYSTOPIC_GUARDS are updated with the changes > from the consensus > Not sure if this is part of this algorithm, or it's actually another helper algorithm that is called when a consensus arrives. I feel it might be cleaner if we do it as a separate algo, but we can proceed like this as well since it's not too confusing. > - If it was at least 3 minutes since we tried the primary guards and we are not in STATE_PRIMARY_GUARDS: > - save previous state > - set state = STATE_PRIMARY_GUARDS > > - STATE_PRIMARY_GUARDS: > - return each entry in PRIMARY_GUARDS in turn > - mark each entry as "unreachable" if algorithm doesn't terminate So IIUC the "algorithm" referenced here is _not_ the algorithm that we are describing right now (let's call it ALGO_CHOOSE_GUARD). Instead the "algorithm" here is the _caller of ALGO_CHOOSE_GUARD_, which is the algorithm responsible for creating circuits, testing whether they work and reporting the results back to CHOOSE_GUARD_ALGO (let's call this other algorithm ALGO_BUILD_CIRCUIT). Maybe we can clarify this? Also, do PRIMARY_GUARDS go into TRIED_GUARDS and count against our thresholds? > - restore previous state (or STATE_TRY_UTOPIC if no previous) > > - STATE_TRY_UTOPIC: > - for each entry in TRIED_GUARDS that was marked as unreachable more than 20 minutes ago > - add it back to REMAINING_UTOPIC_GUARDS > - return each remaining entry from USED_GUARDS in turn > - for each entry, if algorithm doesn't terminate In general, I think we should make the context of this algorithm (ALGO_CHOOSE_GUARD) a bit clearer, so that we know when "Start of algorithm" is supposed to run, and when "End of algorithm" is supposed to run. Because for example one could think here that in an asynchronous setting, when we try a entry from USED_GUARDS and find out whether the circuit succeeded or not, we need to run the algorithm from the beginning including the "Start of algorithm" step. Whereas if I understand correctly you assume that we will just drop in and continue exactly from this point. I feel that this confusion is caused by the ALGO_CHOOSE_GUARD algorithm being pseudo-asynchronous. To address this I suggested additional states for when we are waiting for the results of a circuit construction, but I agree that this might complicate things too much. Is there a way we can make this cleaner? > - mark entry as "unreachable" > - add entry to TRIED_GUARDS > - if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC > - return each entry from REMAINING_UTOPIC_GUARDS randomly selected, weighted by bandwidth > - remove the returned entry from REMAINING_UTOPIC_GUARDS > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_GUARDS > - if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC > > <snip> Finally, what kind of statistics and measurements does the simulator conduct? For example, I can think of reachability related stats like: * Time (or number of guards) till we manage to build first circuit * Time till we manage to recover from flaky network and I can also think of security related stats like: * Number of guards we tried before succeeding first circuit * Number of guards we exposed ourselves to after time t etc.

2 1

Re: [tor-dev] Entry guards, primary guards, dir guards
by George Kadianakis 09 Feb '16

09 Feb '16

Ola Bini <obini(a)thoughtworks.com> writes: > Hey, > > Maybe I misunderstood the hard part - I thought the problem was to > choose the NUM longlived vanguards - since there are only ever NUM > possible guards at each level, not to choose which one to use among > the NUM guards. For the first, it felt like using 259 would work, and > the for the second use case, just randomly choose one of the NUM > guards. > Hmm, let's try to formalize this slightly. Maybe it's helpful. I'm doing this a bit rushed, so maybe I'm wrong. So far we've been designing an algorithm that: a) populates and manages our guardlist b) picks the right guard to use from our guardlist We could in theory decouple these two steps, but so far we've been mixing them together. Step (b) has been easy so far because Tor uses a single guard node for general circuits, so we always pick the very first reachable guard from our guardlist every time. However, when we consider prop247 or directory guards we don't always want to pick the very first available guard. For example, when considering the layer-3 guards of prop247, we want to pick amongst N guards everytime we build a circuit so that we load balance our traffic amongst the guards. When considering directory guards, we want to pick randomly amongst the first 3 directory guards every time, so that if the first guard lied to us, we will also try the second one who might not lie. So maybe the simple answer here is that if prop247 is enabled (this could be a NumGuards=N argument to our algorithm), instead of always returning the first reachable guard, we instead build a list of the first N reachable guards, and randomly choose one of them. Could this work? (see #12466 for a weird behavior that will make us skip bugs if NumEntryGuards != 1) > The other alternative is to simply initialize USED_GUARDS to be > layer-2 guardlist and run the algorithm, then init USED_GUARDS to be > layer-3 guardlist and run the algorithm. Makes sense or am I missing > something? > Hmm, in this case we would just use the first reachable guard from USED_GUARDS. We would only reach other guards if the first guards are unreachable. That will not work for load balancing prop247 for example. (got to go. will be back later!)

1 0

Onion (Hidden) Service Proposal Discussion
by Tim Wilson-Brown - teor 08 Feb '16

08 Feb '16

Hi, We just had a meeting to discuss the following tor proposals[0] in the #tor-dev IRC channel[1]. Proposal 252: Single Onion Services Proposal 260: Rendezvous Single Onion Services Proposal 255: Controller features to allow for load-balancing hidden services Proposal 246: Merging Hidden Service Directories and Introduction Points A quick summary of each proposal: Some onion (hidden) service websites don't need to hide their location. They can have faster connection setup and bandwidth, and put less load on the tor network, by having 3 relays between the client and onion service. Proposal 252 has the onion service open an ORPort, and then clients extend from their third relay to the ORPort. Proposal 260 has the onion service connect directly to the introduction and rendezvous points. The other proposals improve onion service speed in different ways: Proposal 255 improves hidden or onion service load balancing by handing off the rendezvous to another tor instance. Proposal 246 improves hidden or onion service setup time by using the HSDirs as introduction points, and teaching clients to re-use the HSDir connection for the introduction. And a quick summary of our thoughts: Proposal 252 and Proposal 260 achieve similar outcomes. 260 is simpler to code, preserves NAT-punching (which some website providers need), and has already been coded[2]. It's also compatible with 255, which 252 is not. But 252 has a faster connection set-up time, because it skips the rendezvous protocol entirely. We'd like to see more research into the performance differences between 252 and 260. We want to focus on Proposal 224 (next-generation hidden services), and we were concerned that too much other work on onion service proposals would slow that down. So we'd like to finish 260 in the short term, and then reconsider 252 based on resourcing and research outcomes. We thought that 255 was a good idea, but noted that it increases connection set-up time. We noted that 246 already had concerns raised about it on the mailing list. That said, we could use 246 to improve the performance of 260. Tim [0]: https://gitweb.torproject.org/torspec.git/tree/proposals <https://gitweb.torproject.org/torspec.git/tree/proposals> [1]: http://meetbot.debian.net/tor-dev/2016/tor-dev.2016-02-08-22.00.log.html <http://meetbot.debian.net/tor-dev/2016/tor-dev.2016-02-08-22.00.log.html> [2]: https://trac.torproject.org/projects/tor/ticket/17178 <https://trac.torproject.org/projects/tor/ticket/17178> Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F

1 0

Re: [tor-dev] Entry guards, primary guards, dir guards
by George Kadianakis 08 Feb '16

08 Feb '16

Ola Bini <obini(a)thoughtworks.com> writes: > Hey, > > Thanks- this is very helpful. > > When it comes to vanguards, I've already read through the > proposal. I'm not exactly sure I understand how much different 259 > would need to be to support the 247 needs. It seems we should be able > to just run the algorithm NUM_SECOND_GUARDS * NUM_THIRD_GUARDS times > to choose the sets of vanguards for each layer, right? > Hmm, how would that work exactly? Let's say I'm a prop247 hidden service. I just received an introduction and want to setup my rendezvous circuit. To setup my circuit, I would need to do three guard picks, one for every layer. Each layer has a different guard list. First, I use my layer-1 guardlist to pick my layer-1 guard. That's easy, I use a single guard for layer-1, so I always pick the first reachable non-bad guard from the layer-1 guardlist. Then I need to use my layer-2 guardlist to pick my layer-2 guard. Proposal 247 says that each HS has two layer-2 guards , so I would need to pick a guard out of the two top guards in my layer-2 guardlist. How does this happen exactly? A similar thing needs to happen for layer-3.

1 0

Roadmap - Hidden service next generation (prop224)
by David Goulet 08 Feb '16

08 Feb '16

Hi everyone! For a while now, we've had an idea on how to proceed for the engineering part of proposal 224 (next generation hidden service). So, we've put up this pad with *5* large milestones that will in theory happen one after the other. Step 1 is shared randomness for which the code and proposal has been finalized and under review for upstream merge. Yay progress! :) You'll notice that they are pretty huge milestone. As we go forward, we'll break them down in much more details (++tickets). You can already see step 2) has a pad for that already. Our hope is to update that pad regurlarly as implementation moves forward and update tor-dev@ as well with relevant information for the community. You to can help with this huge effort, please come find us on #tor-dev! Code review, comment on designs, testing, etc..., we'll need a lot of these. https://storm.torproject.org/shared/TlPhwNbdgPwLw5h23G3gEDtkWdqxVe9Gqn3KiqV… Don't hesitate to comment on the roadmap using this thread or you can also do it in the pad (which is a "Can Comment" link). Thanks! David

2 2

Re: [tor-dev] Entry guards, primary guards, dir guards
by George Kadianakis 08 Feb '16

08 Feb '16

Ola Bini <obini(a)thoughtworks.com> writes: > Hi again, > > Two questions - first, hopefully I simple one. What are directory > guards, exactly? > > Second, we found a weird behavior in the current code > base. Specifically, when Tor first downloads the microdescriptors, it > chooses 3 guards for this with the V2Dir flag. That's a little bit > less than 1600 nodes right now. However, these three guards gets > persistes as primary guards, which means that almost all Tor users > will have primary guards among those 1600, not among the 1900 that > have the Guard flag. Is this intented behavior? > Very relevant questions. Directory guards were intoduced by proposal 207. They are basically guard nodes for directory connections, so that Tor clients expose themselves to the minimum number of directory relays when downloading the various Tor documents (microdescriptors, etc.). Currently Tor uses the same guardlist for directory guards and entry guards. That's a feature because ideally you would have a single guard that would be both your entry guard and your directory guard. Unfortunately, that's not always possible because some entry guards are not directories (they don't have the V2Dir flag) so they can't be picked as directory guards. And that's basically the weird behavior that you noticed. Because Tor pick its directory guards first and they are picked from a slightly restricted set compared the total set of guards nodes. Eventually when #12538 gets to stable Tor, all relays will be directories, and hence all guards will be potential directory guards. --- So everything is explained now except from why Tor picks 3 directory guards and not one. That's because we have decided to keep the number of directory guards to 3, instead of using a single guard like we do for normal circuits. Otherwise, that single directory guard could launch some hard-to-detect route biasing attacks. For more details see: https://lists.torproject.org/pipermail/tor-dev/2014-May/006820.html https://lists.torproject.org/pipermail/tor-dev/2014-June/006944.html So basically when Tor picks a directory guard for a directory connection, it finds the first three reachable entry guards in its guardlist, and picks one of them. It might be smart to be able to support "multiple guards" mode in the algorithms that we are currently designing. That's because we might keep the "3 directory guards" design for some more time, but even more importantly because if we ever go with a layered guards design we will need to have multiple guards in some layers. For example, consider proposal 247 which specifies a layer guard design to defend against hidden service guard discovery attacks. The proposal basically makes hidden services pick guard nodes for their second and third hops. So instead of looking like this: -> middle_1 -> middle_A -> middle_2 -> middle_B -> middle_3 -> middle_C -> middle_4 -> middle_D HS -> guard -> middle_5 -> middle_E -> Rendezvous Point -> middle_6 -> middle_F -> middle_7 -> middle_G -> middle_8 -> middle_H -> ... -> ... -> middle_n -> middle_n it will look like this: -> guard_3A_A -> guard_2_A -> guard_3A_B -> guard_3A_C -> Rendezvous Point HS -> guard_1 -> guard_3B_D -> guard_2_B -> guard_3B_E -> guard_3B_F -> Rendezvous Point As you can see in this latter design, we pick amongst "2 guard nodes" for the second hop, and amongst "6 guard nodes" for the third hop. Feel free to read the introduction of the proposal for more info. So yeah... it would be nice to support this multiple guard node design in our algorithms as well. We discussed this a bit during our proposal meeting some weeks ago but we kind of let it drop. Do you think it's possible? :)

1 0

Propsal 263 Quantum-safe Hybrid handshake for Tor, updated feature request v1.2
by Zhenfei Zhang 08 Feb '16

08 Feb '16

Hello list, We had a very constructive discussion on this proposal last Thursday. I have updated the feature request based on the feedback from the discussion. We also like to thank Roger for grammar fixes on the proposal. The diff file is available at: https://github.com/zhenfeizhang/ntru-tor/commit/dc48c2065d1772c5497cd6ad900… Major tech updates are: 1. Use SHA3 and SHAKE instead of HMAC_SHA3 2. In previous proposal, when server sends back the message, it sends a ciphertext C = ENCRYPT( P | B, QSPK), and its one-time ECC public key Y = e^y; where P is the secret that server chose, B is servers long term public key. In this new version, we also include servers short term public key in the plaintext, i.e., C = ENCRYPT( P | B | Y, QSPK) and Y is no longer send to the client separately. The client will need to decrypt C first and retrieve Y from the message. Y is not revealed to any one other than the client. This is proposed by Nick. It was also suggested to us by Aniket Kate. We thank Nick and Aniket for the suggestion. This modification will save 32 bytes of traffic as Y is no longer transmitted. Also since Y is now encrypted it will be a little harder for the attacker to attack the 25519 keys. 3. Choosing algorithms and parameters for the protocol. We have identified NTRUEncrypt and R-LWE as two candidates for this protocol. We have agreed to use NTRUEncrypt for now, in the meantime, keep the option open for "newesthope" version of R-LWE type key exchange when it becomes available. Also, for NTRUEncrypt we will be using parameters sets with SHA3, to align with Tor specs. I have modified the feature request to reflect this change. Also in the discussion we were talking about the possibility of using non-product form polynomial version of NTRUEncrypt, as this version will become patent free by Aug 2017, while the patent for product form will last for another 4 years. The main concern is that Debian will not allow patented software in the package. However, through our discussion, it turns out that we may be able to include this proposal in the next one of two release of Tor. From this point of view, both patent (basic NTRU patent, till 2017 and product form patent, till 2021) are going to be an issue if Debian does not agree with SI's patent statement. So does it make sense to keep the product form polynomials as they enables roughly 3 times faster operations on both client side and server side? Thanks for your time, and please let us know if you have any further comments/suggestions. Best regards, Zhenfei

2 1

Re: [tor-dev] Detailed algorithm
by George Kadianakis 08 Feb '16

08 Feb '16

> Hey, > > So - thinking through your comments and thoughts, I realized that the > better way to proceed was to describe the algorithm, and then put it > into a proposal format. The following is updated with most of your > comments and should be a bit clearer. I decided to remove #241 again, > since it's unclear how it actually fits together with #259. The idea > is that the algo is divided into three pieces. If failure is reported > from the algorithm, the caller can wait for a while or just restart it > from scratch immediately: > I feel that this algorithm is a step in the right direction! It's interface logic is quite similar to how Tor picks its guards, and it's more specific than the previous proposals. It's a good first step so I'll CC tor-dev so that Nick, Isis and other people can take a look if they want. After we pin this down, we also need to collect all its security properties in one place. For example, we should state clearly what security properties the thresholds GUARDS_TRY_THRESHOLD_TIME and GUARDS_FAILOVER_THRESHOLD provide. I inline various questions below. I can take a deeper look tomorrow as well. > - Start of algorithm > - Ensure USED_GUARDS is populated (from state file etc) > - Create a list of PRIMARY_GUARDS that contain N_PRIMARY_GUARDS that are not bad by: > - Taking the next entry from USED_GUARDS > - If USED_GUARDS is empty: > - randomly select an entry from UTOPIC_GUARDS, weighted by bandwidth Hmm. PRIMARY_GUARDS stays like this for ever? It probably needs to be updated when a primary guard get removed from the consensus (become bad), and put the next entry of USED_GUARDS in its place. Maybe we need another event (and algorithm) for "receive new consensus"? Or is this considered out of scope? > - Set TRIED_GUARDS to be an empty set Hm. What is the point of TRIED_GUARDS? It's like a list of guards that we found unreachable at some point in time. It's never cleaned, so it will eventually accumulate many nodes. IIUC, we only use that list to enforce our thresholds by looking at timestamps. Can we do without this list, just by checking the timestamps of unreachable USED_GUARDS? Or the logic will be much more complicated? > - Set TRIED_DYSTOPIC_GUARDS to be an empty set > - Set state = STATE_PRIMARY_GUARDS > > - Each iteration of algorithm > - If it was at least 3 minutes since we tried the primary guards and we are not in STATE_PRIMARY_GUARDS: > - save previous state > - set state = STATE_PRIMARY_GUARDS > > - STATE_PRIMARY_GUARDS: > - return each entry in PRIMARY_GUARDS in turn > - mark each entry as "unreachable" if algorithm doesn't terminate What is the "algorithm" here? Is it the guard selection algorithm, or the circuit construction algorithm? I guess the latter? If it's indeed the circuit construction algorithm, then the steps here are not asynchronous anymore, which diverges from how Tor networking is designed. Maybe this could be fixed by introducing some new states for when we are waiting for a circuit to connect and we are now learning whether it was succesful or not. Basically what entry_guard_register_connect_status() does in Tor right now. For example we could have STATE_WAITING_FOR_PRIMARY_GUARD_CIRCUIT for when we are waiting for a primary guard circuit to connect. If it fails, then we need to mark the entry as unreachable. Maybe we also need STATE_WAITING_FOR_UTOPIC_GUARD_CIRCUIT etc. > - restore previous state (or STATE_TRY_UTOPIC if no previous) > > > - STATE_TRY_UTOPIC: > - for each entry in TRIED_GUARDS that was marked as unreachable more than 20 minutes ago > - add to the front of remaining UTOPIC_GUARDS Isn't it already in UTOPIC_GUARDS? I don't see us ever removing stuff from UTOPIC_GUARDS. BTW, what is this step supposed to do? Setup previously TRIED_GUARDS to be retried? > - return each remaining entry from USED_GUARDS in turn > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_GUARDS Add it there even if it it's already there (TRIED_GUARDS is never cleaned)? Or maybe update a timestamp if it's already there? How to specify this nicely? > - if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC > - return each remaining entry from UTOPIC_GUARDS randomly selected, weighted by bandwidth > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_GUARDS > - if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC > TRIED_GUARDS is never cleaned, so this will be almost always true after a while. > - STATE_TRY_DYSTOPIC: > - for each entry in TRIED_DYSTOPIC_GUARDS that was marked as unreachable more than 20 minutes ago > - add to the front of remaining UTOPIC_GUARDS Does it matter if we add it to the front or the back of UTOPIC_GUARDS? >From what I understand, we always sample from UTOPIC_GUARDS based on relay bandwidth so the list order should not matter, right? [This comment and also the comments below also apply for the STATE_TRY_UTOPIC case above] > - return each remaining DYSTOPIC entry from USED_GUARDS in turn Do we even try previously-found unreachable guards here? > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_DYSTOPIC_GUARDS Order matters here right? We probably want FIFO. > - if the number of entries in TRIED_GUARDS+TRIED_DYSTOPIC_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_DYSTOPIC_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of DYSTOPIC_GUARDS: > - mark all guards in PRIMARY_GUARDS, TRIED_GUARDS and TRIED_DYSTOPIC_GUARDS as not "unreachable" > - return failure from the algorithm > - return each remaining entry from DYSTOPIC_GUARDS randomly selected, weighted by bandwidth > - for each entry, if algorithm doesn't terminate > - mark entry as "unreachable" > - add entry to TRIED_DYSTOPIC_GUARDS > - if the number of entries in TRIED_GUARDS+TRIED_DYSTOPIC_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME > is larger than GUARDS_TRY_THRESHOLD, return failure from the algorithm > - if the number of entries in TRIED_DYSTOPIC_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD > proportion of DYSTOPIC_GUARDS: > - mark all guards in PRIMARY_GUARDS, TRIED_GUARDS and TRIED_DYSTOPIC_GUARDS as not "unreachable" Hm, not sure what this is supposed to do. Is it trying to setup the algorithm to retry all guards from the beginning? Shouldn't we edit USED_+GUARDS in that case? > - return failure from the algorithm > Instead of failing in this case, shouldn't we just retry from the top without adding any new guards if we hit these thresholds? How do we do this? Or is this logic considered out of scope? :x > - End of algorithm > - If circuit is set up correctly, let algorithm know > - Algorithm marks the guard chosen as used and makes sure it is in USED_GUARDS > - Otherwise do another run of the algorithm > When does this "End of algorithm" happen?

1 0