October 2012 - tor-dev - lists.torproject.org

Proposal 205: Remove global client-side DNS caching
by Nick Mathewson 18 Dec '12

18 Dec '12

Filename: 205-local-dnscache.txt Title: Remove global client-side DNS caching Author: Nick Mathewson Created: 20 July 2012 Status: Open 0. Overview This proposal suggests that, for reasons of security, we move client-side DNS caching from a global cache to a set of per-circuit caches. This will break some things that used to work. I'll explain how to fix them. 1. Background and Motivation Since the earliest Tor releases, we've kept a client-side DNS cache. This lets us implement exit policies and exit enclaves -- if we remember that www.mit.edu is 18.9.22.169 the first time we see it, then we can avoid making future requests for www.mit.edu via any node that blocks net 18. Also, if there happened to be a Tor node at 18.9.22.169, we could use that node as an exit enclave. But there are security issues with DNS caches. A malicious exit node or DNS server can lie. And unlike other traffic, where the effect of a lie is confined to the request in question, a malicious exit node can affect the behavior of future circuits when it gives a false DNS reply. This false reply could be used to keep a client connecting to an MITM'd target, or to make a client use a chosen node as an exit enclave for that node, or so on. With IPv6, tracking attacks will become even more possible: A hostile exit node can give every client a different IPv6 address for every hostname they want to resolve, such that every one of those addresses is under the attacker's control. And even if the exit node is honest, having a cached DNS result can cause Tor clients to build their future circuits distinguishably: the exit on any subsequent circuit can tell whether the client knew the IP for the address yet or not. Further, if the site's DNS provides different answers to clients from different parts of the world, then the client's cached choice of IP will reveal where it first learned about the website. So client-side DNS caching needs to go away. 2. Design 2.1. The basic idea I propose that clients should cache DNS results in per-circuit DNS caches, not in the global address map. 2.2. What about exit policies? Microdescriptor-based clients have already dropped the ability to track which nodes declare which exit policies, without much ill effect. As we go forward, I think that remembering the IP address of each request so that we can match it to exit policies will be even less effective, especially if proposals to allow AS-based exit policies can succeed. 2.3. What about exit enclaves? Exit enclaves are already borken. They need to move towards a cross-certification solution where a node advertises that it can exit to a hostname or domain X.Y.Z, and a signed record at X.Y.Z advertises that the node is an enclave exit for X.Y.Z. That's out-of-scope for this proposal, except to note that nothing proposed here keeps that design from working. 2.4. What about address mapping? Our current address map algorithm is, more or less: N = 0 while N < MAX_MAPPING && exists map[address]: address = map[address] N = N + 1 if N == MAX_MAPPING: Give up, it's a loop. Where 'map' is the union of all mapping entries derived from the controller, the configuration file, trackhostexits maps, virtual-address maps, DNS replies, and so on. With this design, the DNS cache will not be part of the address map. That means that entries in the address map which relied on happening after the DNS cache entries can no longer work so well. These would include: A) Mappings from an IP address to a particular exit, either manually declared or inserted by TrackHostExits. B) Mappings from IP addresses to other IP addresses. C) Mappings from IP addresses to hostnames. We can try to solve these by introducing an extra step of address mapping after the DNS cache is applied. In other words, we should apply the address map, then see if we can attach to a circuit. If we can, we try to apply that circuit's dns cache, then apply the address map again. 2.5. What about the performance impact? That all depends on application behavior. If the application continues to make all of its requests with the hostname, there shouldn't be much trouble. Exit-side DNS caches and exit-side DNS will avoid any additional round trips across the Tor network; compared to that, the time to do a DNS resolution at the exit node *should* be small. That said, this will hurt performance a little in the case where the exit node and its resolver don't have the answer cached, and it takes a long time to resolve the hostname. If the application is doing "resolve, then connect to an IP", see 2.6 below. 2.6. What about DNSPort? If the application is doing its own DNS caching, they won't get much security benefit from here. If the application is doing a resolve before each connect, there will be a performance hit when the resolver is using a circuit that hadn't previously resolved the address. Also, DNSPort users: AutomapHostsOnResolve is your friend. 3. Alternate designs and future directions 3.1. Why keep client-side DNS caching at all? A fine question! I am not sure it actually buys us anything any longer, since exits also have DNS caching. Shall we discuss that? It would sure simplify matters. 3.2. The impact of DNSSec Once we get DNSSec support, clients will be able to verify whether an exit's answers are correctly signed or not. When that happens, we could get most of the benefits of global DNS caching back, without most of the security issues, if we restrict it to DNSSec-signed answers.

6 12

Proposal: Tuning the Parameters for the Path Bias Defense
by Mike Perry 18 Dec '12

18 Dec '12

Also exists at https://gitweb.torproject.org/user/mikeperry/torspec.git/blob/path-bias-tun… -------------------------------------------------------------------- Title: Tuning the Parameters for the Path Bias Defense Author: Mike Perry Created: 01-10-2012 Status: Open Target: 0.2.4.x+ Overview This proposal describes how we can use the results of simulations in combination with network scans to set reasonable limits for the Path Bias defense, which causes clients to be informed about and ideally rotate away from Guards that provide extremely low circuit success rates. Motivation The Path Bias defense is designed to defend against a type of route capture where malicious Guard nodes deliberately fail circuits that extend to non-colluding Exit nodes to maximize their network utilization in favor of carrying only compromised traffic. This attack was explored in the academic literature in [1], and a variant involving cryptographic tagging was posted to tor-dev[2] in March. In the extreme, the attack allows an adversary that carries c/n of the network capacity to deanonymize c/n of the network connections, breaking the O((c/n)^2) property of Tor's original threat model. Design Description The Path Bias defense is a client-side accounting mechanism in Tor that tracks the circuit failure rate for each of the client's guards. Clients maintain two integers for each of their guards: a count of the number of times a circuit was extended at least one hop through that guard, and a count of the number of circuits that successfully complete through that guard. The ratio of these two numbers is used to determine a circuit success rate for that Guard. The system should issue a notice log message when Guard success rate falls below 70%, a warn when Guard success rate falls below 50%, and should drop the Guard when the success rate falls below 30%. To ensure correctness, checks are performed to ensure that we do not count successes without also counting the first hop. Similarly, to provide a moving average of recent Guard activity while still preserving the ability to ensure correctness, we "scale" the success counts by an integer divisor (currently 2) when the counts exceed the moving average window (300) and when the division does not produce integer truncation. No log messages should be displayed, nor should any Guard be dropped until it has completed at least 150 first hops (inclusive). Analysis: Simulation To test the defense in the face of various types of malicious and non-malicious Guard behavior, I wrote a simulation program in Python[3]. The simulation confirmed that without any defense, an adversary that provides c/n of the network capacity is able to observe c/n of the network flows using circuit failure attacks. It also showed that with the defense, an adversary that wishes to evade detection has compromise rates bounded by: P(compromise) <= (c/n)^2 * (100/CUTOFF_PERCENT) circs_per_client <= circuit_attempts*(c/n) In this way, the defense restores the O((c/n)^2) compromise property, but unfortunately only over long periods of time (see Security Considerations below). The spread between the cutoff values and the normal rate of circuit success has a substantial effect on false positives. From the simulation's results, the sweet spot for the size of this spread appears to be 10%. In other words, we want to set the cutoffs such that they are 10% below the success rate we expect to see in normal usage. The simulation also demonstrates that larger "scaling window" sizes reduce false positives for instances where non-malicious guards experience some ambient rate of circuit failure. Analysis: Live Scan Preliminary Guard node scanning using the txtorcon circuit scanner[4] shows normal circuit completion rates between 80-90% for most Guard nodes. However, it also showed that CPU overload conditions can easily push success rates as low as 45%. Even more concerning is that for a brief period during the live scan, success rates dropped to 50-60% network-wide (regardless of Guard node choice). Based on these results, the notice condition should be 70%, the warn condition should be 50%, and the drop condition should be 30%. Future Analysis: Deployed Clients It's my belief that further analysis should be done by deploying loglines for all three thresholds in clients in the live network to utilize user reports on how often high rates of circuit failure are seen before we deploy changes to rotate away from failing Guards. I believe these log lines should be deployed in 0.2.3.x clients, to maximize the exposure of the code to varying network conditions, so that we have enough data to consider deploying the Guard-dropping cutoff in 0.2.4.x. Security Considerations While the scaling window does provide freshness and can help mitigate "bait-and-switch" attacks, it also creates the possibility of conditions where clients can be forced off their Guards due to temporary network-wide CPU DoS. This provides another reason beyond false positive concerns to set the scaling window as large as is reasonable. A DoS directed at specific Guard nodes is unlikely to allow an adversary to cause clients to rotate away from that Guard, because it is unlikely that the DoS can be precise enough to allow first hops to that Guard to succeed, but also cause extends to fail. This leaves network-wide DoS as the primary vector for influencing clients. Simulation results show that in order to cause clients to rotate away from a Guard node that previously succeeded 80% of its circuits, an adversary would need to induce a 25% success rate for around 350 circuit attempts before the client would reject it, or a 5% success rate for around 215 attempts, both using a scaling window of 300 circuits. Assuming one circuit per Guard per 10 minutes of active client activity, this is a sustained network-wide DoS attack of 60 hours for the 25% case, or 38 hours for the 5% case. Presumably this is enough time for the directory authorities to respond by altering the pb_disablepct consensus parameter before clients rotate, especially given that most clients are not active for even 38 hours on end, and will tend to stop building circuits while idle. If we raised the scaling window to 500 circuits, it would require 1050 circuits if the DoS brought circuit success down to 25% (175 hours), and 415 circuits if the DoS brought the circuit success down to 5% (69 hours). The tradeoff, though, is that larger scaling window values allow Guard nodes to compromise clients for duty cycles of around the size of this window (up to the (c/n)^2 * 100/CUTOFF_PERCENT limit in aggregate), so we do have to find balance between these concerns. Implementation Notes: Log Messages Log messages need to be chosen with care to avoid alarming users. I suggest: Notice: "Your Guard %s is failing more circuits than usual. Most likely this means the Tor network is overloaded. Success counts are %d/%d." Warn: "Your Guard %s is failing a very large amount of circuits. Most likely this means the Tor network is overloaded, but it could also mean an attack against you or potentially the Guard itself. Success counts are %d/%d." Drop: "Your Guard %s is failing an extremely large amount of circuits. [Tor has disabled use of this Guard.] Success counts are %d/%d." The second piece of the Drop message would not be present in 0.2.3.x, since the Guard won't actually be dropped. Implementation Notes: Consensus Parameters The following consensus parameters reflect the constants listed in the proposal. These parameters should also be available for override in torrc. pb_mincircs=150 The minimum number of first hops before we log or drop Guards. pb_noticepct=70 The threshold of circuit success below which we display a notice. pb_warnpct=50 The threshold of circuit success below which we display a warn. pb_disablepct=30 The threshold of circuit success below which we disable the guard. pb_scalecircs=300 The number of first hops at which we scale the counts down. pb_scalefactor=2 The integer divisor by which we scale. 1. http://freehaven.net/anonbib/cache/ccs07-doa.pdf 2. https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html 3. https://gitweb.torproject.org/torflow.git/tree/HEAD:/CircuitAnalysis/PathBi… 4. https://github.com/meejah/txtorcon/blob/exit_scanner/apps/exit_scanner/fail… -- Mike Perry

2 3

Compiling tor against OpenSSL_1_0_2-stable
by Christian Kujau 29 Nov '12

29 Nov '12

Hi, while trying to compile the latest git-checkout against openssl-1.0.2, I've come across the following issues: ---- make[1]: Entering directory `/usr/local/src/tor-git' CC src/common/tortls.o cc1: warnings being treated as errors In file included from /opt/openssl/include/openssl/ssl.h:1382, from src/common/tortls.c:36: /opt/openssl/include/openssl/srtp.h:138: error: redundant redeclaration of ‘SSL_get_selected_srtp_profile’ /opt/openssl/include/openssl/srtp.h:135: note: previous declaration of ‘SSL_get_selected_srtp_profile’ was here make[1]: *** [src/common/tortls.o] Error 1 make[1]: Leaving directory `/usr/local/src/tor-git' make: *** [all] Error 2 ---- There is an open ticket[0] in the openssl bugtracker for this. While the proper solution is to fix openssl/include/openssl/srtp.h, I wanted to compile without -Werror. However, when adding CFLAGS="-Wno-error" during ./configure, -Werror is still added to the ./Makefile and overriding -Wno-error. When adding CFLAGS="-Wno-error" during "make" all the other CFLAGS are gone too. Thus I ended up removing -Werror from the Makefile and tortls.o compiled. While this is really an issue with openssl, I wanted to have this documented, just in case anybody else tries the same. If someone knows of a better workaround (i.e. compiling just tortls.c with -Wno-error and everything else with -Werror), please share! :-) A bit later, compilation stops again: ---- CCLD src/or/tor src/common/libor-crypto.a(aes.o): In function `aes_crypt': aes.c:(.text+0x860): undefined reference to `CRYPTO_ctr128_encrypt' collect2: ld returned 1 exit status make[1]: *** [src/or/tor] Error 1 make[1]: Leaving directory `/usr/local/src/tor-git' make: *** [all] Error 2 ---- Hm, this leaves me puzzled for now. CRYPTO_ctr128_encrypt is still included in openssl-1.0.2 and src/common/aes.o seems to be built with this function included as well, not sure why src/common/libor-crypto.a complains now: ---- $ grep -r CRYPTO_ctr128_encrypt /opt/openssl/ /opt/openssl/include/openssl/modes.h:void CRYPTO_ctr128_encrypt(const unsigned char *in, unsigned char *out, /opt/openssl/include/openssl/modes.h:void CRYPTO_ctr128_encrypt_ctr32(const unsigned char *in, unsigned char *out, Binary file /opt/openssl/bin/openssl matches Binary file /opt/openssl/lib/libcrypto.a matches $ grep -r CRYPTO_ctr128_encrypt . ./src/common/aes.c: CRYPTO_ctr128_encrypt((const unsigned char *)input, Binary file ./src/common/aes.o matches Binary file ./src/common/libor-crypto.a matches ---- Why do I (try to) build against openssl-1.0.2? I'm on Debian/stable which still ships openssl-0.9.8o and I wanted to get rid of this "use a more recent OpenSSL" message during startup :-) Otherwise, today's git-checkout of tor runs just fine when built against openssl-0.9.8 (on powerpc) - yay! Christian. [0] http://rt.openssl.org/Ticket/Display.html?id=2724 -- BOFH excuse #330: quantum decoherence

2 2

use tor controller to detect circuit/path change
by esolve esolve 31 Oct '12

31 Oct '12

Hi, I'm new to Tor controller, Tor client usually open 3 circuits, one for current use and the other 2 for standby. Tor will change the current circuit/path in use from time to time, depending on the network load dynamics I'm wondering whether it is possible to use Tor controller to detect when the circuit/path in use is changed and obtain the list of IP addresses of those relay nodes. thanks!

4 6

[Stegotorus] Re: Do you have time to poke at ST
by vmonmoonshine＠gmail.com 25 Oct '12

25 Oct '12

Hello Zack, Sorry for being bit out of touch as I'm traveling and my access to Internet is sporadic. I'm still working on Stegonotorus. I developed the webpage_tester (now on f--webpage-tester branch on github), that is curl using Stegotorus to download anything on the web and compare it with the original. It is based on assumption that is my best approximation for a browser. I did that in a hope to catch the bug, but I haven't. Basically I failed to browse anything unreliably. I can download 20 megabytes or so with no error. It takes a long time, but It doesn't fail. My payload server is the apache payload server but that shouldn't make a huge difference. I think my payloads even have smaller capacity and less efficient than your fake ones. Anyway, I'm going to tweak the tester proxy to drops packets at random, to force the ack into play, I'll get back to you with more update. Cheers, vmon

1 0

New tech report: Counting daily bridge users
by Karsten Loesing 24 Oct '12

24 Oct '12

Hi everyone, I just finished a new tech report titled "Counting daily bridge users": https://research.torproject.org/techreports/counting-daily-bridge-users-201… >From the abstract: "As part of the Tor Metrics Project, we want to learn how many people use the Tor network on a daily basis. Counting users in an anonymity network is, obviously, a difficult task for which we cannot collect too sensitive usage data. We came up with a privacy-preserving approach for estimating directly connecting user numbers by counting requests to the directory mirrors and deriving approximate user numbers from there. In this report we describe a modified approach for estimating the number of users connecting via bridges by evaluating directory requests made to bridges. We compare this new approach to our current approach that estimates bridge user numbers from total unique IP addresses seen at bridges. We think that results from the new approach are closer to reality, even though that means there are significantly fewer daily bridge users than originally expected." Feedback is much appreciated and could influence our implementation of user number estimates in the future (#7154). Thanks, Karsten

1 0

Re: [tor-dev] Automating Bridge Reachability Testing (#6414)
by Isis 23 Oct '12

23 Oct '12

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 Hi Karsten! Oh sheesh. I did not see it...I will have to figure out why. That is slightly worrying. So, I am rushing to meet the final deadline, but I still think it is doable. I have mostly finished up my OONI work for the month, and I planned to spend the remainder of this month working on the bridge test. I have finished most of the actual Tor connection code, as well as one of the four basic packet level scans (the icmp8 one). Two of the other packet level scans, the TCP SYN and ACK ones, are pretty much copies of the icmp8 one with a couple lines changed, and they shouldn't be a big deal. There is still the vanilla TLS handshake test/scan/thing, which has not been started yet, and will take a bit more time than the others because Python notoriously has problems with SSL bindings and libraries, so I'll need to do a bit of research on newer ones and updates and see which is the best to use now. I hear that tlslite[1] is the current best choice; if anyone else has any input on this it would be very helpful. :) There were a couple minor hups: 1) When George asked me to test pluggable transports, this required significantly more refactoring than I previously thought was necessary. 2) Arturo redesigned the OONI testing framework API again to use a completely different structure, which was supposed to be backwards compatible and turned out not to be (though I believe that my recent OONI commits fixed that). However, I have been fighting the framework already, because the main scripts in OONI (/ooni/oonicli.py and /ooni/ooniprobe.py) control the reactor, and also expect static iterations through single test and single control functions for each asset (an asset in this case would be one bridge address). The bridge testing is rather dynamic (I would like it to be able to evaluate an approximate danger level to running the next test) and so the framework is kind of troublesome. Also, because the framework handles calling the reactor (in Twisted, the reactor is a sort of event scheduler), and it also expects a rather linear progression of defer.Deferreds (in Twisted, those are standin objects which execute callbacks when they get results from some previous deferred/callback), it would be nicer if I had full control of these myself without needing to hack around the parent scripts. I think it's wise that OONI deals with these things for the testwriter in most cases, because the testwriter shouldn't be expected to be an expert in using Twisted. However, I also think that, in the long term, OONI shouldn't prohibit people who know what they are doing or are doing odd things from being able to do so. As a result, I've decided (for now), to use bits are parts of the OONI code before the recent refactoring, and later (after the deliverable) I will work on adding flags to OONI to give the test script full control of the reactor and deferreds, as well as evaluating whether or not the bridge test is even compatible with the new API. I do not want to get caught up in dealing with this right now, I just want to have it all working and deployable in a way that I know will work. 3) The indirect scans are becoming quite complicated to automate in any sane fashion. I still would like to continue working on this, as I'm quite enjoying the difficulty, but due to their temporary and volatile nature (they will change frequently depending on the blocking methods of a particular country and the currently available in-country bounces/proxies/whatever-thing-the-indirect-scan-uses), as well as the fact that many of these methods are still undiscovered, I think it is safe to add them as specialty cases after the fact without impacting overall general testing. There is one in particular that I would like to finish before the deadline because I am quite proud of it and am having a lot of fun working on it, but I'm first going to concentrate on wrapping up the active scans. There are other things which I've marked as helpful things to do, but which are not necessarily part of this deliverable: 1) Having a parser for bridge descriptors to turn them into test inputs, and vice versa. 2) Having some undiscoverable method for setting up lots of IPv6 bridges on one OR (Tor currently only allows up to eight, I believe) and having these be discoverable by bridgedb and no one else. I was thinking of this while talking with Aaron, because he reminded me that people on IPv6 have tons of IPs available, and I was thinking that if we configured some type of one-way hash function, we could say that a bridge descriptor for 2001:db8::1:1 should actually mean multiple descriptors for 2001:db8::fa98:38d2 2001:db8::e099:2188 2001:db8::88aa:3b7 or something, derived from the output of hashing the original descriptor with the OR's key or something else. This would help distribute bridges in the future quite a bit, though it doesn't do much for the current bridge situation. Anyone wanting to help with the above two things, or with an idea for another indirect scan, or with feedback on anything I'm working on, should feel free to contact me and it will be greatly appreciated. :D .-- .. ... .... - -- . .-.. ..- -.-. -.- <(A)3 isis agora lovecruft .-.-. [1] https://github.com/trevp/tlslite On Fri 12 Oct 2012 at 14:56, thus spake Karsten Loesing: > Hi Isis, > > did you see this email? > > Sorry for being pushy, but we're less than three weeks away from the > deadline, which makes me kinda nervous. > > Thanks, > Karsten > > > On 10/8/12 9:14 AM, Karsten Loesing wrote: > > Hi Isis, > > > > can you give me a brief status update on the sponsor F year 2 > > deliverable "Automating Bridge Reachability Testing", ticket #6414? > > > > In particular, how did the two project-internal milestones on September > > 15 and October 7 go? > > > > Do you mind updating #6414 with the status? > > > > The overall deadline is on November 1, which is in 3.5 weeks. How > > realistic do you think it is that we'll have automated bridge > > reachability tests by then? > > > > Thanks, > > Karsten > > > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQIcBAEBCgAGBQJQeJ4pAAoJEKOttnos24s1GlkP/1ODucFe9q9a7KaKisgVqBcx Cg1X3yGI+dsWvKtMwzgNqT/hcS+95GAYQiaa8fDlbiLY3nCWEsGYSOTjsbAmp04O qPCdBiSFE4VqiZy4PYUHUkf8qZTYkXqAiMnyuuLVJINJ+BHLAdwEmEWB77ncQUxV PvG6sxQ3GY64ZqRaSHwudf3H8mEPN/tNWRIXubnvAGM16EV0hWb51uORwo6CG86m lKwpBqbSX5uDgG+B6HCeZps0Zv7cDypI3dtdd8hJHncUpFmfuj2y+Oad1M5DVbMC 4UMvCv/4tMPoPyjTYjWgLQRHEFiMdMwQcdPntnF6XqUBMLvd6v1fk1IxaaqNCDah JWxK8ymUu90FLmmiyaSHQE/tfkFoEDCXz3XzR8xQA1zI2aq0hHdxA+G2JmW8yadQ wt0N4EeCzK154r4+YRC1eJLrsSOhmA7SaAE6A+/iEOgasdMY0YWchTDnlUbUB5iv acbMVITSGqmcRMos5xi450V98Qw1nW3UoBj5wi8uh0BWqnhqfomqL6oloQEdgAze MqtCZ91adKKXntIsEZW0C/klBYg5mZIxdtmAW5eO/j+ogLB/L0/hX4/TZ6OH5i/N 7jJWAF0MbSWI2Q1Gk+oFFulib5m3XWzqg5Yq/+8VfE5n1R5xM1FgBwC932SWLOFZ BV5c9ntZ+iJlbhpdL5yJ =jk13 -----END PGP SIGNATURE-----

4 5

Trip Report: GSoC Mentor Summit
by Damian Johnson 22 Oct '12

22 Oct '12

As per conferencing tradition Friday was spent on travel and meeting the other attendees. Some of the highlights for me were... * David from KDE Besides demoing some KDE eye candy we discussed their project infrastructure. KDE is a federation of smaller projects and had over sixty students this year (ten times the number mentored by Tor). Their project's scale has led to some unusual infrastructure decisions. For instance, they have a partly decentralized git infrastructure where pushes go to a single master host and pulls are from any of several mirrors. The config they use to do this leads to some... odd behavior. For instance a 'git pull' updates your tracking branch but not the origin branch reference. The result is that to do a pull for realz you need to call *both* pull and fetch. No doubt they also get fun behavior from mirroring delays... We also talked a bit about post-review and defaults they could set to better support their setup. KDE has the largest public ReviewBoard instance, but the above git setup makes it a bit confusing to use. * Sukhbir from Debian In 2011 Sukhbir applied to us for GSoC to work on TorBirdy. We loved his proposal, but due to prior commitments he ended up working with Debian instead. Since then he has become a GSoC mentor for Debian and involved with the Tor by implementing his earlier proposal for TorBirdy. Sukhbir's interested in getting even more involved with Tor so we discussed other projects that might interest him, and ways that we could better publicize TorBirdy on our site. * Arc from Python When I found out that Python had a mentor at the summit I made a mental note to hunt him down and ask about packaging best practices. After an unexpected discussion about rugby I found out that it's actually easy to support both python's 2.x and 3.x series by including a 2to3 conversion at build time. This can be done via either distutils or distribute... distutils: http://python3porting.com/2to3.html#running-2to3-on-install distribute: http://packages.python.org/distribute/python3.html I also asked him to look into his crystal ball for when python 3 would take over the world and he said 'Next year. Ubuntu and Fedora are ready and willing to make the switch. The last main holdout is Gnome. They tried to migrate but work there isn't finished yet.' ======================================== Saturday was the first day of the unconference. After an amusingly confused attempt to have each of the couple hundred attendees shake each other's hand there were sessions. Some were a little interesting, but I spent more time on the hallway track since that's the real benefit of the summit. The only useful tidbits I got from the talks were... - Do outreach early. The successful GSoC students who stick around tend to be the ones that get involved before the application phase. We should try harder to recruit college students to hack on tor, with the carrot that this'll give them a leg up when applying for the program. OpenHatch (http://openhatch.org/) might be something to look into for this. This would be a nice task for a community manager if we get one. - Google Code In (https://code.google.com/gci/) is a program somewhat similar to GSoC where highschool students become involved with open source. Last year they had 18 organizations and this year they're narrowing it down to 10. I was already highly tentative about having us apply and now that I've heard more I'm sure we don't have enough bandwidth for the hand-holding this would require. As for the hallway track... * Adriano and Luis from Umit Last year Adriano showed me Open Monitor (http://www.openmonitor.org/) a censorship detector written in python. Sounds familiar? I thought so too, and tried a few times to get them to talk with Ooni Probe and vice versa without success. My impression is that they're UI developers (a skillset we sorely lack in the tor project) with a rather unscalable backend, while Ooni Probe's backend is far more mature but lacks any sort of UI for rendering real time censorship information. I made another stab at getting the two projects to talk, after which the meeting took a weird turn with Adriano arguing that 'some censorship is good'. Evidently they decided that Open Monitor won't look for censorship concerning 'porn or terrorism'. I argued that this was a slippery slope and that censorship monitoring shouldn't try to pass a moral judgment on the content being censored, but after a time it was clear that we were talking past each other. I still think that we should leverage their UI expertise, but that's up to the Ooni Probe devs. * Open Source Lab Met with a couple administrators from the OSU's Open Source Labs (https://osuosl.org/) They provide hosting for several of the largest open source projects including Apache and the Linux Foundation. Mostly we talked about amusing legal threats they get for hosting the phpBB project. Evidently lawyers are quite skilled at clicking the 'this is a phpBB forum' link followed by 'hosted by the OSL' before sending their angry emails. We also talked a bit about setting up non-exit relays. They might be pretty receptive to this if we want to follow up. * Sumana and Rob from Wikimedia Unsurprisingly Wikipedia occasionally has issues with spammers using Tor. We talked about some possible options, such as requiring accounts for Tor users to edit with a sort of proof of work in account creation to make ban evasion more of a pita. * Terri from Python Mailman 3 is coming, and with it an interface that *doesn't* look like it came from the 1980s! Most importantly for us, the new version of Mailman provides a forum interface, letting email and forum users communicate by whichever method they prefer. This would be a good answer to our forums ticket (https://trac.torproject.org/3592) She estimates that it'll be ready in six months or so. ======================================== Flying out on Sunday cut my day short, but there was one session that I thought was interesting. Gnome and Wikimedia are launching a program similar to GSoC to encourage more women to get involved with open source. It runs later this winter. One gotcha is that Google's not involved so mentoring orgs need to cover the $5k stipend. I like the idea. Is this something we want to take part in? If so then I'd be happy to administer the non-financial parts of it. Cheers! -Damian

2 1

Re: [tor-dev] Extending Pyonionoo to provide statistics
by Damian Johnson 19 Oct '12

19 Oct '12

Hi Karsten. This is actually really good timing. As you probably noticed from tor-commits@ I just pushed support for network status documents (v2 and v3 votes, consensus, and microdescriptor consensuses). It's the combination of a month of work from Ravi and a couple more from me. Stem's descriptor parsing functionality is one of its most well developed features and I'm anxious for it to start to get some users. The feature gap between stem and metrics-lib is now pretty small, so I'd love for it to start to take over some of metrics-lib's responsibilities (and hopefully in turn get direct involvement from you and Sathyanarayanan so it'll better meet your needs). > We would start with daily users, both direct and bridge users, and later add > aggregate statistics about relays and bridges, and after that torperf > performance statistics. Gotcha. As I understand it the document types that stem is still missing are... * microdescriptors * bridge pool assignments * exit list entry * torperf output So what you'll need from me is primarily the ability to parse torperf output? Or is there another document type that I'm missing? > I think we'd need Damian's help for the descriptor-parsing side Happy to help, though I'm not entirely sure yet what kind of additional parsing support you'll need. > Sathya, Damian, can you already say how much of 2013 you will be around > for doing Tor stuff and how much time you think you could spend on this > project? For my part a fair bit. This is, of course, a hobby that I do outside of a full time job so work and life might get in the way. That said, any project that includes collaborating with other developers to make use of stem goes to the top of my todo list. > I'm thinking one ticket for implementing > usage statistics in Pyonionoo, a second ticket for the censorship > detector integration which depends on the first ticket, and two more > tickets for network statistics and torperf statistics integration into > Pyonionoo. I'd probably suggest the first two tickets only for trying > to get funding from sponsor F year 3 and save the other two tickets for > later. Hmm, aren't those last two tickets the only ones where I'd be involved? It sounds like this project mostly concerns pyonionoo so guess we should wait for input from Sathyanarayanan... Cheers! -Damian PS. Sathyanarayanan: I was gonna ping you separately but might as well hijack this thread - would you mind giving stem's new networkstatus module a try in pyonionoo? You can find documentation for it at... https://stem.readthedocs.org/en/latest/stem.descriptor.html#module-stem.des… ... let me know if you run into any issues! PPS. Grrr, their pydocs have some rendering bugs... >:( On Fri, Oct 12, 2012 at 9:57 AM, Karsten Loesing <karsten(a)torproject.org> wrote: > Hi Sathya, hi Damian, > > I have been working on improving bridge usage statistics in the past > weeks, and I discussed my results with George in the context of > improving the censorship detector. We concluded that we need to write a > fair amount of new code and that it would be nice to integrate this new > code into Pyonionoo. > > Let me explain in more detail: I'm not yet done with the bridge usage > analysis, but early results are that we can calculate daily bridge users > similar to how we calculate daily direct users. We need a more precise > implementation than what we have in metrics-web though. So, we either > need to redesign the complex beast called metrics-web, or start from > scratch, ideally in a programming language that attracts more potential > contributors. > > The censorship detector takes the output of metrics-web's daily direct > usage numbers and tries to detect sudden drops or increases in usage. > It would be good to also look at bridge usage for censorship events, and > it would be quite important to have a tighter integration of the > censorship detector into the usage-calculating process and look at raw > numbers there. Right now, the vast majority of events that the > censorship detector reports are just false positives. > > We first thought about implementing this in a new Python project that > has several modules: the first module would calculate daily users, the > second would determine possible censorship events, the third would > export data via JSON, the fourth would graph results on a website, and > the fifth would send out email notifications. > > However, that codebase would share a lot of functionality with > Onionoo/Pyonionoo. We could instead extend Pyonionoo and Atlas/Compass > to not only provide network status data, but also statistics about the > Tor network and its usage. We would start with daily users, both direct > and bridge users, and later add aggregate statistics about relays and > bridges, and after that torperf performance statistics. Once we're > there we can retire a large part of metrics-web. > > This project is huge, which is why I'm thinking we should apply for > funding. I expect the project to take at least 6 months of developer > time, in addition to the time to make Pyonionoo a full replacement of > Onionoo. Before we ask for money, we should have a very rough idea > who's going to work on this project. Once we have the money, we'll > actually have to do it, and I can't do this all by myself. > > I think we'd need Damian's help for the descriptor-parsing side and > general help with Python and Sathya to make Pyonionoo modular enough to > provide all these different features. I'd either write or help write > the user-counting code, and I think George would help with integrating > and improving the existing censorship-detecting code. > > Sathya, Damian, can you already say how much of 2013 you will be around > for doing Tor stuff and how much time you think you could spend on this > project? If the answer is "maybe not very much", by all means, please > say so. > > If there's at least some interest in this project, I'd create Trac > tickets in the next few days. I'm thinking one ticket for implementing > usage statistics in Pyonionoo, a second ticket for the censorship > detector integration which depends on the first ticket, and two more > tickets for network statistics and torperf statistics integration into > Pyonionoo. I'd probably suggest the first two tickets only for trying > to get funding from sponsor F year 3 and save the other two tickets for > later. > > Thanks, > Karsten

3 2

Even more notes on relay-crypto constructions
by Nick Mathewson 19 Oct '12

19 Oct '12

I should share with the list an update of where I am with a design for an improved relay crypto protocol. For background and motivation, please see the last thread on the topic [Prop202]. There are three main questions remaining for me in choosing among new relay crypto protocols. Basically, they are: "Am I comfortable with this system?", "Among systems I'm comfortable with, how good is this system?", and "Do I know how to implement this system?" Unfortunately, the stuff I am currently comfortable with and know that I could implement is not nearly as good as the stuff that I'm _nearly_ comfortable enough to use and I don't know how to implement. Let's talk about some designs in detail, using the same terminology as proposal 202. Note: As usual, this is probably largely wrong. If you find it on a mailing list archive years from now, please don't try to learn cryptography from it. What I'm looking for most right now is places where my reasoning is wrong, places where I'm mistaken about what tradeoffs I need need to make, and places where there's research that I should have read or remembered. I. MAC-AND-PAD DESIGNS These are the least involved to implement: all you need is an AEAD construction and a PRNG. Those are both pretty well-understood: you can build a good PRNG out of any stream cipher, and you can build the AEAD mode out of a stream cipher and a MAC, or out of various other constructions. As a wrinkle: it would be good to have a system that generates "two MACs for the price of one." That's because in our topology, we need the ability to address relay cells to any node in the circuit, and one easy way to do that here is to have a construction that generates two MACs, and uses one for "cells that should arrive here" and another for "cells that we should relay". We also want shorter MACs: 16 bytes per hop is excessive for our needs. Authenticators like GCM whose output is the raw result of a polynomial evaluation aren't safe to truncate: Ferguson [Ferguson] has a result showing that it's easier than it should be to perform forgery against truncated-MAC GCM constructions. On the other hand, polynomial authenticators seem safe to truncate (generally) if the encryption step comes _after_ the polynomial evaluation. See for example [Poly1305-Trunc]'s discussion of truncated Poly1305 -- I hope it's right. So to be concrete, let me suggest a few modes of operation. I believe I'm competent to implement these: AES-GCM+AES: AES-GCM, except that we add (modulo 2^128) the output of AES(nonce) to each GCM output, in hopes that it will make GCM safe to truncate. (This is probably crazy somehow.) AES-CTR + HMAC-SHA512/256. AES-CTR + Poly1305. Poly1305 requires nonces, but we can use a counter for those. Salsa20 + Poly1305. For a padding PRNG, we could use any stream cipher we like. In each case, we'd want to authenticate not only the content of the cell, but also the previous cell's authenticator and the position of the cell within the stream. AES-GCM+AES is going to be the fastest on CPUs with specific support for AES and GCM, but not on other architectures until/unless more chips grow instructions specialized for AES and GF(2^128). Salsa20+Poly1305 should be fastest on other architectures. This entire category of designs still has the problems that it had before: it leaks the length of the circuit to the last node in the circuit, and consumes a fairly large portion of each cell (for one truncated mac per hop). Further, it's going to be a bit fiddly (though not impossible) to get it to work with rendezvous circuits. II. WIDE-BLOCK DESIGNS Turn we now to designs where we encrypt each block of the cipher using a 509-byte SPRP, such that each block's SPRP is keyed dependently on the original key and on the encrypted value of the previous block. There be dragons here. Let's talk about some ways we could build that. I'll start by talking about wide-block encryption, then talk about getting the "unrecoverability" property where any missing or corrupted block makes all future blocks unrecoverable. The wide-block SPRP I've used before is LIONESS [Bear-Lion]. It requires two keyed hash operations and two stream cipher operations, so it's going to be at best half the speed of the mac-and-pad designs above: a little worse, maybe, since it forces us to rekey with every block. Might that be acceptable? Right now, AES is not a huge fraction of our runtime, and a relay does AES on each cell three times (TLS,relay crypto,TLS) and SHA1 on each cell twice (TLS,TLS). An exit does AES on each cell twice (TLS,relay) and SHA1 on each cell twice (TLS,relay). So for relays, with a naive SHA1-AES LIONESS, we'd be increasing the stream-cipher operations by 25% and the digests by 100%. On an exit, we'd be increasing the stream-cipher operations by 33% and the digests by 100%. If we were to go with LIONESS, we'd surely want to look into faster, better keyed-hash algorithms than SHA1. I don't know whether one of the polynomial MACs above would be good enough, or whether we need other cryptographic digest properties that those don't give us and we'd need to turn to SHA256 or something. I've heard some suggestions that we should look into BEAR or LION instead, but I'm leery of the idea. They are faster, requiring one fewer application of their primitives, but they are PRPs, not SPRPs -- meaning I think that they don't give you Ind-CCA2 [Bear-Lion, section 6]. I don't know a way to exploit this in the Tor network, but deviating from an ideal block cipher seems to me like one of those ideas that's practically begging for disaster. Can we get faster than LIONESS? Indeed we can! There are a pile of constructions. If I understand correctly, and I'm not missing anything, the ones we might want to use fall into two broad categories: those that (like LIONESS) split the message into a short bit and a long bit, then treat them differently; and those that apply a transformation on the message, encrypt the message, and transform it again. The first category (split, then frob each part based on the other once or twice) would appear to be more of a patent minefield, thanks to the XCB patent. The ones to look at here are [HCTR] and [HCH], which require two applications of a universal hash function (can be polynomial-based) and approximately one encryption pass. HCH is a little more unlike XCB. Neither is exactly trivial. We could build either one out of whatever field and stream cipher we wanted, as above, though bitsliced AES-CTR wouldn't be efficient in this case: we aren't generating enough stream at once for bitslicing to pay off. The second category (frob, encrypt, frob) is pretty elegant IMO. The best-explained of these I've seen so far are in a paper by Palash Sarkar [Efficient-Tweakable], though the earlier TET construction [TET] might also be cool. For these, you need an invertible block-wise (Almost) (Xor-)Universal hash function, typically implemented with GF(2^128). I'm not sure if you could use a different field. The multiplication operations here appear to be multiplication by a primitive element, and multiplication by a per-key element. The encryption step can be realized with a somewhat unorthodox counter-mode stream cipher, or a ciphertext-stealing ECB approach. I don't know what you'd need to do to substitute in an orthodox stream cipher for the one used in iHCH. Sarkar seems to see iHCH as a successor to HCH, which is a little worrisome given that HCH is a spiritual descendant of the patented XCB, but to me the two constructions (HCH, iHCH) look practically nothing alike except for their use of a counter mode step. I am a little intimidated by the idea of trying to implement one of these ciphers. Above, I haven't taken one of our requirements into account: that any change to a single cell must make all future cells unrecoverable. There are modes that are supposed to prevent this, and applying them to a decent wide-block cipher might solve the issue. IGE is one of them [IGE], but it turns out to be broken by an attacker who knows some plaintext. The Accumulated Block Chaining [ABC] construction is supposed to fix that; I'm not too sure whether it's correct or efficient. As a blunt-force approach to the problem, we could rekey between each block, using new keys based on a MAC of the last block. This would be pretty inefficient for primitives that need any serious amount of per-key computation. Finally, we could look into constructions that produce an extra secret output incidental to their regular operation, and which are easily rekeyed for each operation. In this whole field, we need to keep an eye out for the patents on CMC, EME, and XCB. "Joy." III. CHOICE OF CIPHERS AND OTHER PRIMITIVES I am hearing exactly two recommendations for encryption primitives nowadays: AES and Salsa20 (and its family). Nobody's recommending anything else as far as I can tell. AES is still the IBM of the block cipher world, which "Nobody Ever Got Fired For Using." It's a bit of a pain to use it in software, though. Its most obvious implementations have timing attacks due to table lookups [DJB-Timing]. OpenSSL has three fast x86 implementations: one of them uses vector permutations, one uses bit-slicing, and one uses the aesni instructions to invoke the chip's built-in AES capabilities. On high-end Intel chips, these take about 12-25, 7-9, and 1.5 cycles per byte respectively. The bitsliced one really needs to encrypt 4KiB at a time (yes, kibibytes), which makes it fine for counter mode but not so good for CBC. (Those numbers are from the OpenSSL source.) Key setup times are cheap for all of these (I think!), but the bitsliced implementation gets expensive if you change the key (or the stream position). Salsa20 (and its descendant, ChaCha) is the Obvious Second Choice for people who don't want to use AES. It is faster than AES on every platform except those with hardware support for AES; 4-7 cycles per byte seems typical for high-end Intel stuff. You would probably have to go out of your way to implement it in a way that was vulnerable to timing side-channel attacks. The only arguments for its insecurity that I'm aware of are that although it has fewer known flaws than AES, it has received less attention than AES, therefore is likelier to _unsuspected_ problems. The counterargument there is that there _are_ several dozen cryptographers who have tried to attack it (or attack reduced-round variants of it), several of whom have also done successful results against AES. [DJB-Comm] Per-key setup time is basically nonexistent. There are a lot of constructions out there that want to do multiplication in GF(2^128) as a basic operation. That turns out to be less than totally straightforward, though. On newer intel chips, you've got a "multiply without carry" instruction that can supposedly let you get to around 2 cycles per byte. On other platforms, you're reduced to worse trickery to try to get good performance without timing side-channels, for an amount of trickery dependent on what operation you're trying to do exactly. The easiest GF(2^128) operation to implement safely and quickly is multiplication by a known compile-time value. (It's easy enough that even I could do it.) Next easiest is multiply a large number of values by the same run-time-fixed value -- you do precomputation on the value in order to generate some tables. (The scary, fast variants use big tables; the still-a-little-scary variants use 256-byte tables, and get performance on high-end Intel boxes around 7-10 cycles per byte when doing GCM.) Full-on multiplication of two arbitrary GF(2^128) values is slowest still. As a further wrinkle with GF(2^128), OpenSSL doesn't seem to actually expose its "multiply in GF(2^128)" functions as far as I can tell: we would need to snarf such code from elsewhere. Oh! ARMv8 has an optional crypto instruction set that supports AES, SHA256, and GF(2^128) multiplication [ARMv8]. If it looks like most of the ARMs we care about are going to get it, that could factor into our planning. IV. HOW MUCH DOES PERFORMANCE MATTER HERE ANYWAY? A fine question. The right place too look would IMO be at profiles on a busy non-exit non-AESNI server, to see how much time is spent in AES there. Make sure you look at all the AES variants, since it's not uncommon to see more than one used at once. A ridiculously large amount of that time will be in bn_sqr4x_mont and its unindicted co-conspirators , but expect this to get cut a great deal when we move to ECC for TLS DHE and for circuit extension. So if we're willing to make a lot of assumptions, then you can figure out a worst-case performance impact like this. Take the fraction of the time spent in bn_and_friends and remove them from the profile. (Assume that circuit creation dominates over TLS renegotiation because hey why not.) Then assume that the AES calls used for relay crypto's counter mode turn into whatever new relay encryption thing we're proposing. See how much that change costs Tor's performance overall. V. ACKNOWLEDGMENTS Thanks to everybody who's schooled me about this stuff, especially Daniel J. Bernstein, Ian Goldberg, and Robert Ransom. Assume that the good ideas are here due to their patience and that the bad ideas are here due to my slowness on the uptake. Thanks to Susan Born for a much-needed copy-edit. Assume that every correctly structured sentence is one she fixed, and that the bad ones I messed up after her editing. VI. References [Prop202] https://lists.torproject.org/pipermail/tor-dev/2012-June/003649.html [Ferguson] Niels Ferguson, "Authentication weaknesses in GCM", 2005. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Fergu… [DJB-Timing] Daniel J. Bernstein, "Cache-timing attacks on AES", 2004. http://cr.yp.to/papers.html#cachetiming [DJB-Comm] Daniel J. Bernstein, personal communication [Poly1305-Trunc] http://osdir.com/ml/encryption.poly1305/2005-09/msg00007.html [ARMv8] "ARMv8 Instruction Set Overview", 2011, http://board.flatassembler.net/download.php?id=5698 [Bear-Lion] Ross Anderson and Eli Biham. "Two Practical and Provably Secure Block Ciphers: BEAR and LION". http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf [Efficient-Tweakable] Palash Sarkar, "Efficient Tweakable Enciphering Schemes from (Block-Wise) Universal Hash Functions". 2008. http://eprint.iacr.org/2008/004.pdf [IGE] Gligor and Donescu, "On Message Integrity in Symmetric Encryption" has the good IGE analysis: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ige/ige-… The original IGE proposal was by Carl Campell in an old NIST publication that I can't find online; the paper above has a reference for it if you want to chase it more. [ABC] Lars R. Knudsen, "Block Cipher Chaining Modes of Operation". http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/abc/abc-… [HCTR] Peng Wang, Dengguo Feng, and Wenling Wu. "HCTR: A variable-input-length enciphering mode." 2005. http://delta.cs.cinvestav.mx/~debrup/hctr.pdf [HCH] Debrup Chakraborty and Palash Sarkar. "HCH: A new tweakable enciphering scheme using the hash-encrypt-hash approach." http://biblioteca.cinvestav.mx/indicadores/texto_completo/cinvestav/2006/13… [TET] Shai Halevi. "Invertible universal hashing and the TET encryption mode." 2007. http://www.iacr.org/archive/crypto2007/46220405/46220405.pdf

5 10