Re: [tor-dev] Update on 259
> > - Directory guards are 85% of total current guard bandwidth. > - Guards with ORPorts on 80/443 are 42% of total current guard bandwidth. > - Guards on IPv6 are 20% of total current guard bandwidth. > - Guards both on 80/443 and on IPv6 are 8% of total current guard > bandwidth. Useful info, thanks. This tells us it's very unlikely that someone will not have any dirguards, or dystopic guards or ipv6 guards. And if we make the sample set size large enough, something like 50 guards - we are very likely to have all capabilities. > With the above probabilities, everytime you sample a guard you have 20% > probability for it to be an IPv6 guard. To get 4 of them, you will first need > to sample a lot of guards (like 20 or so, but some binomial distribution magic > is required to get the exact probabilities) and add them to your sampled guard > set. I wonder if that's worth it. Maybe, maybe not. I don't think the problem of sampling until we have enough to match the filter is a big problem actually. > Maybe if we have a single guard that satisfies our filters in our sampled > guard > list, we should use that guard instead of sampling for more? I don't exactly > see value in sampling and exposing ourselves to additional guards if we have > one that we like (and we might have even connected to in the past). True, if we have one and that works - all fine with me. The problem is that IF that guard doesn't work, we have no fallback mechanism to sample more guards, so we will never correct for that circuit building. > Symmetrically, I'm also not sure what's the right thing to do if we have zero > guards that satisfy our filters in our sampled guard set. Should we start > sampling randomly till we hit a guard that satisfies us, or should we sample > directly from the correct set (e.g. only from the set of IPv6 guards). I'm > still not sure about this. I'm much more in favor of sampling in general, rather than trying to hit the specific thing. If we sample in general, we will not skew the sampled set at least. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Update on 259
Hey, > On second thought, I think using a single USED_GUARDS list here should be OK > for now. That's also what Tor is doing right now, so this behavior can't be > worse than the status quo. > > On this note, we should add a small "Discussion" section on the proposal and > briefly mention these issues that we might want to solve in the future, but we > don't know how now. Both things sound good to me. > It might be a good idea to enumerate the guards for each possible filter we > will add, and then calculate their guard probabilities, to see how likely it > is > to randomly choose a guard of that type. If we have filters were there is only > 1% probability of picking a bridge of the right type, then these "your current > network settings make it impossible for us to safely choose an entry guard" > messages might appear more frequently than we would like. I'm not sure we can do this - a lot of the filters will be based on backwards compatibility with the existing Tor configuration options, things such as ReachableAddresses - I'm not sure how to reasonably enumerate all possibilities in a useful way. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Update on 259
Hi, > No, clients typically tunnel directory requests over the ORPort when they can. > This is better for anonymity. > > But they will fall back to the DirPort in some circumstances. > And relays use the DirPort all the time. Ah, thanks - that's helpful, > It's worse for the risk of guard compromise. > But it's better because it prevents the client being fingerprinted > using its guard set. Right, so rock or a hard place? =) > > 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. However, it seems you don't like that idea - there seems to be some dissent among the Tor devs which approach is best for this situation. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Update on 259
mpled 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. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Proposal 259: New Guard Selection Behaviour
Hi, Funny, this is exactly the direction my thinking has been going. There are too many different variations on restrictions - it might make sense to just have a large enough sampled set, and then filter it with the further restrictions. If nothing is found, we can fail closed at least. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Next version of the algorithm
ED_GUARDS it should be added *last* (that is, > with lowest priority). Yep, added that. > We should decide if we want to actually use a dynamic percentage here, or just > set the threshold to a constant value. > > A dynamic percentage might give us better security and reachability as the > network evolves, but might also cause unpredictable behaviors if we suddently > get too many guards or too many of them disappear. > > I don't have a strong opinion here. Me neither. I think a percentage is a good starting point - it feels easier to tweak in different ways. > It seems to me that the value 20 here could get reduced to something like 5 or > even less. Of course 5 is also an arbitrary value and to actually find out the > "best" number here we should test the algorithm ourselves in various network > types. Arbitrarily changed to 5. =) Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Next version of the algorithm
Great, lots of good comments. I'll respond in depth once the fever has left my brain! =D On Thu, Mar 03, 2016 at 03:15:26PM +0100, George Kadianakis wrote: > Ola Bini <ob...@thoughtworks.com> writes: > > > Hi, > > Here are some more comments to the latest version of the proposal, as seen > here: > https://github.com/twstrike/torspec > > > 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 private to the algorithm - this is re-initialized every time > > START is called. > > > > Hmm, didn't we decide to persist the unreachability status over runs, right? > Or not? > > The argument for doing so is "What happens if I'm a hidden service that needs > to > make 5 circuits per second, and my first 2 guards happen to be offline? Do I > have to spend time probing them everytime I make a new circuit?". > > > 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 conn
Re: [tor-dev] Next version of the algorithm
Hey, > > Returning to this for a bit. I think it would be good to decide whether we > should keep the unreachable status of guards on permannet disk state or > not. The > very latest prop259 basically forgets the unreachable guard status as soon as > the algorithm terminates. I wonder if we actually want this. Hopefully > guardsim > has a simulation scenario that will illustrate whether that's a good idea or > not. Agreed. I don't know if you saw it, but in the new proposal I have an XXX for exactly that. > Maybe an equivalent heuristic would be that if we are in STATE_RETRY_ONLY and > we manage to connect to a non-primary guard, we hang up the connection, and go > back into STATE_PRIMARY_GUARDS. Maybe. Should we do this only in STATE_RETRY_ONLY or for the UTOPIC and DYSTOPIC states as well? Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Next version of the algorithm
Hi George, Sorry I've been slow to answer and send more info - was spending all day Saturday and Sunday, and this week I'll be in all day meetings. Anyway, just to avoid confusion - After getting the algorithm to the latest stage you saw below, we started work on implementing it to simulate it. Iván and Tania have been working on that. I also wrote it in draft form, so this: https://github.com/twstrike/torspec/blob/review/proposals/259-guard-selection.txt Is completely rewritten more or less from scratch. When it comes to receive new consensus, it is in the latest version of the written proposal above. The link Chelsea sent is a link to the original protocol, not the new one. So to summarize where we are: - We have fixed a bunch of issues in the existing guardsim code - We have added a lot of simulation cases to the existing guardsim - code - We have implemented most of the original implementation in the - guardsim code - We are implementing the new algorithm, described in the spec above - in the guardsim code, and expect that to be done today or tomorrow - The spec above is polished enough, that if you agree we could send - it to a wider distribution and get thoughts. - We might be able to start implementing this in tor proper tomorrow - or wednesday hopefully. From now, the team will take over most communication. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Next version of the algorithm
. You're completely right. Not a good idea. OK - so what if we instead of returning failure enter a new state where we only ever retry guards in 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 ALGO_CHOOSE_ENTRY_GUARD. > > if the number of entries in TRIED_GUARDS is larger than > > a GUARDS_FAILOVER_THRESHOLD proportion of UTOPIC_GUARDS, set state = > > STATE_TRY_DYSTOPIC > > > > Also, I'm not sure I understand the precise security properties that the > above two > checks provide us with. Are both checks needed? Could you explain > them to me please? The first one is to make it possible to constrain how many guards we ever try to connect to, in order to minimize our exposure in a shorter amount of time. The second one is to switch over from utopic conditions to dystopic conditions. IF we are in dystopic conditions, then this heuristic will make it more likely we will faster find a guard to connect to. > > ALGO_CHOOSE_ENTRY_GUARD_END: > > If circuit is set up correctly, let algorithm know > > Algorithm marks the guard chosen as used and makes sure it is > > in USED_GUARDS > > > > Maybe instead of "makes sure it is in" we should say "adds it in"? > It has not been added in a previous step from what I see. Well, since USED_GUARDS is persistent, the guard could have been added in a previous run of the Tor client - that's why I said "makes sure it is in". If you disagree, I can change the language. =) Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Next version of the algorithm
Hi again, Here is the newest version of the algorithm: https://gist.github.com/olabini/343da01de8e01491bf5c The biggest change is the addition of the state STATE_TRY_ONLY_TRIED. Once it enters this state, it will never exit it again. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Entry guards, primary guards, dir guards
Ah, good point. So, it seems N_PRIMARY_GUARDS is an argument to the algorithm. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
[tor-dev] Next version of the algorithm
Hi, Here is the next version of the algorithm - put it in a gist to make it easier to look at: https://gist.github.com/olabini/343da01de8e01491bf5c Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Detailed algorithm
Hi, Thanks for the review. > Maybe we also need to exclude USED_GUARDS from these two lists? Good point, we should definitely do that. > 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. We can probably do that. The reason I put it in here is because it works on the same data structures that are used for the rest of the algorithm. > > - 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). We should probably clarify it. But yes, the algorithm referenced is ALGO_CHOOSE_GUARD. ALGO_CHOOSE_GUARD will terminate if ALGO_BUILD_CIRCUIT successfully builds a circuit. > Also, do PRIMARY_GUARDS go into TRIED_GUARDS and count against our > thresholds? Yes, they probably should. Will change it. > 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. Yes, exactly. "Start of algorithm" sets up the data structures etc. "Each iteration of algorithm" will be called repeatedly until we get failure or a working guard, and at that point "End of algorithm" will be run. I can make it clearer. > 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. I can do that - not sure if it would clarify things. That state is entered every time the word "return" is used in "Each iteration of algorithm". Once "Each iteration of algorithm" is called again, it will continue at the same place. Not sure what you consider pseudo asynchronous about that. =) > 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 Haven't thought abou that yet - we currently only have the things that were already in the simulator code, which primarily checks how many failed vs successful guards we got. These other heuristics look interesting to check as well. Cheers -- Ola Bini (https://olabini.se) "Yields falsehood when quined" yields falsehood when quined. signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
