- tor-dev - lists.torproject.org

Bandwidth Authority Progress
by teor 19 Dec '17

19 Dec '17

Hi asn, Original Subject: Re: [tor-project] Meeting notes, network team meeting, 18 Dec > On 19 Dec 2017, at 07:28, Nick Mathewson <nickm(a)torproject.org> wrote: > > - Met with David Stainton, Moritz and others. Talked about relay load > balancing and bandwidth dirauths. People are sad about the state of the > network: some relays are overloaded while others idle, many overloaded > relays cant even establish circuits to each other. Need to do something > about it: deploy bwscanner and start thinking about peerflow. What about > isis' bridge bandwidth scanner? Can you tell us a bit more about this meeting? What can people do if they want to be involved? When is the next meeting, or how can people find out about it? T -- Tim / teor PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n ------------------------------------------------------------------------

5 5

Tor and (open) SDN
by neutron 19 Dec '17

19 Dec '17

Hello tor developers, I'm neutron a Tor user and operator of some hidden-services. During the next year I will write my master thesis about a software defined network related project. Currently I'm thinking about which research topic I could choose and Tor came up to my mind. I'm interested in getting to know what's out there and if there are any approaches to combine Tor and open SDN*? And what would help to research in that area to support the tor project? I already came across: https://shadow.github.io/ I will be around at 34c3 and would love to have a chat about interesting approaches, projects and ideas. Thank you for your time :) cheers neutron * If I get the SDN terms right, tor is an overlay SDN. I would like to think in the direction to combine tor with Open SDN.

1 0

Help Wanted: Fallback Directory Update
by teor 19 Dec '17

19 Dec '17

(You might have already read this email on a closed list. I'm re-posting it here, with an extra "step 0".) Hi all, Fallback directory mirrors help clients reach the Tor network. We need to rebuild the list every so often when their details change. (We have an automated check for 25% failure, and it just triggered.) Does anyone want to help me do this? It would be nice to get it done this month - but it's not urgent. Here's what needs to be done in detail: 0. Ask operators to opt-in stable relays as fallback directory mirrors If they are on the whitelist already, they don't need to do anything. Ticket: https://trac.torproject.org/projects/tor/ticket/22527 File: https://gitweb.torproject.org/tor.git/tree/scripts/maint/fallback.whitelist 1. Update the fallback whitelist with new and changed relay details Tickets: https://trac.torproject.org/projects/tor/ticket/22321 https://trac.torproject.org/projects/tor/ticket/22527 File: tor/scripts/maint/fallback.whitelist 2. Update updateFallbackDirs.py to have a CONSENSUS_EXPIRY_TOLERANCE of 0. Ticket: https://trac.torproject.org/projects/tor/ticket/20942 File: tor/scripts/maint/updateFallbackDirs.py 3. Run updateFallbackDirs.py with the new whitelist and CONSENSUS_EXPIRY_TOLERANCE. You'll need a decent network connection for this. Please attach the script logs to the trac ticket. Command: tor/scripts/maint/updateFallbackDirs.py > src/or/fallback_dirs.inc 4. Write a changes file Ticket: https://trac.torproject.org/projects/tor/ticket/22271 Draft: o Minor features (fallback directory list): - Replace the 151 fallbacks originally introduced in Tor 0.3.1.3-alpha in May 2017 (of which ~111 were still functional) with a list of NNN fallbacks (NNN new, NNN unchanged, NNN removed) generated in December 2017. Resolves ticket 22271. There are some commands that count fallback changes here: https://trac.torproject.org/projects/tor/wiki/doc/UpdatingFallbackDirectory… 5. Announce the new list on tor-relays@ 6. Tell the relay search maintainer that the list has changed Next Time: I'd like to make the process quicker and easier next time. But I don't want to make any big changes to it at the moment. Let's do that when we have time to try different things. T > On 7 Dec 2017, at 11:57, atagar(a)torproject.org wrote: > > 40/151 (26%) fallback directories have become slow or unresponsive... > > (snip) -- Tim / teor PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n ------------------------------------------------------------------------

1 2

Proposal 288: Privacy-Preserving Statistics with Privcount in Tor (Shamir version)
by Nick Mathewson 14 Dec '17

14 Dec '17

Filename: 288-privcount-with-shamir.txt Title: Privacy-Preserving Statistics with Privcount in Tor (Shamir version) Author: Nick Mathewson, Tim Wilson-Brown, Aaron Johnson Created: 1-Dec-2017 Supercedes: 280 Status: Draft 0. Acknowledgments Tariq Elahi, George Danezis, and Ian Goldberg designed and implemented the PrivEx blinding scheme. Rob Jansen and Aaron Johnson extended PrivEx's differential privacy guarantees to multiple counters in PrivCount: https://github.com/privcount/privcount/blob/master/README.markdown#research… Rob Jansen and Tim Wilson-Brown wrote the majority of the experimental PrivCount code, based on the PrivEx secret-sharing variant. This implementation includes contributions from the PrivEx authors, and others: https://github.com/privcount/privcount/blob/master/CONTRIBUTORS.markdown This research was supported in part by NSF grants CNS-1111539, CNS-1314637, CNS-1526306, CNS-1619454, and CNS-1640548. The use of a Shamir secret-sharing-based approach is due to a suggestion by Aaron Johnson (iirc); Carolin Zöbelein did some helpful analysis here. Aaron Johnson and Tim Wilson-Brown made improvements to the draft proposal. 1. Introduction and scope PrivCount is a privacy-preserving way to collect aggregate statistics about the Tor network without exposing the statistics from any single Tor relay. This document describes the behavior of the in-Tor portion of the PrivCount system. It DOES NOT describe the counter configurations, or any other parts of the system. (These will be covered in separate proposals.) 2. PrivCount overview Here follows an oversimplified summary of PrivCount, with enough information to explain the Tor side of things. The actual operation of the non-Tor components is trickier than described below. In PrivCount, a Data Collector (DC, in this case a Tor relay) shares numeric data with N different Tally Reporters (TRs). (A Tally Reporter performs the summing and unblinding roles of the Tally Server and Share Keeper from experimental PrivCount.) All N Tally Reporters together can reconstruct the original data, but no (N-1)-sized subset of the Tally Reporters can learn anything about the data. (In reality, the Tally Reporters don't reconstruct the original data at all! Instead, they will reconstruct a _sum_ of the original data across all participating relays.) In brief, the system works as follow: To share data, for each counter value V to be shared, the Data Collector first adds Gaussian noise to V in order to produce V', uses (K,N) Shamir secret-sharing to generate N shares of V' (K<=N, K being the reconstruction threshold), encrypts each share to a different Tally Reporter, and sends each encrypted share to the Tally Reporter it is encrypted for. The Tally Reporters then agree on the set S of Data Collectors that sent data to all of them, and each Tally Reporter forms a share of the aggregate value by decrypting the shares it received from the Data Collectors in S and adding them together. The Tally Reporters then, collectively, perform secret reconstruction, thereby learning the sum of all the different values V'. The use of Shamir secret sharing lets us survive up to N-K crashing TRs. Waiting until the end to agree on a set S of surviving relays lets us survive an arbitrary number of crashing DCs. In order to prevent bogus data from corrupting the tally, the Tally Reporters can perform the aggregation step multiple times, each time proceeding with a different subset of S and taking the median of the resulting values. Relay subsets should be chosen at random to avoid relays manipulating their subset membership(s). If an shared random value is required, all relays must submit their results, and then the next revealed shared random value can be used to select relay subsets. (Tor's shared random value can be calculated as soon as all commits have been revealed. So all relay results must be received *before* any votes are cast in the reveal phase for that shared random value.) Below we describe the algorithm in more detail, and describe the data format to use. 3. The algorithm All values below are B-bit integers modulo some prime P; we suggest B=62 and P = 2**62 - 2**30 - 1 (hex 0x3fffffffbfffffff). The size of this field is an upper limit on the largest sum we can calculate; it is not a security parameter. There are N Tally Reporters: every participating relay must agree on which N exist, and on their current public keys. We suggest listing them in the consensus networkstatus document. All parties must also agree on some ordering the Tally Reporters. Similarly, all parties must also agree on some value K<=N. There are a number of well-known "counters", identified known by ASCII identifiers. Each counter is a value that the participating relays will know how to count. Let C be the number of counters. 3.1. Data Collector (DC) side At the start of each period, every Data Collector ("client" below) initializes their state as follows 1. For every Tally Reporter with index i, the client constructs a random 32-byte random value SEED_i. The client then generates a pseudorandom bitstream of C*B bits using the SHAKE-256 XOF with SEED_i as its input, and divides this stream into C values, with the c'th value denoted by MASK(i, c). [Because P is very close to a power of 2, nearly all seeds will produce MASK values in range 0...(P-1). If any does not, the client picks a new seed.] 2. The client encrypts SEED_i using the public key of Tally Reporter i, and remembers this encrypted value. It discards SEED_i. 3. For every counter c, the client generates a noise value Z_c from an appropriate Gaussian distribution. If the noise value is negative, the client adds P to bring Z_c into the range 0...(P-1). (The noise MUST be sampled using the procedure in Appendix C.) The client then uses Shamir secret sharing to generate N shares (x,y) of Z_c, 1 <= x <= N, with the x'th share to be used by the x'th Tally Reporter. See Appendix A for more on Shamir secret sharing. See Appendix B for another idea about X coordinates. The client picks a random value CTR_c and stores it in the counter, which serves to locally blind the counter. The client then subtracts (MASK(x, c)+CTR_c) from y, giving "encrypted shares" of (x, y0) where y0 = y-CTR_c. The client then discards all MASK values, all CTR values, and all original shares (x,y), all CTR and the noise value Z_c. For each counter c, it remembers CTR_c, and N shares of the form (x, y). To increment a counter by some value "inc": 1. The client adds "inc" to counter value, modulo P. (This step is chosen to be optimal, since it will happen more frequently than any other step in the computation.) Aggregate counter values that are close to P/2 MUST be scaled to avoid overflow. See Appendix D for more information. (We do not think that any counters on the current Tor network will require scaling.) To publish the counter values: 1. The client publishes, in the format described below: The list of counters it knows about The list of TRs it knows about For each TR: For each counter c: A list of (i, y-CTR_c-MASK(x,c)), which corresponds to the share for the i'th TR of counter c. SEED_i as encrypted earlier to the i'th TR's public key. 3.2. Tally Reporter (TR) side This section is less completely specified than the Data Collector's behavior: I expect that the TRs will be easier to update as we proceed. (Each TR has a long-term identity key (ed25519). It also has a sequence of short-term curve25519 keys, each associated with a single round of data collection.) 1. When a group of TRs receives information from the Data Collectors, they collectively chose a set S of DCs and a set of counters such that every TR in the group has a valid entry for every counter, from every DC in the set. To be valid, an entry must not only be well-formed, but must also have the x coordinate in its shares corresponding to the TR's position in the list of TRs. 2. For each Data Collector's report, the i'th TR decrypts its part of the client's report using its curve25519 key. It uses SEED_i and SHAKE-256 to regenerate MASK(0) through MASK(C-1). Then for each share (x, y-CTR_c-MASK(x,c)) (note that x=i), the TR reconstructs the true share of the value for that DC and counter c by adding V+MASK(x,c) to the y coordinate to yield the share (x, y_final). 3. For every counter in the set, each TR computes the sum of the y_final values from all clients. 4. For every counter in the set, each TR publishes its a share of the sum as (x, SUM(y_final)). 5. If at least K TRs publish correctly, then the sum can be reconstructed using Lagrange polynomial interpolation. (See Appendix A). 6. If the reconstructed sum is greater than P/2, it is probably a negative value. The value can be obtained by subtracting P from the sum. (Negative values are generated when negative noise is added to small signals.) 7. If scaling has been applied, the sum is scaled by the scaling factor. (See Appendix D.) 4. The document format 4.1. The counters document. This document format builds on the line-based directory format used for other tor documents, described in Tor's dir-spec.txt. Using this format, we describe a "counters" document that publishes the shares collected by a given DC, for a single TR. The "counters" document has these elements: "privctr-dump-format" SP VERSION SP SigningKey [At start, exactly once] Describes the version of the dump format, and provides an ed25519 signing key to identify the relay. The signing key is encoded in base64 with padding stripped. VERSION is "alpha" now, but should be "1" once this document is finalized. "starting-at" SP IsoTime [Exactly once] The start of the time period when the statistics here were collected. "ending-at" SP IsoTime [Exactly once] The end of the time period when the statistics here were collected. "share-parameters" SP Number SP Number [Exactly once] The number of shares needed to reconstruct the client's measurements (K), and the number of shares produced (N), respectively. "tally-reporter" SP Identifier SP Integer SP Key [At least twice] The curve25519 public key of each Tally Reporter that the relay believes in. (If the list does not match the list of participating Tally Reporters, they won't be able to find the relay's values correctly.) The identifiers are non-space, non-nul character sequences. The Key values are encoded in base64 with padding stripped; they must be unique within each counters document. The Integer values are the X coordinate of the shares associated with each Tally Reporter. "encrypted-to-key" SP Key [Exactly once] The curve25519 public key to which the report below is encrypted. Note that it must match one of the Tally Reporter options above. "report" NL "----- BEGIN ENCRYPTED MESSAGE-----" NL Base64Data "----- END ENCRYPTED MESSAGE-----" NL [Exactly once] An encrypted document, encoded in base64. The plaintext format is described in section 4.2. below. The encryption is as specified in section 5 below, with STRING_CONSTANT set to "privctr-shares-v1". "signature" SP Signature [At end, exactly once] The Ed25519 signature of all the fields in the document, from the first byte, up to but not including the "signature" keyword here. The signature is encoded in base64 with padding stripped. 4.2. The encrypted "shares" document. The shares document is sent, encrypted, in the "report" element above. Its plaintext contents include these fields: "encrypted-seed" NL "----- BEGIN ENCRYPTED MESSAGE-----" NL Base64Data "----- END ENCRYPTED MESSAGE-----" NL [At start, exactly once.] An encrypted document, encoded in base64. The plaintext value is the 32-byte value SEED_i for this TR. The encryption is as specified in section 5 below, with STRING_CONSTANT set to "privctr-seed-v1". "d" SP Keyword SP Integer [Any number of times] For each counter, the name of the counter, and the obfuscated Y coordinate of this TR's share for that counter. (The Y coordinate is calculated as y-CTR_c as in 3.1 above.) The order of counters must correspond to the order used when generating the MASK() values; different clients do not need to choose the same order. 5. Hybrid encryption This scheme is taken from rend-spec-v3.txt, section 2.5.3, replacing "secret_input" and "STRING_CONSTANT". It is a hybrid encryption method for encrypting a message to a curve25519 public key PK. We generate a new curve25519 keypair (sk,pk). We run the algorithm of rend-spec-v3.txt 2.5.3, replacing "secret_input" with Curve25519(sk,PK) | SigningKey, where SigningKey is the DC's signing key. (Including the DC's SigningKey here prevents one DC from replaying another one's data.) We transmit the encrypted data as in rend-spec-v3.txt 2.5.3, prepending pk. Appendix A. Shamir secret sharing for the impatient In Shamir secret sharing, you want to split a value in a finite field into N shares, such that any K of the N shares can reconstruct the original value, but K-1 shares give you no information at all. The key insight here is that you can reconstruct a K-degree polynomial given K+1 distinct points on its curve, but not given K points. So, to split a secret, we going to generate a (K-1)-degree polynomial. We'll make the Y intercept of the polynomial be our secret, and choose all the other coefficients at random from our field. Then we compute the (x,y) coordinates for x in [1, N]. Now we have N points, any K of which can be used to find the original polynomial. Moreover, we can do what PrivCount wants here, because adding the y coordinates of N shares gives us shares of the sum: If P1 is the polynomial made to share secret A and P2 is the polynomial made to share secret B, and if (x,y1) is on P1 and (x,y2) is on P2, then (x,y1+y2) will be on P1+P2 ... and moreover, the y intercept of P1+P2 will be A+B. To reconstruct a secret from a set of shares, you have to either go learn about Lagrange polynomials, or just blindly copy a formula from your favorite source. Here is such a formula, as pseudocode^Wpython, assuming that each share is an object with a _x field and a _y field. def interpolate(shares): for sh in shares: product_num = FE(1) product_denom = FE(1) for sh2 in shares: if sh2 is sh: continue product_num *= sh2._x product_denom *= (sh2._x - sh._x) accumulator += (sh._y * product_num) / product_denom return accumulator Appendix B. An alternative way to pick X coordinates Above we describe a system where everybody knows the same TRs and puts them in the same order, and then does Shamir secret sharing using "x" as the x coordinate for the x'th TR. But what if we remove that requirement by having x be based on a hash of the public key of the TR? Everything would still work, so long as all users chose the same K value. It would also let us migrate TR sets a little more gracefully. Appendix C. Sampling floating-point Gaussian noise for differential privacy Background: When we add noise to a counter value (signal), we want the added noise to protect all of the bits in the signal, to ensure differential privacy. But because noise values are generated from random double(s) using floating-point calculations, the resulting low bits are not distributed evenly enough to ensure differential privacy. As implemented in the C "double" type, IEEE 754 double-precision floating-point numbers contain 53 significant bits in their mantissa. This means that noise calculated using doubles can not ensure differential privacy for client activity larger than 2**53: * if the noise is scaled to the magnitude of the signal using multiplication, then the low bits are unprotected, * if the noise is not scaled, then the high bits are unprotected. But the operations in the noise transform also suffer from floating-point inaccuracy, further affecting the low bits in the mantissa. So we can only protect client activity up to 2**46 with Laplacian noise. (We assume that the limit for Gaussian noise is similar.) Our noise generation procedure further reduces this limit to 2**42. For byte counters, 2**42 is 4 Terabytes, or the observed bandwidth of a 1 Gbps relay running at full speed for 9 hours. It may be several years before we want to protect this much client activity. However, since the mitigation is relatively simple, we specify that it MUST be implemented. Procedure: Data collectors MUST sample noise as follows: 1. Generate random double(s) in [0, 1] that are integer multiples of 2**-53. TODO: the Gaussian transform in step 2 may require open intervals 2. Generate a Gaussian floating-point noise value at random with sigma 1, using the random double(s) generated in step 1. 3. Multiply the floating-point noise by the floating-point sigma value. 4. Truncate the scaled noise to an integer to remove the fractional bits. (These bits can never correspond to signal bits, because PrivCount only collects integer counters.) 5. If the floating-point sigma value from step 3 is large enough that any noise value could be greater than or equal to 2**46, we need to randomise the low bits of the integer scaled noise value. (This ensures that the low bits of the signal are always hidden by the noise.) If we use the sample_unit_gaussian() transform in nickm/privcount_nm: A. The maximum r value is sqrt(-2.0*ln(2**-53)) ~= 8.57, and the maximal sin(theta) values are +/- 1.0. Therefore, the generated noise values can be greater than or equal to 2**46 when the sigma value is greater than 2**42. B. Therefore, the number of low bits that need to be randomised is: N = floor(sigma / 2**42) C. We randomise the lowest N bits of the integer noise by replacing them with a uniformly distributed N-bit integer value in 0...(2**N)-1. 6. Add the integer noise to the integer counter, before the counter is incremented in response to events. (This ensures that the signal value is always protected.) This procedure is security-sensitive: changing the order of multiplications, truncations, or bit replacements can expose the low or high bits of the signal or noise. As long as the noise is sampled using this procedure, the low bits of the signal are protected. So we do not need to "bin" any signals. The impact of randomising more bits than necessary is minor, but if we fail to randomise an unevenly distributed bit, client activity can be exposed. Therefore, we choose to randomise all bits that could potentially be affected by floating-point inaccuracy. Justification: Although this analysis applies to Laplacian noise, we assume a similar analysis applies to Gaussian noise. (If we add Laplacian noise on DCs, the total ends up with a Gaussian distribution anyway.) TODO: check that the 2**46 limit applies to Gaussian noise. This procedure results in a Gaussian distribution for the higher ~42 bits of the noise. We can safely ignore the value of the lower bits of the noise, because they are insignificant for our reporting. This procedure is based on section 5.2 of: "On Significance of the Least Significant Bits For Differential Privacy" Ilya Mironov, ACM CCS 2012 https://www.microsoft.com/en-us/research/wp-content/uploads/2012/10/lsbs.pdf We believe that this procedure is safe, because we neither round nor smooth the noise values. The truncation in step 4 has the same effect as Mironov's "safe snapping" procedure. Randomising the low bits removes the 2**46 limit on the sigma value, at the cost of departing slightly from the ideal infinite-precision Gaussian distribution. (But we already know that these bits are distributed poorly, due to floating-point inaccuracy.) Mironov's analysis assumes that a clamp() function is available to clamp large signal and noise values to an infinite floating-point value. Instead of clamping, PrivCount's arithmetic wraps modulo P. We believe that this is safe, because any reported values this large will be meaningless modulo P. And they will not expose any client activity, because "modulo P" is an arithmetic transform of the summed noised signal value. Alternatives: We could round the encrypted value to the nearest multiple of the unprotected bits. But this relies on the MASK() value being a uniformly distributed random value, and it is less generic. We could also simply fail when we reach the 2**42 limit on the sigma value, but we do not want to design a system with a limit that low. We could use a pure-integer transform to create Gaussian noise, and avoid floating-point issues entirely. But we have not been able to find an efficient pure-integer Gaussian or Laplacian noise transform. Nor do we know if such a transform can be used to ensure differential privacy. Appendix D. Scaling large counters We do not believe that scaling will be necessary to collect PrivCount statistics in Tor. As of November 2017, the Tor network advertises a capacity of 200 Gbps, or 2**51 bytes per day. We can measure counters as large as ~2**61 before reaching the P/2 counter limit. If scaling becomes necessary, we can scale event values (and noise sigmas) by a scaling factor before adding them to the counter. Scaling may introduce a bias in the final result, but this should be insignificant for reporting. Appendix Z. Remaining client-side uncertainties [These are the uncertainties at the client side. I'm not considering TR-only operations here unless they affect clients.] Should we do a multi-level thing for the signing keys? That is, have an identity key for each TR and each DC, and use those to sign short-term keys? How to tell the DCs the parameters of the system, including: - who the TRs are, and what their keys are? - what the counters are, and how much noise to add to each? - how do we impose a delay when the noise parameters change? (this delay ensures differential privacy even when the old and new counters are compared) - or should we try to monotonically increase counter noise? - when the collection intervals start and end? - what happens in networks where some relays report some counters, and other relays report other counters? - do we just pick the latest counter version, as long as enough relays support it? (it's not safe to report multiple copies of counters) How the TRs agree on which DCs' counters to collect? How data is uploaded to DCs? What to say about persistence on the DC side?

3 4

IPv6 and v3 onion services
by teor 14 Dec '17

14 Dec '17

Hi David (and others interested in IPv6), We want to add better IPv6 support to Tor relays, clients, and v3 onion services. But if we do IPv6 v3 onion services first, the hop before intro and rend points will know that the circuit is a v3 onion service circuit, because its EXTEND2 cells will have an IPv6 address. So I suggest that we implement IPv6 support in this order: IPv6 single onion services (at any time, only uses direct IPv6 CREATE) IPv6 relay extends IPv6 relay reachability (provides cover traffic for IPv6 client extends) IPv6 client extends for exit circuits IPv6 client extends for multi-hop onion service circuits I've added this to an "Overview" section in: https://trac.torproject.org/projects/tor/wiki/org/roadmaps/Tor/IPv6Features I also like the idea of testing and deploying our IPv6 code on relays first. It's less risky than experimenting on clients or onion services. And our relay operators give us some excellent bug reports. And we can re-use some of the common code from the relay implementation in the client and onion service implementations. (For example, we'll write code that handles link specifiers.) Also, if we get IPv6 relay reachability checks working, that makes it easier to automatically configure IPv6 on relays. More IPv6 relays will make the anonymity set larger for IPv6 clients. What do you think? T

2 5

Proposal 249 updated
by isis agora lovecruft 14 Dec '17

14 Dec '17

Hi all! I've revised prop#249 (I think) according to the discussion from [0,1,2,3]. The revised proposal is in torspec, [4] but for convenience it's included inline below. Please review and hopefully catch any dumb mistakes I made. It looks like implementing this is going to be a bit of a chore, so I'm guessing it would be better to target 0.3.4.x than 0.3.3.x? [0]: https://lists.torproject.org/pipermail/tor-dev/2017-December/012665.html [1]: https://lists.torproject.org/pipermail/tor-dev/2017-December/012688.html [2]: http://meetbot.debian.net/tor-meeting/2017/tor-meeting.2017-12-13-22.03.html [3]: https://pad.riseup.net/p/r.1c4c37baa9251fdfca5a1e1bd5c01f45 [4]: https://gitweb.torproject.org/torspec.git/tree/proposals/249-large-create-c… Best regards, -- ♥Ⓐ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt Filename: 249-large-create-cells.txt Title: Allow CREATE cells with >505 bytes of handshake data Authors: Nick Mathewson, Isis Lovecruft Created: 23 July 15 Updated: 13 December 2017 Status: Open 1. Summary There have been multiple proposals over the last year or so for adding post-quantum cryptography to Tor's circuit extension handshakes. (See for example https://eprint.iacr.org/2015/008 or https://eprint.iacr.org/2015/287 .) These proposals share the property that the request and reply for a handshake message do not fit in a single RELAY cell. In this proposal I describe a new CREATE2V cell for handshakes that don't fit in a 505-byte CREATE2 cell's HDATA section, and a means for fragmenting these CREATE2V cells across multiple EXTEND2 cells. I also discuss replies, migration, and DoS-mitigation strategies. 2. CREATE2V and CREATED2V First, we add two variable-width cell types, CREATE2V and CREATED2V. These cell formats are nearly the same as CREATE2 and CREATED2. (Here specified using Trunnel.) struct create2v_cell_body { /* Handshake type */ u16 htype; /* Length of handshake data */ u16 hlen; /* Handshake data */ u8 hdata[hlen]; /* Padding data to be ignored */ u8 ignored[]; }; struct created2v_cell_body { /* Handshake reply length */ u16 hlen; /* Handshake reply data */ u8 hdata[hlen]; /* Padding data to be ignored */ u8 ignored[]; }; The 'ignored' fields, which extend to the end of the variable-length cells, are reserved. Initiators MAY set them to any length, and MUST fill them with either zero-valued bytes or pseudo-random bytes. Responders MUST ignore them, regardless of what they contain. When a CREATE2V cell is generated in response to a set of EXTEND2 cells, these fields are set by the relay that receives the EXTEND2 cells. (The purpose of the 'ignored' fields here is future-proofing and padding.) Protocols MAY wish to pad to a certain multiple of bytes, or wish to pad the initiator/receiver payloads to be of equal length. This is encouraged but NOT REQUIRED. 3. Fragmented EXTEND2 cells Without changing the current EXTEND2 cell format, we change its semantics: If the 'HLEN' field in an EXTEND2 cell describes a handshake data section that would be too long to fit in the EXTEND2 cell's payload, the handshake data of the EXTEND2 cell is to be continued in one or more subsequent EXTEND2 cells. These subsequent cells MUST have zero link specifiers, handshake type 0xFFFF, and handshake data length field set to zero. Similarly, if the 'HLEN' field in an EXTENDED2 cell would be too long to fit into the EXTENDED2 cell's payload, the handshake reply data of the EXTENDED2 cell is to be continued in one or more subsequent EXTENDED2 cells. These subsequent cells must have the handshake data length field set to zero. These cells must be sent on the circuit with no intervening cells. If any intervening cells are received, the receiver SHOULD destroy the circuit. Protocols which make use of CREATE(D)2V cells SHOULD send an equal number of cells in either direction, to avoid trivially disclosing information about the direction of the circuit: for example a relay might use the fact that it saw five EXTEND2 cells in one direction and three in the other to easily determine whether it is the middle relay on the onion service-side or the middle relay on the client-side of a rendezvous circuit. 4. Interacting with RELAY_EARLY cells The first EXTEND2 cell in a batch must arrive in a RELAY_EARLY cell. The others MAY arrive in RELAY_EARLY cells. For many handshakes, for the possible lengths of many types of circuits, sending all EXTEND2 cells inside RELAY_EARLY cells will not be possible. For example, for a fragmented EXTEND2 cell with parts A B C D E, A is the only fragment that MUST be sent within a RELAY_EARLY. For parts B C D E, these are merely sent as EXTEND2{CREATE2V} cells. Note that this change leaks the size of the handshake being used to intermediate relays. We should analyze this and see whether it matters. Clients and relays MAY send RELAY_DROP cells during circuit construction in order to hide the true size of their handshakes (but they can't send these drop cells inside a train of EXTEND2 or EXTENDED2 cells for a given handshake). 5. Example So for example, if we are a client, and we need to send a 2000-byte handshake to extend a circuit from relay X to relay Y, we might send cells as follows: EXTEND2 { nspec = 2; lstype = [0x01 || 0x02]; (IPv4 or IPv6 node address) lslen = [0x04 || 0x16]; lspec = { node address for Y, taking 8 bytes or 16 bytes}; lstype = 0x03; (An ed25519 node identity) lslen = 32; lspen = { ed25519 node ID for Y, taking 32 bytes } htype = {whatever the handshake type is.} hlen = 2000 hdata = { the first 462 bytes of the handshake } } EXTEND2 { nspec = 0; htype = 0xffff; hlen = 0; hdata = { the next 492 bytes of the handshake } } EXTEND2 { nspec = 0; htype = 0xffff; hlen = 0; hdata = { the next 492 bytes of the handshake } } EXTEND2 { nspec = 0; htype = 0xffff; hlen = 0; hdata = { the next 492 bytes of the handshake } } EXTEND2 { nspec = 0; htype = 0xffff; hlen = 0; hdata = { the final 62 bytes of the handshake } } Upon receiving this last cell, the relay X would send a create2v cell to Y, containing the entire handshake. 6. Migration We can and should implement the EXTEND2 fragmentation feature before we implement anything that uses it. If we can get it widely deployed before it's needed, we can use the new handshake types whenever both of the involved relays support this proposal. Clients MUST NOT send fragmented EXTEND2 cells to relays that don't support them, since this would cause them to close the circuit. Relays MAY send CREATE2V and CREATED2V cells to relays that don't support them, since unrecognized cell types are ignored. 6.1. New Subprotocols and Subprotocol Versions This proposal introduces, following prop#264, the following new subprotocol numbers and their uses. 6.1.1. Relay Subprotocol "Relay 3" -- The OP supports all of "Relay 2", plus support for CREATE2V and CREATED2V cells and their above specification for link-layer authentication specifiers. 6.1.2. Link Subprotocol "Link 5": The OP supports all of "Link 1-4", plus support for the new EXTEND2 semantics. Namely, it understands that an EXTEND2 cell whose "hlen" field is greater than 505 will be followed by further "hdata" in fragmented EXTEND2 cells which MUST follow. It also understands that the following combination of EXTEND2 payload specifiers indicates that the cell is a continuation of the earlier payload portions: nspec = 0; htype = 0xffff; hlen = 0; 6.1.3. Handshake Subprotocol Additionally, we introduce a new subprotocol, "Handshake" and the following number assignments for previously occuring instances: "Handshake 1" -- The OP supports the TAP handshake. "Handshake 2" -- The OP supports the ntor handshake. We also reserve the following assignments for future use: "Handshake 3" -- The OP supports the "hybrid+null" ntor-like handshake from prop#269. "Handshake 4" -- The OP supports a(n as yet unspecified) post-quantum secure hybrid handshake, that is, the "hybrid+null" handshake from "Handshake 3", except with "null" part replaced with another (as yet unspecified) protocol to be composed with the ntor-like ECDH-based handshake. Further handshakes MUST be specified with "Handshake" subprotocol numbers, and MUST NOT be specified with "Relay" subprotocol numbers. The "Relay" subprotocol SHALL be used in the future to denote changes to handshake protocol handling of CREATE* and EXTEND* cells, i.e. CREATE, CREATED, CREATE_FAST, CREATED_FAST, CREATE2, CREATED2, CREATE2V, CREATED2V, EXTEND, EXTENDED, EXTEND2, and EXTENDED2. Thus, "Handshake 1" is taken to be synonymous with "Relay 1", and likewise "Handshake 2" is with "Relay 2". 6.2. Subprotocol Recommendations After the subprotocol additions above, we change to recommending the following in the consensus: recommended-client-protocols […] Link=5 Relay=3 Handshake=2 recommended-relay-protocols […] Link=5 Relay=3 Handshake=2 required-client-protocols […] Link=4-5 Relay=2-3 Handshake=1-2 required-relay-protocols […] Link=3-5 Relay=1-3 Handshake=1-2 6.2. New Consensus Parameters We introduce the following new consensus parameters: Create2VMaximumData SP int The maximum amount of "hlen" data, in bytes, which may carried in either direction within a set of CREATE(D)2V cells. (default: 10240) 7. Resource management issues This feature requires relays and clients to buffer EXTEND2 cell bodies for incoming cells until the entire CREATE2V/CREATED2V body has arrived. To avoid memory-related denial-of-service attacks, the buffers allocated for this data need to be counted against the total data usage of the circuit. Further, circuits which receive and buffer CREATE(D)2V cells MUST store the time the first buffer chunk was allocated, and use it to inform the OOM manager w.r.t. the amount of data used and its staleness. Appendix A. A rejected idea for migration In section 5 above, I gave up on the idea of allowing relay A to extend to relay B with a large CREATE cell when relay A does not support this proposal. There are other ways to do this, but they are impressively kludgey. For example, we could have a fake CREATE cell for new handshake types that always elicits a "yes, keep going!" CREATED cell. Then the client could send the rest of the handshake and receive the rest of the CREATED cell as RELAY cells inside the circuit. This design would add an extra round-trip to circuit extension whenever it was used, however, and would violate a number of Tor's assumptions about circuits (e.g., by having half-created circuits, where authentication hasn't actually been performed). So I'm guessing we shouldn't do that.

2 1

Discussion Meeting for Prop#249 "Large CREATE cells"
by isis agora lovecruft 13 Dec '17

13 Dec '17

Hello all, What: A proposal discussion meeting for prop#249 "Allow CREATE cells with >505 bytes of handshake data". [0] Who: This proposal is likely of interest to those hoping to integrate newer, non-ECC-based, circuit-layer handshakes into the Tor protocol. When: Next week, on Monday or Tuesday (or Wednesday, for some timezones). If you'd like to attend, please vote on a time here: https://doodle.com/poll/v924cbt2at3rzvc9 Where: irc.oftc.net #tor-meeting [0]: https://gitweb.torproject.org/torspec.git/tree/proposals/249-large-create-c… Meeting Preparation Materials ============================= The following is meant for attendees to refresh before the meeting. Please feel free to respond with further summary and/or open questions/concerns. Proposal Summary ~~~~~~~~~~~~~~~~ The proposal outlines two new cell types, CREATE2V and CREATED2V, which are variable-length and (like their CREATE2/CREATED2 counterparts) are sent encapsulated in EXTEND2 cells. Due to their variable-length, however, if a CREATE(D)2V cell's HDATA is larger than the standard allotment of 505 bytes, these new cells are fragmented across multiple EXTEND2 cells. Open Questions/Concerns ~~~~~~~~~~~~~~~~~~~~~~~ 1. Since CREATE2V cells are used for handshakes, and several newer, post-quantum primitives have asymmetric payloads for the client versus server directions, should we require that the CREATE(D)2V padding be used to equalise the number of bytes sent in each direction? 2. Should we randomise the bytes in the padding? (Currently, as proposed, we require all-zero padding.) 3. Should we do anything more future-proofed w.r.t. the future possibility of using an alternate (non-stateful, e.g. not TCP) transport? (Currently, the proposal relies heavily upon the transport-layer to provide delivery guarantee and, perhaps more important, ordering.) 4. Shoule we, for hybrid handshakes (handshakes which use multiple separate primitives to derive shared secrets, e.g. ECDH+RLWE or ECDH+SIDH, by conducting each handshake separately and composing their respective resulting shared secrets), design some mechanism where, if a party only supports say the ECDH portion of the hybrid handshake and not the RLWE part, then they proceed with the portion they understand? For example, a client sends their portion of a ECDH+RLWE handshake to a relay which only understands ECDH, so the relay responds with only ECDH and they continue. This is mostly a difference in subprotocol versioning for handshakes, that is, an ECDH+RLWE handshake, rather than being "handshake type 5" or whatever, would be "handshake type 2 AND/OR handshake type 5". 5. As written, the proposal doesn't specify a maximum (or minimum) size of handshake data. However, the max is somewhat limited by the number of allowed RELAY_EARLY cells; maximum handshake data is then limited to 462+(7*492)=3906 bytes. Best regards, -- ♥Ⓐ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt

3 4

Proposal 287: Reduce circuit lifetime without overloading the network.
by Fernando Fernández Mancera 12 Dec '17

12 Dec '17

Hello, I have been working on this proposal for some time and Nick blessed me to send it as Proposal 287. Here is. Filename: 287-reduce-lifetime.txt Title: Reduce circuit lifetime without overloading the network Author: Fernando Fernandez Mancera Created: 30-Nov-2017 Status: Open Motivation: Currently Tor users are reusing a given circuit for ten minutes (by default) after it's first used. This time is too long because a malicious Exit relay can trace a user's pseudonymous profile, especially if connections from multiple protocols are put on the same circuit. This time it is established on MaxCircuitDirtiness parameter and by default its value is ten minutes. I have been thinking in a way to fix this. The first idea that came to my mind was to use StreamIsolationByHost and StreamIsolationByPort on it, but I wasn't able to sort it out. One day, I thought "Why is time so important?" and later on I realized that maybe focusing on the amount of bytes running through the circuit could end up being a better approach on this problem. Design: I propose two options to reduce this problem, both based on taking into account the amount of bytes running through a circuit. MaxCircuitSizeDirtiness (temporal parameter name) will take an integer field that is contained on an interval and represents the maximum amount of bytes that can be written/read (we need to discuss about the use of one for both) by the circuit. If the circuit exceeds that amount, new streams won't use this circuit anymore. MaxCircuitSizeDirtinessByPort (temporal parameter name) will take an array of integers that are contained on an interval and represents the maximum amount of bytes that can be written/read (we need to discuss about the use of one for both) by the circuit per port (StreamIsolationByPort). This array is parallel to the array of ports from StreamIsolationByPort. If the circuit exceeds that amount, new streams won't use this circuit anymore. Regarding default values it would be useful to set up one a bit lower than the average amount of bytes per circuit. On MaxCircuitSizeDirtinessByPort after discuss it we shouldn't set up a default value because someone can identify the port used. About MaxCircuitDirtiness, if the others are set up by default it could be bigger, like thirty minutes, so if the user doesn't send/receive a significant amount of data the circuit will be changed anyway. Security Implications: It is believed that the proposed changes will improve the anonymity for end users. The end user won't reuse a given circuit if they have sent a considerable amount of bytes, thus making more difficult for malicious Exit relays to be able to trace a user's pseudonymous profile. Obviously this is a probability, of course it's possible that sensitive data will leak in a little amount of data but it's more even possible that sensitive data will leak in a large amount. Specification: In order to implement this feature we will need to add some new functionalities. We need to parse MaxCircuitSizeDirtiness and MaxCircuitSizeDirtinessByPort from the torrc config file. We need to create a function or improve one to check the amount of bytes that are running through the circuit and if this amount is higher than the established value, consider the circuit dirty. Compatibility: The proposed changes should not create any compatibility issues. New Tor clients will be able to take advantage of this without any modification to the network. Implementation: It is proposed that MaxCircuitSizeDirtiness will be enabled by default and also increase MaxCircuitDirtiness to thirty minutes. It is proposed that MaxCircuitSizeDirtinessByPort won't be enabled by default for port 22, 53, and port 80 as StreamIsolationByPort. About TorBrowser or any other Tor application that is able to manage circuits by its own because of KeepAliveIsolateSOCKSAuth option being active by default shouldn't be affected by this new feature. As the same form that it currently ignores MaxCircuitDirtiness parameter. Performance and scalability notes: The proposed changes will reduce Tor network stress as users who do not exceed the set amount will reduce circuit generation by three (if default MaxCircuitDirtinesss value is thirty minutes). I want to work on demonstrating that by a research but first it's nice to get the idea accepted. References: Tor project research ideas [https://research.torproject.org/ideas.html] Enhancing Tor's Performance using Real-time Traffic Classification [https://www.cypherpunks.ca/~iang/pubs/difftor-ccs.pdf] (It's not exactly about that, but they talk about circuit lifetime and the ten minutes problem a few times. Also it's an interesting paper.)

3 8

How about capping single operators to max. 10% exit capacity of the network?
by nusenu 11 Dec '17

11 Dec '17

Hi, since a single operator now controls more than 10% of the tor network's exit capacity I wanted to bring this up here (again [1]). What do you think about capping single operators (family) to 10% exit capacity and 5% for guard operators? regards, nusenu [1] https://lists.torproject.org/pipermail/tor-dev/2016-March/010653.html -- https://mastodon.social/@nusenu twitter: @nusenu_

3 7

Proposal 286: Controller APIs for hibernation access on mobile
by Nick Mathewson 08 Dec '17

08 Dec '17

Filename: 286-hibernation-api.txt Title: Controller APIs for hibernation access on mobile Author: Nick Mathewson Created: 30-November-2017 Status: Open 1. Introduction On mobile platforms, battery life is achieved by reducing needless network access and CPU access. Tor currently provides few ways for controllers and operating systems to tune its behavior. This proposal describes controller APIs for better management of Tor's hibernation mechanisms, and extensions to those mechanisms, for better power management in mobile environments. 1.1. Background: hibernation and idling in Tor today We have an existing "hibernation" mechanism that we use to implement "bandwidth accounting" and "slow shutdown" mechanisms: When a Tor instance is close to its bandwidth limit: it stops accepting new connections or circuits, and only processes those it has, until the bandwidth limit is reached. Once the bandwidth limit is reached, Tor closes all connections and circuits, and all non-controller listeners, until a new accounting limit begins. Tor handles the INT signal on relays similarly: it stops accepting new connections or circuits, and gives the existing ones a short interval in which to shut down. Then Tor closes all connections and exits the process entirely. Tor's "idle" mechanism is related to hibernation, though its implementation is separate. When a Tor clients has passed a certain amount of time without any user activity, it declares itself "idle" and stops performing certain background tasks, such as fetching directory information, or building circuits in anticipation of future needs. (This is tied in the codebase to the "predicted ports" mechanism, but it doesn't have to be.) 1.2. Background: power-management signals on mobile platforms (I'm not a mobile developer, so I'm about to wildly oversimplify. Please let me know where I'm wrong.) Mobile platforms achieve long battery life by turning off the parts they don't need. The most important parts to turn off are the antenna(s) and the screen; the CPU can be run in a slower mode. But it doesn't do much good turning things off when they're unused, if some background app is going to make sure that they're always in use! So mobile platforms use signals of various kinds to tell applications "okay, shut up now". Some apps need to do online background activities periodically; to help this out, mobile platforms give them a signal "Hey, now is a good time if you want to do that" and "stop now!" 1.3. Mostly out-of-scope: limiting CPU wakeups when idle. The changes described here will be of limited use if we do not also alter Tor so that, when it's idle, the CPU is pretty quiet. That isn't the case right now: we have large numbers of callbacks that happen periodically (every second, every minute, etc) whether they need to or not. We're hoping to limit those, but that's not what this proposal is about. 2. Improvements to the hibernation model To present a consistent interface that applications and controllers can use to manage power consumption, we make these enhancements to our hibernation model. First, we add three new hibernation states: "IDLE", "IDLE_UPDATING", "SLEEP", and "SLEEP_UPDATING". "IDLE" is like the current "idle" or "no predicted ports" state: Tor doesn't launch circuits or start any directory activity, but its listeners are still open. Tor clients can enter the IDLE state on their own when they are LIVE, but haven't gotten any client activity for a while. Existing connections and circuits are not closed. If the Tor instance receives any new connections, it becomes LIVE. "IDLE_UPDATING" is like IDLE, except that Tor should check for directory updates as appropriate. If there are any, it should fetch directory information, and then become IDLE again. "SLEEPING" is like the current "dormant state we use for bandwidth exhaustion, but it is controller-initiated: it begins when Tor is told to enter it, and ends when Tor is told to leave it. Existing connections and circuits are closed; listeners are closed too. "SLEEP_UPDATING" is like SLEEP, except that Tor should check for directory updates as appropriate. If there are any, it should fetch directory information, and then SLEEP again. 2.1. Relay operation Relays and bridges should not automatically become IDLE on their own. 2.2. Onion service operation When a Tor instance that is running an onion service is IDLE, it does the minimum to try to remain responsive on the onion service: It keeps its introduction points open if it can. Once a day, it fetches new directory information and opens new introduction points. 3. Controller hibernation API 3.1. Examining the current hibernation state We define a new "GETINFO status/hibernation" to inspect the current hibernation state. Possible values are: - "live" - "idle:control" - "idle:no-activity" - "sleep:control" - "sleep:accounting" - "idle-update:control" - "sleep-update:control" - "shutdown:exiting" - "shutdown:accounting" - "shutdown:control" The first part of each value indicates Tor's current state: "live" -- completely awake "idle" -- waiting to see if anything happens "idle-update" -- waiting to see if anything happens; probing for directory information "sleep" -- completely unresponsive "shutdown" -- unresponsive to new requests; still processing existing requests. The second part of each value indicates the reason that Tor entered this state: "control" -- a controller told us to do this. "no-activity" -- Tor became idle on its own due to not noticing any requests. "accounting" -- the bandwidth system told us to enter this state. "exiting" -- Tor is in this state because it's getting ready to exit. We add a STATUS_GENERAL hibernation event as follows: HIBERNATION "STATUS=" (one of the status pairs above.) Indicates that Tor's hibernation status has changed. Note: Controllers MUST accept status values here that they don't recognize. The "GETINFO accounting/hibernating" value and the "STATUS_SERVER HIBERANATION_STATUS" event keep their old meaning. 3.2. Changing the hibernation state We add the following new possible values to the SIGNAL controller command: "SLEEP" -- enter the sleep state, after an appropriate shutdown interval. "IDLE" -- enter the idle state "SLEEPWALK" -- If in sleep or idle, start probing for directory information in the sleep-update or idle-update state respectively. Remain in that state until we've probed for directory information, or until we're told to IDLE or SLEEP again, or (if we're idle) until we get client activity. Has no effect if not in sleep or idle. "WAKEUP" -- If in sleep, sleep-update, idle, idle-update, or shutdown:sleep state, enter the live state. Has no effect in any other state. 3.3. New configuration parameters StartIdle -- Boolean. If set to 1, Tor begins in IDLE mode.

5 8