tor-dev June 2012

tor-dev@lists.torproject.org

37 participants
46 discussions

Nick's status report for June 2012
by Nick Mathewson 29 Jun '12

29 Jun '12

June was a pretty decent month! With help from Mike Perry, I finished a couple of rounds of job interviews, so we could select a new core developer. Let's welcome Andrea Shepard to the Tor project; she's already off to a great start, even though she's only part-time for her first couple of months. I migrated the Free Haven Anonymity Bibliography (http://freehaven.net) to git, and fixed a bunch of longstanding bugs in it, so that its output finally passes the w3 validator. I wrote up a couple of emails about the statuses of current proposals, and proposals implemented in 0.2.3.x, and send them to tor-dev. I hope to do this every month or two. I finally circulated my proposals for improved cell crypto (202), and for impersonating an HTTPS server (203). Weasel and I had a chat about how to avoid backporting all conceivable patches to 0.2.2.x. From now on, I'm going to distinguish between "new stable" and "extended support stable" -- once a Tor series has been stable for long enough, it should really get fixes for grave bugs only. With help from many others, we tagged Tor 0.2.3.17-beta and 0.2.3.18-rc. These fixed a lot of bugs; I think Tor 0.2.3.x is getting close to being ready for a stable release. Once there are packages available for your platform, please try them out! "I reviewed piles of code, merged a bunch of code, and fixed piles of bugs." This is usually the shortest sentence in my status reports with the highest amount of time actually consumed. For details, see the ChangeLogs for Tor 0.2.3.17-beta and 0.2.3.18-rc inclusive for everything that actually got merged. If you like to follow code getting reviewed and merged, and you have a high tolerance for incoming email volume, I recommend the tor-bugs and tor-commits mailing lists. Some highlights include: * Tor clients now declare a less fingerprintable (and actually accurate, we hope!) set of ciphers in their TLS handshakes. In 0.2.4, this will enable us to use more secure TLS ciphersuites. (See bug 4744 and proposal 198.) * Tor now enables compiler-hardening options by default. * We made a quick workaround for a horrible bug in OpenSSL 1.0.1 that prevents TLS 1.1 and TLS 1.2 from renegotiating successfully. I forked a maint-0.2.3 branch from master. Now changes to Tor 0.2.3 go into maint-0.2.3, which gets merged forward into master; changes made only in master will appear in 0.2.4 only. I started a new repository called "tor-next" (at https://gitweb.torproject.org/tor-next.git). It has two main branches, "tor-next" and "tor-next-023". These branches are regenerated periodically; they contain the patches that I'm currently considering merging to master and to maint-0.2.3 respectively. This way, complex code can get a little testing before I actually merge it. If the alpha code just hasn't been alpha enough for your tastes, and you like building from source, you might want to give tor-next a spin. Tor-next is automatically generated by a script; you can see it in our "githax" repository at https://gitweb.torproject.org/githax.git/blob_plain/HEAD:/scripts/make-tor-… I've started merging pending things into 0.2.4.x, and reviewing patch series which had been tagged for Tor 0.2.4.x. I participated in a fun reddit "ask me anything" session with Runa, Karen, and others. I've started playing around with shadow to get it running on my desktop. It worked out okay, but I haven't yet managed to actually do more with it than say, "Yup, that runs." I've scrambled to try to get ready for the developers' meeting and for PETS in early July. Apparently, I'm out of practice at arranging and preparing for travel. Andrea and I started sketching out plans and possible schedules for Tor 0.2.4. We're doing okay making plans at the proposal level, but trying to select and cost out individual tickets seems to be proving more trouble than it might be worth. Further, we're a bit stymied by the state of deliverables tracking; that's going to take some brain-dumps at the dev meeting. Still, I'm hoping we can have a rough plan for 0.2.4 some time before mid-July: I'd like to be able to declare merge deadlines some time around then. best wishes, -- Nick

1 0

Re: [tor-dev] Stem Proc Integration Tests
by Damian Johnson 29 Jun '12

29 Jun '12

> Erik and I have finished the proc.py integration tests Great! I'm looking forward to checking them out. > Tomorrow, we will be starting the next Stem task regarding the Tor Export project. Do you have any recommendations on where we should start exploring in the Stem documentation? Hmm, this concerns translating Descriptor subclasses [1] into a csv (and I suppose loading them back up). First step would be to google around to see if there's a builtin function what'll do this or help with it. If not then this might simply include dumping out their __dict__... >>> class Foo: ... def __init__(self): ... self.foo = 5 ... self.bar = "hello" ... def set_bar(self, value): ... self.bar = value ... >>> f = Foo() >>> f.__dict__ {'foo': 5, 'bar': 'hello'} >>> ",".join([str(v) for v in f.__dict__.values()]) '5,hello' You probably want to sort the keys and use that order, but besides that this should do the trick. Just add a unit test and you're done. :) If we want to convert csvs *back* into Descriptors then that's a bit more work. > Also, what do you anticipate being necessary when it comes to parsing consensus entries? A NetworkStatusEntry class (and its tests) would be similar to the ServerDescriptor [2] and ExtraInfoDescriptor [3], but a fair bit easier (it only has six entries). To implement this you'd... 1. Read over the ServerDescriptor and ExtraInfoDescriptor to figure out how we're tackling the parsing and verification in python. 2. Read over Karsten's NetworkStatusEntryImpl class [4] to see how he's handling this in metrics-lib. 3. Read the spec for these entries [5]. Do we need both a NetworkStatusEntryV2 and NetworkStatusEntryV3 class? Exactly how should we model this? Karsten: thoughts? 4. Go to 'https://metrics.torproject.org/data.html' to get some test data, so you see what the things that you'll be parsing looks like. 5. Write a NetworkStatusEntry class with the goal of "figure out each and every way that data might be malformed". A large part of this class is to verify that the data we're being given is perfectly valid according to the spec, so read the spec and implement exactly what it says. If there's some ambiguity in the spec or you see data that doesn't conform to the spec then let us know. That's a tor bug. 6. Write unit and integ tests similar to what the other descriptors have... - unit tests are the majority of the work, and exercise all the use cases that you can think of against mock objects - integ tests are pretty short, and just run the parser against some test data from the metrics archive and the cached consensus Let me know if you have any questions! -Damian PS. Karsten: Do we want to call this "NetworkStatusEntry" or something else? It seems like "ConsensusEntry" would be more intuitive, but maybe this would just spawn confusion. [1] https://gitweb.torproject.org/stem.git/blob/HEAD:/stem/descriptor/__init__.… [2] https://gitweb.torproject.org/stem.git/blob/HEAD:/stem/descriptor/server_de… [3] https://gitweb.torproject.org/stem.git/blob/HEAD:/stem/descriptor/extrainfo… [4] https://gitweb.torproject.org/metrics-lib.git/blob/HEAD:/src/org/torproject… [5] https://gitweb.torproject.org/torspec.git/blob/HEAD:/dir-spec.txt#l1334

3 3

Karsten's status report June 1--30
by Karsten Loesing 29 Jun '12

29 Jun '12

Hi all, below's what I did in June. Yes, there's still one more day left in June, but I don't expect to do anything useful tomorrow other than packing for Italy and pretending to have a half weekend. Best, Karsten Fixed a few problems with the metrics website: bridge usage statistics graphs were missing 85% of reported bridge statistics due to a truncated file containing raw observations (#6064); download times in Torperf graphs were consistently 1 second too high because of a trivial math bug (#6070); some direct usage graphs showing possible censorship events displayed upturns or downturns for every single data point (first part of #6170); direct usage graphs of countries with little usage displayed missing values where they should display zero users (second part of #6170). Added a new graph to the metrics website that shows number of cloud bridges over time (#5629) [0]. Runa is still investigating the sudden drops in March and April, but it looks like they're related to a problem with updating cloud images. Visualized Torperf phases from starting a download to 1) receiving the CONNECTED cell, 2) receiving the first byte, and 3) receiving the last byte of the response (#6120). Looked more into improved bridge usage statistics (#5807) with little outcome so far. The directory request statistics reported by bridges still look very promising for estimating daily bridge users. Tried to find reasons for missing extra-info descriptors (#3266). There are some interesting patterns, but it's still unclear what's going on. Finished making the new combined Torperf data format the new default format that we provide on the metrics website (#3036) [1, 2]. Added support for parsing GetTor statistics files to metrics-lib and made the metrics website code use that library instead of implementing its own parser. Discussed sanitizing pluggable transport lines in bridge extra-info descriptors with George and implemented the required code in metrics-db (#4957). Deployed George's changes to the censorship detector script to send out daily mails for censorship events [3]. Apparently, there are still plenty of false positives on that list, but the newly gained awareness might help improving the censorship detector script in the future. Fixed a problem in DocTor, the consensus-health checker, which looked at old consensuses for some checks when it shouldn't. Helped prepare the metrics host for a downtime of a few hours for getting its RAID card replaced. Looks like replacing the broken card has solved previously existing performance problems quite well. Made a few smaller extensions to Onionoo, the data provider behind Atlas: added bridge nicknames; added support for searching by country code (#5960); included exit addresses in summary and search (#5251); added support for relays and bridges with multiple OR addresses (#5245); allowed searches for more than 1 search term (#5248); added reverse DNS lookup results (#5247). Also wrote a design document for Onionoo [4] to facilitate writing a Python version of it. [0] https://metrics.torproject.org/network.html#cloudbridges [1] https://metrics.torproject.org/data.html#performance [2] https://metrics.torproject.org/formats.html#torperf [3] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-censorship-events [4] https://gitweb.torproject.org/onionoo.git/blob/HEAD:/DESIGN

1 0

Proc Unit Testing & Next Project
by Erik I Islo 28 Jun '12

28 Jun '12

Hi Damian, Megan and I have finished a first run at writing unit tests for the proc utilities in stem. The code may be found on Megan's Github at: https://github.com/meganchang/Stem/blob/proc-tests/test/unit/util/proc.py. Until we hear back on a code review, we'll move on to the integration tests. Just for reference, here is a link to the ticket as well: https://trac.torproject.org/projects/tor/ticket/6082. Looking further into the future, we discussed our next project with Stem with Professor Danner today, and agreed that the "Export Tor Desciptors" project would be ideal. ( https://trac.torproject.org/projects/tor/ticket/6171) Do you have any thoughts on this? Otherwise, we just wanted to let you know our plan as we move forward. -Erik & Megan

2 4

Re: [tor-dev] stem test output
by Damian Johnson 27 Jun '12

27 Jun '12

Hi Karsten, hi Sathyanarayanan. Over the last couple weeks I've been making a variety of fixes to stem and its tests. It now runs with python 2.5 and doesn't require tor to be in your path, among other things. However, the hanging issue remains and I'm pretty stuck there. It isn't strictly stem related (I can reproduce the issue with plan sockets), hopefully Nick will have some ideas... https://trac.torproject.org/6235 Karsten, should the 'dirreq-v3-share' percentage values be able to go above 100%? The extra-info descriptors that I just fetched has one such entry, which makes stem's descriptor parser complain... extra-info siltornado 995D0FE5A89563D79A383CCC2444D0E26C6BE625 published 2012-06-24 19:30:31 ... dirreq-v2-share 159.81% dirreq-v3-share 159.81% Cheers! -Damian PS. Including tor-dev@ in case Beck or others are interested.

2 1

Trying to connect to a OR
by Steven Retz 27 Jun '12

27 Jun '12

Everyone, I have been toying with doing something with tor for a long time. I decided to start doing something with it. I wrote this quick POC in C# to connect to a tor node I got from the cache file. I tried to follow the specs in https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=tor-spec.tx t section 2 connections, but apparently I'm doing something wrong. I'm hoping someone can help me out. Steven

1 0

[GSoC] Stem improvements
by Ravi Chandra Padmala 25 Jun '12

25 Jun '12

Hello I have been working on Stem's general controller class. I have completed implementing the methods that handle the GETCONF, SETCONF and the RESETCONF (for the most part, I haven't put some of the code up for review yet). I'm currently working on implementing the SAVECONF, LOADCONF, SIGNAL methods. I also met Sathyanarayanan at Bangalore this weekend and we spent some time working on Stem. He worked on implementing the Controller's QUIT functionality (among other things). -- neena

1 0

Proposal 202: Two improved relay encryption protocols for Tor cells
by Nick Mathewson 21 Jun '12

21 Jun '12

Filename: 202-improved-relay-crypto.txt Title: Two improved relay encryption protocols for Tor cells Author: Nick Mathewson Created: 19 Jun 2012 Status: Open Overview: This document describes two candidate designs for a better Tor relay encryption/decryption protocol, designed to stymie tagging attacks and better accord with best practices in protocol design. My hope is that readers will examine these protocols, evaluate their security and practicality, improve on them, and help to pick one for implementation in Tor. In section 1, I describe Tor's current relay crypto protocol, its drawbacks, how it fits in with the rest of Tor, and some requirements/desiderata for a replacement. In sections 2 and 3, I propose two alternative replacements for this protocol. In section 4, I discuss their pros and cons. 1. Background and Motivation 1.0. A short overview of Tor's current protocols The core pieces of the Tor protocol are the link protocol, the circuit extend protocol, the relay protocol, and the stream protocol. All are documented in [TorSpec]. Briefly: - The link protocol handles all direct pairwise communication between nodes. Everything else is transmitted over it. It uses TLS. - The circuit extend protocol uses public-key crypto to set up multi-node virtual tunnels, called "circuits", from a client through one or more nodes. *** The relay protocol uses established circuits to communicate from a client to a node on a circuit. That's the one we'll be talking about here. *** - The stream protocol is tunneled over relay protocol; clients use it to tell servers to open anonymous TCP connections, to send data, and so forth. Servers use it to report success or failure opening anonymous TCP connections, to send data from TCP connections back to clients, and so forth. In more detail: The link protocol's job is to connect two computers with an encrypted, authenticated stream, to authenticate one or both of them to the other, and to provide a channel for passing "cells" between them. The circuit extend protocol's job is to set up circuits: persistent tunnels that connect a Tor client to an exit node through a series of (typically three) hops, each of which knows only the previous and next hop, and each of which has a set of keys that they share only with the client. Finally, the relay protocol's job is to allow a client to communicate bidirectionally with the node(s) on the circuit, once their shared keys have been established. (We'll ignore the stream protocol for the rest of this document.) Note on terminology: Tor nodes are sometimes called "servers", "relays", or "routers". I'll use all these terms more or less interchangeably. For simplicity's sake, I will call the party who is constructing and using a circuit "the client" or "Alice", even though nodes sometimes construct circuits too. Tor's internal packets are called "cells". All the cells we deal with here are 512 bytes long. The nodes in a circuit are called its "hops"; most circuits are 3 hops long. This doesn't include the client: when Alice builds a circuit through nodes Bob_1, Bob_2, and Bob_3, the first hop is "Bob_1" and the last hop is "Bob_3". 1.1. The current relay protocol and its drawbacks [This section describes Tor's current relay protocol. It is not a proposal; rather it is what we do now. Sections 2 and 3 have my proposed replacements for it.] A "relay cell" is a cell that is generated by the client to send to a node, or by a node to send to the client. It's called a "relay" cell because a node that receives one may need to relay it to the next or previous node in the circuit (or to handle the cell itself). A relay cell moving towards the client is called "inbound"; a cell moving away is called "outbound". When a relay cell is constructed by the client, the client adds one layer of crypto for each node that will process the cell, and gives the cell to the first node in the circuit. Each node in turn then removes one layer of crypto, and either forwards the cell to the next node in the circuit or acts on that cell itself. When a relay cell is constructed by a node, it encrypts it and sends it to the preceding node in the circuit. Each node between the originating node and the client then encrypts the cell and passes it back to the preceding node. When the client receives the cell, it removes layers of crypto until it has an unencrypted cell, which it then acts on. In the current protocol, the body of each relay cell contains, in its unencrypted form: Relay command [1 byte] Zeros [2 bytes] StreamID [2 bytes] Digest [4 bytes] Length [2 bytes] Data [498 bytes] (This only adds up to 509 bytes. That's because the Tor link protocol transfers 512-byte cells, and has a 3 byte overhead per cell. Not how we would do it if we were starting over at this point.) At every node of a circuit, the node relaying a cell encrypts/decrypts it with AES128-CTR. If the cell is outbound and the "zeros" field is set to all-zeros, the node additionally checks whether 'digest' is correct. A correct digest is the first 4 bytes of the running SHA1 digest of: a shared secret, concatenated with all the relay cells destined for this node on this circuit so far, including this cell. If _that's_ true, then the node accepts this cell. (See section 6 of [TorSpec] for full detail; see section A.1 for a more rigorous description.) The current approach has some actual problems. Notably: * It permits tagging attacks. Because AES_CTR is an XOR-based stream cipher, an adversary who controls the first node in a circuit can XOR anything he likes into the relay cell, and then see whether he/she encounters an correspondingly defaced cell at some exit that he also controls. That is, the attacker picks some pattern P, and when he would transmit some outbound relay cell C at hop 1, he instead transmits C xor P. If an honest exit receives the cell, the digest will probably be wrong, and the honest exit will reject it. But if the attacker controls the exit, he will notice that he has received a cell C' where the digest doesn't match, but where C' xor P _does_ have a good digest. The attacker will then know that his two nodes are on the same circuit, and thereby be able to link the user (whom the first node sees) to her activities (which the last node sees). Back when we did the Tor design, this didn't seem like a big deal, since an adversary who controls both the first and last node in a circuit is presumed to win already based on traffic correlation attacks. This attack seemed strictly worse than that, since it was trivially detectable in the case where the attacker _didn't_ control both ends. See section 4.4 of the Tor paper [TorDesign] for our early thoughts here; see Xinwen Fu et al's 2009 work for a more full explanation of the in-circuit tagging attack [XF]; and see "The 23 Raccoons'" March 2012 "Analysis of the Relative Severity of Tagging Attacks" mail on tor-dev (and the ensuing thread) for a discussion of why we may want to care after all, due to attacks that use tagging to amplify route capture. [23R] It also has some less practical issues. * The digest portion is too short. Yes, if you're an attacker trying to (say) change an "ls *" into an "rm *", you can only expect to get one altered cell out of 2^32 accepted -- and all future cells on the circuit will be rejected with similar probability due to the change in the running hash -- but 1/2^32 is a pretty high success rate for crypto attacks. * It does MAC-then-encrypt. That makes smart people cringe. * Its approach to MAC is H(Key | Msg), which is vulnerable to length extension attack if you've got a Merkle-Damgard hash (which we do). This isn't relevant in practice right now, since the only parties who see the digest are the two parties that rely on it (because of the MAC-then-encrypt). 1.2. Some feature requirements Relay cells can originate at the client or at a relay. Relay cells that originate at the client are given to the first node in the circuit, and constructed so that they will be decrypted and forwarded by the first M-1 nodes in the circuit, and finally decrypted and processed by the Mth node, where the client chooses M. (Usually, the Mth node is the the last one, which will be an exit node.) Relay cells that originate at a hop in the circuit are given to the preceding node, and eventually delivered to the client. Tor provides a so called "leaky pipe" circuit topology [TorDesign]: a client can send a cell to any node in the circuit, not just the last node. I'll try to keep that property, although historically we haven't really made use of it. In order to implement telescoping circuit construction (where the circuit is built by iteratively asking the last node in the circuit to extend the circuit one hop more), it's vital that the last hop of the circuit be able to change. Proposal 188 [Prop188] suggests that we implement a "bridge guards" feature: making some (non-public) nodes insert an extra hop into the circuit after themselves, in a way that will make it harder for other nodes in the network to enumerate them. We therefore want our circuits to be one-hop re-extensible: when the client extends a circuit from Bob1 to Bob2, we want Bob1 to be able to introduce a new node "Bob1.5" into the circuit such that the circuit runs Alice->Bob1->Bob1.5->Bob2. (This feature has been called "loose source routing".) Any new approach should be able to coexist on a circuit with the old approach. That is, if Alice wants to build a circuit through Bob1, Bob2, and Bob3, and only Bob2 supports a revised relay protocol, then Alice should be able to build a circuit such that she can have Bob1 and Bob3 process each cell with the current protocol, and Bob2 process it with a revised protocol. (Why? Because if all nodes in a circuit needed to use the same relay protocol, then each node could learn information about the other nodes in the circuit from which relay protocol was chosen. For example, if Bob1 supports the new protocol, and sees that the old relay protocol is in use, and knows that Bob2 supports the new one, then Bob1 has learned that Bob3 is some node that does not support the new relay protocol.) Cell length needs to be constant as cells move through the network. For historical reasons mentioned above in section 1.1, the length of the encrypted part of a relay cell needs to be 509 bytes. 1.3. Some security requirements Two adjacent nodes on a circuit can trivially tell that they are on the same circuit, and the first node can trivially tell who the client is. Other than that, we'd like any attacker who controls a node on the circuit not to have a good way to learn any other nodes, even if he/she controls those nodes. [*] Relay cells should not be malleable: no relay should be able to alter a cell between an honest sender and an honest recipient in a way that they cannot detect. Relay cells should be secret: nobody but the sender and recipient of a relay cell should be able to learn what it says. Circuits should resist transparent, recoverable tagging attacks: if an attacker controls one node in a circuit and alters a relay cell there, no non-adjacent point in the circuit should be able to recover the relay cell as it would have received it had the attacker not altered it. The above properties should apply to sequences of cells too: an attacker shouldn't be able to change what sequence of cells arrives at a destination (for example, by removing, replaying, or reordering one or more cells) without being detected. (Feel free to substitute whatever formalization of the above requirements makes you happiest, and add whatever caveats are necessary to make you comfortable. I probably missed at least two critical properties.) [*] Of course, an attacker who controls two points on a circuit can probably confirm this through traffic correlation. But we'd prefer that the cryptography not create other, easier ways for them to do this. 1.4. A note on algorithms This document is deliberately agnostic concerning the choice of cryptographic primitives -- not because I have no opinions about good ciphers, MACs, and modes of operation -- but because experience has taught me that mentioning any particular cryptographic primitive will prevent discussion of anything else. Please DO NOT suggest algorithms to use in implementing these protocols yet. It will distract! There will be time later! If somebody _else_ suggests algorithms to use, for goodness' sake DON'T ARGUE WITH THEM! There will be time later! 2. Design 1: Large-block encryption In this approach, we use a tweakable large-block cipher for encryption and decryption, and a tweak-chaining function TC. 2.1. Chained large-block what now? We assume the existence of a primitive that provides the desired properties of a tweakable[Tweak] block cipher, taking blocks of any desired size. (In our case, the block size is 509 bytes[*].) It also takes a Key, and a per-block "tweak" parameter that plays the same role that an IV plays in CBC, or that the counter plays in counter mode. The Tweak-chaining function TC takes as input a previous tweak, a tweak chaining key, and a cell; it outputs a new tweak. Its purpose is to make future cells undecryptable unless you have received all previous cells. It could probably be something like a MAC of the old tweak and the cell using the tweak chaining key as the MAC key. (If the initial tweak is secret, I am not sure that TC needs to be keyed.) [*] Some large-block cipher constructions use blocks whose size is the multiple of some underlying cipher's block size. If we wind up having to use one of those, we can use 496-byte blocks instead at the cost of 2.5% wasted space. 2.2. The protocol 2.2.1. Setup phase The circuit construction algorithm needs to produce forward and backward keys Kf and Kb, the forward and backward tweak chaining keys TCKf and TCKb, as well as initial tweak values Tf and Tb. 2.2.2. The cell format We replace the "Digest" and "Zeros" fields of the cell with a single Z-byte "Zeros" field to determine when the cell is recognized and correctly decrypted; its length is a security parameter. 2.2.3. The decryption operations For a relay to handle an inbound RELAY cell, it sets Tb_next to TC(TCKb, Tb, Cell). Then it encrypts the cell using the large block cipher keyed with Kb and tweaked with Tb. Then it sets Tb to Tb_next. For a relay to handle an outbound RELAY cell, it sets Tf_next to TC(TCKf, Tf, Cell). Then it decrypts the cell using the large block cipher keyed with Kf and tweaked with Tf. Then it sets Tf to Tf_next. Then it checks the 'Zeros' field on the cell; if that field is all [00] bytes, the cell is for us. 2.3. Security discussion This approach is fairly simple (at least, no more complex than its primitives) and achieves some of our security goals. Because of the large block cipher approach, any change to a cell will render that cell undecryptable, and indistinguishable from random junk. Because of the tweak chaining approach, if even one cell is missed or corrupted or reordered, future cells will also decrypt into random junk. The tagging attack in this case is turned into a circuit-junking attack: an adversary who tries to mount it can probably confirm that he was indeed first and last node on a target circuit (assuming that circuits which turn to junk in this way are rare), but cannot recover the circuit after that point. As a neat side observation, note that this approach improves upon Tor's current forward secrecy, by providing forward secrecy while circuits are still operational, since each change to the tweak should make previous cells undecryptable if the old tweak value isn't recoverable. The length of Zeros is a parameter for what fraction of "random junk" cells will potentially be accepted by a router or client. If Zeros is Z bytes long, then junk cells will be accepted with P < 2^-(8*Z + 7). (The '+7' is there because the top 7 bits of the Length field must also be 0.) There's no trouble using this protocol in a mixed circuit, where some nodes speak the old protocol and some speak the large-block-encryption protocol. 3. Design 2: short-MAC-and-pad In this design, we behave more similarly to a mix-net design (such as Mixmaster or Mixminion's headers). Each node checks a MAC, and then re-pads the cell to its chosen length before decoding the cell. This design uses as a primitive a MAC and a stream cipher. It might also be possible to use an authenticating cipher mode, if we can find one that works like a stream cipher and allows us to efficiently output authenticators for the stream so far. NOTE TO AE/AEAD FANS: The encrypt-and-MAC model here could be replaced with an authenticated encryption mode without too much loss of generality. 3.1. The protocol 3.1.1 Setup phase The circuit construction algorithm needs to produce forward and backward keys Kf and Kb, forward and backward stream cipher IVs IVf and IVb, and forward and backward MAC keys Mf and Mb. Additionally, the circuit construction algorithm needs a way for the client to securely (and secretly? XXX) tell each hop in the circuit a value 'bf' for the number of bytes of MAC it should expect on outbound cells and 'bb' for the number of bytes it should use on cells it's generating. Each node can get a different 'bf' and 'bb'. These values can be 0: if a node's bf is 0, it doesn't authenticate cells; if its bb is 0, it doesn't originate them. The circuit construction algorithm also needs a way to tell each the client to securely (and secretly? XXX) tell each hop in the circuit whether it is allowed to be the final destination for relay cells. Set the stream Sf and the stream Sb to empty values. 3.1.2. The cell format The Zeros and Digest field of the cell format are removed. 3.1.3. The relay operations Upon receiving an outbound cell, a node removes the first b bytes of the cell, and puts them aside as 'M'. The node then computes between 0 and 2 MACs of the stream consisting of all previously MAC'd data, plus the remainder of the cell: If b>0 and there is a next hop, the node computes M_relay. If this node was told to deliver traffic, or it is the last node in the circuit so far, the node computes M_receive. M_relay is computed as MAC(stream | "relay"); M_receive is computed as MAC(stream | "receive"). If M = M_receive, this cell is for the node; it should process it. If M = M_relay, or if b == 0, this cell should be relayed. If a MAC was computed and neither of the above cases was met, then the cell is bogus; the node should discard it and destroy the circuit. The node then removes the first bf bytes of the cell, and pads the cell at the end with bf zero bytes. Finally, the node decrypts the whole remaining padded cell with the stream cipher. To handle an inbound cell, the node simply does a stream cipher with no checking. 3.1.4. Generating inbound cells. To generate an inbound cell, a node makes a 509-bb byte RELAY cell C, encrypts that cell with Kb, appends the encrypted cell to Sb, and prepends M_receive(Sb) to the cell. 3.1.5. Generating outbound cells Generating an outbound cell is harder, since we need to know what padding the earlier nodes will generate in order to know what padding the later nodes will receive and compute their MACs, but we also need to know what MACs we'll send to the later nodes in order to compute which MACs we'll send to the earlier ones. Mixnet clients have needed to do this for ages, though, so the algorithms are pretty well settled. I'll give one below in A.3. 3.2. Security discussion This approach is also simple and (given good parameter choices) can achieve our goals. The trickiest part is the algorithm that clients must follow to package cells, but that's no so bad. It's not necessary to check MACs on inbound traffic, because nobody but the client can tell scrambled messages from good ones, and the client can be trusted to keep the client's own secrets. With this protocol, if the attacker tries to do a tagging attack, the circuit should get destroyed by the next node in the circuit that has a nonzero "bf" value, with probability == 1-2^-(8*bf). (If there are further intervening honest nodes, they also have a chance to detect the attack.) Similarly, any attempt to replay, or reorder outbound cells should fail similarly. The "bf" values could reveal to each node its position in the circuit and the client preferences, depending on how we set them; on the other hand, having a fixed bf value would reveal to the last node the length of the circuit. Neither option seems great. This protocol doesn't provide any additional forward secrecy beyond what Tor has today. We could fix that by changing our use of the stream cipher so that instead of running in counter mode between cells, we use a tweaked stream cipher and change the tweak with each cell (possibly based on the unused portion of the MAC). This protocol does support loose source routing, so long as the no padding bytes are added by any router-added nodes. In a circuit, every node has at least one relay cell sent to it: even non-exit nodes get a RELAY_EXTEND cell. 4. Discussion I'm not currently seeing a reason to strongly prefer one of these approaches over another. In favor of large-block encryption: - The space overhead seems smaller: we need to use up fewer bytes in order to get equivalent looking security. (For example, if we want to have P < 2^64 that a cell altered by hop 1 could be accepted by hop 2 or hop 3, *and* we want P < 2^64 that a cell altered by hop 2 could be accepted by hop 3, the large-block approach needs about 8 bytes for the Zeros field, whereas the short-MAC-and-pad approach needs 16 bytes worth of MACs.) - We get forward secrecy pretty easily. - The format doesn't leak anything about the length of the circuit, or limit it. - We don't need complicated logic to set the 'b' parameters. - It doesn't need tricky padding code. In the favor of short-MAC-and-pad: - All of the primitives used are much better analyzed and understood. There's nothing esoteric there. The format itself is similar to older, well-analyzed formats. - Most of the constructions for the large-block-cipher approach seem less efficient in CPU cycles than a good stream cipher and a MAC. (But I don't want to discuss that now; see section 1.4 above!) Unclear: - Suppose that an attacker controls the first and last hop of a circuit, and tries an end-to-end tagging attack. With large-block encryption, the tagged cell and all future cells on the circuit turn to junk after the tagging attack, with P~~100%. With short-MAC-and-pad, the circuit is destroyed at the second hop, with P ~~ 1- 2^(-8*bf). Is one of these approaches materially worse for the attacker? - Can we do better than the "compute two MACs" approach for distinguishing the relay and receive cases of the short-MAC-and-pad protocol? - To what extent can we improve these protocols? - If we do short-MAC-and-pad, should we apply the forward security hack alluded to in section 3.2? 5. Acknowledgments Thanks to the many reviewers of the initial drafts of this proposal. If you can make any sense of what I'm saying, they deserve much of the credit. A. Formal description Note that in all these cases, more efficient descriptions exist. A.1. The current Tor relay protocol. Relay cell format: Relay command [1 byte] Zeros [2 bytes] StreamID [2 bytes] Digest [4 bytes] Length [2 bytes] Data [498 bytes] Circuit setup: (Specified elsewhere; the client negotiates with each router in a circuit the secret AES keys Kf, Kb, and the secret 'digest keys' Df, and Db. They initialize AES counters Cf and Cb to 0. They initialize the digest stream Sf to Df, and Sb to Db.) HELPER FUNCTION: CHECK(Cell [in], Stream [in,out]): 1. If the Zeros field of Cell is not [00 00], return False. 2. Let Cell' = Cell with its Digest field set to [00 00 00 00]. 3. Let S' = Stream | Cell'. 4. If SHA1(S') = the Digest field of Cell, set Stream to S', and return True. 5. Otherwise return False. HELPER FUNCTION: CONSTRUCT(Cell' [in], Stream [in,out]) 1. Set the Zeros and Digest field of Cell' to [00] bytes. 2. Set Stream to Stream | Cell'. 3. Construct Cell from Cell' by setting the Digest field to SHA1(Stream), and taking all other fields as-is. 4. Return Cell. HELPER_FUNCTION: ENCRYPT(Cell [in,out], Key [in], Ctr [in,out]) 1. Encrypt Cell's contents using AES128_CTR, with key 'Key' and counter 'Ctr'. Increment 'Ctr' by the length of the cell. HELPER_FUNCTION: DECRYPT(Cell [in,out], Key [in], Ctr [in,out]) 1. Same as ENCRYPT. Router operation, upon receiving an inbound cell -- that is, one sent towards the client. 1. ENCRYPT(cell, Kb, Cb) 2. Send the decrypted contents towards the client. Router operation, upon receiving an outbound cell -- that is, one sent away from the client. 1. DECRYPT(cell, Kf, Cf) 2. If CHECK(Cell, Sf) is true, this cell is for us. Do not relay the cell. 3. Otherwise, this cell is not for us. Send the decrypted cell to the next hop on the circuit, or discard it if there is no next hop. Router operation, to create a relay cell that will be delivered to the client. 1. Construct a Relay cell Cell' with the relay command, length, stream ID, and body fields set as appropriate. 2. Let Cell = CONSTRUCT(Cell', Sb). 3. ENCRYPT(Cell, Kb, Cb) 4. Send the encrypted cell towards the client. Client operation, receiving an inbound cell. For each hop H in a circuit, starting with the first hop and ending (possibly) with the last: 1. DECRYPT(Cell, Kb_H, Cb_H) 2. If CHECK(Cell, Sb_H) is true, this cell was sent from hop H. Exit the loop, and return the cell in its current form. If we reach the end of the loop without finding the right hop, the cell is bogus or corrupted. Client operation, sending an outbound cell to hop H. 1. Construct a Relay cell Cell' with the relay command, length, stream ID, and body fields set as appropriate. 2. Let Cell = CONSTRUCT(Cell', Sf_H) 3. For i = H..1: A. ENCRYPT(Cell, Sf_i, Cf_i) 4. Deliver Cell to the first hop in the circuit. A.2. The large-block-cipher protocol Same as A.1, except for the following changes. The cell format is now: Zeros [Z bytes] Length [2 bytes] StreamID [2 bytes] Relay command [1 byte] Data [504-Z bytes] Ctr is no longer a counter, but a Tweak value. Each key is now a tuple of (Key_Crypt, Key_TC) Streams are no longer used. HELPER FUNCTION: CHECK(Cell [in], Stream [in,out]) 1. If the Zeros field of Cell contains only [00] bytes, return True. 2. Otherwise return false. HELPER FUNCTION: CONSTRUCT(Cell' [in], Stream [in,out]) 1. Let Cell be Cell', with its "Zeros" field set to Z [00] bytes. 2. Return Cell'. HELPER FUNCTION: ENCRYPT(Cell [in,out], Key [in], Tweak [in,out]) 2. Encrypt Cell using Key and Tweak 1. Let Tweak' = TC(Key_TC, Tweak, Cell) 3. Set Tweak to Tweak'. HELPER FUNCTION: DECRYPT(Cell [in,out], Key [in], Tweak [in,out]) 1. Let Tweak' = TC(Key_TC, Tweak, Cell) 2. Decrypt Cell using Key and Tweak 3. Set Tweak to Tweak'. A.3. The short-MAC-and-pad protocol. Define M_relay(K,S) as MAC(K, S|"relay"). Define M_receive(K,S) as MAC(K, S|"receive"). Define Z(n) as a series of n [00] bytes. Define BODY_LEN as 509 The cell message format is now: Relay command [1 byte] StreamID [2 bytes] Length [2 bytes] Data [variable bytes] Helper function: CHECK(Cell [in], b [in], K [in], S [in,out]): Let M = Cell[0:b] Let Rest = Cell[b:...] If b == 0: Return (nil, Rest) Let S' = S | Rest If M == M_relay(K,S')[0:b]: Set S = S' Return ("relay", Rest) If M == M_receive(K,S')[0:b]: Set S = S' Return ("receive", Rest) Return ("BAD", nil) HELPER_FUNCTION: ENCRYPT(Cell [in,out], Key [in], Ctr [in,out]) 1. Encrypt Cell's contents using AES128_CTR, with key 'Key' and counter 'Ctr'. Increment 'Ctr' by the length of the cell. HELPER_FUNCTION: DECRYPT(Cell [in,out], Key [in], Ctr [in,out]) 1. Same as ENCRYPT. Router operation, upon receiving an inbound cell: 1. ENCRYPT(cell, Kb, Cb) 2. Send the decrypted contents towards the client. Router operation, upon receiving an outbound cell: 1. Let Status, Msg = CHECK(Cell, bf, Mf, Sf) 2. If Status == "BAD", drop the cell and destroy the circuit. 3. Let Cell' = Msg | Z(BODY_LEN - len(Msg)) 4. DECRYPT(Cell', Kf, Cf) [*] 5. If Status == "receive" or (Status == nil and there is no next hop), Cell' is for us: process it. 6. Otherwise, send Cell' to the next node. Router operation, sending a cell towards the client: 1. Let Body = a relay cell body of BODY_LEN-bb_i bytes. 2. Let Cell' = ENCRYPT(Body, Kb, Cb) 3. Let Sb = Sb | Cell' 4. Let M = M_receive(Mb, Sb)[0:b] 5. Send the cell M | Cell' back towards the client. Client operation, upon receiving an inbound cell: For each hop H in the circuit, from first to last: 1. Let Status, Msg = CHECK(Cell, bb_i, Mb_i, Sb_i) 2. If Status = "relay", drop the cell and destroy the circuit. (BAD is okay; it means that this hop didn't originate the cell.) 3. DECRYPT(Msg, Kb_i, Cb_i) 4. If Status = "receive", this cell is from hop i; process it. 5. Otherwise, set Cell = Msg. Client operation, sending an outbound cell: Let BF = the total of all bf_i values. 1. Construct a relay cell body Msg of BODY_LEN-BF bytes. 2. For each hop i, let Stream_i = ENCRYPT(Kf_i,Z(CELL_LEN),Cf_i) 3. Let Pad_0 = "". 4. For i in range 1..N, where N is the number of hops: Let Pad_i = Pad_{i-1} | Z(bf_i) Let S_last = the last len(Pad_i) bytes of Stream_i. Let Pad_i = Pad_i xor S_last Now Pad_i is the padding as it will stand after node i has processed it. 5. For i in range N..1, where N is the number of hops: If this is the last hop, let M_* = M_receive. Else let M_* = M_relay. Let Body = Msg xor the first len(Msg) bytes of Stream_i Let M = M_*(Mf, Body | Pad_(i-1)) Set Msg = M[:bf_i] | Body 6. Send Msg outbound to the first relay in the circuit. [*] Strictly speaking, we could omit the pad-and-decrypt operation once we know we're the final hop. R. References [Prop188] Tor Proposal 188: Bridge Guards and other anti-enumeration defenses https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/188-bridge-g… [TorSpec] The Tor Protocol Specification https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=tor-spec.t… [TorDesign] Dingledine et al, "Tor: The Second Generation Onion Router", https://svn.torproject.org/svn/projects/design-paper/tor-design.pdf [Tweak] Liskov et al, "Tweakable Block Ciphers", http://www.cs.berkeley.edu/~daw/papers/tweak-crypto02.pdf [XF] Xinwen Fu et al, "One Cell is Enough to Break Tor's Anonymity" [23R] The 23 Raccoons, "Analysis of the Relative Severity of Tagging Attacks" http://archives.seul.org/or/dev/Mar-2012/msg00019.html (You'll want to read the rest of the thread too.)

3 3

[GSoC] Vidalia Status Report - Week 4
by Feroze Naina 21 Jun '12

21 Jun '12

I'm currently working on integrating the UI interaction into a Vidalia plugin. I will be starting work on the HiddenService configuration. I have also completed the Torrc Prototype and it has been merged into alpha. I'm also a little behind schedule. 1. http://feroze.in/gsoc12.html

1 0

The master branch is now 0.2.4.0-alpha-dev
by Nick Mathewson 20 Jun '12

20 Jun '12

Hi, all. I have forked off a maint-0.2.3 and a release-0.2.3 branch in the usual fashion, and incremented the version in the master branch to "0.2.4.0-alpha-dev". All branches targeted for inclusion in Tor 0.2.3.x should now be based on "maint-0.2.3"; all branches targeted for inclusion in 0.2.4 or later can still be based on master. For a reminder of the difference of maint and release, see doc/HACKING in the Tor repository. I do not expect to actually start merging anything into 0.2.4.x this week, but you never know. peace, -- Nick

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

tor-dev June 2012