- tor-dev - lists.torproject.org

[RFC] Proposal: A First Take at PoW Over Introduction Circuits
by George Kadianakis 14 Apr '20

14 Apr '20

Hello list, hope everyone is safe and doing well! I present you an initial draft of a proposal on PoW-based defences for onion services under DoS. The proposal is not finished yet and it needs tuning and fixing. There are many places marked with XXX and TODO around the proposal that should be addressed. The important part is that looking at the numbers it does seem like this proposal can work as a concept and serve its intended purpose. The most handwavey parts of the proposal right now are [INTRO_QUEUE] and [POW_SECURITY] and if this thing fails in the end, it's probably gonna be something that slipped over there. Hence, we should polish these sections before we proceed with any sort of engineering here. In any case, I decided to send it to the list even in premature form, so that it can serve as a stable point of reference in subsequent discussions. It can also be found in my git repo: https://github.com/asn-d6/torspec/tree/pow-over-intro Cheers and stay safe! --- Filename: xxx-pow-over-intro-v1 Title: A First Take at PoW Over Introduction Circuits Author: George Kadianakis Created: 2 April 2020 Status: Draft 0. Abstract This proposal aims to thwart introduction flooding DoS attacks by introducing a dynamic Proof-Of-Work protocol that occurs over introduction circuits. 1. Motivation So far our attempts at limiting the impact of introduction flooding DoS attacks on onion services has been focused on horizontal scaling with Onionbalance, optimizing the CPU usage of Tor and applying congestion control using rate limiting. While these measures move the goalpost forward, a core problem with onion service DoS is that building rendezvous circuits is a costly procedure both for the service and for the network. If we ever hope to have truly reachable global onion services, we need to make it harder for attackers to overload the service with introduction requests. This proposal achieves this by allowing onion services to specify an optional dynamic proof-of-work scheme that its clients need to participate in if they want to get served. With the right parameters, this proof-of-work scheme acts as a gatekeeper to block amplification attacks by attackers while letting legitimate clients through. 1.1. Threat model [THREAT_MODEL] 1.1.1. Attacker profiles [ATTACKER_MODEL] This proposal is written to thwart specific attackers. A simple PoW proposal cannot defend against all and every DoS attack on the Internet, but there are adverary models we can defend against. Let's start with some adversary profiles: "The script-kiddie" The script-kiddie has a single computer and pushes it to its limits. Perhaps it also has a VPS and a pwned server. We are talking about an attacker with total access to 10 Ghz of CPU and 10 GBs of RAM. We consider the total cost for this attacker to be zero $. "The small botnet" The small botnet is a bunch of computers lined up to do an introduction flooding attack. Assuming 500 medium-range computers, we are talking about an attacker with total access to 10 Thz of CPU and 10 TB of RAM. We consider the upfront cost for this attacker to be about $400. "The large botnet" The large botnet is a serious operation with many thousands of computers organized to do this attack. Assuming 100k medium-range computers, we are talking about an attacker with total access to 200 Thz of CPU and 200 TB of RAM. The upfront cost for this attacker is about $36k. We hope that this proposal can help us defend against the script-kiddie attacker and small botnets. To defend against a large botnet we would need more tools in our disposal (see [FUTURE_WORK]). {XXX: Do the above make sense? What other attackers do we care about? What other metrics do we care about? Network speed? I got the botnet costs from here [REF_BOTNET] Back up our claims of defence.} 1.1.2. User profiles [USER_MODEL] We have attackers and we have users. Here are a few user profiles: "The standard web user" This is a standard laptop/desktop user who is trying to browse the web. They don't know how these defences work and they don't care to configure or tweak them. They are gonna use the default values and if the site doesn't load, they are gonna close their browser and be sad at Tor. They run a 2Ghz computer with 4GB of RAM. "The motivated user" This is a user that really wants to reach their destination. They don't care about the journey; they just want to get there. They know what's going on; they are willing to tweak the default values and make their computer do expensive multi-minute PoW computations to get where they want to be. "The mobile user" This is a motivated user on a mobile phone. Even tho they want to read the news article, they don't have much leeway on stressing their machine to do more computation. We hope that this proposal will allow the motivated user to always connect where they want to connect to, and also give more chances to the other user groups to reach the destination. 1.1.3. The DoS Catch-22 [CATCH22] This proposal is not perfect and it does not cover all the use cases. Still, we think that by covering some use cases and giving reachability to the people who really need it, we will severely demotivate the attackers from continuing the DoS attacks and hence stop the DoS threat all together. Furthermore, by increasing the cost to launch a DoS attack, a big class of DoS attackers will disappear from the map, since the expected ROI will decrease. 2. System Overview 2.1. Tor protocol overview +----------------------------------+ | | +-------+ INTRO1 +-----------+ INTRO2 +--------+ | |Client |-------->|Intro Point|------->| PoW |-----------+ | +-------+ +-----------+ |Verifier| | | +--------+ | | | | | | | | | +----------v---------+ | | |Intro Priority Queue| | +---------+--------------------+---+ | | | Rendezvous | | | circuits | | | v v v The proof-of-work scheme specified in this proposal takes place during the introduction phase of the onion service protocol. It's an optional mechanism that only occurs if the service requires it. It can be enabled and disabled either through its torrc or through the control port. In summary, the following steps are taken for the protocol to complete: 1) Service encodes PoW parameters in descriptor [DESC_POW] 2) Client fetches descriptor and computes PoW [CLIENT_POW] 3) Client completes PoW and sends results in INTRO1 cell [INTRO1_POW] 4) Service verifies PoW and queues introduction based on PoW effort [SERVICE_VERIFY] 2.2. Proof-of-work overview 2.2.1. Primitives For our proof-of-work scheme we want to minimize the spread of resources between a motivated attacker and legitimate clients. This means that we are looking to minimize any benefits that GPUs or ACICs can offer to an attacker. For this reason we chose argon2 [REF_ARGON2] as the hash function for our proof-of-work scheme since it's well audited and GPU-resistant and to some extend ASIC-resistant as well. As a password hash function, argon2 by default outputs 32 bytes of hash, and takes as primary input a message and a nonce/salt. For the purposes of this specification we will define an argon2() function as: uint8_t hash_output[32] = argon2(uint8_t *message, uint8_t *nonce)'. See section [ARGON_PARAMS] for more information on the secondary inputs of argon2. 2.2.2. Dynamic PoW DoS is a dynamic problem where the attacker's capabilities constantly change, and hence we want our proof-of-work system to be dynamic and not stuck with a static difficulty setting. Hence, instead of forcing clients to go below a static target like in Bitcoin to be successful, we ask clients to "bid" using their PoW effort. Effectively, a client gets higher priority the higher effort they put into their proof-of-work. This is similar to how proof-of-stake works but instead of staking coins, you stake work. The benefit here is that legitimate clients who really care about getting access can spend a big amount of effort into their PoW computation, which should guarantee access to the service given reasonable adversary models. See [POW_SECURITY] for more details about these guarantees and tradeoffs. 3. Protocol specification 3.1. Service encodes PoW parameters in descriptor [DESC_POW] This whole protocol starts with the service encoding the PoW parameters in the 'encrypted' (inner) part of the v3 descriptor. As follows: "pow-params" SP type SP seed-b64 SP expiration-time NL [At most once] type: The type of PoW system used. We call the one specified here "v1" seed-b64: A random seed that should be used as the input to the PoW hash function. Should be 32 random bytes encoded in base64 without trailing padding. expiration-time: A timestamp after which the above seed expires and is no longer valid as the input for PoW. It's needed so that the size of our replay cache does not grow infinitely. It should be set to an hour in the future (+- some randomness). {TODO: PARAM_TUNING} {XXX: Expiration time makes us even more susceptible to clock skews, but it's needed so that our replay cache refreshes. How to fix this? See [CLIENT_BEHAVIOR] for more details.} 3.2. Client fetches descriptor and computes PoW [CLIENT_POW] If a client receives a descriptor with "pow-params", it should assume that the service is expecting a PoW input as part of the introduction protocol. In such cases, the client should have been configured with a specific PoW 'target' (which is a 32-byte integer similar to the 'target' of Bitcoin [REF_TARGET]). See [POW_SECURITY] for more information of how such a target should be set. For the purposes of this section, we will assume that the target has been set automatically by Tor, or the user configured it manually. Now the client parses the descriptor and extracts the PoW parameters. It makes sure that the expiration-time has not expired and if it has, it needs to fetch a new descriptor. To complete the PoW the client follows the following logic: a) Client generates 'nonce' as 32 random bytes. b) Client derives 'seed' by decoding 'seed-b64'. c) Client computes hash_output = argon2(seed, nonce) d) Client interprets hash_output as a 32-byte big-endian integer. e) Client checks if int(hash_output) <= target. e1) If yes, success! The client uses 'hash_output' as the hash and 'nonce' and 'seed' as its inputs. e2) If no, fail! The client interprets 'nonce' as a big-endian integer, increments it by one, and goes back to step (c). At the end of the above procedure, the client should have a triplet (hash_output, seed, nonce) that can be used as the answer to the PoW puzzle. How quickly this happens depends solely on the 'target' parameter. 3.3. Client sends PoW in INTRO1 cell [INTRO1_POW] Now that the client has an answer to the puzzle it's time to encode it into an INTRODUCE1 cell. To do so the client adds an extension to the encrypted portion of the INTRODUCE1 cell by using the EXTENSIONS field (see [PROCESS_INTRO2] section in rend-spec-v3.txt). The encrypted portion of the INTRODUCE1 cell only gets read by the onion service and is ignored by the introduction point. We propose a new EXT_FIELD_TYPE value: [01] -- PROOF_OF_WORK The EXT_FIELD content format is: POW_VERSION [1 byte] POW_SEED [32 bytes] POW_NONCE [32 bytes] POW_OUTPUT [32 bytes] where: POW_VERSION is 1 for the protocol specified in this proposal POW_SEED is 'seed' from the section above POW_NONCE is 'nonce' from the section above POW_OUTPUT is 'hash_output' from the section above {XXX: do we need POW_VERSION? Perhaps we can use EXT_FIELD_TYPE as version} {XXX: do we need to encode the SEED? Perhaps we can ommit it since the service already knows it. But what happens in cases of desynch, if client has diff seed from service?} {XXX: Do we need to include the output? Probably not. The service has to compute it anyway during verification. What's the use?} This will increase the INTRODUCE1 payload size by 99 bytes since the extension type and length is 2 extra bytes, the N_EXTENSIONS field is always present and currently set to 0 and the EXT_FIELD is 97 bytes. According to ticket #33650, INTRODUCE1 cells currently have more than 200 bytes available. 3.4. Service verifies PoW and handles the introduction [SERVICE_VERIFY] When a service receives an INTRODUCE1 with the PROOF_OF_WORK extension, it should check its configuration on whether proof-of-work is required to complete the introduction. If it's not required, the extension SHOULD BE ignored. If it is required, the service follows the procedure detailed in this section. 3.4.1. PoW verification To verify the client's proof-of-work the service extracts (hash_output, seed, nonce) from the INTRODUCE1 cell and MUST do the following steps: 1) Make sure that the client's seed is identical to the active seed. 2) Check the client's nonce for replays (see [REPLAY_PROTECTION] section). 3) Verify that 'hash_output =?= argon2(seed, nonce) If any of these steps fail the service MUST ignore this introduction request and abort the protocol. If all the steps passed, then the circuit is added to the introduction queue as detailed in section [INTRO_QUEUE]. 3.4.1.1. Replay protection [REPLAY_PROTECTION] The service MUST NOT accept introduction requests with the same (seed, nonce) tuple. For this reason a replay protection mechanism must be employed. The simplest way is to use a simple hash table to check whether a (seed, nonce) tuple has been used before for the actiev duration of a seed. Depending on how long a seed stays active this might be a viable solution with reasonable memory/time overhead. If there is a worry that we might get too many introductions during the lifetime of a seed, we can use a Bloom filter as our replay cache mechanism. The probabilistic nature of Bloom filters means that sometimes we will flag some connections as replays even if they are not; with this false positive probability increasing as the number of entries increase. However, with the right parameter tuning this probability should be negligible and well handled by clients. {TODO: PARAM_TUNING} 3.4.2. The Introduction Queue [INTRO_QUEUE] 3.4.2.1. Adding introductions to the introduction queue When PoW is enabled and a verified introduction comes through, the service instead of jumping straight into rendezvous, queues it and prioritizes it based on how much effort was devoted by the client to PoW. This means that introduction requests with high effort should be prioritized over those with low effort. To do so, the service maintains an "introduction priority queue" data structure. Each element in that priority queue is an introduction request, and its priority is the effort put into its PoW: When a verified introduction comes through, the service interprets the PoW hash as a 32-byte big-endian integer 'hash_int' and based on that integer it inserts it into the right position of the priority_queue: The smallest 'hash_int' goes forward in the queue. If two elements have the same value, the older one has priority over the newer one. {XXX: Is this operation with 32-bytes integers expensive? How to make cheaper?} {TODO: PARAM_TUNING: If the priority queue is only ordered based on the effort what attacks can happen in various scenarios? Do we want to order on time+effort? Which scenarios and attackers should we examine here?} {TODO: PARAM_TUNING: What's the max size of the queue? How do we trim it? Can we use WRED usefully?} 3.4.2.2. Handling introductions from the introduction queue [HANDLE_QUEUE] The service should handle introductions by pulling from the introduction queue. 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. With this tempo, we can process 200 introduction cells per second. {XXX: Is this good?} {TODO: PARAM_TUNING: STRAWMAN: This needs hella tuning. Processing 20 cells per 100ms is probably unmaintainable, since each cell is quite expensive: doing so involving path selection, crypto and making circuits. We will need to profile this procedure and see how we can do this scheduling better.} {XXX: This might be a nice place to promote multithreading. Queues and pools are nice objects to do multithreading since you can have multiple threads pull from the queue, or leave stuff on the queue. Not sure if this should be in the proposal tho.} 4. Attacker strategies [ATTACK_META] Now that we defined our protocol we need to start tweaking the various knobs. But before we can do that, we first need to understand a few high-level attacker strategies to see what we are fighting against. 4.1.1. Total overwhelm strat Given the way the introduction queue works (see [HANDLE_QUEUE]), a very effective strategy for the attacker is to totally overwhelm the queue processing by sending more high-effort introductions than the onion service can handle at any given tick. To do so, the attacker would have to send at least 20 high-effort introduction cells every 100ms, where high-effort is a PoW which is above the estimated level of "the motivated user" (see [USER_MODEL]). An easier attack for the adversary, is the same strategy but with introduction cells that are all above the comfortable level of "the standard user" (see [USER_MODEL]). This would block out all standard users and only allow motivated users to pass. {XXX: What other attack strategies we should care about?} 5. Parameter tuning [POW_SECURITY] There are various parameters in this system that need to be tuned. We will first start by tuning the default difficulty of our PoW system. That's gonna define an expected time for attackers and clients to succeed. We are then gonna tune the parameters of the argon2 hash function. That will define the resources that an attacker needs to spend to overwhelm the onion service, the resources that the service needs to spend to verify introduction requests, and the resources that legitimate clients need to spend to get to the onon service. 5.1. PoW Difficulty settings The difficulty setting of our PoW basically dictates how difficult it should be to get a success in our PoW system. In classic PoW systems, "success" is defined as getting a hash output below the "target". However, since our system is dynamic, we define "success" as an abstract high-effort computation. Even tho our system is dynamic, we still need default difficulty settings that will define the metagame. The client and attacker can still aim higher or lower, but for UX purposes and for analysis purposes we do need to define some difficulties. We hence created the table (see [REF_TABLE]) below which shows how much time a legitimate client with a single machine should expect to burn before they get a single success. The x-axis is how many successes we want the attacker to be able to do per second: the more successes we allow the adversary, the more they can overwhelm our introduction queue. The y-axis is how many machines the adversary has in her disposal, ranging from just 5 to 1000. =============================================================== | Expected Time (in seconds) Per Success For One Machine | =========================================================================== | | | Attacker Succeses 1 5 10 20 30 50 | | per second | | | | 5 5 1 0 0 0 0 | | 50 50 10 5 2 1 1 | | 100 100 20 10 5 3 2 | | Attacker 200 200 40 20 10 6 4 | | Boxes 300 300 60 30 15 10 6 | | 400 400 80 40 20 13 8 | | 500 500 100 50 25 16 10 | | 1000 1000 200 100 50 33 20 | | | ============================================================================ Here is how you can read the table above: - If an adversary has a botnet with 1000 boxes, and we want to limit her to 1 success per second, then a legitimate client with a single box should be expected to spend 1000 seconds getting a single success. - If an adversary has a botnet with 1000 boxes, and we want to limit her to 5 successes per second, then a legitimate client with a single box should be expected to spend 200 seconds getting a single success. - If an adversary has a botnet with 500 boxes, and we want to limit her to 5 successes per second, then a legitimate client with a single box should be expected to spend 100 seconds getting a single success. - If an adversary has access to 50 boxes, and we want to limit her to 5 successes per second, then a legitimate client with a single box should be expected to spend 10 seconds getting a single success. - If an adversary has access to 5 boxes, and we want to limit her to 5 successes per second, then a legitimate client with a single box should be expected to spend 1 seconds getting a single success. With the above table we can create some profiles for default values of our PoW difficulty. So for example, we can use the last case as the default parameter for Tor Browser, and then create three more profiles for more expensive cases, scaling up to the first case which could be hardest since the client is expected to spend 15 minutes for a single introduction. {TODO: PARAM_TUNING You can see that this section is completely CPU/memory agnostic, and it does not take into account potential optimizations that can come from GPU/ASICs. This is intentional so that we don't put more variables into this equation right now, but as this proposal moves forward we will need to put more concrete values here.} 5.2. Argon2 parameters [ARGON_PARAMS] We now need to define the secondary argon2 parameters as defined in [REF_ARGON2]. This includes the number of lanes 'h', the memory size 'm', the number of iterations 't'. Section 9 of [REF_ARGON2] recommends an approach of how to tune these parameters. To tune these parameters we are looking to *minimize* the verification speed of an onion service, while *maximizing* the sparse resources spent by an adversary trying to overwhelm the service using [ATTACK_META]. When it comes to verification speed, to verify a single introduction cell the service needs to do a single argon2 call: so the service will need to do hundreds of those per second as INTRODUCE2 cells arrive. The service will have to do this verification step even for very cheap zero-effort PoW received, so this has to be a cheap procedure so that it doesn't become a DoS vector of each own. Hence each individual argon2 call must be cheap enough to be able to be done comfortably and plentifuly by an onion service with a single host (or horizontally scaled with Onionbalance). At the same time, the adversary will have to do thousands of these calls if she wants to make high-effort PoW, so it's this assymetry that we are looking to exploit here. Right now, the most expensive resource for adversaries is the RAM size, and that's why we chose argon2 which is memory-hard. To minmax this game we will need {TODO: PARAM_TUNING: I've had a hard time minmaxing this game for argon2. Even argon2 invocations with a small memory parameter will take multiple milliseconds to run on my machine, and the parameters recommended in section 8 of the paper all take many hundreds of milliseconds. This is just not practical for our use case, since we want to process hundreds of such PoW per second... I also did not manage to find a benchmark of argon2 calls for different CPU/GPU/FPGA configurations.} 5. Client behavior [CLIENT_BEHAVIOR] This proposal introduces a bunch of new ways where a legitimate client can fail to reach the onion service. Furthermore, there is currently no end-to-end way for the onion service to inform the client that the introduction failed. The INTRO_ACK cell is not end-to-end (it's from the introduction point to the client) and hence it does not allow the service to inform the client that the rendezvous is never gonna occur. Let's examine a few such cases: 5.1. Timeout issues Alice can fail to reach the onion service if her introduction request falls off the priority queue, or if the priority queue is so big that the connection times out. Is building a new introduction circuit sufficient here? Or do we need to build an end-to-end mechanism over the introduction circuit to inform her? {XXX} How should timeout values change here since the priority queue will cause bigger delays than usual to rendezvous? Can there be some feedback mechanism to inform the client of its queue position or ETA? 5.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. How should this be handled? Should we have multiple active seeds at the same time similar to how we have overlapping descriptors and time periods in v3? This would solve the problem but it grows the complexity of the system substantially. {XXX} 5.3. Other descriptor issues Another race condition here is if the service enables PoW, while a client has a cached descriptor. How will the client notice that PoW is needed? Does it need to fetch a new descriptor? Should there be another feedback mechanism? {XXX} 5. Discussion 5.1. UX This proposal has user facing UX consequences. Here are a few UX approaches with increasing engineering difficulty: a) Tor Browser needs a "range field" which the user can use to specify how much effort they want to spend in PoW if this ever occurs while they are browsing. The ranges could be from "Easy" to "Difficult", or we could try to estimate time using an average computer. This setting is in the Tor Browser settings and users need to find it. b) We start with a default effort setting, and then we use the new onion errors (see #19251) to estimate when an onion service connection has failed because of DoS, and only then we present the user a "range field" which they can set dynamically. Detecting when an onion service connection has failed because of DoS can be hard because of the lack of feedback (see [CLIENT_BEHAVIOR]) c) We start with a default effort setting, and if things fail we automatically try to figure out an effort setting that will work for the user by doing some trial-and-error connections with different effort values. Until the connection succeeds we present a "Service is overwhelmed, please wait" message to the user. For this proposal to work initially we need at least (a), and then we can start thinking of how far we want to take it. 5.2. Future directions [FUTURE_WORK] This is just the beginning in DoS defences for Tor and there are various future avenues that we can investigate. Here is a brief summary of these: "More advanced PoW schemes" -- We could use more advanced memory-hard PoW schemes like MTP-argon2 or Itsuku to make it even harder for adversaries to create successful PoWs. Unfortunately these schemes have much bigger proof sizes, and they won't fit in INTRODUCE1 cells. See #31223 for more details. "Third-party anonymous credentials" -- We can use anonymous credentials and a third-party token issuance server on the clearnet to issue tokens based on PoW or CAPTCHA and then use those tokens to get access to the service. See [REF_CREDS] for more details. "PoW + Anonymous Credentials" -- We can make a hybrid of the above ideas where we present a hard puzzle to the user when connecting to the onion service, and if they solve it we then give the user a bunch of anonymous tokens that can be used in the future. This can all happen between the client and the service without a need for a third party. All of the above approaches are much more complicated than this proposal, and hence we want to start easy before we get into more serious projects. 5.3. Environment We love the environment! We are concerned of how PoW schemes can waste energy by doing useless hash iterations. Here is a few reasons we still decided to pursue a PoW approach here: "We are not making things worse" -- DoS attacks are already happening and attackers are already burning energy to carry them out both on the attacker side, on the service side and on the network side. We think that asking legitimate clients to carry out PoW computations is not gonna affect the equation too much, since an attacker right now can very quickly cause the same damage that hundreds of legitimate clients do a whole day. "We hope to make things better" -- The hope is that proposals like this will make the DoS actors go away and hence the PoW system will not be used. As long as DoS is happening there will be a waste of energy, but if we manage to demotivate them with technical means, the network as a whole will less wasteful. Also see [CATCH22] for a similar argument. 6. References [REF_ARGON2]: https://github.com/P-H-C/phc-winner-argon2/blob/master/argon2-specs.pdf https://password-hashing.net/#argon2 [REF_TABLE]: The table is based on the script below plus some manual editing for readability: https://gist.github.com/asn-d6/99a936b0467b0cef88a677baaf0bbd04 [REF_BOTNET]: https://media.kasperskycontenthub.com/wp-content/uploads/sites/43/2009/07/0… [REF_CREDS]: https://lists.torproject.org/pipermail/tor-dev/2020-March/014198.html [REF_TARGET]: https://en.bitcoin.it/wiki/Target

3 5

Walking onions status update: week 6 notes
by Nick Mathewson 10 Apr '20

10 Apr '20

Walking Onions: week 6 update On our current grant from the zcash foundation, I'm working on a full specification for the Walking Onions design. I'm going to try to send out these updates once a week. My previous updates are linked below: Week 1: formats, preliminaries, git repositories, binary diffs, metaformat decisions, and Merkle Tree trickery. https://lists.torproject.org/pipermail/tor-dev/2020-March/014178.html Week 2: Specifying details of SNIP and ENDIVE formats, in CDDL. https://lists.torproject.org/pipermail/tor-dev/2020-March/014181.html Week 3: Expanding ENDIVEs into SNIPs. https://lists.torproject.org/pipermail/tor-dev/2020-March/014194.html Week 4: Voting (part 1) and extending circuits. https://lists.torproject.org/pipermail/tor-dev/2020-March/014207.html Week 5: Voting (part 2) https://lists.torproject.org/pipermail/tor-dev/2020-April/014218.html This week I did a pass through all of the proposal that's written so far, trying to revise it for consistency and to look for unexpected gaps. Then I wrote a first take on a section about client behavior, and outlined sections about how to keep onions services working. == Fixing inconsistencies There were, predictably, some places where I had wrote things in an introduction to a section, and then turn around and did them differently later in the section. I tried to make those consistent when I could. For one example, I think Microdescs should now be embedded in votes. They were separate before, for space reasons, but now that we have defined support for compression and diffs in voting, we don't need to keep votes as small as we did before. But when I went to explain voting, I didn't actually give a place to put in microdescriptors. This is fixed now. == Example rules, and changes to voting. Thanks to Teor's help and feedback on previous iterations of voting, the voting operations [VOTING] are now more consistent, and specified more consistently. I had to describe a "sorting" operation for use with voting, since CBOR's default "canonical" ordering is not what we actually want semantically. To try to make sure voting could do what we need, I wrote up an example VotingRules object in a new appendix [EXRULES]. This turned up a few impedance mismatches between the available voting rules, the SNIP format, and the ENDIVE format. I fixed some of these, and marked others with "XXX" strings to come back and fix on the next pass through voting. == More index and extension protocol work I've found a need for a new link specifier (LS) for use with onion services. Unlike a regular routing index LS, this kind includes a routing index and a count of how many relays to skip after that position. This lets a client say, for example, "Give me the third relay after the one whose HDirIndex is 0xbf9630". (In order to answer this query, the extending relay needs to return not only the SNIP for the third relay, but all SNIPs between the first relay and that relay, so that the client can trust the answer.) This kind of LS can be used with the new NIL handshake if the client _only_ wants to fetch the descriptors; the details are in the circuit-protocol section [EXTENDING]. == Client operations, part 1 In a new section 06, I've sketched out solutions for guards, bridges, bootstrapping, and several kinds of path restriction [CLIENTS]. In doing so I've turned up a possible need for new IP-based and key-based indices; I've added those to a new appendix where I'm listing the different indices I think we'll need [INDEXLIST]. == Outlines of work to come I've added outlines for a new section 7 about making onion services work, and a new section 8 about tracking some new ways that relays might have to misbehave. I've also added quick sketches for a pair of additional proposals we'll need: one for a better family notation, and one for finally migrating away from the last vestiges of TAP. But none of those are quite next: In the coming week, if time permits, I want to get exit policies figured out. They are the biggest missing piece of section 06 right now, and seem to me to be the biggest remaining gap in the specification. == Fun facts: At 109KiB, this is now the longest Tor proposal ever. I will need to come up with a different fun fact next week. == References: [CLIENTS] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/06-clien… [EXTENDING] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/05-exten… [EXRULES] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/AF-examp… [INDEXLIST] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/AG-index… [VOTING] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/03-votin…

1 0

Walking onions status update: week 5 notes
by Nick Mathewson 06 Apr '20

06 Apr '20

Walking Onions: week 5 update On our current grant from the zcash foundation, I'm working on a full specification for the Walking Onions design. I'm going to try to send out these updates once a week. My previous updates are linked below: Week 1: formats, preliminaries, git repositories, binary diffs, metaformat decisions, and Merkle Tree trickery. https://lists.torproject.org/pipermail/tor-dev/2020-March/014178.html Week 2: Specifying details of SNIP and ENDIVE formats, in CDDL. https://lists.torproject.org/pipermail/tor-dev/2020-March/014181.html Week 3: Expanding ENDIVEs into SNIPs. https://lists.torproject.org/pipermail/tor-dev/2020-March/014194.html Week 4: Voting (part 1) and extending circuits. https://lists.torproject.org/pipermail/tor-dev/2020-March/014207.html This week found me still rather distracted by fallout from current events and preparations for more isolation at home. I didn't get a complete rewrite done. But I do, however, think I figured out voting. == The big idea for voting Our current system for voting on relay properties is fairly piecemeal: every property has its own independent specification in dir-spec.txt [DIRSPEC], which can get kind of cumbersome. Every time we have a new property to specify, if it can't be defined as a flag, we need to define a new consensus method that puts it in the consensus or the microdescriptors. Until authorities have upgraded to support the new method, they can't sign consensuses generated with it, since they don't know how those consensuses are generated. We can solve both problems by defining "vote tabulation" as a set of parameterized operations operating over a set of CBOR inputs. Individual operations can be simple, like "Take the median of all integer votes", or progressively more complex. What's more, we can specify these voting operations themselves as data, which gives us more advantages: First, that we no longer need independent English-language specs for each field in the consensus--and second, that we can introduce new voting rules or change the existing ones without adding new code. As long as a quorum of authorities agree about the rules for voting on some field, the other authorities can safely follow those rules, and include the new field in the consensus ENDIVE and SNIPs. We would only need to introduce new consensus methods when we wanted to introduce support for an entirely new operation. After voting is done, some transformations are needed to transform the objects it produces. SNIP signatures need to be signed, indexes built, and so on. I've left this unspecified for now, since I am likely to return to the SNIP and ENDIVE formats again in the coming weeks, and I'll want to tweak the transformation quite a lot. This is not something I would want to implement in C. Rust would be a better fit -- or some functional language. Fortunately, only authorities need to follow this algorithm. I have initial specifications written for these operations that I believe are sufficient (or nearly so?) for all the things that we do in voting now. These are in the draft voting spec as it stands [VOTING]. I expect that they are full of errors, but I wouldn't be too concerned right now; I'm going to need to do another pass over them, but I want to return to voting a bit later (see below) once I have more SNIP uses specified. == Backward compatibility in voting There are two separate backward compatibility issues in voting. The first issue is easier: how to operate when we aren't sure whether all the authorities have upgraded to support this new voting format. For this purpose, I'm including legacy votes as part of the new vote format, signatures and all. This will make the new votes bigger until all the authorities have definitely upgraded, but other changes (voting diffs and compression) should offset this risk. We can stop sending legacy votes when everybody has upgraded. (I thought about having an "implicit version" of each legacy vote derived from the new vote, but that seemed riskier, and like it would involve lots more new code of dubious benefit.) The second issue is a bit harder: for clients that haven't upgraded to walking onions, we'll need to generate legacy consensus documents for a some time. This doesn't need to follow exactly the same rules as consensus voting uses today: instead we should have legacy consensus documents derived from the CBOR consensus, so that we only need to maintain one voting algorithm long term. I've left this part unspecified for now too; I'll be comping back to it after a round of revisions and SNIP usage design. == Next steps I plan to spend the first part of week going over what I've written so far and trying to make it correct and consistent, and to fill in the baps that I have. After that, I'm planning to write the example sections for how circuit extension works. If time remains, this is when I finally move on to section 6 of the proposal, which will be pretty involved -- I've got to explain how to implement all (or most?) of our current client behavior using walking onions, and what that implies about the set of indexes and fields in our documents. == Other updates Our paper got into USENIX Security 2020! (This is the paper about Walking Onions that Chelsea Komlo and Ian Goldberg wrote with me. It has basically the same content as our existing tech report [TECHREPORT].) The conference is scheduled in mid-August, in Boston: we'll see whether people are gathering in groups by then. If not, I imagine we'll be putting together some kind of video. [DIRSPEC] https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt [TECHREPORT] https://crysp.uwaterloo.ca/software/walkingonions/ [VOTING] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/03-votin…

1 0

Re: [tor-dev] Chutney tests fail for tor/maint-0.3.5 (bug #33677)
by c 01 Apr '20

01 Apr '20

(Forgot to hit "reply all" in my mail client) On Mon, 30 Mar 2020 13:22:21 +1000 teor <teor(a)riseup.net> wrote: > This ticket is a cleanup ticket, after some other changes have been made. > I've edited the ticket description to make that clearer. Understood, thank you for clarifying. > Check for onion service descriptor uploads: > https://trac.torproject.org/projects/tor/ticket/33609 > > Someone else is working on the microdescriptor changes at the moment. > > Would you like to start working on the onion service descriptor changes? Sure, it would give me an opportunity to learn about onion descriptors in more detail. I will get started on it. But first, looking at it more, I think my struggle with understanding what to do stems from my unfamiliarity with the Chutney codebase (first I have heard of the tool was with this project, even though commits date back to 2011). I need to make sure I understand #33609 sufficiently: - Is the requested functionality only for Chutney or will Tor potentially need any changes to allow for HS verification? - So I know where to begin looking in the codebase, the ticket wants us to "check each onion service log" -- is this referring to Tor log output (such as the instances chutney spawns), chutney-specific logs, or something else entirely? - For "check v2 and v3 onion services" -- check if they've propagated the network? - For "call it an extra 200% 'bootstrap' stage" -- again is this chutney-specific? I only know bootstrapping percentage from Tor notice-level logging and obviously it only goes up to 100%, so I'm wondering if "200%" is a magic number here or something arbitrary. From this and the parent #33050 it doesn't seem to me like the request is very clear. I am reading proposals 311-313 after sending this message so maybe I can come across some answers to my questions/confusions via the proposals themselves. The proposals will probably give me a better idea of the work I am in for overall, too, and perhaps I should have come across them sooner. I figure it is wise regardless to ask for clarification here and read while I wait for feedback. Efficiency and all :) Caitlin

2 1

txtorcon 20.0.0
by meejah 01 Apr '20

01 Apr '20

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 I'm pleased to announce txtorcon 20.0.0. This fixes a few bugs and officially deprecates Python 2 support. * Use real GeoIP database or nothing (https://github.com/meejah/txtorcon/issues/250) * Change abstract base classes import in preperation for Python 3.8 (thanks @glowatsk) * Python 3.4 is no longer supported * Python 2 is deprecated; all new code should be Python 3. Support for Python 2 will be removed in a future release. You can download the release from PyPI or GitHub (or of course "pip install txtorcon"): https://pypi.python.org/pypi/txtorcon/20.0.0 https://github.com/meejah/txtorcon/releases/tag/v20.0.0 Releases are also available from the hidden service: http://timaq4ygg2iegci7.onion/txtorcon-20.0.0.tar.gz http://timaq4ygg2iegci7.onion/txtorcon-20.0.0.tar.gz.asc Or via a "version 3" service: http://fjblvrw2jrxnhtg67qpbzi45r7ofojaoo3orzykesly2j3c2m3htapid.onion/txtor… http://fjblvrw2jrxnhtg67qpbzi45r7ofojaoo3orzykesly2j3c2m3htapid.onion/txtor… You can verify the sha256sum of both by running the following 4 lines in a shell wherever you have the files downloaded: cat <<EOF | sha256sum --check 122cd081786396f57718adda1c1a5eb01b8e9a4832fcd140918b45c10359377a txtorcon-20.0.0.tar.gz 5c1145566a8733105da851b794e7b15cb56cea48693635b55c4bddfb79fe629d txtorcon-20.0.0-py2.py3-none-any.whl EOF thanks, meejah -----BEGIN PGP SIGNATURE----- iQFFBAEBCgAvFiEEnVor1WiOy4id680/wmAoAxKAaacFAl6EDnURHG1lZWphaEBt ZWVqYWguY2EACgkQwmAoAxKAaadv4AgAkIny/Pt55kEppkxlqu4/B4ddfU7oQNLD 8lwoYyUZbYtS8XwiBaqY6SR/UU9MhhswdoPU50WBq3h4Im+3jrmm7MbVD4uR6Uvt BnZIMzCJlQNcGpfbaGmtyrtbBNazQLTDOAxxQ7WM/MD8rip1zlP8MeL7yBgE3VEC JInw9DWN+fbQhbsTQgdiLLLhBXOFqZuXgz7auPnGzu+5LsIeJd6ZnWzuQ6TlzL3R rLgrMAasxTMzKoJB51jmDpCOeaj4b68XK+MY130/xSdENb2ZyGbuSF4LpZUjs4RU Sqiwtevu/bT/th0XBqcg79RHnwGLK/g1pJRB27RaOVbuh6f+lENc4Q== =4q9v -----END PGP SIGNATURE-----

1 0

Improving onion service availability during DoS using anonymous credentials
by George Kadianakis 30 Mar '20

30 Mar '20

Hello list, there has been lots of discussions about improving onion service availability under DoS conditions. Many approaches have been proposed [OOO] but only a few have been tried and even fewer show any real improvements to the availability of the service. An approach that we've been considering is the use of anonymous credentials as a way to prioritize good clients from bad clients. The idea is that the service gives tokens to clients it believes to be good, and prioritizes client with tokens over clients without tokens whenever possible. This is a post to start a discussion of how such approaches could work and whether they are worth pursuing futher. == Preliminaries == === When should the access control take place? === Doing DoS defenses with anon credentials is all about enforcing access control at the right point of the protocol so that the amplification factor of evil clients gets cut as early as possible. Very roughly the phases of the onion service protocol are: descriptor fetch phase, intro phase, rendezvous phase. Let's see how those look like for the purposes of access control: - Doing the access control during the descriptor fetch stage is something worth considering because it's the first phase of the protocol and hence the earliest and best place to soak up any damage from evil clients. There is already a form of optional access control implemented here called "client authorization" and it's worth thinking of what's lacking to make it useful against DoS attackers. I'm gonna address this in section [CLIENTAUTH]. - Doing the access control during the introduction phase is another fruitful approach. Blocking bad clients during introduction means that they dont get to force the service to create a costly rendezvous circuit, and since services have a long-term circuit open towards the intro points it makes it easier for services to pass access control related data to the intro point. This is actually the approach we are gonna be talking most about in this post. - Finally, doing the access control during the rendezvous phase is way too late since by that time the onion service has already spent lots of resources catering the evil client, so let's ignore that. === Entities of an anonymous credential system === Anonymous credential systems traditionally have three entities that concern us: - The Issuer: the entity who issues the credentials/tokens - The Prover: the entity who collects tokens and uses them to get access - The Verifier: the entity who verifies that tokens are legit and grants/restricts access In the world of onion services, the Issuer is naturally the onion service, and the Prover is the onion service client. The Verifier could either be the onion service itself or its introduction points. We will see below how this could work and the relevant tradeoffs. +--------+ +------------+ +--------------------+ | Client |<-+-+-+-->|Intro point |<--+---+-->|Onion service | |(Prover)| |(Verifier?) | |(Issuer)(Verifier?) | +--------+ +------------+ +--------------------+ === How do tokens get around? === A main question here is "How do good clients end up with tokens?". For the purposes of this post, we will assume that clients get these tokens in an out of band fashion. For example, a journalist can give tokens to her sources over Signal so they can use them with Securedrop. Or a forum operator can give tokens to old-time members of the forum to be used during a DoS. A natural chicken-and-egg problem occurs here since how is an onion service supposed to give tokens to its users if it's unreachable because of a DoS? We realize this is a big problem and we are not sure exactly how to solve it. This problem naturally limits the use of anonymous credential solutions, and sorta makes them a second-layer of defense since it assumes a first-layer of defense that allows operators to pass tokens to the good people. A first-layer approach here could perhaps look like PrivacyPass where users get tokens by solving CAPTCHAs. == Anonymous credentials == By surveying the anonymous credential literature we have found various types of anonymous credential schemes that are relevant for us: - Discrete-logarithm-based credentials based on blind signatures: This is a class of anon credential schemes that allow us to separate the verifier from the issuer. In particular this means that we can have the service issue the tokens, but the introduction point being the verifier. They are usually based on blind signatures like in the case of Microsoft's U-Prove system [UUU]. - Discrete-logarithm-based credentials based on OPRF: Another approach here is to use OPRF constructions based on the discrete logarithm problem to create an anonymous credential scheme like in the case of PrivacyPass [PPP]. The downside, IIUC, is that in PrivacyPass you can't have a different issuer and verifier so it's the onion service that needs to do the token verification restricting the damage soaking potential. - KVAC (Keyed-Verification Anonymous Credentials): KVAC-based credentails have comparable performance to Dlog-based credentials, and are also easier to create security proofs for due to them being based on symmetric primitives like algebraic MAC constructions [FFF]. The downside is that they assume that the verifier and the issuer is the same entity (the onion service). KVACs are used by Signal for protecting their group chat metadata [GGG]. Which construction and scheme we choose depends on our constraints and the parameters we are trying to minmax. So let's try to explore these constraints and parameters some more. == Space constraints == Let's assume that a client found some anonymous credentials for a service. How will clients present their credentials to the verifier, being either the service or the intro point? The natural approach here is for the client to include their token as part of the INTRODUCE1 cell. === How much space is available in INTRODUCE1 cells? [SPACE_CONSTRAINTS] === >From a brief experiment, I see that the INTRODUCE1 cell payload total size is 498 bytes, and we are already using 310 bytes from it, so that leaves about 188 bytes for use. The cell is extensible using cell extensions that can go either to the intro point [III] or to the service directly [EEE]. === How big are anonymous credentials redemptions? === >From looking at the literature it seems unlikely that those anonymous credentials can be presented given the size limitations from above. In particular here is the size needed for presenting/redeeming an anonymous credential in the various schemes: - Privacy Pass [PPP]: Credential redemption takes 396 bytes - Signal [GGG]: Their paper does not say exactly, but by peeking into their code it seems like presenting the credential takes about 620 bytes [CCC]. So if I'm not mistaken, it seems like we will need another way to present anonymous credentials to the service or intro point. === How can we trasmit these credentials then? === The unfortunate fact here is that presenting those credentials does not fit into the remaining space of an INTRODUCE1 cell, but it also wouldn't even fit if we created an entirely new relay cell for this purpose (say INTRO_REDEEM) since the relay cell payload is about 498 bytes and all the credentials above, except from PrivacyPass (!), are bigger than that. This means that we will either need to use a space-compact anonymous credential scheme, or to implement wide relay cells as suggested in ticket #33650 (which seems like lots of work!). == Computational constraints [COMPUTATIONAL_CONSTRAINTS] == Another big topic for consideration here is the computational resources required for the various operations of the scheme. In particular, how hard it is to issue such tokens, present such tokens and to verify such tokens. Different schemes have different computational profiles. I'm not gonna attempt to summarize the literature here because it will take me more time than I have right now. However, it's clear that our main priority here is a lightweight verification procedure, so that services or intro points spend as little energy as possible validating (potentially evil) tokens. It's imperative that verifying tokens is orders of magnitude more lightweight than the regular job that a service would do if credentials did not exist (i.e. doing path selection, creating a rendezvous circuit, doing the crypto, etc.) Our second priority here is a lighweight token issuance procedure, so that services don't spend too much time issuing tokens, especially if this is done in an automatic real-time manner that can be abused by an adversary. And finally, we don't particularly care about the token presentation procedure being lightweight, since this is a procedure that the attacker will also have to do and hence we want to incur as much costs to them as possible. == Discussion == ==== What's lacking from HSv3 client authorization [CLIENTAUTH] ==== It's really important to understand what's lacking from descriptor-level client authorization [QQQ] with regards to DoS defences before we spend time and energy implementing any anonymous credential approach. To use the descriptor-level client authorization feature for DoS protection the onion service operator creates a mirror of the website that is only reachable using descriptor-level client auth and then they pass client auth tokens to the clients they trust to be good natured. The above system can also be automated and turned into a web service. However this system has a bunch of drawbacks: - Given the implicit and anonymous nature of the descriptor-level client authorization system, if an evil actor gets their hand in a client auth token and they start DoSing the service, then the operator has no means to distinguish that client from any other client. Hence there is no way to identify individual bad clients and revoke them. This is the biggest issue with descriptor-based client authorization for the purposes of DoS defense. - Managing the access list (adding and removing clients) in the descriptor-level client authorization system is an expensive process because it requires uploading a new set of descriptors. Doing this too often (in an automated way) can cause lots of network traffic and also perhaps race conditions with clients who fetch descriptors. - Because the authentication happens by adding new lines on the descriptor, there is a fundamental limit on how many authed clients it can support. In particular, with some back-of-the-envelope calculations [ZZZ] an onion service can support a max of 250 authed clients this way. However, there is nothing stopping the operator from passing the same token to multiple clients and managing them as groups. The above issues would be addressed with intro-level client authorization since the authentication is explicit and done in real-time. It's worth thinking of the above drawbacks more and how we can bypass them to do something useful with the current system before we jump into new complexities and tradeoffs. --- Thanks for reading and looking forward to your feedback :) [OOO]: https://trac.torproject.org/projects/tor/ticket/31223 [ZZZ]: https://lists.torproject.org/pipermail/tor-dev/2016-November/011658.html [QQQ]: https://eprint.iacr.org/2013/516.pdf [PPP]: https://www.petsymposium.org/2018/files/papers/issue3/popets-2018-0026.pdf [UUU]: https://www.microsoft.com/en-us/research/project/u-prove/ [FFF]: https://eprint.iacr.org/2013/516.pdf [GGG]: https://signal.org/blog/signal-private-group-system/ [III]: https://github.com/torproject/torspec/blob/f81b1e6cc53b91abb3ae206807bc371f… [EEE]: https://github.com/torproject/torspec/blob/f81b1e6cc53b91abb3ae206807bc371f… [CCC]: https://github.com/signalapp/zkgroup/blob/4294e428216113d81f5c0cb50f578797d…

2 2

Chutney tests fail for tor/maint-0.3.5 (bug #33677)
by c 30 Mar '20

30 Mar '20

Hi, For the Outreachy.org internship project I decided to take on bug #33677 [1]. I followed steps to run `make test-network-all` both on tor master and maint-0.3.5 branches, using Chutney master branch. I tested before and after tweaking value of HS_WAIT_FOR_UNCHECKED_DIR_INFO just to ensure my testing environment was sane; all tests passed (except for two that were skipped on master: mixed+hs-v23 and mixed+hs-v23-ipv6, and one on 0.3.5: mixed+hs-v2, I assume this is expected though) on the first go, on both branches of Tor. Tests pass on Tor master after setting HS_WAIT_FOR_UNCHECKED_DIR_INFO to 0, but on maint-0.3.5 I've run tests a few times (both with and without CHUTNEY_DEBUG set) each time with a different outcome. Some of the tests which fail: basic-min [2], single-onion-v23 [3], bridges+ipv6-min [4], and ipv6-exit-min [5]. I have excerpted logs at the bottom of this message, narrowed down to test failures; let me know if I need to provide full logs or additional information. I'll keep digging on this issue; I just wanted to show my current progress and share what I hope to be useful information. Caitlin [1]: <https://trac.torproject.org/projects/tor/ticket/33677> "Stop waiting a set time for onion service descriptors" [2]: basic-min.log [...] Connecting: Exit to 127.0.0.1:4747 via client localhost:9005 DEBUG: socket 5 connecting to ('localhost', 9005)... DEBUG: Registering send-data-11 DEBUG: Registering check-12 Transmitting Data: DEBUG: Socks 4a request to 127.0.0.1:4747 DEBUG: Test status: {'send-data-11': 'not done', 'check-12': 'not done'}: 2/0/0 DEBUG: Test status: {'send-data-11': 'not done', 'check-12': 'not done'}: 2/0/0 DEBUG: Done with run(); all_done == False and failure_count == 0 Transmission: Failure [...] chutney verify round 1/1 failed Chutney failed 1 bootstraps; we may have a problem here. FAIL basic-min (exit status: 1) [3]: single-onion-v23.log [...] Connecting: HS to bkjqakom5elyh45a.onion:5858 (127.0.0.1:4747) via client localhost:9005 DEBUG: socket 7 connecting to ('localhost', 9005)... DEBUG: Registering send-data-21 DEBUG: Registering check-22 HS to moymkdharroenjd6zarfurdwmrr55j2zune6k7wafyfakwy2cis327id.onion:5858 (127.0.0.1:4747) via client localhost:9005 DEBUG: socket 8 connecting to ('localhost', 9005)... DEBUG: Registering send-data-23 DEBUG: Registering check-24 Transmitting Data: DEBUG: Socks 4a request to bkjqakom5elyh45a.onion:5858 DEBUG: Socks 4a request to moymkdharroenjd6zarfurdwmrr55j2zune6k7wafyfakwy2cis327id.onion:5858 DEBUG: new client from 127.0.0.1:54314 (fd=9) DEBUG: successfully connected (fd=8) DEBUG: Succeeded send-data-23 DEBUG: successful verification DEBUG: Succeeded check-24 DEBUG: Test status: {'send-data-21': 'not done', 'check-22': 'not done', 'send-data-23': 'success', 'check-24': 'success'}: 2/2/0 DEBUG: Test status: {'send-data-21': 'not done', 'check-22': 'not done', 'send-data-23': 'success', 'check-24': 'success'}: 2/2/0 DEBUG: Done with run(); all_done == False and failure_count == 0 Transmission: Failure [...] chutney verify round 1/1 failed Chutney failed 1 bootstraps; we may have a problem here. FAIL single-onion-v23 (exit status: 1) [4]: bridges+ipv6-min.log [...] Couldn't launch test005bc command '/home/c/git/tor/src/app/tor -f /home/c/git/chutney/net/nodes/005bc/torrc': exit 1, output 'Mar 28 10:47:36.717 [notice] Tor 0.3.5.10-dev (git-38e07b88fac51f2a) running on Linux with Libevent 2.1.8-stable, OpenSSL 1.1.1d, Zlib 1.2.11, Liblzma 5.2.4, and Libzstd 1.3.7. Mar 28 10:47:36.717 [notice] Tor can't help you if you use it wrong! Learn how to be safe at https://www.torproject.org/download/download#warning Mar 28 10:47:36.717 [notice] Read configuration file "/home/c/git/chutney/net/nodes/005bc/torrc". Mar 28 10:47:36.721 [warn] You have used DirAuthority or AlternateDirAuthority to specify alternate directory authorities in your configuration. This is potentially dangerous: it can make you look different from all other Tor users, and hurt your anonymity. Even if you've specified the same authorities as Tor uses by default, the defaults could change in the future. Be sure you know what you're doing. Mar 28 10:47:36.721 [warn] TestingTorNetwork is set. This will make your node almost unusable in the public Tor network, and is therefore only advised if you are building a testing Tor network! Mar 28 10:47:36.722 [notice] Opening Socks listener on 127.0.0.1:9005 Mar 28 10:47:36.722 [warn] Could not bind to 127.0.0.1:9005: Address already in use. Is Tor already running? Mar 28 10:47:36.722 [notice] Opening Control listener on 127.0.0.1:8005 Mar 28 10:47:36.722 [warn] Could not bind to 127.0.0.1:8005: Address already in use. Is Tor already running? Mar 28 10:47:36.722 [notice] Opening Control listener on /home/c/git/chutney/net/nodes/005bc/control Mar 28 10:47:36.722 [notice] Opened Control listener on /home/c/git/chutney/net/nodes/005bc/control Mar 28 10:47:36.722 [notice] Closing partially-constructed Control listener on /home/c/git/chutney/net/nodes/005bc/control:0 Mar 28 10:47:36.722 [warn] Failed to parse/validate config: Failed to bind one of the listener ports. Mar 28 10:47:36.722 [err] Reading config failed--see warnings above. ' [...] Launching chutney using Python 3.7.6 DEBUG: Tor version 0.3.5.10-dev (git-38e07b88fac51f2a). test000a is running with PID 2870: Tor 0.3.5.10-dev (git-38e07b88fac51f2a) test001a is running with PID 2873: Tor 0.3.5.10-dev (git-38e07b88fac51f2a) test002ba is running with PID 2911: Tor 0.3.5.10-dev (git-38e07b88fac51f2a) test003r is running with PID 2879: Tor 0.3.5.10-dev (git-38e07b88fac51f2a) test004br is running with PID 2882: Tor 0.3.5.10-dev (git-38e07b88fac51f2a) test005bc is stopped: Tor 0.3.5.10-dev (git-38e07b88fac51f2a) 5/6 nodes are running [...] bootstrap-network.sh failed Chutney failed 1 bootstraps; we may have a problem here. FAIL bridges+ipv6-min (exit status: 1) [5]: ipv6-exit-min.log [...] Connecting: Exit to 127.0.0.1:4747 via client localhost:9005 DEBUG: socket 5 connecting to ('localhost', 9005)... DEBUG: Registering send-data-11 DEBUG: Registering check-12 Transmitting Data: DEBUG: Socks 4a request to 127.0.0.1:4747 DEBUG: Test status: {'send-data-11': 'not done', 'check-12': 'not done'}: 2/0/0 DEBUG: Test status: {'send-data-11': 'not done', 'check-12': 'not done'}: 2/0/0 DEBUG: Done with run(); all_done == False and failure_count == 0 Transmission: Failure [...] chutney verify round 1/1 failed Chutney failed 1 bootstraps; we may have a problem here. FAIL ipv6-exit-min (exit status: 1)

2 1

Walking onions status update: week 3 notes
by Nick Mathewson 29 Mar '20

29 Mar '20

Walking Onions: week 3 update On our current grant from the zcash foundation, I'm working on a full specification for the Walking Onions design. I'm going to try to send out these updates once a week. My previous updates are linked below: Week 1: formats, preliminaries, git repositories, binary diffs, metaformat decisions, and Merkle Tree trickery. https://lists.torproject.org/pipermail/tor-dev/2020-March/014178.html Week 2: Specifying details of SNIP and ENDIVE formats, in CDDL. https://lists.torproject.org/pipermail/tor-dev/2020-March/014181.html You might like to check out those updates, and their references, if this update doesn't make sense to you. === As you might recall, the SNIPs need to be nice and small, but they need to be completely self-contained. The ENDIVE, on the other hand, needs to be diff-friendly, and compressible. Relays need to derive all the SNIPs from the ENDIVE. The ENDIVE and SNIP formats that I worked on during last week [SNIPFMT] was designed to meet these criteria. This week, I wrote up the algorithms to extract signed SNIPs from an ENDIVE. This is in section 4 [RECONST] of the specs in my work-in-progress repository [GITREPO] This was mainly straightforward consequence from the work I did last week, but there were a few things that turned up. One trickier aspect of this work is that we want to move most of the decision-making to the authorities, and have the relays simply do an expansion algorithm. Updating all the relays would be slow, so relays need to be able to handle new index types and data types without fully understanding them. That means that we need to specify an algorithm that can work flexibly with many future kinds of data. Another tricky aspect is that the data which the relays need to put into SNIPs all needs to be signed, so all of that data needs to come out the same when relays calculate it as the when the authorities calculate it. Thus, all the algorithms for building Merkle trees and indices and SNIPRouterData bodies need to be deterministic. I think that I got all of this relatively right in [RECONST], but there are probably some mistakes hiding in there. I'm hoping that there is a cleaner alternative to the weighted-index reconstruction algorithm -- the one that's there right now puts a lot of requirements on the input data, in order to avoid floating-point operations. === After working on ENDIVE expansion, I moved on to the problem of authorities voting. There's a lot of uncertainty here and decisions I'll need to make. The biggest decision is how the new voting process for ENDIVEs should relate to the current voting process for consensus documents. The choices seem to be: * Have two processes with different kinds of votes. * Expand the information that goes into current votes, and generate ENDIVEs as a new kind of consensus from the current voting process. * Design the ENDIVE voting process so that it can also be used to generate current-style consensuses. Using separate processes might be simplest, but it does carry risk for duplicated code, and for the two voting processes reaching divergent results. It would also be potentially bad if an authority could vote differently in each process. The second approach -- where ENDIVEs are another kind of consensus generated from current-style voting documents -- has some charm to it, but it perpetuates our current consensus-voting system, and makes us specify a second encoding of CBOR objects as text, if we want to vote on them meaningfully. This is a bit nasty, since the standard-specified text encoding of cbor is not a bijection, and doesn't mesh too well with our old directory format. Therefore the third approach seems a little better to me now. In it, we'd specify our votes as a CBOR-based format loosely based on the current vote format, and describe a way to extract from them the same data that is currently used for our voting algorithm. This would let us encode CBOR within the document naturally, while not having to throw away too much of our existing voting specification and voting code. I've got a few more ideas here, though I don't have any specs yet. I've been collecting the ideas in a notes file [VNOTES] so I don't forget them. === While working on voting notes, I found some areas where the ENDIVE and SNIP formats might be better. First, I hadn't thought about authority certificates. Those should go in, so that we can have the ENDIVE-signing keys be signed themselves with the authorities' long-lived identities. Second, there seem to be some opportunities for transmitting indices in a simpler way. Instead of assigning a weight to each router separately, for example, we could derive one weighted index from another weighted index by re-weighting it, as we do with the "bandwidth-weights" values in the current consensus. Teor also made some good suggestions for improving the diff format; I incorporated one and made a note to check the other. === I also spent a little while this week reading about BLS signatures, since they are the leading candidate for how we might do threshold signatures here. === Next week I'm going to try to get voting all specified. This will be a pretty deep dive, since I will need to maintain some backward compatibility with existing voting algorithms. There may be opportunities for simplification, however. === [GITREPO] https://github.com/nmathewson/walking-onions-wip [RECONST] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/04-recon… d [SNIPFMT] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/02-endiv… [VNOTES] https://github.com/nmathewson/walking-onions-wip/blob/master/notes/voting.t…

3 3

Walking onions status update: week 4 notes
by Nick Mathewson 29 Mar '20

29 Mar '20

Walking Onions: week 4 update On our current grant from the zcash foundation, I'm working on a full specification for the Walking Onions design. I'm going to try to send out these updates once a week. My previous updates are linked below: Week 1: formats, preliminaries, git repositories, binary diffs, metaformat decisions, and Merkle Tree trickery. https://lists.torproject.org/pipermail/tor-dev/2020-March/014178.html Week 2: Specifying details of SNIP and ENDIVE formats, in CDDL. https://lists.torproject.org/pipermail/tor-dev/2020-March/014181.html Week 3: Expanding ENDIVEs into SNIPs. https://lists.torproject.org/pipermail/tor-dev/2020-March/014194.html This week was pretty rough for me; the impact of being isolated at home is starting to kick in, and my kid is still trying to find a schedule that works for him. I got a lot less done this week than I had planned. That said, I _did_ get some good design done, in two areas: voting, and circuit extension. == Voting I'm trying to generalize our voting algorithms to minimize the need for new consensus formats in the future. I want most new fields to be self-describing in terms of how to tabulate votes for them. Trying to work this out has taken a bunch of energy, though and I'm not quite sure I'm doing it right. The work here is unfinished. I still think it's reasonable to encode existing votes and new votes in a new cbor-based structure. By using compression, a little redundancy in votes shouldn't hurt us too badly -- though that's something I need to benchmark eventually before we build this. I've come up with a way for voters to use diffs and compression when _uploading_ votes: first, the voter asks for a summary of what mechanisms are supported by the recipient and which older votes it has. Next, the voter can use that information to upload a vote diff with an appropriate compression format. Right now I believe that I have most of the fields for the votes figured out, but I need to clean them up a _lot_. SNIP bodies can work similarly to how microdescriptors work now, if we like -- or they could involve individual votes on input fields. I think I'm going to write up what I can here, and then revisit SNIP bodies once I've worked some on section 6 (the "fancy" client behavior). While working on voting, I found a need for various changes in the already written sections. For one example, the previous description of the ENDIVE format included the SNIP signatures as part of the signed ENDIVE. But we can't actually generate that as part our voting protocol: the authorities can't sign SNIPs until they know the complete ENDIVE contents, and so putting the SNIP signatures in the signed part of the ENDIVE would add an extra round of voting and signatures. Instead, I've moved the SNIP signatures (and related stuff) into the signature header of the ENDIVE. I've also worked somewhat on the so-called "root document" holding the network configuration parameters. I'm hoping that this document can have an effective lifetime of weeks or months for clients, and that clients can download only the parts that they need. The format is in section 02, but needs more description. The work-in-progress voting writeup is in [VOTING], but it is not so close to done. I think it will need a lot of writing before it's ready for even preliminary review; it doesn't make sense as it is, and it contradicts itself in places. == Extending circuits There are a few wrinkles here that we hadn't actually specified in earlier walking onions work! When one relay is told to extending a circuit to a target relay by index, the extending relay actually needs to include part of a SNIP for that second relay: otherwise, the extending relay won't know which onion key the client expects to receive for it. We don't want to send an entire SNIP -- only the parts that the client will expect to match. In addition to wide EXTEND cells, we'll also need wide RENDEZVOUS and INTRODUCE1 and INTRODUCE2 and TRUNCATED cells. All together, that means that having a general "cell fragmentation" mechanism is probably warranted; I've started a separate proposal for that [WIDE_EVERYTHING]. We're going to need a general extension format for CREATE and EXTEND cells, to signal other information, like SNIPs, requests for SNIPs, and so on. We also need a way to ask for SNIPs without actually performing a handshake. I've tried to fit these all together in a fairly logical way in [EXTENDING], but there's more to write here, including examples. == Fun facts The walking onion proposal is now the second-longest that we have ever had, behind only proposal 224 (v3 hidden services). == Next steps In this coming week I plan to try to wrap up section 3 on voting and section 5 on extending circuits. I'm going to go back to the start of section 2 and start revising all I've written so far for consistency. Time permitting, I want to sketch out all the knowns and unknowns for section 6 (on tricky client behavior). [EXTENDING] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/05-exten… [VOTING] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/02-votin… [WIDE_EVERYTHING] https://github.com/nmathewson/walking-onions-wip/blob/master/other-proposal…

2 1

Walking Onions status update: week 2 notes
by Nick Mathewson 29 Mar '20

29 Mar '20

Walking onions -- week 2 update Hi! On our current grant from the zcash foundation, I'm working on a full specification for the Walking Onions design. I'm going to try to send these out thee updates once a week, in case anybody is interested. My previous updates are linked below: Week 1: formats, preliminaries, git repositories, binary diffs, metaformat decisions, and Merkle Tree trickery. https://lists.torproject.org/pipermail/tor-dev/2020-March/014178.html You might like to have a look at that update, and its references, if this update doesn't make sense to you. === This week, I worked specifying the nitty-gritty of the SNIP and ENDIVE document formats. I used the CBOR meta-format [CBOR] to build them, and the CDDL specification language [CDDL] to specify what they should contain. As before, I've been working in a git repository at [GITHUB]; you can see the document I've been focusing on this week at [SNIPFMT]. (That's the thing to read if you want to send me patches for my grammar.) There were a few neat things to do here: * I had to define SNIPs so that clients and relays can be mostly agnostic about whether we're using a merkle tree or a bunch of signatures. * I had to define a binary diff format so that relays can keep on downloading diffs between ENDIVE documents. (Clients don't download ENDIVEs). I did a quick prototype of how to output this format, using python's difflib. * To make ENDIVE diffs as efficient as possible, it's important not to transmit data that changes in every ENDIVE. To this end, I've specified ENDIVEs so that the most volatile parts (Merkle trees and index ranges) are recomputed on the relay side. I still need to specify how these re-computations work, but I'm pretty sure I got the formats right. Doing this calculation should save relays a bunch of bandwidth each hour, but cost some implementation complexity. I'm going to have to come back to this choice going forward to see whether it's worth it. * Some object types are naturally extensible, some aren't. I've tried to err on the size of letting us expand important things in the future, and using maps (key->value mappings) for object that are particularly important. In CBOR, small integers are encoded with a little less space than small strings. To that end, I'm specifying the use of small integers for dictionary keys that need to be encoded briefly, and strings for non-tor and experimental extensions. * This is a fine opportunity to re-think how we handle document liveness. Right now, consensus directories have an official liveness interval on them, but parties that rely on consensuses tolerate larger variance than is specified in the consensus. Instead of that approach, the usable lifetime of each object is now specified in the object, and is ultimately controlled by the authorities. This gives the directory authorities more ability to work around network tolerance issues. Having large lifetime tolerances in the context of walking onions is a little risky: it opens us up to an attack where a hostile relay holds multiple ENDIVEs, and decides which one to use when responding to a request. I think we can address this attack, however, by making sure that SNIPs have a published time in them, and that this time moves monotonically forward. * As I work, I'm identifying other issues in tor that stand in the way of a good efficient walking onion implementation that will require other follow-up work. This week I ran into a need for non-TAP-based v2 hidden services, and a need for a more efficient family encoding. I'm keeping track of these in my outline file. Fun fact: In number of bytes, the walking onions proposal is now the 9th-longest proposal in the Tor proposal repository. And it's still growing! Next week, I'm planning to specify ENDIVE reconstruction, circuit extension, and maybe start on a specification for voting. [CBOR] RFC 7049: "Concise Binary Object Representation (CBOR)" https://tools.ietf.org/html/rfc7049b [CDDL] RFC 8610: "Concise Data Definition Language (CDDL): A Notational Convention to Express Concise Binary Object Representation (CBOR) and JSON Data Structures" https://tools.ietf.org/html/rfc8610 [GITREPO] https://github.com/nmathewson/walking-onions-wip [SNIPFMT] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/02-endiv…

3 6