- tor-dev - lists.torproject.org

Proposal: Load Balancing with Overhead Parameters
by Mike Perry 01 Feb '16

01 Feb '16

This proposal aims to allow us to load balance properly between Guard, Middle, and Exit nodes with the addition of padding traffic to the network. Canonical proposal current lives in my load_balancing-squashed branch: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/xxx… Here is the text in-line, for ease of commenting on-list: ============================================================== Filename: xxx-load-balancing-with-overhead.txt Title: Load Balancing with Overhead Parameters Authors: Mike Perry Created: 01 January 2016 Status: Draft 0. Motivation In order to properly load balance in the presence of padding and non-negligible amounts of directory and hidden service traffic, the load balancing equations in Section 3.8.3 of dir-spec.txt are in need of some modifications. In addition to supporting the idea of overhead, the load balancing equations can also be simplified by treating Guard+Exit nodes as Exit nodes in all cases. This causes the 9 sub-cases of the current load balancing equations to consolidate into a single solution, which also will greatly simplify the consensus process, and eliminate edge cases such as #16255[1]. 1. Overview For padding overhead due to Proposals 251 and 254, and changes to hidden service path selection in Proposal 247, it will be useful to be able to specify a pair of parameters that represents the additional traffic present on Guard and Middle nodes due to these changes. The current load balancing equations unfortunately make this excessively complicated. With overhead factors included, each of the 9 subcases goes from being a short solution to over a page of calculations for each subcase. Moreover, out of 8751 hourly consensus documents produced in 2015[2], only 78 of them had a non-zero weight for using Guard+Exit nodes in the Guard position (weight Wgd), and most of those were well under 1%. The highest weight for using Guard+Exits in the Guard position recorded in 2015 was 2.62% (on December 10th, 2015). This means clients that chose a Guard node during that particular hour used only 2.62% of Guard+Exit flagged nodes' bandwidth when performing a bandwidth-weighted Guard selection. All clients that chose a Guard node during any other hour did not consider Guard+Exit nodes at all as potential candidates for their Guards. This indicates that we can greatly simplify these load balancing equations with little to no change in diversity to the network. 2. Simplified Load Balancing Equations Recall that the point of the load balancing equations in section 3.8.3 of dir-spec.txt is to ensure that an equal amount of client traffic is distributed between Guards, Middles, Exits, and Guard+Exits, where each flag type can occupy one or more positions in a path. This allocation is accomplished by solving a system of equations for weights for flag position selection to ensure equal allocation of client traffic for each position in a circuit. If we ignore overhead for the moment and treat Guard+Exit nodes as Exit nodes, then this allows the simplified system of equations to become: Wgg*G == M + Wme*E + Wmg*G # Guard position == middle position Wgg*G == Wee*E # Guard position == equals exit position Wmg*G + Wgg*G == G # Guard allocation weights sum to 1 Wme*E + Wee*E == E # Exit allocation weights sum to 1 This system has four equations and four unknowns, and by transitivity we ensure that allocated capacity for guard, middle, and exit positions are all equal. Unlike the equations in 3.8.3 of dir-spec.txt, there are no special cases to the solutions of these equations because there is no shortage of constraints and no decision points for allocation based on scarcity. Thus, there is only one solution. Using SymPy's symbolic equation solver (see attached script) we obtain: E + G + M E + G + M 2*E - G - M 2*G - E - M Wee: ---------, Wgg: ---------, Wme: -----------, Wmg: ------------ 3*E 3*G 3*E 3*G For the rest of the flags weights, we will do the following: Dual-flagged (Guard+Exit) nodes should be treated as Exits: Wgd = 0, Wmd = Wme, Wed = Wee Directory requests use middle weights: Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm Handle bridges and strange exit policies: Wgm=Wgg, Wem=Wee, Weg=Wed 2.1. Checking for underflow and overflow In the old load balancing equations, we required a case-by-case proof to guard against overflow and underflow, and to decide what to do in the event of various overflow and underflow conditions[3]. Even still, the system proved fragile to changes, such as the implementation of Guard uptime fractions[1]. Here, with the simplified equations, we can plainly see that the only time that a negative weight can arise is in Wme and Wmg, when 2*E < G+M or when 2*G < E+M. In other words, only when Exits or Guards are scarce. Similarly, the only time that a weight exceeding 1.0 can arise is in Wee and Wgg, which also happens when 2*E < G+M or 2*G < E+M. This means that parameters will always overflow in pairs (Wee and Wme, and/or Wgg and Wmg). In both these cases, simply clipping the parameters at 1 and 0 provides as close of a balancing condition as is possible, given the scarcity. 3. Load balancing with Overhead Parameters Intuitively, overhead due to padding and path selection changes can be represented as missing capacity in the relevant position. This means that in the presence of a Guard overhead fraction of G_o and a Middle overhead fraction of M_o, the total fraction of actual client traffic carried in those positions is (1-G_o) and (1-M_o), respectively. Then, to achieve a balanced allocation of traffic, we consider only the actual client capacity carried in each position: # Guard position minus overhead matches middle position minus overhead: (1-G_o)*(Wgg*G) == (1-M_o)*(M + Wme*E + Wmg*G) # Guard position minus overhead matches exit position: (1-G_o)*(Wgg*G) == 1*(Wee*E) # Guard weights still sum to 1: Wmg*G + Wgg*G == G # Exit weights still sum to 1: Wme*E + Wee*E == E Solving this system with SymPy unfortunately yields some unintuitively simplified results. For each weight, we first show the SymPy solution, and then factor that solution into a form analogous to Section 2: -(G_o - 1)*(M_o - 1)*(E + G + M) Wee: --------------------------------------- E*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (1 - G_o)*(1 - M_o)*(E + G + M) Wee: --------------------------------------- E*(2 - G_o - M_o + (1 - G_o)*(1 - M_o)) (M_o - 1)*(E + G + M) Wgg: --------------------------------------- G*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (1 - M_o)*(E + G + M) Wgg: --------------------------------------- G*(2 - G_o - M_o + (1 - G_o)*(1- M_o)) -E*(M_o - 1) + G*(G_o - 1)*(-M_o + 2) - M*(M_o - 1) Wmg: --------------------------------------------------- G*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (2 - M_o)*G*(1 - G_o) - M*(1 - M_o) - E*(1 - M_o) Wmg: --------------------------------------------------- G*(2 - G_o - M_o + (1 - G_o )*(1 - M_o)) E*(G_o + M_o - 2) + G*(G_o - 1)*(M_o - 1) + M*(G_o - 1)*(M_o - 1) Wme: ----------------------------------------------------------------- E*(G_o + M_o - (G_o - 1)*(M_o - 1) - 2) (2 - G_o - M_o)*E - G*(1 - G_o)*(1 - M_o) - M*(1 - G_o)*(1 - M_o) Wme: ----------------------------------------------------------------- E*(2 - G_o - M_o + (1 - G_o)*(1 - M_o)) A simple spot check with G_o = M_o = 0 shows us that with zero overhead, these solutions become identical to the solutions in Section 2 of this proposal. The final condition that we need to ensure is that these weight values never become negative or greater than 1.0[3]. 3.1. Ensuring against underflow and overflow Note that if M_o = G_o = 0, then the solutions and the overflow conditions are the same as in Section 2. Unfortunately, SimPy is unable to solve multivariate inequalities, which prevents us from directly deriving overflow conditions for each variable independently (at least easily and without mistakes). Wolfram Alpha is able to derive closed form solutions to some degree for this, but they are more complicated than checking the weights for underflow and overflow directly. However, for all overflow and underflow cases, simply warning in the event of overflow or underflow in the weight variable solutions above is equivalent anyway. Optimal load balancing given this scarcity should still result if we clip the resulting solutions to [0, 1.0]. It will be wise in the implementation to test the overflow conditions with M_o = G_o = 0, and with their actual values. This will allow us to know if the overflow is a result of inherent unbalancing, or due to input overhead values that are too large (and need to be reduced by, for example, reducing padding). 4. Consensus integration 4.1. Making use of the Overhead Factors In order to keep the consensus process simple on the Directory Authorities, the overhead parameters represent the combined overhead from many factors. The G_o variable is meant to account for sum of directory overhead, netflow padding overhead, future two-hop padding overhead, and future hidden service overhead (for cases where Guard->Middle->Exit circuits are not used). The M_o variable is meant to account for multi-hop padding overhead, hidden service overhead, as well as an overhead for any future two-hop directory connections (so that we can consolidate Guards and Directory guard functionality into a single Guard node). There is no need for an E_o variable, because even if there were Exit-specific overhead, it could be represented by an equivalent reductions in both G_o and M_o instead. Since all relevant padding and directory overhead information is included in the extra-info documents for each relay, the M_o and G_o variables could be computed automatically from these extra-info documents during the consensus process. However, it is probably wiser to keep humans in the loop and set them manually as consensus parameters instead, especially since we have not previously had to deal with serious adversarial consequences from malicious extra-info reporting. For clarity, though, it may be a good idea to separate all of the components of M_o and G_o into separate consensus parameters, and combine them (via addition) in the final equations. That way it will be easier to pinpoint the source of any potential overflow issues. This separation will also enable us to potentially govern padding's contribution to the overhead via a single tunable value. 4.2 Integration with Guardfraction The GuardFraction changes in Proposal 236 and #16255 should continue to work with these new equations, so long as the total T, G, and M values are counted after the GuardFraction multiplier has been applied. 4.3. Guard flag assignment Ideally, the Guard flag assignment process would also not count Exit-flagged nodes when determining the Guard flag uptime and bandwidth cutoffs, since we will not be using Guard+Exit flagged nodes as Guard nodes at all when this change is applied. This will result in more accurate thresholds for Guard node status, as well as better control over the true total amount of Guard bandwidth in the consensus. 1. https://trac.torproject.org/projects/tor/ticket/16255 2. https://collector.torproject.org/archive/relay-descriptors/consensuses/ 3. http://tor-dev.torproject.narkive.com/17H9FewJ/correctness-proof-for-new-ba… Appendix A: SymPy Script for Balancing Equation Solutions #!/usr/bin/python from sympy.solvers import solve from sympy import simplify, Symbol, init_printing, pprint # Sympy variable declarations (G,M,E,D) = (Symbol('G'),Symbol('M'),Symbol('E'),Symbol('D')) (Wgd,Wmd,Wed,Wme,Wmg,Wgg,Wee) = (Symbol('Wgd'),Symbol('Wmd'),Symbol('Wed'), Symbol('Wme'),Symbol('Wmg'),Symbol('Wgg'), Symbol('Wee')) (G_o, M_o) = (Symbol('G_o'),Symbol('M_o')) print "Current Load Balancing Equation Solutions, Case 1:" pprint(solve( [Wgg*G + Wgd*D - (M + Wmd*D + Wme*E + Wmg*G), Wgg*G + Wgd*D - (Wee*E + Wed*D), Wed*D + Wmd*D + Wgd*D - D, Wmg*G + Wgg*G - G, Wme*E + Wee*E - E, Wmg - Wmd, 3*Wed - 1], Wgd, Wmd, Wed, Wme, Wmg, Wgg, Wee)) print print "Case 1 with guard and middle overhead: " pprint(solve( [(1-G_o)*(Wgg*G + Wgd*D) - (1-M_o)*(M + Wmd*D + Wme*E + Wmg*G), (1-G_o)*(Wgg*G + Wgd*D) - (Wee*E + Wed*D), Wed*D + Wmd*D + Wgd*D - D, Wmg*G + Wgg*G - G, Wme*E + Wee*E - E, Wmg - Wmd, 3*Wed - 1], Wgd, Wmd, Wed, Wme, Wmg, Wgg, Wee)) print "\n\n" print "Elimination of combined Guard+Exit flags (no overhead): " pprint(solve( [(Wgg*G) - (M + Wme*E + Wmg*G), (Wgg*G) - 1*(Wee*E), Wmg*G + Wgg*G - G, Wme*E + Wee*E - E], Wme, Wmg, Wgg, Wee)) print print "Elimination of combined Guard+Exit flags (Guard+middle overhead): " combined = solve( [(1-G_o)*(Wgg*G) - (1-M_o)*(M + Wme*E + Wmg*G), (1-G_o)*(Wgg*G) - 1*(Wee*E), Wmg*G + Wgg*G - G, Wme*E + Wee*E - E], Wme, Wmg, Wgg, Wee) pprint(combined)

4 7

Fwd: Need to know if this is a bug
by Siddhartha De 30 Jan '16

30 Jan '16

Dear all , I just found out that the tor.exe included in the Tor Browser ( ver 5.5 ) for Windows bundle ( Tor ver 0.2.7.6 ) does not support TransPort and TransListenAddress ... The error message given was :- Jan 29 23:16:24.129 [warn] Failed to parse/validate config: TransPort and TransListenAddress are disabled in this build. Jan 29 23:16:24.129 [err] Reading config failed--see warnings above. Is this a deliberate design consideration or a bug ... If we keep the tor.exe of both the browser bundle and expert bundles synced I think it would be easier for users who would like to use Tor both as a browser as well as a Transparent Proxy . Thanking you , Yours sincerely , Siddhartha De

2 1

Re: [tor-dev] Fwd: [guardian-dev] RC-7 is out - try to repro? Re: towards reproducible Orbot
by Nathan Freitas 30 Jan '16

30 Jan '16

On Thu, Jan 28, 2016, at 02:27 PM, Ximin Luo wrote: > Hey, thanks for this! > > I'd like to ask please upload this (or 15.1) to F-Droid soon. The version > currently in F-Droid is RC-4 and is broken with orwall - > orwall-allowed/redirected apps see no internet, but tor is connected and > orfox can access it. RC-7 fixes this issue, I just tested it out. Yes, will do. Thanks for testing.

1 0

Proposals should have reviews. Let's make sure that happens. Here's a schedule.
by Nick Mathewson 29 Jan '16

29 Jan '16

So, one of the longstanding problems with Tor's (change) proposal system has been that proposals sit around for a long time without sufficient discussion or approval. When they're about to be implemented, we do an informal "hey did anybody look at that?" check, but that's not really good enough. Here's what I've been thinking of doing, as discussed at the tor dev IRC meeting yesterday. 1. Everybody who will review proposals* should nominate one or two proposals currently in state "Open" or "Draft". People should nominate proposals that they themselves didn't write. 2. I'll schedule review & discussion sessions, about one per week, trying to hit times where interested people can make it. Everybody who will review proposals* should try to show up if they can, having read the proposal or proposals under discussion for that week. Then we talk about the proposal(s)! 3. We'll try to move nominated proposals towards "Accepted" or "Rejected", improving them as necessary. * I'm not going to be too elitist here, but: If you show up and contribute usefully to discussions, I will prioritize your nominations more than I will prioritize nominations from people who don't contribute so much. This is a draft process, so we'll try to see after a month or two (possibly at the next face-to-face dev meeting?) how it's going. Here's the schedule I have in mind for the first meeting, based on proposals already nominated at the IRC dev meeting. I'm going to go a bit aggressively for the first couple of weeks, so that we can get a sense of how this process works out. Everything is subject to change. We'll be putting notes online from these meetings. Tuesday January 19: 11am Eastern (1600 UTC) Guard node proposals! We'll be talking about these proposals: Prop#259: New Guard Selection Behaviour [DRAFT] Prop#241: Resisting guard-turnover attacks [DRAFT] Prop#247: Defending Against Guard Discovery Attacks using Vanguards [DRAFT] Friday January 22: 11 am Eastern (1600 UTC) Prop#251: Padding for netflow record resolution reduction [DRAFT] Monday January 25: 8pm Eastern (0100 UTC on Tuesday Jan 26) Prop#250: Random Number Generation During Tor Voting [DRAFT] Friday January 29: 8:30 am eastern (1330 UTC) Prop#252: Single Onion Services [DRAFT] Prop#260: Rendezvous Single Onion Services [DRAFT] Prop#246: Merging Hidden Service Directories and Introduction Points [OPEN] Also nominated are: Prop#264: Putting version numbers on the Tor subprotocols [OPEN] Prop#257: Refactoring authorities and taking parts offline [DRAFT] Prop#258: Denial-of-service resistance for directory authorities [OPEN] -- Nick

8 15

Fwd: [guardian-dev] RC-7 is out - try to repro? Re: towards reproducible Orbot
by Nathan Freitas 29 Jan '16

29 Jan '16

With this release and updates to our build process, we are close to having Orbot be reproducible. Otherwise, this should be the last RC for v15.1, and it now includes built-in Obfs4, Obfs3, Scramblesuit bridges from TBB, plus a few new ones from Nima. This will make it much easier for users in places who need bridges to be able to use them without taking an extra step. ----- Original message ----- From: Nathan of Guardian <nathan(a)guardianproject.info> To: guardian-dev(a)lists.mayfirst.org Subject: [guardian-dev] RC-7 is out - try to repro? Re: towards reproducible Orbot Date: Thu, 28 Jan 2016 10:12:59 -0500 On Wed, Jan 27, 2016, at 10:10 AM, Hans-Christoph Steiner wrote: > >>>>> Then anyone will be able to run this to verify the build: > >>>>> > >>>>> git checkout 15.1.0-RC-4 > >>>>> ./make-release-build > >>>>> ./compare-to-official-release ~/Downloads/Orbot-v15.1.0-RC-4.apk \ > >>>>> bin/Orbot-v15.1.0-RC-4.apk I've just posted RC7 built from make-release-build. I haven't attempted to run the compare script yet, so if someone out there wants to try, that would be great. My bet is that I didn't do something right, and it won't match, but I would love to be proven wrong! APK: https://guardianproject.info/releases/Orbot-v15.1.0-RC-7.apk Sig: https://guardianproject.info/releases/Orbot-v15.1.0-RC-7.apk.asc /** 15.1.0-RC-7 / 27-January-2016 / 91225ab053d0ffec4a414be461ee41e6465446bd **/ * fd45fa3 enable TransProxy and DNSPort by default without root - some users run their own iptables transproxy scripts with AFWall and n /** 15.1.0-RC-6 / 27-January-2016 / a8dbdacbcb2412bb08c4a665145371c3ac4abef1 **/ Fixes to enable/attempt reproducible builds for this release * 226d92e make-release-build: env vars need to be first on the command line * 20c16ae ignore more files generated by the build * 9883a89 faketime is only needed when building, not when cleaning * eaa2dde explicitly indicate we are building armeabi * 1b76c36 add make calls for both armeabi and x86 with clean * 75eb36e remove lib binaries * 3be93a0 only build for x86 and armeabi ...and one small UI bug: 1839b8f add-in missing "break" for Meek Google -- Nathan of Guardian nathan(a)guardianproject.info _______________________________________________ List info: https://lists.mayfirst.org/mailman/listinfo/guardian-dev To unsubscribe, email: guardian-dev-unsubscribe(a)lists.mayfirst.org

2 1

Getting people started on guard selection algorithms [prop259]
by George Kadianakis 29 Jan '16

29 Jan '16

Hello Nick, isis and Mike! It seems like some Thoughtworks folks (from here on referred to as FRITO [0]) are interested in helping us with Tor hidden services development for 4 weeks or so. They start early next week! :) They were looking for a coding project that is tractable within a month given a team of four people. Also, it should be fun, interesting and be related to hidden services. One of the projects we discussed and found potentially fitting was proposal 259: https://gitweb.torproject.org/torspec.git/tree/proposals/259-guard-selectio… It is my undertanding that the next steps here involve implementing the various proposed algorithms and evaluating how they cope in some simulated scenarios. Nick and Isis started working on this in Python here: https://github.com/isislovecruft/guardsim You can find the scenarios that need to be tested here: https://github.com/isislovecruft/guardsim/blob/master/doc/stuff-to-test.txt This project seems quite suitable for the FRITO crew :) The idea here is that after we decide which one is the best algorithm to use, we would implement it for little-t-tor in C. The best algorithm is the one that achieves the greatest reachability and security tradeoff. The algorithm should also be designed in such a way that fits into the tor asynchronous networking API. It would be amazing if FRITO could help us here as well, but maybe we can start up with the Python simulation and see if they like the project! Isis and Nick, are you currently working on the guardsim code? Would you be OK if it was taken over by FRITO? Any advice for them? Also, is there a ticket we should be using for this project? If not, I will make one ASAP. Cheers! [0]: FRITO is derived from their names: Fan, Reinaldo, Ivan, Tania and Ola. They are all CCed. PS: We recently did a reading group about prop259 and a few other proposals that you might find interesting. The minutes can be found here: https://lists.torproject.org/pipermail/tor-dev/2016-January/010265.html and the raw logs here: http://meetbot.debian.net/tor-dev/2016/tor-dev.2016-01-19-16.03.log.html

2 1

Tor not affected by recent openssl security advisories
by Nick Mathewson 29 Jan '16

29 Jan '16

Somebody always asks whether Tor is affected by each OpenSSL advisory, so I'm sending this mail in order to get a URL to send people to. :) Here are today's advisories: https://mta.openssl.org/pipermail/openssl-announce/2016-January/000061.html With respect to the first ( "DH small subgroups (CVE-2016-0701)" ), Tor is not affected because we set the SSL_OP_SINGLE_DH_USE() option. We started setting this option back in Tor 0.1.1.9-alpha, back in 2005. With respect to the second ( "SSLv2 doesn't block disabled ciphers (CVE-2015-3197)" ), Tor is not affected because we disable SSLv2 by setting SSL_OP_NO_SSLv2. We started setting this option in Tor 0.0.2pre8, back in 2003. Of course, other applications that you use over Tor may be affected, even though Tor is not; please remember to upgrade them as patches become available. best wishes, -- Nick

3 3

Proposal 247: Alternate Path Lengths
by Mike Perry 28 Jan '16

28 Jan '16

While discussing proposal 247 with George yesterday, we realized that we still get security benefit from additional ephemeral hops beyond the vanguards themselves. Recall the high-level 247 path design is: C - L - M - S -- S - M - L - H Where: C = Client L = Long lived Layer1 guard M = Medium lifespan Layer2 guard S = Short lifespan Layer3 guard H = Hidden Service (or hsdir) E = Ephemeral Hop (used below) I = Intro Point (used below) R = Rend Point (used below) The benefit to just one more hop is easiest to see in the Introduction Point case, where George and I reasoned that it probably is a good idea to pick an intro point that is not the same as the Layer3 (S) set, otherwise the hidden service is effectively publishing its Layer3 guards in its descriptor, and using those same nodes to connect to rendezvous points. Clients probably also do not want the multi-visit linkability of using their layer3 vanguards to directly connect to an HS intro point. This means the intro circuit becomes: C - L - M - S - E -- I - S - M - L - H Similarly, in the rend case, hidden services probably do not want to expose their Layer3 (S) guards quite so easily to a client's chosen Rendezvous Point, and again, the client probably does not want to use their Layer3 (S) guards as its Rendezvous point, to avoid visit linkability. This means we again have 8 hops for rends: C - L - M - S - R -- E - S - M - L - H Unfortunately, this is starting to get ridiculous. While there are clear security benefits here, I think 8 hops is definitely at the point where we can forget about voice and other interactive traffic behaving reasonably. So what could we cut, if we wanted to? Well, going back to the Prop247 threat model, we want the adversary to perform at least two attacks: a Sybil and one or mode node compromise attacks. So maybe we can (in some cases, or optionally?) eliminate the M nodes from the path. Since the linkability risks may be acceptable for some applications, maybe we can also optionally allow clients or servers to omit the ephemeral hop. This basically gives us three options for path lengths. Let's consider each path type: Hsdir post/fetch: 1. C - L - M - S - E - H 2. C - L - S - E - H 3. C - L - S - H Intro: 1. C - L - M - S - E -- I - S - M - L - H 2. C - L - S - E -- I - S - L - H *3. C - L - S -- I&S - L - H (* IP Intersection attack!) Rend: 1. C - L - M - S - R -- E - S - M - L - H 2. C - L - S - R -- E - S - L - H 3. C - L - R&S -- S - L - H Looking at these, we can see that we sacrifice the middle guards in the second option, which will come at the cost of one less compromise attack (but still the need to compromise the long-lived guard). We also lose the unlinkability in the third option, and this actually bites us in Intro 3: the hidden service L guard can perform a long-term intersection attack, watching for published intro points and matching that to the circuits that H makes to them. So that path length probably should not be used. But what about the others? Especially that Rend case? I really like the security properties of the full 8 hop paths, but it seems to me that for highly-interactive applications, we can provide the option for users to give up some of the unlinkability in exchange for that 4 hop circuit, which might actually allow for e2e hidden service voice and video to have a shot at working. Are there any risks with paths this short for that case? Does it make sense to provide users with these different path length and latency options? I'm thinking that the service could list its preferred path length in its hsdesc, and the client could override that as it chooses (either for more or less security). Is that dangerous? We were already considering letting users choose their guard set sizes. Why not path lengths also (or instead)? -- Mike Perry

3 8

Notes from 3rd Tor proposal reading group [prop250]
by George Kadianakis 27 Jan '16

27 Jan '16

Hello there, yesterday we held another reading group on #tor-dev to discuss proposal 250 (Random Number Generation During Tor Voting). You can find the logs here: http://meetbot.debian.net/tor-dev/2016/tor-dev.2016-01-26-15.58.log.html Here are some code and spec changes that we need to do after discussion with Nick: Code & spec changes: - Remove ed25519 keys from code and spec. - SHA256 -> Keccak - "SUGGESTION: On 3.1.1, wouldn't it just be easier to sort the R_b in ascending order and use them in HASHED_REVEALS?" - "Why does REVEAL put the TS first and COMMIT puts it last? (Still on 4.1.1)" Spec changes: - Specify TIMESTAMP better in spec - Fix base32 commits in proposal - Specify what happens during SRV generation when there is no previous_SRV - Remove the XXX in 3.1.1 since it's taken care of - Document the phase determination logic better. - Remove MUST paragraph from 3.1.2

1 0

Proposal xxx: Filtering malicious rendezvous points at hidden service server side
by s7r 26 Jan '16

26 Jan '16

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hello, Inspired by asn, dgoulet and Mike Perry discussing alternate path lengths for proposal 247, I wrote a proposal that could fit in nicely with proposal 247, maybe even allow us to make the 3rd hop wild (random) so we don't have to worry about HSDirs + HSDir fetch/post circuits and introduction points + introduction points circuits linking short term layer 3 guards. Please find the proposal attached as well as inline for comments. Looking forward for reviews. If I've structured it wrong or something I apologize in advance - will do better next time. Filename: xxx-malicious-rendezvous-point-filter.txt Title: Filtering malicious rendezvous points at hidden service server side Authors: s7r [ 0x837FA52C81265B11 ] Created: 23 January 2016 Status: Draft 0. Definitions client = an user running Tor as a client, which connects to a hidden service. hidden service server = the Tor instance hosting the hidden service. rendezvous point = the relay which acts as the rendezvous meeting point in a circuit between a hidden service client and a hidden service server. 1. Motivation A hidden service circuit (rendezvous circuit) is always initiated by the client so the relay which should act as the rendezvous meeting point is selected by the client. We assume that any client can be an attacker and will try to make the hidden service server connect to a malicious rendezvous point under his control. The attacker is also a Sybil (holds an unknown % of the bandwidth in the Tor network). By making the hidden service server build many circuits to his evil rendezvous points, the attacker gets a high probability that the hidden service server will eventually pick his evil relays in a circuit, so the attacker will trivially perform a successful hidden service guard discovery attack or, with more luck, discover the real location of the hidden service server. The hidden service server can only defend itself by building a 3 hop circuit to the rendezvous point, but in practice this is not always enough. 2. Logic for filtering malicious rendezvous points To be able to make fair assumptions about which rendezvous point might be malicious or not we are going to use the probability theory and statistics, precisely the binominal distribution equation [0]. In simple words, we count and keep track of how many rendezvous circuits a hidden service server built and to which rendezvous points. Then, based on the weight (middle probability fraction) of each rendezvous point, we determine if one was insanely overpicked by clients. Think of this like: Alice plays a game with Bob in which Bob has the success probability to draw a certain number n%. In practice however, he shows a success rate of more than (n*2)% (2 times bigger), Alice assumes Bob is not playing nice and will refuse to play with him for the next 24 hours or so. Fast example: A hidden service server built 100 rendezvous circuits in the last 24 hours, out of which in 7 of them the rendezvous point was a relay with the middle probability fraction of 0.5%. We assume that rendezvous point is malicious and refuse to build rendezvous circuits to it for the next 24 hours. 3. Equations and formulas 3.1 Probability of different clients genuinely picking the same rendezvous point n = total number of established rendezvous circuits. k = number of clients that could have genuinely picked the same rendezvous point. p = probability of picking that rendezvous point per client (middle probability fraction of the relay) divided to 100. H = Probability mass function expanded. C = The result of the equation, the value we need to determine multiplied with 100 to have the percent value. Formulas: H = n! / k!^(n - k)! C = H * p^k * (1 - p)^n - k Example: n = 100 k = 9 p = 0.5% / 100 = 0.005 H = 100! / 9!^91! = 20023492720 C = 20023492720 * 0.000000000000000000001953125 * 0.63372, ~ 0.00000000002478376524710625 * 100, ~ 0.000000002478376524710625% 3.2 Expected number of clients to pick the same rendezvous point n = Total number of established rendezvous circuits. p = Probability of picking that rendezvous point per client (middle probability fraction of the relay) divided to 100. We multiply this with 2 intentionally so we will allow 2 times more circuits than we would expect based on this formula - this should reduce the error margin enough. C = The result of the equation, the value we need to determine. Formula: C = n * p Example: n = 100 p = 0.5% / 100 = 0.005 * 2 = 0.01 C = 100 * 0.01 = 1 4. Implementation and variables We keep track in the persistent state of a hidden service server of the total number of built rendezvous circuits as well as a counter for number of rendezvous circuits per rendezvous point. Variables: REND_FILTER_MONITOR_PERIOD = count and track the rendezvous circuits built within this latest period. We set it to 24 hours. REND_FILTER_BAN_PERIOD = for how long we are going to ban a malicious rendezvous point. We set it to 24 hours. REND_FILTER_TOLERANCE = how many circuits we allow per rendezvous point regardless of its middle probability fraction. We set it to 4. REND_FILTER_BAN_ACTIVATION = when we should ban a malicious rendezvous point. To determine this, we are going to get from REND_FILTER_MONITOR_PERIOD the total number of established rendezvous circuits as well as the number of established rendezvous circuits with a given rendezvous point and apply the formula from 3.2 with approximation to the next whole number (example: 5.01 = 6; 5.99 = 6). Example: A hidden service server built 100 circuits in the last 24 hours out of which 5 to a rendezvous point with the middle probability fraction 1% (p = 0.02), so the expected number of circuits we expect is 2, but allow up to maximum 4 (if REND_FILTER_TOLERANCE > REND_FILTER_BAN_ACTIVATION, REND_FILTER_TOLERANCE prevails). In this case we consider this too much of a coincidence and ban this rendezvous point for the next 24 hours. We keep this ban in our persistent state with a timestamp so we'll know when it expires. 5. Ban malicious rendezvous points just for rendezvous circuits, not for anything else If we treat as relay as a malicious rendezvous point for a given time period, this only means we are not building circuits with it as the rendezvous point, but we don't exclude it for other purpose circuits, regardless which are those other purpose circuits. We may use them in our exit circuits, consensus fetch circuits, as HSDirs and HSDir fetch / post circuits, as Introduction Points or Introduction Point circuits. 6. Non zero probability to assign the malicious rendezvous point flag to an innocent relay This is indeed a non-zero value and it can be computed with the formula from 3.1, but it's a value so close to zero that we think it's totally worth it. Even if accidentally (low chances) an innocent relay will be banned, this will be something local to the hidden service server. It won't affect that relay at all, nor how other client or hidden service servers treat that relay. It has nothing to do with the network wide consensus as well. A honest client will always retry with a different rendezvous point, so honest clients should not experience reachability issues. 7. Rendezvous points that aren't included in hidden service server's consensus Clients and hidden service servers might have different consensuses. This means that a hidden service server can be genuinely asked to build a rendezvous circuit to a rendezvous point for which it has no middle probability fraction because it's not included in that consensus. We should allow REND_FILTER_TOLERANCE number of circuits to the rendezvous points for which we have no weights at all and if that rendezvous point appears in a later consensus within the REND_FILTER_MONITOR_PERIOD update its middle probability fraction value to ensure the filter will activate and work properly once REND_FILTER_TOLERANCE threshold was reached. 8. Security implications for maintaining such records in the persistent state of a hidden service server An attacker which compromises the location of a hidden service server will access this additional information: total number of rendezvous circuits built within the last REND_FILTER_MONITOR_PERIOD and to which rendezvous points these circuits were. This tradeoff should be worth it as well, since if the location of a hidden service server is compromised it is game over anyway, and this additional information shouldn't be so important to the attacker, except maybe for better determining the popularity of that hidden service (this can be determined many other ways, like the logs from the application running behind the hidden service, network counter, datacenter/ISP level counters and logs, etc.). To avoid co-location linkability between different hidden services, we should keep rendezvous circuits records and counters individually for each hidden service. The logic is designed to adjust by itself dynamically, based on the popularity and usage of a hidden service. If it's a high profile hidden service, experiencing 10000 connections per 24 hours, the REND_FILTER_BAN_ACTIVATION will increase for every rendezvous point. 9. Default option, with possibility to turn off for testing environments and experiments We add a new torrc option named HiddenServiceRendFilter 0|1 and set it to 1 by default. It can be turned off by setting it to 0, if this will be desired in some testing environments or experiments. 10. Other considerations, limitations and compatibility with other existing proposals This proposal won't disable an attacker entirely, but it will make it much harder and more expensive, given that the attacker will have to run more malicious relays to act as rendezvous points, increasing the capacity of the Tor network overall and directly the costs of the attack. Also, the attacker will have to grow the popularity of a hidden service so that he can establish more rendezvous circuits using the same rendezvous points. This will at least be kind of hard if other genuine clients pick the same rendezvous points and get noisy to the hidden service operator (much more traffic, same number or slightly more users on his service). This proposal is compatible with all the other hidden service related proposals to date. For tools like OnionBalance, each backend / fallback Tor instance included in the master hidden service descriptor will just transparently and individually maintain their own tracking vales and ban list. With proposal 260 - Rendezvous Single Onion Services this should be disabled since it makes no sense. Set HiddenServiceRendFilter 0 in a RSOS type hidden service. This proposal should be quite helpful once we implement enough padding between relays, where an attacker might have to own the entire path in order to distinguish dummy traffic from real traffic. This proposal should fit in nicely with proposal 247 - Vanguards and could make it safe to leave the 3rd hop wild (no layer 3 short term guards) and use only layer 2 medium term guards + layer 1 long term guard since an attacker will be able to establish less circuits to his malicious rendezvous point, thus drastically decreasing the chances of the hidden service server to also pick his malicious relay as 3rd hop to the malicious rendezvous point (layer 2 guards discovery). [0]: https://en.wikipedia.org/wiki/Binomial_distribution -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (MingW32) iQEcBAEBCAAGBQJWo/K4AAoJEIN/pSyBJlsRAnMIAKFDDFm0DICrog1JecmrO82y N7dJf6tDURjGkUTr5i+mf91S4gTvxYigkT/tWTPH2E65XQGl2qLXo4d1+vgfaJmf H7QxUFy2kt+oFV03pg7SsF1KlMLaIVjlPMC17hPjAL8wnLMPkTICUn+VqWVYqmq+ w4uFPncm42mhkd3EwRq3HCrwq4O7PasWfSBYXmAuIJl6CWDkZqBI+UUj56dqQG6c zpWUMIZpfaMQzEJ438VhpVpiN19Ep5hIV5dJfz4MJ9eyhyas487nRXYyirEWqBs0 VXUsb/m/wgHICLjLukNYJ/+NZUk+Y5mIhL756HIiYUlL8UK85MaJhbozvjhqLnw= =tMjA -----END PGP SIGNATURE-----

5 13