- tor-dev - lists.torproject.org

Re: [tor-dev] Request for comments on notes on parallel cell crypto
by Nick Mathewson 19 Nov '12

19 Nov '12

On Sun, Nov 18, 2012 at 7:43 PM, Andrea Shepard <andrea(a)torproject.org> wrote: > I've made some notes on parallelizing cell crypto on relays which I've > attached to this mail and added to the wiki page on this [1], which I > would like comment on. Particularly, I want to resolve the following > points: > > * Should we operate on cell_t or packed_cell_t? After reading your comments, I don't feel strongly that packed_cell_t is correct. Either would probably be okay. I think I might have said "packed_cell_t" on the grounds that we already have a specialized allocator for them, whereas we don't currently heap-allocate as many cell_t as we would need for this. I might also have said "packed_cell_t" on the theory that copying data from cell_t to packed_cell_t would waste cycles, but I'm not sure that's significant here. Or maybe I was thinking of the amount of space wasted in packed_cell_t vs cell_t, and worried about the number of queued cells we're likely to have at once. For queueing the cell_ts, and where to put a next pointer: I *think* (but can't be sure) that most of our cell_t objects are currently short-lived, and most of our long-lived cell objects are currently packed_cell_t. So adding fields to cell_t wouldn't hurt much, since they don't currently represent very much of our total allocation, I think. (We should double-check that!) > * Is it acceptable for the main thread to call functions to > manipulate job-dispatching data structures that need to > acquire a lock if we can be sure everything that ever > holds the lock only does so very briefly to manipulate > those structures and will never block while holding it, > or do we need to design something that's lock-free for > the main thread? I don't think the main thread needs to be lock-free so long as it won't often block for too long. I was initially planning to have locks protect the work-queues initially, and only substitute in a lock-free work-queue implementation if it turned out to matter. (How long the lock is held by the main thread is less important for performance IIUC than whether the main thread will spend much time blocked waiting for the lock, or how much lock contention there will be.) > * The functions that currently call relay_crypt()/ > relay_crypt_one_payload() will have to be split into > two parts, one that queues a cell to be crypted and > another that handles the finished, crypted cell. > How will the worker threads cause the second part to > be called in the main thread? (NickM, there's probably > some libevent voodoo I don't know about yet for this?) So, I'd suggest the we start with a work queue each way: one queue (or set of queues) to enqueue stuff for worker threads, and one to enqueue the crypted stuff for the main cell to process it. That said, we'll need a way to alert the main thread "Hey, you have more data on your queue!" The easiest way to do that is, using Libevent 2.0 or later, to just call event_active() on a "struct event" whose callback processes the data. (This needs to require Libevent 2.0 or later, since Libevent 1.4 and earlier didn't let you do this threadsafely.) The next easiest alternative would be to construct a socketpair, have the main thread listen on the read side of it (using a read event), and have the worker thread write a byte to the socketpair whenever the queue went from "observed" . There are faster ways to do all of the above, and more ways we could optimize libevent to help with our particular case, but for now I'll suggest we ignore them: getting even one extra core to do crypto with will more than pay for all the overhead in a v1 implementation. We can find the painful points and optimize them later -- and waiting to do so will ensure we don't waste time optimizing outside of critical paths. In fact, we should probably be doing this for the rest of the design: looking to see if there are cases where even if we think we might need to get complex eventually, we can still do them simply at first. (For the case of sending work to the worker threads, a mutex/condition-var pair will do. Windows Vista added real condition variables, and there's plenty of compat code around to fake them with earlier Windowses.) I suggest that for the first implementation of this, we can just make the multithreaded crypto stuff require Libevent 2.0 or later. We'll want a compile option to turn it off for old OpenBSDs anyway. Turning multithreaded cypto off should be easy, right? Instead of "Thread1: enqueue. Thread2: unqueue, encrypt, enqueue. Thread1: unqueue, process", you just replace the first "enqueue" operation with "encrypt and process" -- perhaps making a stub relaycrypt_dispatcher_t that doesn't actually dispatch anything, but just does the crypto operation immediately. This might even be a good intermediate step while refactoring the crypto. > Once these are resolved I'll be making a branch for this and > writing the headers with proposed data structures and interfaces > for review. Cool; thank you! Another observation about your design sketch: If we implement this nicely, I think it will be possible to stress-test it and load-test the relaycrypt_dispatcher_t part of it without actually requiring the rest of Tor to be running. IOW, we could have a performance-test for this component that didn't require any actual Tor traffic to be happening, or circuits to exist. IMO that would be a pretty good idea, since it would help us optimize as needed, and it would encourage loose coupling. cheers, -- Nick

3 3

Proposal 215: Let the minimum consensus method change with time
by Nick Mathewson 19 Nov '12

19 Nov '12

Filename: 215-update-min-consensus-ver.txt Title: Let the minimum consensus method change with time Author: Nick Mathewson Created: 15 Nov 2012 Status: Open 0. Overview This proposal suggests that we drop the requirement that authorities support the very old consensus method "1", and instead move to a wider window of recognized consensus methods as Tor evolves. 1. Background and Motivation When we designed the directory voting system, we added the notion of "consensus method" so that we could smoothly upgrade the voting process over time. We also said that all authorities must support the consensus method '1', and must fall back to it if they don't support the method that the supermajority of authorities will choose. Consensus method 1 is no longer viable for the Tor network. It doesn't result in a microdescriptor consensus, and omits other fields that clients need in order to work well. Consensus methods under 12 have security issues, since they let a single authority set a consensus parameter. In the future, new consensus methods will be needed so that microdescriptor-using clients can use IPv6 exits and ECC onion-keys. Rolling back from those would degrade functionality. We need a way to change the minimum consensus method over time. 2. Design I propose that we change the minimum consensus method about once per release cycle, or once per ever other release cycle. As a rule of thumb, let the minimum consensus method in Tor series X be the highest method supported by the oldest version that "anybody reasonable" would use for running an authority. Typically, that's the stable version of the previous release series. For flexibility, it might make sense to choose a slightly older method, if falling back to that method wouldn't cause security problems. For example, while Tor 0.2.4.x is under development, authorities should really not be running anything before Tor 0.2.3.x. Tor 0.2.3.x has supported consensus method 13 since 0.2.3.21-rc, so it's okay for 0.2.4.x to require 13 as the minimum method. We even might go back to method 12, since the worst outcome of not using 13 would be some warnings in client logs. Consensus method 12 was a security improvement, so we don't want to roll back before that. 2.1. Behavior when the method used is one we don't know The spec currently says that if an authority sees that a method will be used that it doesn't support, it should act as if the consensus method will be "1". This attempt will be doomed, since the other authorities will be computing the consensus with a more recent method, and any attempt to use method "1" won't get enough signatures. Instead, let's say that authorities fall back to the most recent method that they *do* support. This isn't any likelier to reach consensus, but it is less likely to result in anybody signing something they don't like. 3. Likely outcomes If a bunch of authorities were to downgrade to a much older version, all at once, then newer authorities would not be able to sign the consensus they made. That's probably for the best: if a bunch of authorities were to suddenly start running 0.2.0.x, consensing along with them would be a poor idea. 4. Alternatives We might choose a less narrow window of allowable method, when we can do so securely. Maybe two release series, rather than one, would be a good interval to do when the consensus format isn't changing rapidly. We might want to have the behavior when we see that everybody else will be using a method we don't support be "Don't make a consensus at all." That's harder to program, though.

1 0

Free and Open Source Software internships for women
by Sathyanarayanan Gunasekaran 16 Nov '12

16 Nov '12

Free and Open Source Software (FOSS) is software that gives the user the freedom to use, copy, study, change, and improve it. FOSS contributors believe that this is the best way to develop software because it benefits society, creates a fun collaborative community around a project, and allows anyone to make innovative changes that reach many people. In an effort to get more women involved in FOSS, a number of organizations are offering Outreach Program for Women internships from January 2 to April 2, 2013. The application deadline is December 3, 2012. The applicants need to get in touch with individual projects they are interested in working on and make a small contribution ahead of the application deadline. Participants will work remotely from home, while getting guidance from an assigned mentor and collaborating within their project’s team and the rest of the FOSS community. The projects include software development, system administration, web development, user experience design, graphic design, documentation, and marketing. The stipend for the program is $5,000 (USD). Any woman available for a full time internship who has not previously participated in the Outreach Program for Women or Google Summer of Code is welcome to apply. College women from the Southern Hemisphere who will have a school summer break during most of this time are particularly encouraged to apply. Please visit https://www.torproject.org/getinvolved/volunteer.html.en#opw to learn more and apply.

1 0

Proposal 214: Allow 4-byte circuit IDs in a new link protocol
by Nick Mathewson 10 Nov '12

10 Nov '12

Filename: 214-longer-circids.txt Title: Allow 4-byte circuit IDs in a new link protocol Author: Nick Mathewson Created: 6 Nov 2012 Status: Open 0. Overview Relays are running out of circuit IDs. It's time to make the field bigger. 1. Background and Motivation Long ago, we thought that 65535 circuit IDs would be enough for anybody. It wasn't. But our cell format in link protocols is still: Cell [512 bytes] CircuitID [2 bytes] Command [1 byte] Payload [509 bytes] Variable-length cell [Length+5 bytes] CircID [4 bytes] Command [1 byte] Length [2 bytes] Payload [Length bytes] This means that a relay can run out of circuit IDs pretty easily. 2. Design I propose a new link cell format for relays that support it. It should be: Cell [514 bytes] CircuitID [4 bytes] Command [1 byte] Payload [509 bytes] Variable cell (Length+7 bytes) CircID [4 bytes] Command [1 byte] Length [2 bytes] Payload [Length bytes] We need to keep the payload size in fixed-length cells to its current value, since otherwise the relay protocol won't work. This new cell format should be used only when the link protocol is 4. (To negotiation link protocol 4, both sides need to use the "v3" handshake, and include "4" in their version cells. If version 4 or later is negotiated, this is the cell format to use.) 2.1. Better allocation of circuitID space In the current Tor design, circuit ID allocation is determined by whose RSA public key has the lower modulus. How ridiculous! Instead, I propose that when the version 4 link protocol is in use, the connection initiator use the low half of the circuit ID space, and the responder use the low half of the circuit ID space. 3. Discussion * Why 4 bytes? Because 3 would result in an odd cell size, and 8 seems like overkill. * Will this be distinguishable from the v3 protocol? Yes. Anybody who knows they're seeing the Tor protocol can probably tell by the TLS record sizes which version of the protocol is in use. Probably not a huge deal though; which approximate range of versions of Tor a client or server is running is not something we've done much to hide in the past. * Why a new link protocol and not a new cell type? Because pretty much every cell has a meaningful circuit ID. * Okay, why a new link protocol and not a new _set of_ cell types? Because it's a bad idea to mix short and long circIDs on the same channel. (That would leak which cells go with what kind of circuits ID, potentially.) * How hard is this to implement? I wasn't sure, so I coded it up. I've got a probably-buggy implementation in branch "wide_cird_ids" in my public repository. Be afraid! More testing is needed!

5 6

authentication questions on Tor controller
by jiang song 08 Nov '12

08 Nov '12

I just start to use tor controller, I notice the mannual says: pass Tor the "--CookieAuthentication 1" option when you start it. Tor will create a file in its data directory called "control_auth_cookie". All your controller needs to do is to pass the contents of this file to authenticate() when it connects to Tor. there are two kinds of Tor, one is installed and can be run by command "tor" the other is Tor Browser Bundle, 1) with command "tor", when it establishes, if I run example.py the result is "Connection refused. Is the ControlPort enabled?" I tried command: "tor --CookieAuthentication 1" to start Tor, but I can't find the so called data directory, and the running information says： Could not open "/etc/tor/torrc": Permission denied 2) with TBB, after I started TBB, if I run example.py, it seems it can connect to ControlPort, but it prompts for a password there is a Data directory in TBB, but I can't find the so called " control_auth_cookie" file, so when I run TBB, how can I pass "--CookieAuthentication 1" to tor? example.py : import time import TorCtl class BandwidthListener(TorCtl.PostEventListener): def __init__(self): TorCtl.PostEventListener.__init__(self) def bandwidth_event(self, event): print "tor read %i bytes and wrote %i bytes" % (event.read, event.written) # constructs a listener that prints BW events myListener = BandwidthListener() # initiates a TorCtl connection, returning None if it was unsuccessful conn = TorCtl.connect() if conn: # tells tor to send us BW events conn.set_events(["BW"]) # attaches the listener so it'll receive BW events conn.add_event_listener(myListener) # run until we get a keyboard interrupt try: while True: time.sleep(10) except KeyboardInterrupt: pass

2 1

Working on GUI
by vimalathithan 08 Nov '12

08 Nov '12

Hi, I am new to this community. A group consists of 5 members from School of Informatics and Computing, working with Professor Jean Camp on a research paper. Our research is to carry out a case study after making changes in the UI of Tor Browser. Could anyone here, please provide a link to learn more about Tor UI to get started with the development activities. Also it would be of great help, if some related document are shared. Please apologize me, if I posted my query to a wrong mailing list or my query sounds naive. Regards, Vimalathithan Rajasekaran Graduate Student - Computer Science School of Informatics and Computing Indiana University - Bloomington

9 11

Proposal 213: Remove stream-level sendmes from the design
by Roger Dingledine 06 Nov '12

06 Nov '12

Filename: 213-remove-stream-sendmes.txt Title: Remove stream-level sendmes from the design Author: Roger Dingledine Created: 4-Nov-2012 Status: Open 1. Motivation Tor uses circuit-level sendme cells to handle congestion / flow fairness at the circuit level, but it has a second stream-level flow/congestion/fairness layer under that to share a given circuit between multiple streams. The circuit-level flow control, or something like it, is needed because different users are competing for the same resources. But the stream-level flow control has a different threat model, since all the streams belong to the same user. When the circuit has only one active stream, the downsides are a) that we waste 2% of our bandwidth sending stream-level sendmes, and b) because of the circuit-level and stream-level window parameters we picked, we end up sending only half the cells we might otherwise send. When the circuit has two active streams, they each get to send 500 cells for their window, because the circuit window is 1000. We still spend the 2% overhead. When the circuit has three or more active streams, they're all typically limited by the circuit window, since the stream-level window won't kick in. We still spend the 2% overhead though. And depending on their sending pattern, we could experience cases where a given stream might be able to send more data on the circuit, but it chooses not to because its stream-level window is empty. More generally, we don't have a good handle on the interactions between all the layers of congestion control in Tor. It would behoove us to simplify in the case where we're not clear on what it buys us. 2. Design We should strip all aspects of this stream-level flow control from the Tor design and code. 2.1. But doesn't having a lower stream window than circuit window save room for new streams? It could be that a feature of the stream window is that there's always space in the circuit window for another begin cell, so new streams will open faster than otherwise. But first, if there are two or more active streams going, there won't be any extra space. Second, since begin cells are client-to-exit, and typical circuits don't fill their outbound circuit windows very often anyway, and also since we're hoping to move to a world where we isolate more activities between circuits, I'm not inclined to worry much about losing this maybe-feature. See also proposal 168, "reduce default circuit window" -- it's interesting to note that proposal 168 was unknowingly dabbling in exactly this question, since reducing the default circuit window to 500 or less made stream windows moot. It might be worth resurrecting the proposal 168 experiments once this proposal is implemented. 2.2. If we dump stream windows, we're effectively doubling them. Right now the circuit window starts at 1000, and the stream window starts at 500. So if we just rip out stream windows, we'll effectively change the stream window default to 1000, doubling the amount of data in flight and potentially clogging up the network more. We could either live with that, or we could change the default circuit window to 500 (which is easy to do even in a backward compatible way, since the edge connection can simply choose to not send as many cells). 3. Evaluation It would be wise to have some plan for making sure we didn't screw up the network too much with this change. The main trouble there is that torperf et al only do one stream at a time, so we really have no good baseline, or measurement tools, to capture network performance for multiple parallel streams. Maybe we should resolve task 7168 before the transition, so we're more prepared. 4. Transition Option one is to do a two-phase transition. In the first phase, edges stop enforcing the deliver window (i.e. stop closing circuits when the stream deliver goes negative, but otherwise they send and receive stream-level sendmes as now). In the second phase (once all old versions are gone), we can start disobeying the deliver window, and also stop sending stream-level sendmes back. That approach takes a while before it will matter. As an optimization, since clients can know which relay versions support the new behavior, we could have relays interpret violating the deliver window as signaling support for removed stream-level sendmes: the relay would then stop sending or expecting sendmes. That optimization is somewhat klunky though, first because web-browsing clients don't generally finish out a stream window in the upstream direction (so the klunky trick will probably never happen by accident), and second because if we lower the circuit window to 500 (see Sec 2.2), there's now no way to violate stream deliver windows. Option two is to introduce another relay cell type, which the client sends before opening any streams to let the other side know that it shouldn't use or expect stream-level sendmes. A variation here is to extend either the create cell or the begin cell (ha -- and they thought I was crazy when I included the explicit \0 at the end of the current begin cell payload), so we can specify our circuit preferences without any extra overhead. Option three is to wait until we switch to a new circuit protocol (e.g. when we move to ntor or ace), and use that as the signal to drop stream-level sendmes from the design. And hey, if we're lucky, by then we'll have sorted out the n23 questions (see ticket 4506) and we might be dumping circuit-level sendmes at that point too. Options two or three seem way better than option one. And since it's not super-urgent, I suggest we hold off on option two to see if option three makes sense.

3 7

Damian's Status Report - October 2012
by Damian Johnson 02 Nov '12

02 Nov '12

Ahhh, the beginning of winter. That very special time of the year when Seattle skies are perpetual overcast and gloomy. When crowds flock to the coffee shops and the best thing to do with your time is hook up to a caffeine IV and code. ... on a side note it has been a really productive month. ======================================== * Stem Website Stem now has a far more developer friendly website! https://stem.readthedocs.org/en/latest/index.html Barring the obvious new sections I revised vast swaths of stem's API documentation. Feedback welcome! The tutorial section is just starting, but I have some ideas for expanding it. ======================================== * Network Status Document Parsing After a couple months of work by Ravi and me the network status document handling is *finally* done. It turned out to be a... very big feature branch. Announcement: https://lists.torproject.org/pipermail/tor-dev/2012-October/004092.html Docs: https://stem.readthedocs.org/en/latest/api/descriptor/networkstatus.html Code: https://gitweb.torproject.org/stem.git/commitdiff/ea356b7?hp=5cd457b With this done we're very nearly at feature parity with metrics-lib (and I suspect a bit past it in terms of testing). In finishing this up I also spotted an undocumented oddity with microdescriptor 'directory-signature' lines. [1] ======================================== * GSoC Mentor Summit Met with the developers of numerous other open source projects. I was really impressed at how many worthwhile conversations were crammed into such a short conference. Highlights include... * Arc from Python had distutils suggestions, thanks to which stem and arm will soon have both Python 2.x and 3.x support. * OSU's Open Source Labs are entertaining the thought of running Tor relays. * Discussed TorBirdy and other Tor projects with Sukhbir. He mentioned an issue with trac permissions that is now fixed. [2] * Talked with Terri from Python about Mailman 3, which would be a great answer for the requests we get to have a Tor forum. [3] * Attended a talk led by Marina from Gnome about their outreach program for women. We'll likely be taking part in it this year. For the full trip report see... https://lists.torproject.org/pipermail/tor-dev/2012-October/004115.html ======================================== Other changes include... * Cleaning up orphaned pyc files as a part of running our tests (feature suggested by Ravi) [4] * Ported arm's str_tools module to stem and added unit tests [5][6] * Code reviewed Ravi's attach_stream addition, waiting on the revisions [7] * Arm troubleshooting on irc with zack and ultramage. Also fixed a broken link on arm's site spotted by wh6iQ. * A new contributor, Eoin, spotted some great issues and contributed patches. Tickets include... * python 2.5 compatibility bugs [8] * count of the number of skipped tests [9] * error with the whitespace checker [10] * spelling corrections [11] * Sathyanarayanan spotted some nice bugs including... * on python 2.5-2.6 a missing microdescriptor consensus wasn't causing the related test to be skipped [12] * integ tests for the process module would fail if tor was already running [13] ======================================== Next up: Ravi and I are working on tor event handling, the last major feature stem is missing as a controller library. After that we plan to port arm over, then tidy up loose ends in preparation for stem's initial release. Cheers! -Damian [1] https://trac.torproject.org/7072 [2] https://trac.torproject.org/7186 [3] https://trac.torproject.org/3592 [4] https://trac.torproject.org/7103 [5] https://trac.torproject.org/7158 [6] https://stem.readthedocs.org/en/latest/api/util/str_tools.html [7] https://trac.torproject.org/7152 [8] https://trac.torproject.org/7244 [9] https://trac.torproject.org/7246 [10] https://trac.torproject.org/7263 [11] https://trac.torproject.org/7245 [12] https://trac.torproject.org/7250 [13] https://trac.torproject.org/7251

1 0

circuitmux_ewma.c
by Gisle Vanem 01 Nov '12

01 Nov '12

These gcc extensions: /*** EWMA circuitmux_policy_t method table ***/ circuitmux_policy_t ewma_policy = { .alloc_cmux_data = ewma_alloc_cmux_data, .free_cmux_data = ewma_free_cmux_data, Doesn't work well with MSVC. Here is a patch: --- ..\..\Git-latest\src\or\circuitmux_ewma.c 2012-11-01 15:53:23.125000000 +0100 +++ circuitmux_ewma.c 2012-11-01 17:52:55.371093500 +0100 @@ -200,15 +200,22 @@ /*** EWMA circuitmux_policy_t method table ***/ -circuitmux_policy_t ewma_policy = { .alloc_cmux_data = ewma_alloc_cmux_data, - .free_cmux_data = ewma_free_cmux_data, - .alloc_circ_data = ewma_alloc_circ_data, - .free_circ_data = ewma_free_circ_data, - .notify_circ_active = ewma_notify_circ_active, - .notify_circ_inactive = ewma_notify_circ_inactive, - .notify_set_n_cells = NULL, /* EWMA doesn't need this */ - .notify_xmit_cells = ewma_notify_xmit_cells, - .pick_active_circuit = ewma_pick_active_circuit +#ifdef __GNUC__ + #define STRUCT_INIT(member,val) member = val +#else + #define STRUCT_INIT(member,val) val +#endif + +circuitmux_policy_t ewma_policy = { + STRUCT_INIT (.alloc_cmux_data, ewma_alloc_cmux_data), + STRUCT_INIT (.free_cmux_data, ewma_free_cmux_data), + STRUCT_INIT (.alloc_circ_data, ewma_alloc_circ_data), + STRUCT_INIT (.free_circ_data, ewma_free_circ_data), + STRUCT_INIT (.notify_circ_active, ewma_notify_circ_active), + STRUCT_INIT (.notify_circ_inactive, ewma_notify_circ_inactive), + STRUCT_INIT (.notify_set_n_cells, NULL), /* EWMA doesn't need this */ + STRUCT_INIT (.notify_xmit_cells, ewma_notify_xmit_cells), + STRUCT_INIT (.pick_active_circuit, ewma_pick_active_circuit) }; /*** EWMA method implementations using the below EWMA helper functions ***/ --gv

2 2

Reminder of November, December deadlines for Tor 0.2.4
by Nick Mathewson 01 Nov '12

01 Nov '12

Hi, all! >From the Tor 0.2.4 schedule at https://trac.torproject.org/projects/tor/wiki/org/roadmaps/Tor/024 : """November 20, 2012: Big feature proposal freeze. Any big feature which requires a design proposal must have its design proposal finished by this date. If it needs changes after this date, then maybe we didn't design it well enough, and we probably shouldn't merge it. December 10, 2012: Big feature merge freeze. No big features will be merged after this date. December 15, 2012: Small feature proposal freeze. Any small feature which requires a design proposal must have its tiny little design proposal finished by this date. January 10, 2013: Feature merge freeze. No features after this date. I mean it. ... The definition of "big patch" is deliberately vague. Note that the cutoffs above are merge freezes, not submission freezes.""" (I've just added 10 days to that first deadline, and 5 days to the third.) Also, I'm currently thinking that, to give these deadlines teeth, I shouldn't self-enforce, since I've veered between "pushover" and "insane zealot" in the past in ways that didn't make a lot of sense. Rather, I'm going to say that in cases of doubt ("Is this a little feature") and cases where I'd like to violate freezes ("surely this can go in on December 12"), I'm not going to merge patches on my sole discretion any more. Rather, I'm going to say that at least two of me, Roger, and Andrea ought to agree to violate a freeze before we do so. (I will try not to forget and mess this up.) With any luck, this will let us get closer to a reasonable 6 month release cycle. yrs, -- Nick

1 0