May 2020 - tor-dev - lists.torproject.org

the consequences of deprecating debian alpha repos with every new major branch
by nusenu 21 Dec '21

21 Dec '21

Hi, tldr: - more outdated relays (that is a claim I'm making and you could easily proof me wrong by recreating the 0.3.3.x alpha repos and ship 0.3.3.7 in them and see how things evolve after a week or so) - more work for the tpo website maintainer - less happy relay operators [3][4] - more work for repo maintainers? (since a new repo needs to be created) When the tor 0.3.4 alpha repos (deb.torproject.org) first appeared on 2018-05-23 I was about to submit a PR for the website to include it in the sources.list generator [1] on tpo but didn't do it because I wanted to wait for a previous PR to be merged first. The outstanding PR got merged eventually (2018-06-28) but I still did not submit a PR to update the repo generator for 0.3.4.x nonetheless and here is why. Recently I was wondering why are there so many relays running tor version 0.3.3.5-rc? (see OrNetStats or Relay Search) (> 3.2% CW fraction) Then I realized that this was the last version the tor-experimental-0.3.3.x-* repos were shipping before they got abandoned due to the new 0.3.4.x-* repos (I can no longer verify it since they got removed by now). Peter made it clear in the past that the current way to have per-major-version debian alpha repos (i.e. tor-experimental-0.3.4.x-jessie) will not change [2]: > If you can't be bothered to change your sources.list once or twice a > year, then you probably should be running stable. but maybe someone else would be willing to invoke a "ln" commands everytime a new new alpha repo is born. tor-alpha-jessie -> tor-experimental-0.3.4.x-jessie once 0.3.5.x repos are created the link would point to tor-alpha-jessie -> tor-experimental-0.3.5.x-jessie It is my opinion that this will help reduce the amount of relays running outdated versions of tor. It will certainly avoid having to update the tpo website, which isn't a big task and could probably be automated but it isn't done currently. "..but that would cause relay operators to jump from i.e. 0.3.3.x to 0.3.4.x alphas (and break setups)!" Yes, and I think that is better than relays stuck on an older version because the former repo no longer exists and operators still can choose the old repos which will not jump to newer major versions. [1] https://www.torproject.org/docs/debian.html.en#ubuntu [2] https://trac.torproject.org/projects/tor/ticket/14997#comment:3 [3] https://lists.torproject.org/pipermail/tor-relays/2018-June/015549.html [4] https://trac.torproject.org/projects/tor/ticket/26474 -- https://twitter.com/nusenu_ https://mastodon.social/@nusenu

4 7

tor relay process health data for operators (controlport)
by nusenu 16 Nov '20

16 Nov '20

Hi, every now and then I'm in contact with relay operators about the "health" of their relays. Following these 1:1 discussions and the discussion on tor-relays@ I'd like to rise two issues with you (the developers) with the goal to help improve relay operations and end user experience in the long term: 1) DNS (exits only) 2) tor relay health data 1) DNS ------ Current situation: Arthur Edelstein provides public measurements to tor exit relay operators via his page at: https://arthuredelstein.net/exits/ This page is updated once daily. the process to use that data looks like this: - first they watch Arthur's measurement results - if their failure rate is non-zero they try to tweak/improve/change their setup - wait for another 24 hours (next measurement) This is a somewhat suboptimal and slow feedback loop and is probably also less accurate and less valuable data when compared to the data the tor process can provide. Suggestion for improvement: Exposes the following DNS status information via tor's controlport to help debug and detect DNS issues on exit relays: (total numbers since startup) - amount of DNS queries send to the resolver - amount of DNS queries send to the resolver due to a RESOLVE request - DNS queries send to resolver due to a reverse RESOLVE request - amount of queries that did not result in any answer from the resolver - breakdown of number of responses by response code (RCODE) https://www.iana.org/assignments/dns-parameters/dns-parameters.xhtml#dns-pa… - max amount of DNS queries send per curcuit If this causes a significant performance impact this feature should be disabled by default. 2) general relay health metrics -------------------------------- Compared to other server daemons (webserver, DNS server, ..) tor provides little data for operators to detect operational issues and anomalies. I'd suggest to provide the following stats via the control port: (most of them are already written to logfiles by default but not accessible via the controlport as far as I've seen) - total amount of memory used by the tor process - amount of currently open circuits - circuit handshake stats (TAP / NTor) DoS mitigation stats - amount of circuits killed with too many cells - amount of circuits rejected - marked addresses - amount of connections closed - amount of single hop clients refused - amount of closed/failed circuits broken down by their reason value https://gitweb.torproject.org/torspec.git/tree/tor-spec.txt#n1402 https://gitweb.torproject.org/torspec.git/tree/control-spec.txt#n1994 - amount of closed/failed OR connections broken down by their reason value https://gitweb.torproject.org/torspec.git/tree/control-spec.txt#n2205 If this causes a significant performance impact this feature should be disabled by default. cell stats - extra info cell stats as defined in: https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt#n1072 This data should be useful to answer the following questions: - High level questions: Is the tor relay healthy? - is it hitting any resource limits? - is the tor process under unusual load? - why is tor using more memory? - is it slower than usual at handling circuits? - can the DNS resolver handle the amount of DNS queries tor is sending it? This data could help prevent errors from occurring or provide additional data when trying to narrow down issues. When it comes to the question: **Is it "safe" to make this data accessible via the controlport?** I assume it is safe for all information that current versions of tor writes to logfiles or even publishes as part of its extra info descriptor. Should tor provide this or similar data I'm planing to write scripts for operators to make use of that data (for example a munin plugin that connects to tor's controlport). I'm happy to help write updates for control-spec should these features seem reasonable to you. Looking forward to hearing your feedback. nusenu -- https://twitter.com/nusenu_ https://mastodon.social/@nusenu

5 7

Re: [tor-dev] [RFC] Proposal: A First Take at PoW Over Introduction Circuits
by tevador 25 Sep '20

25 Sep '20

Hi all, I was asked by George to submit my comments about the proposal and to suggest suitable RandomX parameters for this PoW scheme. > For our dynamic PoW system to work, we will need to be able to compare PoW > tokens with each other. To do so we define a function: > unsigned effort(uint8_t *token) > which takes as its argument a hash output token, and returns the number of > leading zero bits on it. This definition makes the effort exponential, i.e. the computational resources required to reach one notch higher effort increase by a factor of 2 each time. I suggest to use linear effort defined as the quotient of dividing a bitstring of 1s by the hash value: == Example A: effort(00000001100010101101) = 11111111111111111111 / 00000001100010101101 or in decimal: effort(6317) = 1048575 / 6317 = 165. This definition of effort has the advantage of directly expressing the expected number of hashes that the client had to calculate to reach the effort. With the exponential definition, we could have an equivalent linear effort of either 128 (7 leading zeroes) or 256 (8 leading zeroes), while the linear definition provides smoother classification of PoW results. > The EXT_FIELD content format is: > > POW_VERSION [1 byte] > POW_NONCE [32 bytes] > I suggest to use a 16-byte nonce value, which is more than sufficient given the target security level and has the benefit of reducing the replay cache size to half. Since we expect the seed to be valid for around 3 hours (as proposed), then even if the service receives 1 million proofs per second and each proof has an effort of 1 million, then the number of submitted nonces from clients will only reach about 10^10. With a 108-bit solution space (subtracting 20 bits as the search space per client), the probability that two clients accidentally submit the same nonce is roughly 10^-13 (see [REF_BIRTHDAY]). Additionally, I suggest to add the client's effort for convenience: The updated EXT_FIELD content format would be: POW_VERSION [1 byte] POW_EFFORT [4 bytes] POW_NONCE [16 bytes] Including the effort has 2 benefits: 1. In case the Intro Priority Queue is full, the service doesn't need to waste time verifying PoW solutions that have effort lower than the last element in the queue. While an attacker can always lie about the actual effort of their nonce value, I think this field can still save some CPU cycles when the service is under heavy load. 2. The service can conveniently verify the reported effort with the following inequality: POW_EFFORT * pow_function(POW_NONCE, SEED) <= MAX_RESULT where MAX_RESULT is the highest possible output from the pow_function. In the case of Example A, that would be: 165 * 6317 = 1042305 <= 1048576 > Similar to how our cell scheduler works, the onion service subsystem will > poll the priority queue every 100ms tick and process the first 20 cells from > the priority queue (if they exist). The service will perform the rendezvous > and the rest of the onion service protocol as normal. I suggest to use a different selection method rather than always taking the first 20 requests. Selecting cells from the front of the queue actually minimizes the effort that an attacker needs to expend to completely block access to the service. The attacker can always submit the minimum effort required to occupy the first 20 slots in each 100 ms window. This can be done by submitting just 200 requests per second and observing how many circuits are successfully open and adjusting the effort until no other request can go through. This is the "Total overwhelm strategy" described in § 5.1.1. See the following examples to show how selecting the first N cells from the queue is unfair. I will use N = 4 for clarity. E denotes some value of effort. == Example B: ATTACKER LEGITIMATE CLIENTS ___________ _________ ____________ ______________ / \ / \ +--------+--------+--------+--------+----+----+----+----+----+----+----+----+ | 2E | 2E | 2E | 2E | E | E | E | E | E | E | E | E | +--------+--------+--------+--------+----+----+----+----+----+----+----+----+ ^ ^ ^ ^ selected selected selected selected Here both the attacker and the legitimate clients have expended a combined effort of 8E. All of the attacker's cells get selected, while none of the other clients get through. Instead, I suggest to use Stochastic universal sampling [REF_SUS], where the probability that a cell gets selected is proportional to its effort. == Example C: Here the total effort in the queue is 16E, so we first select a random value in the interval [0, 4E) and then select 4 evenly spaced cells: ATTACKER LEGITIMATE CLIENTS ___________ _________ ____________ ______________ / \ / \ +--------+--------+--------+--------+----+----+----+----+----+----+----+----+ | 2E | 2E | 2E | 2E | E | E | E | E | E | E | E | E | +--------+--------+--------+--------+----+----+----+----+----+----+----+----+ ^ ^ ^ ^ selected selected selected selected In this case, 2 cells are selected from each group, which is fairer considering that each group expended the same effort. == Example D: Now if the attacker wanted to block access to all legitimate clients, they would need to at least quadruple their total PoW effort (and there would still be a chance that a legitimate client gets selected from the end of the queue): ATTACKER LEGITIMATE CLIENTS __________________________ ______________________ ______________ / \ / \ +--------------+--------------+---------------+--------------+-+-+-+-+-+-+-+-+ | 8E | 8E | 8E | 8E |E|E|E|E|E|E|E|E| +--------------+--------------+--------------+---------------+-+-+-+-+-+-+-+-+ ^ ^ ^ ^ selected selected selected selected Note: With linear effort, the original selection method becomes even worse because the attacker can occupy the front of the queue with an effort of just E+1 per cell rather than 2E. In some cases, Stochastic universal sampling can select a single element multiple times, which is not a problem for genetic algorithms, but we want to avoid it. I suggest to restart the selection algorithm from the beginning of the next cell in those cases and shorten the sampling interval according to the remaining portion of the queue. See the following example. == Example E: +---------------+-------------+--------------+------------+-+-+-+-+-+-+-+-+-+-+ | 16E | 8E | 6E |E|E|E|E|E|E|E|E|E|E| +---------------+-------------+--------------+------------+-+-+-+-+-+-+-+-+-+-+ ^ ^ ^ ^ selected selected selected selected > In particular, the service starts with a default suggested-effort value of 15. > > Everytime the service handles an introduction request from the priority queue > in [HANDLE_QUEUE], the service compares the request's effort to the current > suggested-effort value. If the new request's effort is lower than the > suggested-effort, set the suggested-effort equal to the effort of the new > request. > > Everytime the service trims the priority queue in [HANDLE_QUEUE], the service > compares the request at the trim point against the current suggested-effort > value. If the trimmed request's effort is higher than the suggested-effort, > set the suggested-effort equal to the effort of the new request. I think the default suggested-effort is a bit too high. Assuming each attempt takes around 1 ms to calculate, the client would need, on average, 2^15 ms = 33 seconds to find a solution using 1 CPU core. I suggest to specify a minimum effort instead. Requests with effort < MIN_EFFORT and requests without the PROOF_OF_WORK extension would be treated as having effort = 1 for the purposes of the sampling algorithm. Secondly, the proposed method of calculating the suggested-effort is susceptible to gaming by attackers. Since the service can only update the value in the directory once every 'hs-pow-desc-upload-rate-limit' seconds, they could stop the attack for a little while just before the directory gets updated, which would cause the suggested-effort value to be too low despite an ongoing attack. I suggest to take the median effort of the selected cells during each 100 ms window. For the examples above that would be: Example C: 1.5E Example D: 8E Example E: 7E Then I would take the median of these values over the directory update period. > > 5. Attacker strategies > Additional attacks: 5.1.2 PoW Spam Attack The attacker may try to spam many requests with random values of POW_NONCE, requiring the service to waste cycles verifying the invalid proofs. No such request would make it into the Intro Queue, but it may still be a viable DoS strategy depending on proof verification time and the number of intro requests that can be practically delivered through the network. 5.1.3 Precomputed PoW attack The attacker may precompute many valid PoW nonces and submit them all at once before the current seed expires, overwhelming the service temporarily even using a single computer. > 4.2. Seed expiration issues > > As mentioned in [DESC_POW], the expiration timestamp on the PoW seed can > cause issues with clock skewed clients. Furthermore, even not clock skewed > clients can encounter TOCTOU-style race conditions here. > > The client descriptor refetch logic of [CLIENT_TIMEOUT] should take care of > such seed-expiration issues, since the client will refetch the descriptor. > I suggest to use 2 concurrent seeds, i.e. to accept PoW both from the current and the last seed epoch. We use this approach in Monero. It would however require adding the seed value into the proof of work extension field and also double the memory requirements for verification with RandomX. > The proposal suggests argon2, and Mike has been looking at Randomx. However, > after further consideration and speaking with some people (props to Alex > Biryukov), it seems like those two functions are not well fitted for this > purpose, since they are memory-hard both for the client and the service. And > since we are trying to minimize the verification overhead, so that the > service can do hundreds of verifications per second, they don't seem like > good fits. Asymmetric function like Equihash, Cuckoo cycle [REF_CUCKOO] and MTP have the advantage of being very fast to verify, but they run much faster on GPUs and specialized hardware, so I don't think they are particularly suitable for this purpose. When we designed RandomX to be used as the PoW algorithm by Monero, we selected the parameters very conservatively to maximize the ASIC resistance of the algorithm. That's because it is very difficult to change the PoW algorithm once it's deployed. TOR is not limited by this, so we can be much more aggressive when configuring RandomX. I suggest to use a configuration that gives the fastest possible verification time without completely breaking the algorithm. In particular, the following parameters should be set differently from Monero: RANDOMX_ARGON_SALT = "RandomX-TOR-v1" The unique RandomX salt means we do not need to use a separate salt as PoW input as specified in § 3.2. RANDOMX_ARGON_ITERATIONS = 1 RANDOMX_CACHE_ACCESSES = 4 RANDOMX_DATASET_BASE_SIZE = 1073741824 RANDOMX_DATASET_EXTRA_SIZE = 16777216 These 4 changes reduce the RandomX Dataset size to ~1 GiB, which allows the number of iteration to be reduced from 8 to 4. The combined effect of this is that Dataset initialization becomes 4 times faster, which is needed due to more frequent updates of the seed (Monero updates once per ~3 days). RANDOMX_PROGRAM_COUNT = 2 RANDOMX_SCRATCHPAD_L3 = 1048576 Additionally, reducing the number of programs from 8 to 2 makes the hash calculation about 4 times faster, while still providing resistance against program filtering strategies (see [REF_RANDOMX_PROGRAMS]). Since there are 4 times fewer writes, we also have to reduce the scratchpad size. I suggest to use a 1 MiB scratchpad size as a compromise between scratchpad write density and memory hardness. Most x86 CPUs will perform roughly the same with a 512 KiB and 1024 KiB scratchpad, while the larger size provides higher resistance against specialized hardware, at the cost of possible time-memory tradeoffs (see [REF_RANDOMX_TMTO] for details). Lastly, we reduce the output of RandomX to just 8 bytes: RANDOMX_HASH_SIZE = 8 64-bit preimage security is more than sufficient for proof-of-work and it allows the result to be treated as a little-endian encoded unsigned integer for easy effort calculation. RandomX would be used as follows: The service will select a 32-byte POW_SEED and initialize the cache and the dataset: randomx_init_cache(myCache, POW_SEED, 32); randomx_init_dataset(myDataset, myCache, 0, randomx_dataset_item_count()); randomx_vm *myMachine = randomx_create_vm(flags, NULL, myDataset); Then in order to validate a PoW token, we could use something like this: int validateProof(uint32_t pow_effort, void* pow_nonce) { uint64_t result; randomx_calculate_hash(myMachine, pow_nonce, 16, &result); if (mulh(pow_effort, result) == 0) { return 1; } return 0; } I suggest to set MIN_EFFORT = 10000, which takes about 1 second on my laptop. Requests with pow_effort < MIN_EFFORT would not be validated. I have collected some performance figures for the fast mode with the above RandomX configuration (~1 GiB of memory is required): H/s = hashes per second == CPUs: Intel Core i3-3220 - 1 thread 700 H/s - 3 threads 1400 H/s Intel Xeon (dual core VPS, Sandy Bridge, unknown model) - 1 thread 2000 H/s - 2 threads 4000 H/s Intel Core i5-2500K (stock) - 1 thread 2200 H/s - 4 threads 8200 H/s Intel Core i7-8550U (laptop) - 1 thread 2700 H/s - 8 threads 10000 H/s Intel Core i7-9850H (laptop) - 1 thread 3100 H/s - 12 threads 16000 H/s AMD Ryzen 1700 @ 3300MHz - 1 thread 2300 H/s - 16 threads 23800 H/s AMD Ryzen 3700X @ 3300MHz - 1 thread 2500 H/s - 16 threads 27500 H/s AMD Epyc 7702P - 1 thread 2100 H/s - 128 threads 139000 H/s == GPUs: NVIDIA GeForce GTX 1660 Ti (credits to SChernykh, see [REF_RANDOMX_CUDA]) - 3072 intensity 2600 H/s According to the above results, the time to verify a single hash is around 400-500 μs. A mid-range GPU has a similar performance as a single CPU core. Most CPUs made since 2011 have similar per-core performance except of low-end CPUs without hardware AES support. References: [REF_BIRTHDAY]: https://en.wikipedia.org/wiki/Birthday_attack#Mathematics [REF_SUS]: https://en.wikipedia.org/wiki/Stochastic_universal_sampling [REF_CUCKOO]: https://github.com/tromp/cuckoo [REF_RANDOMX_PROGRAMS]: https://github.com/tevador/RandomX/blob/master/doc/design.md#12-the-easy-pr… [REF_RANDOMX_TMTO]: https://github.com/tevador/RandomX/issues/65 [REF_RANDOMX_CUDA]: https://github.com/SChernykh/RandomX_CUDA

7 21

DNS-over-HTTPS (DOH) in Firefox/Torbrowser
by nusenu 01 Jul '20

01 Jul '20

Hi, since Mozilla did tests [0] on DOH [1] in Firefox I was wondering if Torbrowser developers have put any thought into that as well? Note: I'm _not_ suggesting to use DOH in torbrowser I'm just asking because the answer probably matters for exit documentation in the relay guide if clients do DNS themselves over TCP connections instead of relying on the exit (even if torbrowser is not the only tor client). thanks, nusenu [0] https://www.ghacks.net/2018/03/20/firefox-dns-over-https-and-a-worrying-shi… [1] https://datatracker.ietf.org/doc/draft-hoffman-dns-over-https/ -- https://mastodon.social/@nusenu twitter: @nusenu_

4 4

Support for full DNS resolution and DNSSEC validation
by Christian Hofer 14 Jun '20

14 Jun '20

Hi there, I have a proposal regarding DNS name resolution. Ticket: https://trac.torproject.org/projects/tor/ticket/34004 Proposal: https://trac.torproject.org/projects/tor/attachment/ticket/34004/317-secure… Implementation: https://github.com/torproject/tor/pull/1869 All functioniality is behind the DNSResolver feature flag, so don't forget to activate it before you start testing. Please let me know what you think. BR Christian

7 29

Moving key material out of the main tor process
by Linus Nordberg 03 Jun '20

03 Jun '20

Hi, tl;dr How to move key material out of tor? ## The idea of a vault component ahf and others in the network team have been discussing the possibility of a "vault" component in tor, for moving private keys out of the tor process. Separating secret key material from the code handling data from the network seems valuable and providing a component making different implementations "pluggable" would allow for anyone to use their favourite technology without touching the tor code base. Examples are local trusted execution environments like Intel SGX and Arm TrustZone and various HSM's and security keys/tokens. One way of implementing this would be to define a protocol, for a vault component to talk to a daemon running on the same host as tor, over some IPC mechanism. This protocol would allow tor to request a signature over a hash, or a document, in a certain key. Whether the daemon has access to the key material or has to forward the request to a separate device or hardware component is irrelevant to the protocol and the vault component. Even if the design focuses on signatures it should probably take encryption and decryption into account, to be added later. ## The vault as a possible match for TorHSM Such a vault component would fit well with a project where Peter Stuge and myself are building an HSM for Tor directory authority signing keys [0] based on the CrypTech design [1]. [0] https://trac.cryptech.is/wiki/ExternalProjectsTorHSM [1] https://cryptech.is/ One of the options for tor to delegate the signing of votes and consensuses to such a device would be to use a vault component as described above. We would then have a signing daemon responsible for the USB communication with the TorHSM device. Another option would be to build support directly into tor for communicating with the device, through a library capable of a USB vendor specific protocol defined by TorHSM. There are pros and cons with both options. I'd like to hear what the Tor developers community think would be best. ## Asynchronous signing API Vault or not, tor needs to change the way signing is done to be able to move key material out of the main process. First, external devices may need more time to perform a signature operation than what tor can accept to spend blocking in its main thread. Second, an external device might disappear or malfunction, requiring the possibility for an operation to time out. This can be implemented either with callbacks or with a state machine with more well defined state transitions. Maybe there are more options that I didn't think of. ## Protocol choice If we decide to go for the vault component with a separate daemon we should consider using the ssh-agent protocol for tor to talk to the daemon. Apart from being already defined there are multiple well tested implementations of this protocol. It also has a couple of features we might want, such as forgetting a certain key and locking/unlocking of the vault. Finally, it's extensible and should accommodate potential additions we might want to make later.

3 4

Proposal XXX: FlashFlow: A Secure Speed Test for Tor (Parent Proposal)
by Matt Traudt 02 Jun '20

02 Jun '20

Filename: xxx-flashflow.txt Title: FlashFlow: A Secure Speed Test for Tor (Parent Proposal) Author: Matthew Traudt, Aaron Johnson, Rob Jansen, Mike Perry Created: 23 April 2020 Status: Draft 1. Introduction FlashFlow is a new distributed bandwidth measurement system for Tor that consists of a single authority node ("coordinator") instructing one or more measurement nodes ("measurers") when and how to measure Tor relays. A measurement consists of the following steps: 1. The measurement nodes demonstrate to the target relay permission to perform measurements. 2. The measurement nodes open many TCP connections to the target relay and create a one-hop circuit to the target relay on each one. 3. For 30 seconds the measurement nodes send measurement cells to the target relay and verify that the cells echoed back match the ones sent. During this time the relay caps the amount of background traffic it transfers. Background and measurement traffic are handled separately at the relay. Measurement traffic counts towards all the standard existing relay statistics. 4. For every second during the measurement, the measurement nodes report to the authority node how much traffic was echoed back. The target relay also reports the amount of per-second background (non-measurement) traffic. 5. The authority node sums the per-second reported throughputs into 30 sums (one for each second) and calculates the median. This is the estimated capacity of the relay. FlashFlow performs a measurement of every relay according to a schedule described later in this document. Periodically it produces relay capacity estimates in the form of a v3bw file, which is suitable for direct consumption by a Tor directory authority. Alternatively an existing load balancing system such as Simple Bandwidth Scanner could be modified to use FlashFlow's v3bw file as input. It is envisioned that each directory authority that wants to use FlashFlow will run their own FlashFlow deployment consisting of a coordinator that they run and one or more measurers that they trust (e.g. because they run them themselves), similar to how each runs their own Torflow/sbws. Section 5.2 of this proposal describes long term plans involving multiple FlashFlow deployments. FlashFlow is more performant than Torflow: FlashFlow takes 5 hours to measure the entire existing Tor network from scratch (with 3 Gbit/s measurer capacity) while Torflow takes 2 days; FlashFlow measures relays it hasn't seen recently as soon as it learns about them (i.e. every new consensus) while Torflow can take a day or more; and FlashFlow accurately measures new high-capacity relays the first time and every time while Torflow takes days/weeks to assign them their full fair share of bandwidth (especially for non-exits). FlashFlow is more secure than Torflow: FlashFlow allows a relay to inflate its measured capacity by up to 1.33x (configured by a parameter) while Torflow allows weight inflation by a factor of 89x [0] or even 177x [1]. After an overview in section 2 of the planned deployment stages, section 3, 4, and 5 discuss the short, medium, and long term deployment plans in more detail. 2. Deployment Stages FlashFlow's deployment shall be broken up into three stages. In the short term we will implement a working FlashFlow measurement system. This requires code changes in little-t tor and an external FlashFlow codebase. The majority of the implementation work will be done in the short term, and the product is a complete FlashFlow measurement system. Remaining pieces (e.g. better authentication) are added later for enhanced security and network performance. In the medium term we will begin collecting data with a FlashFlow deployment. The intermediate results and v3bw files produced will be made available (semi?) publicly for study. In the long term experiments will be performed to study ways of using FF v3bw files to improve load balancing. Two examples: (1) using FF v3bw files instead of sbws's (and eventually phasing out torflow/sbws), and (2) continuing to run sbws but use FF's results as a better estimate of relay capacity than observed bandwidth. Authentication and other FlashFlow features necessary to make it completely ready for full production deployment will be worked on during this long term phase. 3. FlashFlow measurement system: Short term The core measurement mechanics will be implemented in little-t tor, but a separate codebase for the FlashFlow side of the measurement system will also be created. This section is divided into three parts: first a discussion of changes/additions that logically reside entirely within tor (essentially: relay-side modifications), second a discussion of the separate FlashFlow code that also requires some amount of tor changes (essentially: measurer-side and coordinator-side modifications), and third a security discussion. 3.1 Little-T Tor Components The primary additions/changes that entirely reside within tor on the relay side: - New torrc options/consensus parameters. - New cell commands. - Pre-measurement handshaking (with a simplified authentication scheme). - Measurement mode, during which the relay will echo traffic with measurers, set a cap on the amount of background traffic it transfers, and report the amount of transferred background traffic. 3.1.1 Parameters FlashFlow will require some consensus parameters/torrc options. Each has some default value if nothing is specified; the consensus parameter overrides this default value; the torrc option overrides both. FFMeasurementsAllowed: A global toggle on whether or not to allow measurements. Even if all other settings would allow a measurement, if this is turned off, then no measurement is allowed. Possible values: 0, 1. Default: 0 (disallowed). FFAllowedCoordinators: The list of coordinator TLS certificate fingerprints that are allowed to start measurements. Relays check their torrc when they receive a connection from a FlashFlow coordinator to see if it's on the list. If they have no list, they check the consensus parameter. If nether exist, then no FlashFlow deployment is allowed to measure this relay. Default: empty list. FFMeasurementPeriod: A relay should expect on average, to be measured by each FlashFlow deployment once each measurement period. A relay will not allow itself to be measured more than twice by a FlashFlow deployment in any time window of this length. Relays should not change this option unless they really know what they're doing. Changing it at the relay will not change how often FlashFlow will attempt to measure the relay. Possible values are in the range [1 hour, 1 month] inclusive. Default: 1 day. FFBackgroundTrafficPercent: The maximum amount of regular non-measurement traffic a relay should handle while being measured, as a percent of total traffic (measurement + non-measurement). This parameter is a trade off between having to limit background traffic and limiting how much a relay can inflate its result by handling no background traffic but reporting that it has done so. Possible values are in the range [0, 99] inclusive. Default: 25 (a maximum inflation factor of 1.33). FFMaxMeasurementDuration: The maximum amount of time, in seconds, that is allowed to pass from the moment the relay is notified that a measurement will begin soon and the end of the measurement. If this amount of time passes, the relay shall close all measurement connections and exit its measurement mode. Note this duration includes handshake time, thus it necessarily is larger than the expected actual measurement duration. Possible values are in the range [10, 120] inclusive. Default: 45. 3.1.2 New Cell Types FlashFlow will introduce a new cell command MEASURE. The payload of each MEASURE cell consists of: Measure command [1 byte] Length [2 bytes] Data [Length-3 bytes] The measure commands are: 0 -- MSM_PARAMS [forward] 1 -- MSM_PARAMS_OK [backward] 2 -- MSM_ECHO [forward and backward] 3 -- MSM_BG [backward] 4 -- MSM_ERR [forward and backward] Forward cells are sent from the measurer/coordinator to the relay. Backward cells are sent from the relay to the measurer/coordinator. MSM_PARAMS and MSM_PARAMS_OK are used during the pre-measurement stage to tell the target what to expect and for the relay to positively acknowledge the message. MSM_ECHO cells are the measurement traffic; the measurer generates them, sends them to the target, and the target echos them back. The target send a MSM_BG cell once per second to report the amount of background traffic it is handling. MSM_ERR cells are used to signal to the other party that there has been some sort of problem and that the measurement should be aborted. These measure commands are described in more detail in the next section. The only cell that sometimes undergoes cell encryption is MSM_ECHO; no other cell ever gets cell encrypted. (All cells are transmitted on a regular TLS-wrapped OR connection; that encryption still exists.) The relay "decrypts" MSM_ECHO cells before sending them back to the measurer; this mirrors the way relays decrypt/encrypt RELAY_DATA cells in order to induce realistic cryptographic CPU load. The measurer usually skips encrypting MSM_ECHO cells to reduce its own CPU load; however, to verify the relay is actually correctly decrypting all cells, the measurer will choose random outgoing cells, encrypt them, remember the ciphertext, and verify the corresponding incoming cell matches. 3.1.3 Pre-Measurement Handshaking/Starting a Measurement The coordinator connects to the target relay and sends it a MSM_PARAMS cell. If the target is unwilling to be measured at this time or if the coordinator didn't use a TLS certificate that the target trusts, it responds with an error cell and closes the connection. Otherwise it checks that the parameters of the measurement are acceptable (e.g. the version is acceptable, the duration isn't too long, etc.). If the target is happy, it sends a MSM_PARAMS_OK, otherwise it sends a MSM_ERR and closes the connection. Upon learning the IP addresses of the measurers from the coordinator in the MSM_PARAMS cell, the target whitelists their IPs in its DoS detection subsystem until the measurement ends (successfully or otherwise), at which point the whitelist is cleared. Upon receiving a MSM_PARAMS_OK from the target, the coordinator will instruct the measurers to open their TCP connections with the target. If the coordinator or any measurer receives a MSM_ERR, it reports the error to the coordinator and considers the measurement a failure. It is also a failure if any measurer is unable to open at least half of its TCP connections with the target. The payload of MSM_PARAMS cells [XXX more may need to be added]: - version [1 byte] - msm_duration [1 byte] - num_measurers [1 byte] - measurer_info [num_measurers times] - ipv4_addr [4 bytes] - num_conns [2 bytes] version dictates how this MSM_PARAMS cell shall be parsed. msm_duration is the duration, in seconds, that the actual measurement will last. num_measurers is how many measurer_info structs follow. For each measurer, the ipv4_addr it will use when connecting to the target is provided, as is num_conns, the number of TCP connections that measurer will open with the target. Future versions of FlashFlow and MSM_PARAMS will use TLS certificates instead of IP addresses. MSM_PARAMS_OK has no payload: it's just padding bytes to make the cell 514 bytes long. The payload of MSM_ECHO cells: - arbitrary bytes [max to fill up 514 byte cell] The payload of MSM_BG cells: - second [1 byte] - sent_bg_bytes [4 bytes] - recv_bg_bytes [4 bytes] second is the number of seconds since the measurement began. MSM_BG cells are sent once per second from the relay to the FlashFlow coordinator. The first cell will have this set to 1, and each subsequent cell will increment it by one. sent_bg_bytes is the number of background traffic bytes sent in the last second (since the last MSM_BG cell). recv_bg_bytes is the same but for received bytes. The payload of MSM_ERR cells: - err_code [1 byte] - err_str [possibly zero-len null-terminated string] The error code is one of: [... XXX TODO ...] 255 -- OTHER The error string is optional in all cases. It isn't present if the first byte of err_str is null, otherwise it is present. It ends at the first null byte or the end of the cell, whichever comes first. 3.1.4 Measurement Mode The relay considers the measurement to have started the moment it receives the first MSM_ECHO cell from any measurer. At this point, the relay - Starts a repeating 1s timer on which it will report the amount of background traffic to the coordinator over the coordinator's connection. - Enters "measurement mode" and limits the amount of background traffic it handles according to the torrc option/consensus parameter. The relay decrypts and echos back all MSM_ECHO cells it receives on measurement connections until it has reported its amount of background traffic the same number of times as there are seconds in the measurement (e.g. 30 per-second reports for a 30 second measurement). After sending the last MSM_BG cell, the relay drops all buffered MSM_ECHO cells, closes all measurement connections, and exits measurement mode. During the measurement the relay targets a ratio of background traffic to measurement traffic as specified by a consensus parameter/torrc option. For a given ratio r, if the relay has handled x cells of measurement traffic recently, Tor then limits itself to y = xr/(1-r) cells of non-measurement traffic this scheduling round. The target will enforce that a minimum of 10 Mbit/s of measurement traffic is recorded since the last background traffic scheduling round to ensure it always allows some minimum amount of background traffic. 3.2 FlashFlow Components The FF coordinator and measurer code will reside in a FlashFlow repository separate from little-t tor. There are three notable parameters for which a FF deployment must choose values. They are: - The number of sockets, s, the measurers should open, in aggregate, with the target relay. We suggest s=160 based on the FF paper. - The bandwidth multiplier, m. Given an existing capacity estimate for a relay, z, the coordinator will instruct the measurers to, in aggregate, send m*z Mbit/s to the target relay. We recommend m=2.25. - The measurement duration, d. Based on the FF paper, we recommend d=30 seconds. The rest of this section first discusses notable functions of the FlashFlow coordinator, then goes on to discuss FF measurer code that will require supporting tor code. 3.2.1 FlashFlow Coordinator The coordinator is responsible for scheduling measurements, aggregating results, and producing v3bw files. It needs continuous access to new consensus files, which it can obtain by running an accompanying Tor process in client mode. The coordinator has the following functions, which will be described in this section: - result aggregation. - schedule measurements. - v3bw file generation. 3.2.1.1 Aggregating Results Every second during a measurement, the measurers send the amount of verified measurement traffic they have received back from the relay. Additionally, the relay sends a MSM_BG cell each second to the coordinator with amount of non-measurement background traffic it is sending and receiving. For each second's reports, the coordinator sums the measurer's reports. The coordinator takes the minimum of the relay's reported sent and received background traffic. If, when compared to the measurer's reports for this second, the relay's claimed background traffic is more than what's allowed by the background/measurement traffic ratio, then the coordinator further clamps the relay's report down. The coordinator adds this final adjusted amount of background traffic to the sum of the measurer's reports. Once the coordinator has done the above for each second in the measurement (e.g. 30 times for a 30 second measurement), the coordinator takes the median of the 30 per-second throughputs and records it as the estimated capacity of the target relay. 3.2.1.2 Measurement Schedule The short term implementation of measurement scheduling will be simpler than the long term one due to (1) there only being one FlashFlow deployment, and (2) there being very few relays that support being measured by FlashFlow. In fact the FF coordinator will maintain a list of the relays that have updated to support being measured and have opted in to being measured, and it will only measure them. The coordinator divides time into a series of 24 hour periods, commonly referred to as days. Each period has measurement slots that are longer than a measurement lasts (30s), say 60s, to account for pre- and post-measurement work. Thus with 60s slots there's 1,440 slots in a day. At the start of each day the coordinator considers the list of relays that have opted in to being measured. From this list of relays, it repeatedly takes the relay with the largest existing capacity estimate. It selects a random slot. If the slot has existing relays assigned to it, the coordinator makes sure there is enough additional measurer capacity to handle this relay. If so, it assigns this relay to this slot. If not, it keeps picking new random slots until one has sufficient additional measurer capacity. Relays without existing capacity estimates are assumed to have the 75th percentile capacity of the current network. If a relay is not online when it's scheduled to be measured, it doesn't get measured that day. 3.2.1.2.1 Example Assume the FF deployment has 1 Gbit/s of measurer capacity. Assume the chosen multiplier m=2. Assume there are only 5 slots in a measurement period. Consider a set of relays with the following existing capacity estimates and that have opted in to being measured by FlashFlow. - 500 Mbit/s - 300 Mbit/s - 250 Mbit/s - 200 Mbit/s - 100 Mbit/s - 50 Mbit/s The coordinator takes the largest relay, 500 Mbit/s, and picks a random slot for it. It picks slot 3. The coordinator takes the next largest, 300, and randomly picks slot 2. The slots are now: 0 | 1 | 2 | 3 | 4 -------|-------|-------|-------|------- | | 300 | 500 | | | | | The coordinator takes the next largest, 250, and randomly picks slot 2. Slot 2 already has 600 Mbit/s of measurer capacity reserved (300*m); given just 1000 Mbit/s of total measurer capacity, there is just 400 Mbit/s of spare capacity while this relay requires 500 Mbit/s. There is not enough room in slot 2 for this relay. The coordinator picks a new random slot, 0. 0 | 1 | 2 | 3 | 4 -------|-------|-------|-------|------- 250 | | 300 | 500 | | | | | The next largest is 200 and the coordinator randomly picks slot 2 again (wow!). As there is just enough spare capacity, the coordinator assigns this relay to slot 2. 0 | 1 | 2 | 3 | 4 -------|-------|-------|-------|------- 250 | | 300 | 500 | | | 200 | | The coordinator randomly picks slot 4 for the last remaining relays, in that order. 0 | 1 | 2 | 3 | 4 -------|-------|-------|-------|------- 250 | | 300 | 500 | 100 | | 200 | | 50 3.2.1.3 Generating V3BW files Every hour the FF coordinator produces a v3bw file in which it stores the latest capacity estimate for every relay it has measured in the last week. The coordinator will create this file on the host's local file system. Previously-generated v3bw files will not be deleted by the coordinator. A symbolic link at a static path will always point to the latest v3bw file. $ ls -l v3bw -> v3bw.2020-03-01-05-00-00 v3bw.2020-03-01-00-00-00 v3bw.2020-03-01-01-00-00 v3bw.2020-03-01-02-00-00 v3bw.2020-03-01-03-00-00 v3bw.2020-03-01-04-00-00 v3bw.2020-03-01-05-00-00 3.2.2 FlashFlow Measurer The measurers take commands from the coordinator, connect to target relays with many sockets, send them traffic, and verify the received traffic is the same as what was sent. Measurers need access to a lot of internal tor functionality. One strategy is to house as much logic as possible inside an compile-time-optional control port module that calls into other parts of tor. Alternatively FlashFlow could link against tor and call internal tor functions directly. [XXX for now I'll assume that an optional little-t tor control port module housing a lot of this code is the best idea.] Notable new things that internal tor code will need to do on the measurer (client) side: 1. Open many TLS+TCP connections to the same relay on purpose. 2. Verify echo cells. 3.2.2.1 Open many connections FlashFlow prototypes needed to "hack in" a flag in the open-a-connection-with-this-relay function call chain that indicated whether or not we wanted to force a new connection to be created. Most of Tor doesn't care if it reuses an existing connection, but FF does want to create many different connections. The cleanest way to accomplish this will be investigated. On the relay side, these measurer connections do not count towards DoS detection algorithms. 3.2.2.2 Verify echo cells A parameter will exist to tell the measurers with what frequency they shall verify that cells echoed back to them match what was sent. This parameter does not need to exist outside of the FF deployment (e.g. it doesn't need to be a consensus parameter). The parameter instructs the measurers to check 1 out of every N cells. The measurer keeps a count of how many measurement cells it has sent. It also logically splits its output stream of cells into buckets of size N. At the start of each bucket (when num_sent % N == 0), the measurer chooses a random index in the bucket. Upon sending the cell at that index (num_sent % N == chosen_index), the measurer records the cell. The measurer also counts cells that it receives. When it receives a cell at an index that was recorded, it verifies that the received cell matches the recorded sent cell. If they match, no special action is taken. If they don't match, the measurer indicates failure to the coordinator and target relay and closes all connections, ending the measurement. 3.2.2.2.1 Example Consider bucket_size is 1000. For the moment ignore cell encryption. We start at idx=0 and pick an idx in [0, 1000) to record, say 640. At idx=640 we record the cell. At idx=1000 we choose a new idx in [1000, 2000) to record, say 1236. At idx=1236 we record the cell. At idx=2000 we choose a new idx in [2000, 3000). Etc. There's 2000+ cells in flight and the measurer has recorded two items: - (640, contents_of_cellA) - (1236, contents_of_cellB) Consider the receive side now. It counts the cells it receives. At receive idx=640, it checks the received cell matches the saved cell from before. At receive idx=1236, it again checks the received cell matches. Etc. 3.2.2.2.2 Motivation A malicious relay may want to skip decryption of measurement cells to save CPU cycles and obtain a higher capacity estimate. More generally, it could generate fake measurement cells locally, ignore the measurement traffic it is receiving, and flood the measurer with more traffic that it (the measurer) is even sending. The security of echo cell verification is discussed in section 3.3.1. 3.3 Security In this section we discuss the security of various aspects of FlashFlow and the tor changes it requires. 3.3.1 Echo Cell Verification: Bucket Size A smaller bucket size means more cells are checked and FF is more likely to detect a malicious target. It also means more bookkeeping overhead (CPU/RAM). An adversary that knows bucket_size and cheats on one item out of every bucket_size items will have a 1/bucket_size chance of getting caught in the first bucket. This is the worst case adversary. While cheating on just a single item per bucket yields very little advantage, cheating on more items per bucket increases the likelihood the adversary gets caught. Thus only the worst case is considered here. In general, the odds the adversary can successfully cheat in a single bucket are (bucket_size-1)/bucket_size Thus the odds the adversary can cheat in X consecutive buckets are [(bucket_size-1)/bucket_size]^X In our case, X will be highly varied: Slow relays won't see very many buckets, but fast relays will. The damage to the network a very slow relay can do by faking being only slightly faster is limited. Nonetheless, for now we motivate the selection of bucket_size with a slow relay: - Assume a very slow relay of 1 Mbit/s capacity that will cheat 1 cell in each bucket. Assume a 30 second measurement. - The relay will handle 1*30 = 30 Mbit of traffic during the measurement, or 3.75 MB, or 3.75 million bytes. - Cells are 514 bytes. Approximately (e.g. ignoring TLS) 7300 cells will be sent/recv over the course of the measurement. - A bucket_size of 50 results in about 146 buckets over the course of the 30s measurement. - Therefore, the odds of the adversary cheating successfully as (49/50)^(146), or about 5.2%. This sounds high, but a relay capable of double the bandwidth (2 Mbit/s) will have (49/50)^(2*146) or 0.2% odds of success, which is quite low. Wanting a <1% chance that a 10 Mbit/s relay can successfully cheat results in a bucket size of approximately 125: - 10*30 = 300 Mbit of traffic during 30s measurement. 37.5 million bytes. - 37,500,000 bytes / 514 bytes/cell = ~73,000 cells - bucket_size of 125 cells means 73,000 / 125 = 584 buckets - (124/125)^(584) = 0.918% chance of successfully cheating Slower relays can cheat more easily but the amount of extra weight they can obtain is insignificant in absolute terms. Faster relays are essentially unable to cheat. 3.3.2 Weight Inflation Target relays are an active part of the measurement process; they know they are getting measured. While a relay cannot fake the measurement traffic, it can trivially stop transferring client background traffic for the duration of the measurement yet claim it carried some. More generally, there is no verification of the claimed amount of background traffic during the measurement. The relay can claim whatever it wants, but it will not be trusted above the ratio the FlashFlow deployment is configured to know. This places an easy to understand, firm, and (if set as we suggest) low cap on how much a relay can inflate its measured capacity. Consider a background/measurement ratio of 1/4, or 25%. Assume the relay in question has a hard limit on capacity (e.g. from its NIC) of 100 Mbit/s. The relay is supposed to use up to 25% of its capacity for background traffic and the remaining 75%+ capacity for measurement traffic. Instead the relay ceases carrying background traffic, uses all 100 Mbit/s of capacity to handle measurement traffic, and reports ~33 Mbit/s of background traffic (33/133 = ~25%). FlashFlow would trust this and consider the relay capable of 133 Mbit/s. (If the relay were to report more than ~33 Mbit/s, FlashFlow limits it to just ~33 Mbit/s.) With r=25%, FlashFlow only allows 1.33x weight inflation. Prior work shows that Torflow allows weight inflation by a factor of 89x [0] or even 177x [1]. The ratio chosen is a trade-off between impact on background traffic and security: r=50% allows a relay to double its weight but won't impact client traffic for relays with steady state throughput below 50%, while r=10% allows a very low inflation factor but will cause throttling of client traffic at far more relays. We suggest r=25% (and thus 1/(1-0.25)=1.33x inflation) for a reasonable trade-off between performance and security. It may be possible to catch relays performing this attack, especially if they literally drop all background traffic during the measurement: have the measurer (or some party on its behalf) create a regular stream through the relay and measure the throughput on the stream before/during/after the measurement. This can be explored longer term. 3.3.3 Incomplete Authentication The short term FlashFlow implementation has the relay set two torrc options if they would like to allow themselves to be measured: a flag allowing measurement, and the list of coordinator TLS certificate that are allowed to start a measurement. The relay drops MSM_PARAMS cells from coordinators it does not trust, and immediately closes the connection after that. A FF coordinator cannot convince a relay to enter measurement mode unless the relay trusts its TLS certificate. A trusted coordinator specifies in the MSM_PARAMS cell the IP addresses of the measurers the relay shall expect to connect to it shortly. The target adds the measurer IP addresses to a whitelist in the DoS connection limit system, exempting them from any configured connection limit. If a measurer is behind a NAT, an adversary behind the same NAT can DoS the relay's available sockets until the end of the measurement. The adversary could also pretend to be the measurer. Such an adversary could induce measurement failures and inaccuracies. (Note: the whitelist is cleared after the measurement is over.) 4. FlashFlow measurement system: Medium term The medium term deployment stage begins after FlashFlow has been implemented and relays are starting to update to a version of Tor that supports it. We plan to host a FlashFlow deployment consisting of a FF coordinator and a single FF measurer on a single 1 Gbit/s machine. Data produced by this deployment will be made available (semi?) publicly, including both v3bw files and intermediate results. Any development changes needed during this time would go through separate proposals. 5. FlashFlow measurement system: Long term In the long term, finishing-touch development work will be done, including adding better authentication and measurement scheduling, and experiments will be run to determine the best way to integrate FlashFlow into the Tor ecosystem. Any development changes needed during this time would go through separate proposals. 5.1 Authentication to Target Relay Short term deployment already had FlashFlow coordinators using TLS certificates when connecting to relays, but in the long term, directory authorities will vote on the consensus parameter for which coordinators should be allowed to perform measurements. The voting is done in the same way they currently vote on recommended tor versions. FlashFlow measurers will be updated to use TLS certificates when connecting to relays too. FlashFlow coordinators will update the contents of MSM_PARAMS cells to contain measurer TLS certificates instead of IP addresses, and relays will update to expect this change. 5.2 Measurement Scheduling Short term deployment only has one FF deployment running. Long term this may no longer be the case because, for example, more than one directory authority decides to adopt it and they each want to run their own deployment. FF deployments will need to coordinate between themselves to not measure the same relay at the same time, and to handle new relays as they join during the middle of a measurement period (during the day). The following is quoted from Section 4.3 of the FlashFlow paper. To measure all relays in the network, the BWAuths periodically determine the measurement schedule. The schedule determines when and by whom a relay should be measured. We assume that the BWAuths have sufficiently synchronized clocks to facilitate coordinating their schedules. A measurement schedule is created for each measurement period, the length p of which determines how often a relay is measured. We use a measurement period of p = 24 hours. To help avoid active denial-of-service attacks on targeted relays, the measurement schedule is randomized and known only to the BWAuths. Before the next measurement period starts, the BWAuths collectively generate a random seed (e.g. using Tor’s secure-randomness protocol). Each BWAuth can then locally determine the shared schedule using pseudorandom bits extracted from that seed. The algorithm to create the schedule considers each measurement period to be divided into a sequence of t-second measurement slots. For each old relay, slots for each BWAuth to measure it are selected uniformly at random without replacement from all slots in the period that have sufficient unallocated measurement capacity to accommodate the measurement. When a new relay appears, it is measured separately by each BWAuth in the first slots with sufficient unallocated capacity. Note that this design ensures that old relays will continue to be measured, with new relays given secondary priority in the order they arrive. 5.3 Experiments [XXX todo] 5.4 Other Changes/Investigations/Ideas - How can FlashFlow data be used in a way that doesn't lead to poor load balancing given the following items that lead to non-uniform client behavior: - Guards that high-traffic HSs choose (for 3 months at a time) - Guard vs middle flag allocation issues - New Guard nodes (Guardfraction) - Exit policies other than default/all - Directory activity - Total onion service activity - Super long-lived circuits - Add a cell that the target relay sends to the coordinator indicating its CPU and memory usage, whether it has a shortage of sockets, how much bandwidth load it has been experiencing lately, etc. Use this information to lower a relays weight, never increase. - If FlashFlow and sbws work together (as opposed to FlashFlow replacing sbws), consider logic for how much sbws can increase/decrease FF results - Coordination of multiple FlashFlow deployments: scheduling of measurements, seeding schedule with shared random value. - Other background/measurement traffic ratios. Dynamic? (known slow relay => more allowed bg traffic?) - Catching relays inflating their measured capacity by dropping background traffic. - What to do about co-located relays. Can they be detected reliably? Should we just add a torrc option a la MyFamily for co-located relays? - What is the explanation for dennis.jackson's scary graphs in this [2] ticket? Was it because of the speed test? Why? Will FlashFlow produce the same behavior? 6. Citations [0] F. Thill. Hidden Service Tracking Detection and Bandwidth Cheating in Tor Anonymity Network. Master’s thesis, Univ. Luxembourg, 2014. [1] A. Johnson, R. Jansen, N. Hopper, A. Segal, and P. Syverson. PeerFlow: Secure Load Balancing in Tor. Proceedings on Privacy Enhancing Technologies (PoPETs), 2017(2), April 2017. [2] Mike Perry: Graph onionperf and consensus information from Rob's experiments https://trac.torproject.org/projects/tor/ticket/33076

5 8

Proposal 320: Removing TAP usage from v2 onion services
by Nick Mathewson 29 May '20

29 May '20

``` Filename: 320-tap-out-again.md Title: Removing TAP usage from v2 onion services Author: Nick Mathewson Created: 11 May 2020 Status: Open ``` (This proposal is part of the Walking Onions spec project. It updates proposal 245.) # Removing TAP from v2 onion services As we implement walking onions, we're faced with a problem: what to do with TAP keys? They are bulky and insecure, and not used for anything besides v2 onion services. Keeping them in SNIPs would consume bandwidth, and keeping them indirectly would consume complexity. It would be nicer to remove TAP keys entirely. But although v2 onion services are obsolescent and their cryptographic parameters are disturbing, we do not want to drop support for them as part of the Walking Onions migration. If we did so, then we would force some users to choose between Walking Onions and v2 onion services, which we do not want to do. Instead, we describe here a phased plan to replace TAP in v2 onion services with ntor. This change improves the forward secrecy of _some_ of the session keys used with v2 onion services, but does not improve their authentication, which is strongly tied to truncated SHA1 hashes of RSA1024 keys. Implementing this change is more complex than similar changes elsewhere in the Tor protocol, since we do not want clients or services to leak whether they have support for this proposal, until support is widespread enough that revealing it is no longer a privacy risk. ## Ntor keys, link specifiers, and SNIPs in v2 descriptors. We define these entries that may appear in v2 onion service descriptors, once per introduction point. "identity-ed25519" "ntor-onion-key" [at most once each per intro point.] These values are in the same format as and follow the same rules as their equivalents in router descriptors. "link-specifiers" [at most once per introduction point] This value is the same as the link specifiers in a v3 onion service descriptor, and follows the same rules. Services should not include any of these fields unless a new network parameter, "hsv2-intro-updated" is set to 1. Clients should not parse these fields or use them unless "hsv2-use-intro-updated" is set to 1. We define a new field that can be used for hsv2 descriptors with walking onions: "snip" [at most once] This value is the same as the snip field introduced to a v3 onion service descriptor by proposal (XXX) and follows the same rules. Services should not include this field unless a new network parameter, "hsv2-intro-snip" is set to 1. Clients should not parse this field or use it unless the parameter "hsv2-use-intro-snip" is set to 1. Additionally, relays SHOULD omit the following legacy intro point parameters when a new network parameter, "hsv2-intro-legacy" is set to 0: "ip-address", "onion-port", and "onion-key". Clients should treat them as optional when "hsv2-tolerate-no-legacy" is set to 1. ## INTRODUCE cells, RENDEZVOUS cells, and ntor. We allow clients to specify the rendezvous point's ntor key in the INTRODUCE2 cell instead of the TAP key. To do this, the client simply sets KLEN to 32, and includes the ntor key for the relay. Clients should only use ntor keys in this way if the network parameter "hsv2-client-rend-ntor" is set to 1, and if the entry "allow-rend-ntor" is present in the onion service descriptor. Services should only advertise "allow-rend-ntor" in this way if the network parameter "hsv2-service-rend-ntor" is set to 1. ## Migration steps First, we implement all of the above, but set it to be disabled by default. We use torrc fields to selectively enable them for testing purposes, to make sure they work. Once all non-LTS versions of Tor without support for this proposal are obsolete, we can safely enable "hsv2-client-rend-ntor", "hsv2-service-rend-ntor", "hsv2-intro-updated", and "hsv2-use-intro-updated". Once all non-LTS versions of Tor without support for walking onions are obsolete, we can safely enable "hsv2-intro-snip", "hsv2-use-intro-snip", and "hsv2-tolerate-no-legacy". Once all non-LTS versions of Tor without support for _both_ of the above implementations are finally obsolete, we can finally set "hsv2-intro-legacy" to 0. ## Future work There is a final TAP-like protocol used for v2 hidden services: the client uses RSA1024 and DH1024 to send information about the rendezvous point and to start negotiating the session key to be used for end-to-end encryption. In theory we could get a benefit to forward secrecy by using ntor instead of TAP here, but we would get not corresponding benefit for authentication, since authentication is still ultimately tied to HSv2's scary RSA1024-plus-truncated-SHA1 combination. Given that, it might be just as good to allow the client to insert a curve25519 key in place of their DH1024 key, and use that for the DH handshake instead. That would be a separate proposal, though: this proposal is enough to allow all relays to drop TAP support.

8 11

Proposal 322: Extending link specifiers to include the directory port
by Nick Mathewson 27 May '20

27 May '20

``` Filename: 322-dirport-linkspec.md Title: Extending link specifiers to include the directory port Author: Nick Mathewson Created: 27 May 2020 Status: Open ``` ## Motivation Directory ports remain the only way to contact a (non-bridge) Tor relay that isn't expressible as a Link Specifier. We haven't specified a link specifier of this kind so far, since it isn't a way to contact a relay to create a channel. But authorities still expose directory ports, and encourage relays to use them preferentially for uploading and downloading. And with Walking Onions, it would be convenient to try to make every kind of "address" a link specifier -- we'd like want authorities to be able to specify a list of link specifiers that can be used to contact them for uploads and downloads. > It is possible that after revision, Walking Onions won't need a way > to specify this information. If so, this proposal should be moved > to "Reserve" status as generally unuseful. ## Proposal We reserve a new link specifier type "dir-url", for use with the directory system. This is a variable-length link specifier, containing a URL prefix. The only currently supported URL schema is "http://". Implementations SHOULD ignore unrecognized schemas. IPv4 and IPv6 addresses MAY be used directory; hostnames are also allowed. Implementations MAY ignore hostnames and only use raw addresses. The URL prefix includes everything through the string "tor" in the directory hierarchy. A dir-url link specifier SHOULD NOT appear in an EXTEND cell; implementations SHOULD reject them if they do appear.

1 0

Proposal 321: Better performance and usability for the MyFamily option (v2)
by Nick Mathewson 27 May '20

27 May '20

``` Filename: 321-happy-families.md Title: Better performance and usability for the MyFamily option (v2) Author: Nick Mathewson Created: 27 May 2020 Status: Open ``` ## Problem statement. The current family mechanism allows well-behaved relays to identify that they all belong to the same 'family', and should not be used in the same circuits. Right now, families work by having every family member list every other family member in its server descriptor. This winds up using O(n^2) space in microdescriptors and server descriptors. (For RAM, we can de-duplicate families which sometimes helps.) Adding or removing a server from the family requires all the other servers to change their torrc settings. The is growth in size is not just a theoretical problem. Family declarations currently make up a little over 55% of the microdescriptors in the directory--around 24% after compression. The largest family has around 270 members. With Walking Onions, 270 members times a 160-bit hashed identifier leads to over 5 kilobytes per SNIP, which is much greater than we'd want to use. This is an updated version of proposal 242. It differs by clarifying requirements and providing a more detailed migration plan. ## Design overview. In this design, every family has a master ed25519 "family key". A node is in the family iff its server descriptor includes a certificate of its ed25519 identity key with the family key. The certificate format the one in the tor-certs.txt spec; we would allocate a new certificate type for this usage. These certificates would need to include the signing key in the appropriate extension. Note that because server descriptors are signed with the node's ed25519 signing key, this creates a bidirectional relationship between the two keys, so that nodes can't be put in families without their consent. ## Changes to router descriptors We add a new entry to server descriptors: "family-cert" NL "-----BEGIN FAMILY CERT-----" NL cert "-----END FAMILY CERT-----". This entry contains a base64-encoded certificate as described above. It may appear any number of times; authorities MAY reject descriptors that include it more than three times. ## Changes to microdescriptors We add a new entry to microdescriptors: `family-keys`. This line contains one or more space-separated strings describing families to which the node belongs. These strings MUST be sorted in lexicographic order. Clients MUST NOT depend on any particular property of these strings. ## Changes to voting algorithm We allocate a new consensus method number for voting on these keys. When generating microdescriptors using a suitable consensus method, the authorities include a "family-keys" line if the underlying server descriptor contains any valid family-cert lines. For each valid family-cert in the server descriptor, they add a base-64-encoded string of that family-cert's signing key. > See also "deriving family lines from family-keys?" below for an > interesting but more difficult extension mechanism that I would > not recommend. ## Relay configuration There are several ways that we could configure relays to let them include family certificates in their descriptors. The easiest would be putting the private family key on each relay, so that the relays could generate their own certificates. This is easy to configure, but slightly risky: if the private key is compromised on any relay, anybody can claim membership in the family. That isn't so very bad, however -- all the relays would need to do in this event would be to move to a new private family key. A more orthodox method would be to keep the private key somewhere offline, and using it to generate a certificate for each relay in the family as needed. These certificates should be made with long-enough lifetimes, and relays should warn when they are going to expire soon. ## Changes to relay behavior Each relay should track which other relays they have seen using the same family-key as itself. When generating a router descriptor, each relay should list all of these relays on the legacy 'family' line. This keeps the "family" lines up-to-date with "family-keys" lines for compliant relays. Relays should continue listing relays in their family lines if they have seen a relay with that identity using the same family-key at any time in the last 7 days. The presence of this line should be configured by a network parameter, `derive-family-line`. Relays whose family lines do not stay at least mostly in sync with their family keys should be marked invalid by the authorities. ## Client behavior Clients should treat node A and node B as belonging to the same family if ANY of these is true: * The client has descriptors for A and B, and A's descriptor lists B in its family line, and B's descriptor lists A in its family line. * Client A has descriptors for A and B, and they both contain the same entry in their family-keys or family-cert. ## Migration For some time, existing relays and clients will not support family certificates. Because of this, we try to make sure above the well-behaved relays will list the same entries in both places. Once enough clients have migrated to using family certificates, authorities SHOULD disable `derive-family-line`. ## Security Listing families remains as voluntary in this design as in today's Tor, though bad-relay hunters can continue to look for families that have not adopted a family key. A hostile relay family could list a "family" line that did not match its "family-certs" values. However, the only reason to do so would be in order to launch a client partitioning attack, which is probably less valuable than the kinds of attacks that they could run by simply not listing families at all. ## Appendix: deriving family lines from family-keys? As an alternative, we might declare that _authorities_ should keep family lines in sync with family-certs. Here is a design sketch of how we might do that, but I don't think it's actually a good idea, since it would require major changes to the data flow of the voting system. In this design, authorties would include a "family-keys" line in each router section in their votes corresponding to a relay with any family-cert. When generating final microdescriptors using this method, the authorities would use these lines to add entries to the microdescriptors' family lines: 1. For every relay appearing in a routerstatus's family-keys, the relays calculate a consensus family-keys value by listing including all those keys that are listed by a majority of those voters listing the same router with the same descriptor. (This is the algorithm we use for voting on other values derived from the descriptor.) 2. The authorities then compute a set of "expanded families": one for each family key. Each "expanded family" is a set containing every router in the consensus associated with that key in its consensus family-keys value. 3. The authorities discard all "expanded families" of size 1 or smaller. 4. Every router listed for the "expanded family" has every other router added to the "family" line in its microdescriptor. (The "family" line is then re-canonicalized according to the rules of proposal 298 to remove its ) 5. Note that the final microdescriptor consensus will include the digest of the derived microdescriptor in step 4, rather than the digest of the microdescriptor listed in the original votes. (This calculation is deterministic.) The problem with this approach is that authorities would have to s to fetch microdescriptors they do not have in order to replace their family lines. Currently, voting never requires an authority to fetch a microdescriptor from another authority. If we implement vote compression and diffs as in the Walking Onions proposal, however, we might suppose that votes could include microdescriptors directly. Still, this is likely more complexity than we want for a transition mechanism. ## Appendix: Deriving family-keys from families?? We might also imagine that authorities could infer which families exist from the graph of family relationships, and then include synthetic "family-keys" entries for routers that belong to the same family. This has two challenges: first, to compute these synthetic family keys, the authorities would need to have the same graph of family relationships to begin with, which once again would require them to include the complete list of families in their votes. Secondly, finding all the families is equivalent to finding all maximal cliques in a graph. This problem is NP-hard in its general case. Although polynomial solutions exist for nice well-behaved graphs, we'd still need to worry about hostile relays including strange family relationships in order to drive the algorithm into its exponential cases. ## Appendix: New assigned values We need a new assigned value for the certificate type used for family signing keys. We need a new consensus method for placing family-keys lines in microdescriptors. ## Appendix: New network parameters * `derive-family-line`: If 1, relays should derive family lines from observed family-keys. If 0, they do not. Min: 0, Max: 1. Default: 1.

1 0