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

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

19 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 19 Dec '12

19 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

Opening new SOCKS to client plugin for new circuit?
by David Fifield 15 Dec '12

15 Dec '12

I noticed a change in behavior in cb62a0b69a7d67b427224ca4c3075b49853a3a1f or thereabouts. tor opens a new SOCKS connection to a client transport plugin while bootstrapping at 50% (if descriptors are not cached) or at 85% (if descriptors are not cached). The upshot is that the flash proxy transport, for which new connections are not free, needs two connected browser proxies in order to bootstrap. Earlier revisions permit bootstrapping and circuit creation with just one connection to the proxy. I start an external proxy thus: $ ./flashproxy-client --external --unsafe-logging 2012-12-03 09:02:05 Listening remote on 0.0.0.0:9000. 2012-12-03 09:02:05 Listening remote on [::]:9000. 2012-12-03 09:02:05 Listening local on 127.0.0.1:9001. 2012-12-03 09:02:05 Listening local on [::1]:9001. The "remote" listener is waiting for WebSocket connections from a browser. The "local" listener is waiting for SOCKS connections from Tor. Then I start Tor to use the proxy: $ ./src/or/tor ClientTransportPlugin "websocket socks4 127.0.0.1:9001" UseBridges 1 Bridge "websocket 0.0.1.0:1" LearnCircuitBuildTimeout 0 CircuitBuildTimeout 60 Log "info stderr" ... Dec 03 09:02:13.000 [notice] Bootstrapped 10%: Finishing handshake with directory server. flashproxy-client notices Tor's pending SOCKS connection: 2012-12-03 09:02:13 Local connection from 127.0.0.1:55421. 2012-12-03 09:02:13 SOCKS request from 127.0.0.1:55421. 2012-12-03 09:02:13 Got SOCKS request for 0.0.1.0:1. 2012-12-03 09:02:13 locals (1): [u'127.0.0.1:55421'] 2012-12-03 09:02:13 remotes (0): [] 2012-12-03 09:02:13 Data from unlinked local 127.0.0.1:55421 (217 bytes). 2012-12-03 09:02:13 locals (1): [u'127.0.0.1:55421'] 2012-12-03 09:02:13 remotes (0): [] Then I open a browser to make a single WebSocket connection which will appear as one of the pluggable transport's "remotes". http://crypto.stanford.edu/flashproxy/embed.html?debug=1&client=127.0.0.1:9… flashproxy-client sees the new remote and starts proxying data. 2012-12-03 09:02:17 Remote connection from 127.0.0.1:51321. 2012-12-03 09:02:17 Data from WebSocket-pending 127.0.0.1:51321. 2012-12-03 09:02:17 locals (1): [u'127.0.0.1:55421'] 2012-12-03 09:02:17 remotes (1): [u'127.0.0.1:51321'] 2012-12-03 09:02:17 Linking 127.0.0.1:55421 and 127.0.0.1:51321. Now bootstrapping continues (over the WebSocket channel) until reaching 85%, and then it says "connections all too old, or too non-canonical" and makes a new SOCKS request: Dec 03 09:02:18.000 [notice] new bridge descriptor '3VXRyxz67OeRoqHn' (fresh): $7C03D29CA58BE8EED5F483F31A2DEDF6FD7CC444~3VXRyxz67OeRoqHn at 0.0.1.0 Dec 03 09:02:18.000 [notice] We now have enough directory information to build circuits. Dec 03 09:02:18.000 [notice] Bootstrapped 80%: Connecting to the Tor network. ... Dec 03 09:02:18.000 [info] circuit_handle_first_hop(): Next router is [scrubbed]: Connections all too old, or too non-canonical. Launching a new one. Dec 03 09:02:18.000 [notice] Bootstrapped 85%: Finishing handshake with first hop. Dec 03 09:02:18.000 [info] connection_read_proxy_handshake(): Proxy Client: connection to 0.0.1.0:1 successful flashproxy-client sees the SOCKS request, but because there are no more browser connections forthcoming, everything stalls at this point. 2012-12-03 09:02:18 Local connection from 127.0.0.1:55427. 2012-12-03 09:02:18 SOCKS request from 127.0.0.1:55427. 2012-12-03 09:02:18 Got SOCKS request for 0.0.1.0:1. 2012-12-03 09:02:18 locals (2): [u'127.0.0.1:55421', u'127.0.0.1:55427'] 2012-12-03 09:02:18 remotes (1): [u'127.0.0.1:51321'] 2012-12-03 09:02:18 Data from unlinked local 127.0.0.1:55427 (231 bytes). I've verified this failure to bootstrap with recent 190c1d4981e5751aabd3d894095851c830f1d570. After bisecting, I think the last commit with the old behavior (boostrapped 100%) was 751b3aabb5ab88fca16834e559a8d9835831b05f. There were some compile errors during bisecting so I couldn't narrow it to a specific revision; git reports There are only 'skip'ped commits left to test. The first bad commit could be any of: 35924435d22c2469ecbe06156c8069a928859d63 e136f7ccb4e671e33b6c92a48df819082291f5c1 4768c0efe3e9471cc367c3740d1a4ba0ab79626c 6cce6241dd4405f6cf21057f9913e07633cf18bb 519c971f6a3b89f1e81cda3c0290d4d943ec0d78 77dac97354974e8a819d8e35ad4e7a76199999b4 32337502f11e6c84e4db8591f5f81c4fc6d1da58 8b14db9628f0e8982e894034e86c8efdd78cff32 15303c32ec9d84aff8de5ed9df28e779c36c6e5c 28f108bcceab59fcf9f27e33065f64bfdb0f159a 7f952da55334d3a3693d1c6e8531fd96730265db f0f87cb68a22feaf552a18b521d3313d843f8793 838743654c1bed2bfe22789ff53a1993c005f176 9ad7ba9f2267a9ee34fafda9356f1fa86633f00f cb62a0b69a7d67b427224ca4c3075b49853a3a1f We cannot bisect more! Based on the log, cb62a0b69a7d67b427224ca4c3075b49853a3a1f seems a likely cause of the change: "Use channel_is_bad_for_new_circs(), connection_or_get_num_circs() in main.c". I thought I would be able to reproduce this with another transport or with a simple SOCKS proxy, showing two connections where there used to be one, but I can't. I see two connections even with the old code. For example with an ssh SOCKS proxy (ssh -v -D 9001 -N localhost): debug1: Connection to port 9001 forwarding to socks port 0 requested. debug1: channel 2: new [dynamic-tcpip] debug1: Connection to port 9001 forwarding to socks port 0 requested. debug1: channel 3: new [dynamic-tcpip] I guess that the difference is that previously, the second connection happens after bootstrapping is complete, while now it happens at 85%. (That is only a guess, I haven't verified it.) David Fifield

2 2

Stem code review 2012-12-10
by Sean Robinson 15 Dec '12

15 Dec '12

Stem devs, This is a review of recent commits to Stem. It begins where my last review ended[0] and finishes at the "Adding a close_stream..." merge. The pydoc changes to Controller.extend_circuit are good additions. I do not understand much of the context for changes regarding network status docs, exit policy, address type, etc. But, the code appears to do what the comments claim it should do (e.g. lazy loading address info). Take that evaluation with a grain of salt. As to re-attaching event listeners[1], I agree that putting a specialized hook into BaseController.msg seems bad. I have an alternate idea[2] that puts the re-attachment in an authenticate method. I am not proposing this as the solution, but I hope this sparks the idea for another way to handle re-attachment. I think the 'as' import keyword[3] is mainly for shortening long names and easily avoiding namespace collision. For example: >>> import pkg.reallylongmodulename as rlmn and >>> import socket >>> import niftysocket.socket as nsocket [0]: https://lists.torproject.org/pipermail/tor-dev/2012-December/004240.html [1]: https://gitweb.torproject.org/stem.git/commit/885a294646703a537c37cd2a5ac9a… [2]: https://gitorious.org/stem-robinson/stem-robinson/commits/exp-reattach-list… [3]: https://gitweb.torproject.org/stem.git/commit/3da47d3b9d6d1ae5c6b2013a4247c… [4]: this footnote intentionally left blank -- Sean Robinson

2 1

Flashproxy alpha bundles
by Alexandre 15 Dec '12

15 Dec '12

Hello everybody, We now have some flashproxy Tor Browser Bundles ready. These are alpha bundles, made by adding our files to the existing obfsproxy bundle. We would appreciate some testing and feedback. You can get the bundles here: Windows: https://people.torproject.org/~dcf/flashproxy/tor-flashproxy-browser-2.4.6-… https://people.torproject.org/~dcf/flashproxy/tor-flashproxy-browser-2.4.6-… OSX: https://people.torproject.org/~dcf/flashproxy/TorBrowser-FlashProxy-2.4.6-a… https://people.torproject.org/~dcf/flashproxy/TorBrowser-FlashProxy-2.4.6-a… 32-bit GNU/Linux: https://people.torproject.org/~dcf/flashproxy/tor-flashproxy-browser-gnu-li… https://people.torproject.org/~dcf/flashproxy/tor-flashproxy-browser-gnu-li… 64-bit GNU/Linux: https://people.torproject.org/~dcf/flashproxy/tor-flashproxy-browser-gnu-li… https://people.torproject.org/~dcf/flashproxy/tor-flashproxy-browser-gnu-li… To verify the signatures you will need David Fifield's public key. You can get it at: http://bamsoftware.com/david/david.asc or by fetching key 0x6BC758CBC11F6276 from: x-hkp://pool.sks-keyservers.net If your machine is behind a NAT device, you will need to configure port forwarding. The client listens for incoming WebSocket connections on port 9000 by default. If you want to forward a different port, you will need to edit your torrc. Find this line, ClientTransportPlugin websocket exec flashproxy-client --register :0 :9000 and change 9000 to the port you have chosen to forward. Once you have configured port forwarding you should be able to start the Browser Bundle as you normally would. Some specific things we would like feedback on are: - Is configuring port forwarding insurmountable for you? - If it didn't work, was it at least clear what was wrong? What was the output in the Vidalia log? - Were you able to use this as your main Tor process for a day? - Was it ever obvious to you that you had switched to another proxy (this would have broken existing circuits)? We have a wiki page setup for usability discussions at: https://trac.torproject.org/projects/tor/wiki/FlashProxyUsability Feel free to edit it. You can also leave comments on this trac ticket: https://trac.torproject.org/projects/tor/ticket/7425 Please send feedback, bug reports, etc. to the tor-dev list, or to dcf(a)torproject.org. Thanks. Alex

5 13

Proposal 216 (ntor) redux
by Nick Mathewson 14 Dec '12

14 Dec '12

Here's a slightly updated version of the ntor proposal, as changed while I was doing the implementation (see [A] for more information on that). For a diff between the old version and the new one, see [B]. The interesting changes were: * To specify that the key expansion uses HKDF from RFC5869. (This is the standardized version of originally recommended key expansion approach.) * To specify that the length of a node ID is ID_LENGTH bytes, not H_LENGTH. * To make the t_key tweak value not be a prefix of the m_expand value. This is probably cosmetic. * To specify a way for embedding these handshakes in EXTEND/EXTENDED/CREATE/CREATED cells so that they can be used to extend from a server that doesn't know about proposal 200. * To specify checking EXP() outputs for the point at infinity rather than checking inputs for group membership. I am not convinced this is necessary [C], but Ian Goldberg thought it was a good idea. The ntor branch has a reference implementation of the handshake in src/test/ntor_ref.py [D] which has been verified to interoperate with the C implementation. [A] https://trac.torproject.org/projects/tor/ticket/7202 [B] https://gitweb.torproject.org/torspec.git/blobdiff/08b4c89058e7704f9cdb1e11… [C] If a client generates a bad public key, it will at worst get no security. If a server generates a bad public key, it will at worst provide no security--but a server that wants to provide no security can already leak its outputs. The case to worry about would be if an MITM attacker replaced the X value or the Y value when communicating between the server and the client. But I believe that the inclusion of X and Y in the auth_input and secret_input steps prevents such an MITM attacker from successfully convincing the client that the handshake was successful. Still, "belt and suspenders." [D] https://gitweb.torproject.org/nickm/tor.git/blob_plain/ntor:/src/test/ntor_… ==== Filename: 216-ntor-handshake.txt Title: Improved circuit-creation key exchange Author: Nick Mathewson Created: 11-May-2011 Status: Open Summary: This is an attempt to translate the proposed circuit handshake from "Anonymity and one-way authentication in key-exchange protocols" by Goldberg, Stebila, and Ustaoglu, into a Tor proposal format. It assumes that proposal 200 is implemented, to provide an extended CREATE cell format that can indicate what type of handshake is in use. Notation: Let a|b be the concatenation of a with b. Let H(x,t) be a tweakable hash function of output width H_LENGTH bytes. Let t_mac, t_key, and t_verify be a set of arbitrarily-chosen tweaks for the hash function. Let EXP(a,b) be a^b in some appropriate group G where the appropriate DH parameters hold. Let's say elements of this group, when represented as byte strings, are all G_LENGTH bytes long. Let's say we are using a generator g for this group. Let a,A=KEYGEN() yield a new private-public keypair in G, where a is the secret key and A = EXP(g,a). If additional checks are needed to insure a valid keypair, they should be performed. Let PROTOID be a string designating this variant of the protocol. Let KEYID be a collision-resistant (but not necessarily preimage-resistant) hash function on members of G, of output length H_LENGTH bytes. Let each node have a unique identifier, ID_LENGTH bytes in length. Instantiation: Let's call this PROTOID "ntor-curve25519-sha256-1" (We might want to make this shorter if it turns out to save us a block of hashing somewhere.) Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32. Set t_mac == PROTOID | ":mac" t_key == PROTOID | ":key_extract" t_verify == PROTOID | ":verify" Set EXP(a,b) == curve25519(.,b,a), and g == 9 . Let KEYGEN() do the appropriate manipulations when generating the secret key (clearing the low bits, twiddling the high bits). Set KEYID(B) == B. (We don't need to use a hash function here, since our keys are already very short. It is trivially collision-resistant, since KEYID(A)==KEYID(B) iff A==B.) Protocol: Take a router with identity key digest ID. As setup, the router generates a secret key b, and a public onion key B with b, B = KEYGEN(). The router publishes B in its server descriptor. To send a create cell, the client generates a keypair x,X = KEYGEN(), and sends a CREATE cell with contents: NODEID: ID -- ID_LENGTH bytes KEYID: KEYID(B) -- H_LENGTH bytes CLIENT_PK: X -- G_LENGTH bytes The server generates a keypair of y,Y = KEYGEN(), and computes secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID KEY_SEED = H(secret_input, t_key) verify = H(secret_input, t_verify) auth_input = verify | ID | B | Y | X | PROTOID | "Server" The server sends a CREATED cell containing: SERVER_PK: Y -- G_LENGTH bytes AUTH: H(auth_input, t_mac) -- H_LENGTH byets The client then checks Y is in G^* [see NOTE below], and computes secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID KEY_SEED = H(secret_input, t_key) verify = H(secret_input, t_verify) auth_input = verify | ID | B | Y | X | PROTOID | "Server" The client verifies that AUTH == H(auth_input, t_mac). Both parties check that none of the EXP() operations produced the point at infinity. [NOTE: This is an adequate replacement for checking Y for group membership, if the group is curve25519.] Both parties now have a shared value for KEY_SEED. They expand this into the keys needed for the Tor relay protocol. Key expansion: Currently, the key expansion formula used by Tor here is K = SHA(K0 | [00]) | SHA(K0 | [01]) | SHA(K0 | [02]) | ... where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions. Instead, let's have it be HKDF-SHA256 as defined in RFC5869: K = K_1 | K_2 | K_3 | ... Where K_1 = H(m_expand | INT8(1) , KEY_SEED ) and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED ) and m_expand is an arbitrarily chosen value, and INT8(i) is a octet with the value "i". Ian says this is due to a construction from Krawczyk at http://eprint.iacr.org/2010/264 . Let m_expand be PROTOID | ":key_expand" In RFC5869's vocabulary, this is HKDF-SHA256 with info == m_expand, salt == t_key, and IKM == secret_input. Performance notes: In Tor's current circuit creation handshake, the client does: One RSA public-key encryption A full DH handshake in Z_p A short AES encryption Five SHA1s for key expansion And the server does: One RSA private-key decryption A full DH handshake in Z_p A short AES decryption Five SHA1s for key expansion While in the revised handshake, the client does: A full DH handshake A public-half of a DH handshake 3 H operations for the handshake 3 H operations for the key expansion and the server does: A full DH handshake A private-half of a DH handshake 3 H operations for the handshake 3 H operations for the key expansion Integrating with the rest of Tor: Add a new optional entry to router descriptors and microdescriptors: "ntor-onion-key" SP Base64Key NL where Base64Key is a base-64 encoded 32-byte value, with padding omitted. Add a new consensus method to tell servers to copy "ntor-onion-key" entries to from router descriptors to microdescriptors. In microdescriptors, "ntor-onion-key" can go right after the "onion-key" line. Add a "UseNTorHandshake" configuration option and a corresponding consensus parameter to control whether clients use the ntor handshake. If the configuration option is "auto", clients should obey the consensus parameter. Have the configuration default be "auto" and the consensus value initially be "0". Reserve the handshake type [00 02] for this handshake in CREATE2 and EXTEND2 cells. Specify that this handshake type can be used in EXTEND/EXTENDED/ CREATE/CREATED cells as follows: instead of a 190-byte TAP onionskin, send the 16-byte string "ntorNTORntorNTOR", followed by the client's ntor message. Instead of a 148-byte TAP response, send the server's ntor response. (We need this so that a client can extend from an 0.2.3 server, which doesn't know about CREATE2/CREATED2/EXTEND/EXTENDED2.) Test vectors for HKDF-SHA256: These are some test vectors for HKDF-SHA256 using the values for M_EXPAND and T_KEY above, taking 100 bytes of key material. INPUT: "" (The empty string) OUTPUT: d3490ed48b12a48f9547861583573fe3f19aafe3 f81dc7fc75eeed96d741b3290f941576c1f9f0b2 d463d1ec7ab2c6bf71cdd7f826c6298c00dbfe67 11635d7005f0269493edf6046cc7e7dcf6abe0d2 0c77cf363e8ffe358927817a3d3e73712cee28d8 INPUT: "Tor" (546f72) OUTPUT: 5521492a85139a8d9107a2d5c0d9c91610d0f959 89975ebee6c02a4f8d622a6cfdf9b7c7edd3832e 2760ded1eac309b76f8d66c4a3c4d6225429b3a0 16e3c3d45911152fc87bc2de9630c3961be9fdb9 f93197ea8e5977180801926d3321fa21513e59ac INPUT: "AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT" (414e20414c41524d494e47204954454d20544f2046494e44204f4e20 594f5552204352454449542d524154494e472053544154454d454e54) OUTPUT: a2aa9b50da7e481d30463adb8f233ff06e9571a0 ca6ab6df0fb206fa34e5bc78d063fc291501beec 53b36e5a0e434561200c5f8bd13e0f88b3459600 b4dc21d69363e2895321c06184879d94b18f0784 11be70b767c7fc40679a9440a0c95ea83a23efbf

3 2

Re: [tor-dev] Flashproxy alpha bundles
by Veggie Monster 14 Dec '12

14 Dec '12

> connections, so browser implementations don't let you do it. > So the user has to be able to accept connections on his end. Apparently Chrome Canary lets you do that: http://iceddev.github.com/blog/2012/11/05/node-js-in-chrome/ Vmon

2 1

Re: [tor-dev] RFC on obfs3 pluggable transport
by Veggie Monster 13 Dec '12

13 Dec '12

Hey Ian, > [There's no such thing as a "bi-quadratic residue" in this setting; all > quadratic residues in this group have one square root which is itself a > quadratic residue and one which is not.] I guess you are right. Because (q,2) = 1, all quadratic residues are bi-quadratic residues, hence no meaningful distinction: [vmon@telly biquad-attack]$ sage mount_attack.sage Key oracle biquadratic residue ratio: 0.500503540039062 Random oracle biquadratic residue ratio: 0.496414184570312 [https://github.com/vmon/biquad-attack] Thanks, Vmon

1 0

Re: [tor-dev] RFC on obfs3 pluggable transport
by vmonmoonshine＠gmail.com 12 Dec '12

12 Dec '12

>The only issue with your trick, is that I'm not looking forward >implementing a custom DH key exchange in Python (especially the DH >parameter generation and public key validation parts). >From the conversation of Zack with Steven at the breakfast table at Hotel Cellai, I'm pretty sure that Stegotorus is using DH based on elliptic curve and its twist protocol. So you can find an implementation of it there. Though I haven't looked at the crypto part of the code myself. Also could you please refer me to the reference that proves that X or p-X is uniformly random. It seems to me that you are taking a quadratic residue to an even power, so you always get a bi-quadratic residue for X. Then if I'm the distinguisher who knows the public group, and I see that the bi-quadratic residues appears 1/2 times instead of 1/4 of the times then I can smell that something going on. Take care, Vmon

2 1

Stem code review 2012-12-04
by Sean Robinson 08 Dec '12

08 Dec '12

Stem devs, I did a code review of recent Stem commits ("Tor event handling" merge (commit 42872dd08e81d6b3) through "Checking for None by identity" (commit 69f72efc9367092c)). My comments and questions follow. I will skip my own contributions (they were great 8-) in that range, as I am biased. Event._log_if_unrecognized() is a good idea that vastly improves the readability of Event subclasses and reduces code duplication. Regarding commit fb0aec5d95e9d2e6 "tidying up boilerplate": 1) I do not like the new _get_event() with assert_class and assert_content. There are transformations and tests and returned values all within what is a mock object builder, meaning it works via side-effect. This could be surprising to test writers. 2) I vote to keep "self.assertTrue(isinstance(event, stem.response.events.StatusEvent))" style tests after producing the event. The quoted key/value mapping is more readable, now. Good work. Why not look for quoted positional args before non-quoted positional args? Why not do just like kwarg handling? Why restrict SignalEvents to expected_signals when control-spec.txt allows more? This may mean changes later to add support for things the protocol already claims to support. I set up coverage.py for another project and I wondered if it would work with Stem. So, I ran "coverage run --parallel-mode --branch --omit="test*" ./run_tests.py -u -i -t RUN_NONE" in the stem directory. The results are 66% - 100% coverage per module. Another impressive accomplishment. And this is only running a subset of the possible tests. -- Sean Robinson

2 3