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

Proposal 247 (Hidden Service Vanguards) Overhaul
by Mike Perry 09 Jun '17

09 Jun '17

I spent some time trying to clean up proposal 247 based on everyone's comments, as well as based on my own thoughts. Please have a look if you commented on the original proposal, and complain if I've not taken your thoughts into account. (Aaron: In particular, I made several tradeoffs in favor of performance and DoS resistance that may be at odds with some of your suggestions, but I think the end result is still OK after looking into the Sybil rates and thinking about the adversary model in more detail. You may disagree). I've attached my updated version of the proposal inline in this mail, but the canonical updated proposal is in my remote at: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/247… Here's a summary of the changes (which are also listed in Git): * Try to make a coherent threat model and specify its assumptions * Fold in my comments about using disjoint sets ("buckets") for the third level guard. * Make the parameter discussion subsection its own section, and include tables with far more detail for the Sybil success rates. * Put the rotation period in a separate subsection from the number of guards * Switch to using min(X,X) and max(X,X) for the distribution for the second and third layer guard lifespans, respectively. Add a subsection describing this distribution (3.2.3) * Changed the default parameters based on these tables, and based on my own intuition about Tor's performance properties. * Move the load balancing, torrc, and other performance considerations to their own section (Section 5). * Move "3.2. Distinguishing new HS circuits from normal HS circuits" to section 4.1. * Fold in some of "3.3. Circuit nodes can now be linked to specific hidden services" into 4.1. Some of it I just removed, though, because I did not find it credible. * Added Roger's concerns about guard linkability to Section 4.2. * Added a denial of service subsection to Section 4.3. ================================ Filename: 247-hs-guard-discovery.txt Title: Defending Against Guard Discovery Attacks using Vanguards Author: George Kadianakis Created: 2015-07-10 Status: Draft 0. Motivation A guard discovery attack allow attackers to determine the guard node of a Tor client. The hidden service rendezvous protocol provides an attack vector for a guard discovery attack since anyone can force an HS to construct a 3-hop circuit to a relay (#9001). Following the guard discovery attack with a compromise and/or coercion of the guard node can lead to the deanonymization of a hidden service. 1. Overview This document tries to make the above guard discovery + compromise attack harder to launch. It introduces an optional configuration option which makes the hidden service also pin the second and third hops of its circuits for a longer duration. With this new path selection, we force the adversary to perform a Sybil attack and two compromise attacks before succeeding. This is an improvement over the current state where the Sybil attack is trivial to pull off, and only a single compromise attack is required. With this new path selection, an attacker is forced to do a one or more node compromise attacks before learning the guard node of a hidden service. This increases the uncertainty of the attacker, since compromise attacks are costly and potentially detectable, so an attacker will have to think twice before beginning a chain of node compromise attacks that he might not be able to complete. 1.1. Visuals Here is how a hidden service rendezvous circuit currently looks like: -> middle_1 -> middle_A -> middle_2 -> middle_B -> middle_3 -> middle_C -> middle_4 -> middle_D HS -> guard -> middle_5 -> middle_E -> Rendezvous Point -> middle_6 -> middle_F -> middle_7 -> middle_G -> middle_8 -> middle_H -> ... -> ... -> middle_n -> middle_n this proposal pins the two middles nodes to a much more restricted set, as follows: -> guard_3A_A -> guard_2_A -> guard_3A_B -> guard_3A_C -> Rendezvous Point HS -> guard_1 -> guard_3B_D -> guard_2_B -> guard_3B_E -> guard_3B_F -> Rendezvous Point Note that the third level guards are partitioned into buckets such that they are only used with one specific second-level guard. In this way, we ensure that even if an adversary is able to execute a Sybil attack against the third layer, they only get to learn one of the second-layer Guards, and not all of them. This prevents the adversary from gaining the ability to take their pick of the weakest of the second-level guards for further attack. 2. Design This feature requires the HiddenServiceGuardDiscovery torrc option to be enabled. When a hidden service picks its guard nodes, it also picks two additional sets of middle nodes `second_guard_set` and `third_guard_set` of size NUM_SECOND_GUARDS and NUM_THIRD_GUARDS respectively for each hidden service. These sets are unique to each hidden service created by a single Tor client, and must be kept separate and distinct. When a hidden service needs to establish a circuit to an HSDir, introduction point or a rendezvous point, it uses nodes from `second_guard_set` as the second hop of the circuit and nodes from that second hop's corresponding `third_guard_set` as third hops of the circuit. A hidden service rotates nodes from the 'second_guard_set' at a random time between MIN_SECOND_GUARD_LIFETIME hours and MAX_SECOND_GUARD_LIFETIME hours. A hidden service rotates nodes from the 'third_guard_set' at a random time between MIN_THIRD_GUARD_LIFETIME and MAX_THIRD_GUARD_LIFETIME hours. These extra guard nodes should be picked with the same path selection procedure that is used for regular middle nodes (though see Section 5.1 for performance reasons to restrict this slightly). Each node's rotation time is tracked independently, to avoid disclosing the rotation times of the primary and second-level guards. XXX how should proposal 241 ("Resisting guard-turnover attacks") be applied here? 2.1. Security parameters We set NUM_SECOND_GUARDS to 4 nodes and NUM_THIRD_GUARDS to 16 nodes (ie four sets of four). XXX: 3 and 12 might be another option here, in which case our rotation period for the second guard position can be reduced to 15 days. We set MIN_SECOND_GUARD_LIFETIME to 1 day, and MAX_SECOND_GUARD_LIFETIME to 33 days, for an average rotation rate of ~11 days, using the min(X,X) distribution specified in Section 3.2.2. We set MIN_THIRD_GUARD_LIFETIME to 1 hour, and MAX_THIRD_GUARD_LIFETIME to 18 hours, for an average rotation rate of ~12 hours, using the max(X,X) distribution specified in Section 3.2.2. XXX make all the above consensus parameters? Yes. Very yes, especially if we decide to change the primary guard lifespan. See Section 3 for more analysis on these constants. 3. Rationale and Security Parameter Selection 3.1. Threat model, Assumptions, and Goals Consider an adversary with the following powers: - Can launch a Sybil guard discovery attack against any node of a rendezvous circuit. The slower the rotation period of the node, the longer the attack takes. Similarly, the higher the percentage of the network is compromised, the faster the attack runs. - Can compromise any node on the network, but this compromise takes time and potentially even coercive action, and also carries risk of discovery. We also make the following assumptions about the types of attacks: 1. A Sybil attack is noisy. It will require either large amounts of traffic, multiple test circuits, or both. 2. A Sybil attack against the second or first layer Guards will be more noisy than a Sybil attack against the third layer guard, since the second and first layer Sybil attack requires a timing side channel in order to determine success, where as the Sybil success is almost immediately obvious to third layer guard, since it will now be returned as a rend point for circuits for the hidden service in question. 3. As soon as the adversary is confident they have won the Sybil attack, an even more aggressive circuit building attack will allow them to determine the next node very fast (an hour or less). 4. The adversary is strongly disincentivized from compromising nodes that may prove useless, as node compromise is even more risky for the adversary than a Sybil attack in terms of being noticed. Given this threat model, our security parameters were selected so that the first two layers of guards should be hard to attack using a Sybil guard discovery attack and hence require a node compromise attack. Ideally, we want the node compromise attacks to carry a non-negligible probability of being useless to the adversary by the time they complete. On the other hand, the outermost layer of guards should rotate fast enough to _require_ a Sybil attack. 3.2. Parameter Tuning 3.2.1. Sybil rotation counts for a given number of Guards The probability of Sybil success for Guard discovery can be modeled as the probability of choosing 1 or more malicious middle nodes for a sensitive circuit over some period of time. P(At least 1 bad middle) = 1 - P(All Good Middles) = 1 - P(One Good middle)^(num_middles) = 1 - (1 - c/n)^(num_middles) c/n is the adversary compromise percentage In the case of Vanguards, num_middles is the number of Guards you rotate through in a given time period. This is a function of the number of vanguards in that position (v), as well as the number of rotations (r). P(At least one bad middle) = 1 - (1 - c/n)^(v*r) Here's detailed tables in terms of the number of rotations required for a given Sybil success rate for certain number of guards. 1.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 11 6 4 3 3 2 2 2 2 1 1 15% 17 9 6 5 4 3 3 2 2 2 2 25% 29 15 10 8 6 5 4 4 3 3 2 50% 69 35 23 18 14 12 9 8 7 6 5 60% 92 46 31 23 19 16 12 11 10 8 6 75% 138 69 46 35 28 23 18 16 14 12 9 85% 189 95 63 48 38 32 24 21 19 16 12 90% 230 115 77 58 46 39 29 26 23 20 15 95% 299 150 100 75 60 50 38 34 30 25 19 99% 459 230 153 115 92 77 58 51 46 39 29 5.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 3 2 1 1 1 1 1 1 1 1 1 15% 4 2 2 1 1 1 1 1 1 1 1 25% 6 3 2 2 2 1 1 1 1 1 1 50% 14 7 5 4 3 3 2 2 2 2 1 60% 18 9 6 5 4 3 3 2 2 2 2 75% 28 14 10 7 6 5 4 4 3 3 2 85% 37 19 13 10 8 7 5 5 4 4 3 90% 45 23 15 12 9 8 6 5 5 4 3 95% 59 30 20 15 12 10 8 7 6 5 4 99% 90 45 30 23 18 15 12 10 9 8 6 10.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 2 1 1 1 1 1 1 1 1 1 1 15% 2 1 1 1 1 1 1 1 1 1 1 25% 3 2 1 1 1 1 1 1 1 1 1 50% 7 4 3 2 2 2 1 1 1 1 1 60% 9 5 3 3 2 2 2 1 1 1 1 75% 14 7 5 4 3 3 2 2 2 2 1 85% 19 10 7 5 4 4 3 3 2 2 2 90% 22 11 8 6 5 4 3 3 3 2 2 95% 29 15 10 8 6 5 4 4 3 3 2 99% 44 22 15 11 9 8 6 5 5 4 3 The rotation counts in these tables were generated with: def count_rotations(c, v, success): r = 0 while 1-math.pow((1-c), v*r) < success: r += 1 return r 3.2.2. Rotation Period As specified in Section 3.1, the primary driving force for the third layer selection was to ensure that these nodes rotate fast enough that it is not worth trying to compromise them, because it is unlikely for compromise to succeed and yield useful information before the nodes stop being used. For this reason we chose 1 to 18 hours, with a weighted distribution (Section 3.2.3) causing the expected average to be 12 hours. From the table in Section 3.2.1, it can be seen that this means that the Sybil attack will complete with near-certainty (99%) in 29*12 hours (14.5 days) for the 1% adversary, 3 days for the 5% adversary, and 1.5 days for the 10% adversary. Since rotation of each node happens independently, the distribution of when the adversary expects to win this Sybil attack in order to discover the next node up is uniform. This means that on average, the adversary should expect that half of the rotation period of the next node is already over by the time that they win the Sybil. With this fact, we choose our range and distribution for the second layer rotation to be short enough to cause the adversary to risk compromising nodes that are useless, yet long enough to require a Sybil attack to be noticeable in terms of client activity. For this reason, we choose a minimum second-layer guard lifetime of 1 day, since this gives the adversary a minimum expected value of 12 hours for during which they can compromise a guard before it might be rotated. If the total expected rotation rate is 11 days, then the adversary can expect overall to have 5.5 days remaining after completing their Sybil attack before a second-layer guard rotates away. 3.2.3. Rotation distribution In order to skew the distribution of the third layer guard towards higher values, we use max(X,X) for the distribution, where X is a random variable that takes on values from the uniform distribution. In order to skew the distribution of the second layer guard towards low values (to increase the risk of compromising useless nodes) we skew the distribution towards lower values, using min(X,X). Here's a table of expectation (arithmetic means) for relevant ranges of X (sampled from 0..N). The current choice for second-layer guards is noted with **, and the current choice for third-layer guards is noted with ***. Range Min(X,X) Max(X,X) 10 2.85 6.15 11 3.18 6.82 12 3.51 7.49 13 3.85 8.15 14 4.18 8.82 15 4.51 9.49 16 4.84 10.16 17 5.18 10.82*** 18 5.51 11.49 19 5.84 12.16 20 6.18 12.82 21 6.51 13.49 22 6.84 14.16 23 7.17 14.83 24 7.51 15.49 25 7.84 16.16 26 8.17 16.83 27 8.51 17.49 28 8.84 18.16 29 9.17 18.83 30 9.51 19.49 31 9.84 20.16 32 10.17** 20.83 33 10.51 21.49 34 10.84 22.16 35 11.17 22.83 36 11.50 23.50 37 11.84 24.16 38 12.17 24.83 39 12.50 25.50 4. Security concerns and mitigations 4.1. Mitigating fingerprinting of new HS circuits By pinning the middle nodes of rendezvous circuits, we make it easier for all hops of the circuit to detect that they are part of a special hidden service circuit with varying degrees of certainty. The Guard node is able to recognize a Vanguard client with a high degree of certainty because it will observe a client IP creating the overwhelming majority of its circuits to just a few middle nodes in any given 10-18 day time period. The middle nodes will be able to tell with a variable certainty that depends on both its traffic volume and upon the popularity of the service, because they will see a large number of circuits that tend to pick the same Guard and Exit. The final nodes will be able to tell with a similar level certainty that depends on their capacity and the service popularity, because they will see a lot of rend handshakes that all tend to have the same second hop. The most serious of these is the Guard fingerprinting issue. When proposal xxx-padding-negotiation is implemented, services that enable this feature should use those padding primitives to create fake circuits to random middle nodes that are not their guards, in an attempt to look more like a client. Additionally, if Tor Browser implements "virtual circuits" based on SOCKS username+password isolation in order to enforce the re-use of paths when SOCKS username+passwords are re-used, then the number of middle nodes in use during a typical user's browsing session will be proportional to the number of sites they are viewing at any one time. This is likely to be much lower than one new middle node every ten minutes, and for some users, may be close to the number of Vanguards we're considering. This same reasoning is also an argument for increasing the number of second-level guards beyond just two, as it will spread the hidden service's traffic over a wider set of middle nodes, making it both easier to cover, and behave closer to a client using SOCKS virtual circuit isolation. 4.2. Hidden service linkability Multiple hidden services on the same Tor instance should use separate second and third level guard sets, otherwise an adversary is trivially able to determine that the two hidden services are co-located by inspecting their current chosen rend point nodes. Unfortunately, if the adversary is still able to determine that two or more hidden services are run on the same Tor instance through some other means, then they are able to take advantage of this fact to execute a Sybil attack more effectively, since there will now be an extra set of guard nodes for each hidden service in use. For this reason, if Vanguards are enabled, and more than one hidden service is configured, the user should be advised to ensure that they do not accidentally leak that the two hidden services are from the same Tor instance. 4.3. Denial of service Since it will be fairly trivial for the adversary to enumerate the current set of rend nodes for a hidden service, denial of service becomes a serious risk for Vanguard users. For this reason, it is important to support a large number of third-level guards, to increase the amount of resources required to bring a hidden service offline by DoSing just a few Tor nodes. 5. Performance considerations The switch to a restricted set of nodes will very likely cause significant performance issues, especially for high-traffic hidden services. If any of the nodes they select happen to be temporarily overloaded, performance will suffer dramatically until the next rotation period. 5.1. Load Balancing Since the second and third level "guards" are chosen from the set of all nodes eligible for use in the "middle" hop (as per hidden services today), this proposal should not significantly affect the long-term load on various classes of the Tor network, and should not require any changes to either the node weight equations, or the bandwidth authorities. Unfortunately, transient load is another matter, as mentioned previously. It is very likely that this scheme will increase instances of transient overload at nodes selected by high-traffic hidden services. One option to reduce the impact of this transient overload is to restrict the set of middle nodes that we chose from to some percentage of the fastest middle-capable relays in the network. This may have some impact on load balancing, but since the total volume of hidden service traffic is low, it may be unlikely to matter. 5.2. Circuit build timeout The adaptive circuit build timeout mechanism in Tor is what corrects for instances of transient node overload right now. The timeout will naturally tend to select the current fastest and least-loaded paths even through this set of restricted routes, but it may fail to behave correctly if there are a very small set of nodes in each guard set, as it is based upon assumptions about the current path selection algorithm, and it may need to be tuned specifically for Vanguards, especially if the set of possible routes is small. 5.3. OnionBalance At first glance, it seems that this scheme makes multi-homed hidden services such as OnionBalance[1] even more important for high-traffic hidden services. Unfortunately, if it is equally damaging to the user for any of their multi-homed hidden service locations to be discovered, then OnionBalance is strictly equivalent to simply increasing the number of second-level guard nodes in use, because an active adversary can perform simultaneous Sybil attacks against all of the rend points offered by the multi-homed OnionBalance introduction points. 5.4. Default vs optional behavior We suggest this torrc option to be optional because it changes path selection in a way that may seriously impact hidden service performance, especially for high traffic services that happen to pick slow guard nodes. However, by having this setting be disabled by default, we make hidden services who use it stand out a lot. For this reason, we should in fact enable this feature globally, but only after we verify its viability for high-traffic hidden services, and ensure that it is free of second-order load balancing effects. Even after that point, until Single Onion Services are implemented, there will likely still be classes of very high traffic hidden services for whom some degree of location anonymity is desired, but for which performance is much more important than the benefit of Vanguards, so there should always remain a way to turn this option off. 6. Future directions Here are some more ideas for improvements that should be done sooner or later: - Maybe we should make the size and rotation period of secondary/third guard sets to be configurable by the user. - To make it harder for an adversary, a hidden service MAY extend the path length of its circuits by an additional static hop. This forces the adversary to use another coercion attack to walk the chain up to the hidden service. 7. Acknowledgments Thanks to Aaron Johnson, John Brooks, Mike Perry and everyone else who helped with this idea. 1. https://onionbalance.readthedocs.org/en/latest/design.html#overview -- Mike Perry

7 14

onion moshing
by David Stainton 25 Sep '16

25 Sep '16

I was inspired by onioncat to write a twisted python implementation. Onionvpn doesn't have as many features as onioncat. I've successfully tested that onionvpn and onioncat can talk to each other and play nice. Both onionvpn and onioncat implement a virtual public network. Anyone can send packets to you if they know your onion address or ipv6 address... however injection attacks are unlikely since the attacker cannot know the contents of your traffic without compromising the tor process managing the onion service. I've also tested with mosh; that is, you can use mosh which only works with ipv4 over an ipv4-to-ipv6 tunnel over onionvpn/onioncat. Like this: mosh-client -> udp/ipv4 -> ipv6 -> tun device -> tcp-to-tor -> onion service decodes ipv6 to tun device -> ipv6 -> udp/ipv4 -> mosh-server https://github.com/david415/onionvpn If an onionvpn/onioncat operator were to NAT the onion ipv6 traffic to the Internet then that host essentially becomes a special IPv6 exit node for the tor network. The same can be done for IPv4. Obviously operating such an exit node might be risky due to the potential for abuse... however don't you just love the idea of being about to use low-level network scanners over tor? I wonder if Open Observatory of Network Interference would be interested in this. david

4 3

adding smartcard support to Tor
by Razvan Dragomirescu 03 Jun '16

03 Jun '16

Hello, I am not sure if this has been discussed before or how hard it would be to implement, but I'm looking for a way to integrate a smartcard with Tor - essentially, I want to be able to host hidden service keys on the card. I'm trying to bind the hidden service to a hardware component (the smartcard) so that it can be securely hosted in a hostile environment as well as impossible to clone/move without physical access to the smartcard. I have Tor running on the USBArmory by InversePath ( http://inversepath.com/usbarmory.html ) and have a microSD form factor card made by Swissbit ( www.swissbit.com/products/security-products/overwiev/security-products-over… ) up and running on it. I am a JavaCard developer myself and I have developed embedded Linux firmwares before but I have never touched the Tor source. Is there anyone that is willing to take on a side project doing this? Would it be just a matter of configuring OpenSSL to use the card (I haven't tried that yet)? Thank you, Razvan -- Razvan Dragomirescu Chief Technology Officer Cayenne Graphics SRL

8 34

Quantum-safe Hybrid handshake for Tor
by Zhenfei Zhang 29 Apr '16

29 Apr '16

Hi list, This is a proposal to use quantum-safe hybrid handshake for Tor communications. Given NSA's recent announcement on moving towards quantum-safe cryptography, it would be nice to have a quantum-safe feature for Tor. The idea of the quantum-safe hybrid handshake is to combine both classical key exchange and a key encapsulation mechanism (KEM) instantiated by a quantum safe encryption algorithm, so that the combination gives both (classical) authentication and quantum safety. In a bit more details, the client and the server agrees on a classic pre-master secret, $c$, using the ntor protocol. In parallel, client generates a public/private key pair of the quantum-safe encryption algorithm, and send the public key to the server. The server picks a random string, $q$, encrypts it with the public key and send the ciphertext back to the client. The final secret is the output of KDF(c|q). This proposal defeats the harvest-then-decrypt attack with a minimum impact to the existing ntor protocol. An adversary needs to be able to break the quantum-safe encryption algorithm to learn q. On the other hand, if the quantum-safe encryption algorithm turns out to be not secure, the protocol is still as secure as ntor protocol. In other words, it will at least do no harm to the current security. In addition, this is a modular design that allows us to use any quantum-safe cryptographic primitives. As a proof of concept, we instantiated the protocol with NTRUEncrypt lattice-based crypto. We implemented the the protocol with NTRU parameters that gives 128 bits security. The code is available at https://github.com/NTRUOpenSourceProject/ntru-tor Please find the attachment for the request to change the feature. The proof of the protocol can be found at: https://eprint.iacr.org/2015/287.pdf Some known issue: 1. cell size. As far as we know, all quantum-safe encryption algorithms have large key and/or ciphertext size that exceeds the cell size ~500. So this protocol needs to transmit multiple cells, no matter which quantum-safe encryption algorithm we chose. This is addressed by "Proposal 249: Allow CREATE cells with >505 bytes of handshake data". 2. quantum-safe authentication: there is no quantum-safe authentication in this protocol. We believe that authentication can wait, as future (quantum) adversary cannot come back to present time and break authentication. Hence, we use ntor authentication to keep the proposal compact and simple. It will be a future work after this proposal. Thanks for your time, and happy holidays! Zhenfei Zhang Security Innovation.

9 26

Relay Database: Existing Schemas?
by nusenu 26 Feb '16

26 Feb '16

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 Hi, I'm planing to store relay data in a database for analysis. I assume others have done so as well, so before going ahead and designing a db schema I'd like to make sure I didn't miss pre-existing db schemas one could build on. Data to be stored: - - (most) descriptor fields - - everything that onionoo provides in a details record (geoip, asn, rdns, tordnsel, cw, ...) - - historic records I didn't find something matching so far, so I'll go ahead, but if you know of other existing relay db schemas I'd like to hear about it. thanks, nusenu "GSoC2013: Searchable Tor descriptor archive" (Kostas Jakeliunas) https://www.google-melange.com/gsoc/project/details/google/gsoc2013/wfn/ 5866452879933440 https://lists.torproject.org/pipermail/tor-dev/2013-May/004923.html https://lists.torproject.org/pipermail/tor-dev/2013-September/005357.htm l https://github.com/wfn/torsearch (btw, someone knows the license of this?) > This is true: the summary/details documents (just like in Onionoo > proper) deal with the *last* known info about relays. ernie https://gitweb.torproject.org/metrics-db.git/plain/doc/manual.pdf (didn't find db/tordir.sql mentioned in the pdf) "Instructions for setting up relay descriptor database" https://lists.torproject.org/pipermail/tor-dev/2010-March/001783.html "Set up descriptor database for other researchers" https://trac.torproject.org/projects/tor/ticket/1643 -----BEGIN PGP SIGNATURE----- iQIcBAEBCgAGBQJVLrmVAAoJEFv7XvVCELh0+ycP/0VkRWMGAhx7YwWhixtOPB0q ouitosse3SdLCMd1W7cps7nnQhcGv8E1xeUPYeizNQ+RIK9ldvnwgxhVt9ETOI3e oL6bcx3B/NSbTcGfZhIU6XCCX7+39CXz3/+/gXg4c1a5Cd9rYKuwTn7ZApPUNAK2 9yfckCwHaqh67ZDHB1A7nrHX1BJAjwhri5JRGomHSUXPwNZOyMzpgPkB+I92esqc Z4ajQo2D+Vyk42qF7apqp5ApVBLdt5ycUtW1j4s4KvyJH2BjeP4tCXvvYLKv9IvN TGHMJ111NQXbuk6H1OdaDmMZhhW6utPk8YAbNc7RZHqCdH7No40zFVlikLDrV2Xl uLt8FMlck7hGQv/4udA59Dw3PGHfrSiCbvJXb0S2jarnWOH2O+zSSuMs8jQM/x7k 6tIOlwtRDVGw3VuvNbb4MJnLzdHRxq3qy6ueDYuhmhHslxjD1Cbr3eE1RA7Da9aX kNDgjfXtdah52HWUZbIIxHQYzyCg5G3M5yy51GhUlA2Fe1sbPpNcEBeyEDK/jH3Y +7G+tgR+CdMvSFraCiYKHa1drVPJHeqNvZAqPNHKxpKwOwOoJEYrsW4wb/mJ7ybe o8xNYK691hcaMvHqwI47tw4hZfrI0f0+gQKKzENQQk8/8yUZ/0jgMRlW/Cz0yYIa FZEg+OJ/yEs8vKfYerIN =Rfn4 -----END PGP SIGNATURE-----

3 2

Proposal: Rendezvous Single Onion Services
by Tim Wilson-Brown - teor 12 Feb '16

12 Feb '16

Hi All, Please find below and attached a proposal: Rendezvous Single Onion Services. This is an updated and expanded version of "Direct Onion Services: Fast-but-not-hidden services”. It also borrows heavily from "Single Onion Services" (Proposal #252). The proposal is available in the branch “feature-17178-rsos” at https://github.com/teor2345/torspec.git <https://github.com/teor2345/torspec.git> as torspec/proposals/ideas/xxx-rend-single-onion.txt Work on this proposal is being tracked in trac ticket #17178 at https://trac.torproject.org/projects/tor/ticket/17178 <https://trac.torproject.org/projects/tor/ticket/17178> There is a basic implementation in the branch “feature-17178-rsos” at https://github.com/teor2345/tor.git <https://github.com/teor2345/tor.git> This can be tested with the chutney branch "feature-17178-rsos” at https://github.com/teor2345/chutney.git <https://github.com/teor2345/chutney.git> using the command: src/test/test-network.sh --flavor rsos-min Regards, Tim ----- Filename: xxx-rend-single-onion.txt Title: Rendezvous Single Onion Services Author: Tim Wilson-Brown, John Brooks, Aaron Johnson, Rob Jansen, George Kadianakis, Paul Syverson, Roger Dingledine Created: 2015-10-17 Status: Draft 1. Overview Rendezvous single onion services are an alternative design for single onion services, which trade service-side location privacy for improved performance, reliability, and scalability. Rendezvous single onion services have a .onion address identical to any other onion service. The descriptor contains the same information as the existing double onion (hidden) service descriptors. The introduction point and rendezvous protocols occur as in double onion services, with one modification: one-hop connections are made from the onion server to the introduction and rendezvous points. This proposal is a revision of the unnumbered proposal Direct Onion Services: Fast-but-not-hidden services by Roger Dingledine, and George Kadianakis at https://lists.torproject.org/pipermail/tor-dev/2015-April/008625.html It incorporates much of the discussion around hidden services since April 2015, including content from Single Onion Services (Proposal #252) by John Brooks, Paul Syverson, and Roger Dingledine. 2. Motivation Rendezvous single onion services are best used by sites which: * Don’t require location anonymity * Would appreciate lower latency or self-authenticated addresses * Would like to work with existing tor clients and relays * Can’t accept connections to an open ORPort Rendezvous single onion services have a few benefits over double onion services: * Connection latency is lower, as one-hop circuits are built to the introduction and rendezvous points, rather than three-hop circuits * Stream latency is reduced on a four-hop circuit * Less Tor network capacity is consumed by the service, as there are fewer hops (4 rather than 6) between the client and server via the rendezvous point Rendezvous single onion services have a few benefits over single onion services: * A rendezvous single onion service can load-balance over multiple rendezvous backends (see proposal #255) * A rendezvous single onion service doesn't need an accessible ORPort (it works behind a NAT, and in server enclaves that only allow outward connections) * A rendezvous single onion service is compatible with existing tor clients, hidden service directories, introduction points, and rendezvous points Rendezvous single onion services have a few drawbacks over single onion services: * Connection latency is higher, as one-hop circuits are built to the introduction and rendezvous points. Single onion services perform one extend to the single onion service’s ORPort only It should also be noted that, while single onion services receive many incoming connections from different relays, rendezvous single onion services make many outgoing connections to different relays. This should be taken into account when planning the connection capacity of the infrastructure supporting the onion service. Rendezvous single onion services are not location hidden on the service side, but clients retain all of the benefits and privacy of onion services. (The rationale for the 'single' and 'double' nomenclature is described in section 7.4 of proposal #252.) We believe that it is important for the Tor community to be aware of the alternative single onion service designs, so that we can reach consensus on the features and tradeoffs of each design. However, we recognise that each additional flavour of onion service splits the anonymity set of onion service users. Therefore, it may be best for user anonymity that not all designs are adopted, or that mitigations are implemented along with each additional flavour. (See sections 8 & 9 for a further discussion.) 3. Onion descriptors The rendezvous single onion descriptor format is identical to the double onion descriptor format. 4. Reaching a rendezvous single onion service as a client Clients reach rendezvous single onion services in an identical fashion to double onion services. The rendezvous design means that clients do not know whether they are talking to a double or rendezvous single onion service, unless that service tells them. (This may be a security issue.) However, the use of a four-hop path between client and rendezvous single onion service may be statistically distinguishable. (See section 8 for further discussion of security issues.) (Please note that this proposal follows the hop counting conventions in the tor source code. A circuit with a single connections between the client and the endpoint is one-hop, a circuit with 4 connections (and 3 nodes) between the client and endpoint is four-hop.) 5. Publishing a rendezvous single onion service To act as a rendezvous single onion service, a tor instance (or cooperating group of tor instances) must: * Publish onion descriptors in the same manner as any onion service, using three-hop circuits. This avoids service blocking by IP address, proposal #224 (next-generation hidden services) avoids blocking by onion address. * Perform the rendezvous protocol in the same manner as a double onion service, but make the intro and rendezvous connections one-hop. (This may allow intro and rendezvous points to block the service.) 5.1. Configuration options 5.1.1 RendezvousSingleOnionServiceNonAnonymousServer The tor instance operating a rendezvous single onion service must make one-hop circuits to the introduction and rendezvous points: RendezvousSingleOnionServiceNonAnonymousServer 0|1 If set, make one-hop circuits between the Rendezvous Single Onion Service server, and the introduction and rendezvous points. This option makes every onion service instance hosted by this tor instance a Rendezvous Single Onion Service. (Default: 0) Because of the grave consequences of misconfiguration here, we have added ‘NonAnonymous’ to the name of the torrc option. Furthermore, Tor MUST issue a startup warning message to operators of the onion service if this feature is enabled. [Should the name start with ‘NonAnonymous’ instead?] As RendezvousSingleOnionServiceNonAnonymousServer modifies the behaviour of every onion service on a tor instance, it is impossible to run hidden (double onion) services and rendezvous single onion services on the same tor instance. This is considered a feature, as it prevents hidden services from being discovered via rendezvous single onion services on the same tor instance. 5.1.2 Recommended Additional Options: Correctness Based on the experiences of Tor2Web with one-hop paths, operators should consider using the following options with every rendezvous single onion service, and every single onion service: UseEntryGuards 0 One-hop paths do not use entry guards. This also deactivates the entry guard pathbias code, which is not compatible with one-hop paths. Entry guards are a security measure against Sybil attacks. Unfortunately, they also act as the bottleneck of busy onion services and overload those Tor relays. LearnCircuitBuildTimeout 0 Learning circuit build timeouts is incompatible with one-hop paths. It also creates additional, unnecessary connections. Perhaps these options should be set automatically on (rendezvous) single onion services. Tor2Web sets these options automatically: UseEntryGuards 0 LearnCircuitBuildTimeout 0 5.1.3 Recommended Additional Options: Performance LongLivedPorts The default LongLivedPorts setting creates additional, unnecessary connections. This specifies no long-lived ports (the empty list). PredictedPortsRelevanceTime 0 seconds The default PredictedPortsRelevanceTime setting creates additional, unnecessary connections. RendPostPeriod 0 seconds This option typically hides the startup time of a hidden service by randomly posting over a 2 hour period. Since single onion services value speed over anonymity, they can post descriptors straight away. (Actually, 30 seconds after they bootstrap, for descriptor stability.) However, we do not recommend setting the following option to 1, unless bug #17359 is resolved so tor onion services can bootstrap without predicted circuits. __DisablePredictedCircuits 0 This option disables all predicted circuits. It is equivalent to: LearnCircuitBuildTimeout 0 LongLivedPorts PredictedPortsRelevanceTime 0 seconds And turning off hidden service server preemptive circuits, which is currently unimplemented (#17360) 5.1.3 Recommended Additional Options: Security We recommend that no other services are run on a rendezvous single onion service tor instance. Since tor runs as a client (and not a relay) by default, rendezvous single onion service operators should set: SocksPort 0 Disallow connections from client applications to the tor network via this tor instance. ClientOnly 1 Even if the defaults file configures this instance to be a relay, never relay any traffic or serve any descriptors. 5.2. Publishing descriptors A single onion service must publish descriptors in the same manner as any onion service, as defined by rend-spec. 5.3. Authorization Client authorization for a rendezvous single onion service is possible via the same methods used for double onion services. 6. Related Proposals, Tools, and Features 6.1. Load balancing High capacity services can distribute load and implement failover by: * running multiple instances that publish to the same onion service directories, * publishing descriptors containing multiple introduction points (OnionBalance), * publishing different introduction points to different onion service directories (OnionBalance upcoming(?) feature), * handing off rendezvous to a different tor instance via control port messages (proposal #255), or by a combination of these methods. 6.2. Ephemeral single onion services (ADD_ONION) The ADD_ONION control port command could be extended to support ephemerally configured rendezvous single onion services. Given that RendezvousSingleOnionServiceNonAnonymousServer modifies the behaviour of all onion services on a tor instance, if it is set, any ephemerally configured onion service should become a rendezvous single onion service. 6.3. Proposal 224 ("Next-Generation Hidden Services") This proposal is compatible with proposal 224, with onion services acting just like a next-generation hidden service, but making one-hop paths to the introduction and rendezvous points. 6.4. Proposal 246 ("Merging Hidden Service Directories and Intro Points") This proposal is compatible with proposal 246. The onion service will publish its descriptor to the introduction points in the same manner as any other onion service. Clients will use the merged hidden service directory and introduction point just as they do for other onion services. 6.5. Proposal 252 ("Single Onion Services") This proposal is compatible with proposal 252. The onion service will publish its descriptor to the introduction points in the same manner as any other onion service. Clients can then choose to extend to the single onion service, or continue with the rendezvous protocol. Running a rendezvous single onion service and single onion service allows older clients to connect via rendezvous, and newer clients to connenct via extend. This is useful for the transition period where not all clients support single onion services. 6.5. Proposal 255 ("Hidden Service Load Balancing") This proposal is compatible with proposal 255. The onion service will perform the rendezvous protocol in the same manner as any other onion service. Controllers can then choose to handoff the rendezvous point connection to another tor instance, which should also be configured as a rendezvous single onion service. 7. Considerations 7.1 Modifying RendezvousSingleOnionServiceNonAnonymousServer at runtime Implementations should not reuse introduction points or introduction point circuits if the value of RendezvousSingleOnionServiceNonAnonymousServer is different than it was when the introduction point was selected. This is because these circuits will have an undesirable length. There is specific code in tor that preserves introduction points on a HUP, if RendezvousSingleOnionServiceNonAnonymousServer has changed, all circuits should be closed, and all introduction points must be discarded. 7.2 Delaying connection expiry Tor clients typically expire connections much faster than tor relays [citation needed]. (Rendezvous) single onion service operators may find that keeping connections open saves on connection latency. However, it may also place an additional load on the service. (This could be implemented by increasing the configured connection expiry time.) 7.3. (No) Benefit to also running a Tor relay In tor Trac ticket #8742, running a relay and hidden onion service on the same tor instance was disabled for security reasons. While there may be benefits to running a relay on the same instance as a rendezvous single onion service (existing connections mean lower latency, it helps the tor network overall), a security analysis of this configuration has not yet been performed. In addition, a potential drawback is overloading a busy single onion service. 6.4 Predicted circuits We should look whether we can optimize further the predicted circuits that Tor makes as a onion service for this mode. 8. Security Implications 8.1 Splitting the Anonymity Set Each additional flavour of onion service, and each additional externally visible onion service feature, provides oportunities for fingerprinting. Also, each additional type of onion service shrinks the anonymity set for users of double onion (hidden) services who require server location anonymity. These users benefit from the cover provided by current users of onion services, who use them for client anonymity, self-authentication, NAT-punching, or other benefits. For this reason, features that shrink the double onion service anonymity set should be carefully considered. The benefits and drawbacks of additional features also often depend on a particular threat model. It may be that a significant number of users and sites adopt (rendezvous) single onion services due to their benefits. This could increase the traffic on the tor network, therefore increasing anonymity overall. However, the unique behaviour of each type of onion service may still be distinguishable from both the client and server ends of the connection. 8.2 Hidden Service Designs can potentially be more secure As a side-effect, by optimizing for performance in this feature, it allows us to lean more heavily towards security decisions for regular onion services. 8.3 One-hop onion service paths may encourage more attacks There's a possible second-order effect here since both encrypted services and hidden services will have foo.onion addresses and it's not clear based on the address whether the service will be hidden -- if *some* .onion addresses are easy to track down, are we encouraging adversaries to attack all rendezvous points just in case? 9. Further Work Further proposals or research could attempt to mitigate the anonymity-set splitting described in section 8. Here are some initial ideas. 9.1 Making Client Exit connections look like Client Onion Service Connections A mitigation to this fingerprinting is to make each (or some) exit connections look like onion service connections. This provides cover for particular types of onion service connections. Unfortunately, it is not possible to make onion service connections look like exit connections, as there are no suitable dummy servers to exit to on the Internet. 9.1.1 Making Client Exit connections perform Descriptor Downloads (Some) exit connections could perform a dummy descriptor download. (However, descriptors for recently accessed onion services are cached, so dummy downloads should only be performed occasionally.) Exit connections already involve a four-hop "circuit" to the server (including the connection between the exit and the server on the Internet). The server on the Internet is not included in the consensus. Therefore, this mitigation would effectively cover single onion services which are not relays. 9.1.2 Making Client Exit connections perform the Rendezvous Protocol (Some) exit connections could perform a dummy rendezvous protocol. Exit connections already involve a four-hop "circuit" to the server (including the connection between the exit and the server on the Internet). Therefore, this mitigation would effectively cover rendezvous single onion services, as long as a dummy descriptor download was also performed occasionally. 9.1.3 Making Single Onion Service rendezvous points perform name resolution Currently, Exits perform DNS name resolution, and changing this behaviour would cause unacceptable connection latency. Therefore, we could make onion service connections look like exit connections by making the rendezvous point do name resolution (that is, descriptor fetching), and, if needed, the introduction part of the protocol. This could potentially *reduce* the latency of single onion service connections, depending on the length of the paths used by the rendezvous point. However, this change makes rendezvous points almost as powerful as Exits, a careful security analysis will need to be performed before this is implemented. There is also a design issue with rendezvous name resolution: a client wants to leave resolution (descriptor download) to the RP, but it doesn't know whether it can use the exit-like protocol with an RP until it has downloaded the descriptor. This might mean that single onion services of both flavours need a different address style or address namespace. We could use .single.onion or something. (This would require an update to the HSDir code.) 9.2 Performing automated and common queries over onion services Tor could create cover traffic for a flavour of onion service by performing automated or common queries via an onion service of that type. In addition, onion service-based checks have security benefits over DNS-based checks. See Genuine Onion, Syverson and Boyce, 2015, at http://www.nrl.navy.mil/itd/chacs/syverson-genuine-onion-simple-fast-flexib… Here are some examples of automated queries that could be performed over an onion service: 9.2.1 torcheck over onion service torcheck ("Congratulations! This browser is configured to use Tor.") could be retrieved from an onion service. Incidentally, this would resolve the exitmap issues in #17297, but it would also fail to check that exit connections work, which is important for many Tor Browser users. 9.2.2 Tor Browser version checks over onion service Running tor browser version checks over an onion service seems to be an excellent use-case for onion services. It would also have the Tor Project "eating its own dogfood", that is, using onion services for its essential services. 9.2.3 Tor Browser downloads over onion service Running tor browser downloads over an onion service might require some work on the onion service codebase to support high loads, load-balancing, and failover. It is a good use case for a (rendezvous) single onion service, as the traffic over the tor network is only slightly higher than for Tor Browser downloads over tor. (4 hops for [R]SOS, 3 hops for Exit.) 9.2.4 SSL Observatory submissions over onion service HTTPS certificates could be submitted to HTTPS Everywhere's SSL Observatory over an onion service. This option is disabled in Tor Browser by default. Perhaps some users would be more comfortable enabling submission over an onion service, due to the additional security benefits. -----

2 2

Proposal: Load-balancing hidden services by splitting introduction from rendezvous
by Tom van der Woerdt 12 Feb '16

12 Feb '16

Hey all, I'd like your thoughts and comments on this proposal. Tom PS: If you want to deliver them in person, I'm in Berlin. Filename: xxx-intro-rendezvous-controlsocket.txt Title: Load-balancing hidden services by splitting introduction from rendezvous Author: Tom van der Woerdt Created: 2015-09-30 Status: draft 1. Overview and motivation To address scaling concerns with the onion web, we want to be able to spread the load of hidden services across multiple machines. OnionBalance is a great stab at this, and it can currently give us 60x the capacity by publishing 6 separate descriptors, each with 10 introduction points, but more is better. This proposal aims to address hidden service scaling up to a point where we can handle millions of concurrent connections. The basic idea involves splitting the 'introduce' from the 'rendezvous', in the tor implementation, and adding new events and commands to the control specification to allow intercepting introductions and transmitting them to different nodes, which will then take care of the actual rendezvous. External controller code could relay the data to another node or a pool of nodes, all which are run by the hidden service operator, effectively distributing the load of hidden services over multiple processes. By cleverly utilizing the current descriptor methods, we could publish up to sixty unique introduction points, which could translate to many thousands of parallel tor workers. This should allow hidden services to go multi-threaded, with a few small changes. 2. Specification We propose two additions to the control specification, of which one is an event and the other is a new command. We also introduce a new configuration option. 2.1. DisableAutomaticRendezvous configuration option The syntax is: "DisableAutomaticRendezvous" SP [1|0] CRLF This configuration option is defined to be a boolean toggle which, if set, stops the tor implementation from automatically doing a rendezvous when an INTRODUCE2 cell is received. Instead, an event will be sent to the controllers. If no controllers are present, the introduction cell should be dropped, as acting on it instead of dropping it could open a window for a DoS. For security reasons, the configuration should be made available only in the configuration files, and not as an option settable by the controller. 2.2. The "INTRODUCE" event The syntax is: "650" SP "INTRODUCE" SP RendezvousData CRLF RendezvousData = implementation-specific, but must not contain whitespace, must only contain human-readable characters, and should be no longer than 512 bytes The INTRODUCE event should contain sufficient data to allow continuing the rendezvous from another Tor instance. The exact format is left unspecified and left up to the implementation. From this follows that only matching versions can be used safely to coordinate the rendezvous of hidden service connections. 2.3. "PERFORM-RENDEZVOUS" command The syntax is: "PERFORM-RENDEZVOUS" SP RendezvousData CRLF This command allows a controller to perform a rendezvous using data received through an INTRODUCE event. The format of RendezvousData is not specified other than that it must not contain whitespace, and should be no longer than 512 bytes. 3. Compatibility and security The implementation of these methods should, ideally, not change anything in the network, and all control changes are opt-in, so this proposal is fully backwards compatible. Controllers handling this data must be careful to not leak rendezvous data to untrusted parties, as it could be used to intercept and manipulate hidden services traffic. 4. Example Let's take an example where a client (Alice) tries to contact Bob's hidden service. To do this, Bob follows the normal hidden service specification, except he sets up ten servers to do this. One of these publishes the descriptor, the others have this desabled. When the INTRODUCE2 cell arrives at the node which published the descriptor, it does not immediately try to perform the rendezvous, but instead outputs this to the controller. Through an out-of-band process this message is relayed to a controller of another node of Bob's, and this transmits the "PERFORM-RENDEZVOUS" command to that node. This node finally performs the rendezvous, and will continue to serve data to Alice, whose client will now not have to talk to the introduction point anymore. 5. Other considerations We have left the actual format of the rendezvous data in the control protocol unspecified, so that controllers do not need to worry about the various types of hidden service connections, most notably proposal 224. The decision to not implement the actual cell relaying in the tor implementation itself was taken to allow more advanced configurations, and to leave the actual load-balancing algorithm to the implementor of the controller. The developer of the tor implementation should not have to choose between a round-robin algorithm and something that could pull CPU load averages from a centralized monitoring system.

5 9

Re: [tor-dev] Comparing Stem, metrics-lib, and zoossh
by Karsten Loesing 17 Jan '16

17 Jan '16

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello Philipp and iwakeh, hello list, Damian and I sat down yesterday at the dev meeting to talk about doing a comparison of the various descriptor-parsing libraries with respect to capabilities, run-time performance, memory usage, etc. We put together a list of things we'd like to compare and tests we'd like to run that we thought we'd want to share with you. Damian and I will both be working on these for metrics-lib for a short while and then switch to Stem. Please feel free to join us in these effort. The result is supposed to live on Stem's home page unless somebody comes up with a better place. Thanks! All the best, Damian and Karsten On 30/09/15 10:57, Karsten Loesing wrote: > 1. capabilities - supported descriptor types - all the ones on > CollecTor's formats.html - hidden service descriptors (have an > agreed @type for that) - getting/producing descriptors - reading > from file/directory - reading from tarballs - reading from > CollecTor's .xz-compressed tarballs - fetching from CollecTor - > downloading from directories (authorities or mirrors) - generating > (for unit test) - recognizing @type annotation - inferencing from > file name - keeping reading history - user documentation - > validation (format, crypto, successful sanitization) - packages > available - how much usage by (large) applications > > 2. performance (CPU time, memory overhead) - compression: > .xz-compressed tarballs/decompressed tarballs/plain-text - > descriptor type: consensus, server descriptor, extra-info > descriptor, microdescriptors - validation: on or off (allows lazy > loading) > > 3. tests by descriptor type - @type server-descriptor 1.0 - Stem's > "List Outdated Relays" - average advertised bandwidth - fraction of > relays that can exit to port 80 - @type extra-info 1.0 - sum of all > written and read bytes from write-history/read-history - number of > countries from which v3 requests were received - @type > network-status-consensus-3 - average number of relays with Exit > flag - @type network-status-vote-3 - Stem's "Votes by Bandwidth > Authorities" - @type dir-key-certificate-3 - @type > network-status-microdesc-consensus-3 1.0 - @type microdescriptor > 1.0 - look at single microdesc cons and microdescs, compile list > of extended families - fraction of relays that can exit to port 80 > - @type network-status-2 1.0 - @type directory 1.0 - @type > bridge-network-status - @type bridge-server-descriptor - @type > bridge-server-descriptor 1.0 - @type bridge-extra-info 1.3 - @type > bridge-pool-assignment - @type tordnsel 1.0 - @type torperf 1.0 > > 4. action items - get in touch with Dererk for packaging > metrics-lib for Debian > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 Comment: GPGTools - http://gpgtools.org iQEcBAEBAgAGBQJWDOCYAAoJEJD5dJfVqbCrwAMIAJ0Chlui/Qv5kiGy9WZVkoKU UsxiK1IGVh/eGrpunzKdWQtVhvv+285Ab0OUB4URTK5mpOE+bKD3vcFy3ziXvpke xl5X2rZ/MtzJpRrGcAue0+2YZBrmOsGtGbclH9LcnTRgs65AKFMUp/SPf30LS0Pw l8tg6xUtB7/97qxwNDj08J9Yp/YtWaankE0zuI3py10qa/2RTXBSjZ0JkemLmhxL zVy2yUirNdC+bq9rNh+qh2LMIIEEVbGX2sHJx4JdbLjrJAyrSPtyFhXaih4jkIz3 TptTymRwX8Peny7zEJkkGojH6FkOW0gwpfaZBd4vkphLUbyupHIt3k9aKS15Je0= =uGPS -----END PGP SIGNATURE-----

3 23

Proposal 262: Re-keying live circuits with new cryptographic material
by Nick Mathewson 29 Dec '15

29 Dec '15

[Proposal 261 probably needs this.] Filename: 262-rekey-circuits.txt Title: Re-keying live circuits with new cryptographic material Author: Nick Mathewson Created: 28 Dec 2015 Status: Open 1. Summary and Motivation Cryptographic primitives have an upper limit of how much data should be encrypted with the same key. But currently Tor circuits have no upper limit of how much data they will deliver. While the upper limits of our AES-CTR crypto is ridiculously high (on the order of hundreds of exabytes), the AEZ crypto we're considering suggests we should rekey after the equivalent in cells after around 280 TB. 280 TB is still high, but not ridiculously high. So in this proposal I explain a general mechanism for rekeying a circuit. We shouldn't actually build this unless we settle on 2. RELAY_REKEY cell operation To rekey, the circuit initiator ("client") can send a new RELAY_REKEY cell type: struct relay_rekey { u16 rekey_method IN [0, 1]; u8 rekey_data[]; } const REKEY_METHOD_ACK = 0; const REKEY_METHOD_SHAKE128_CLIENT = 1; This cell means "I am changing the key." The new key material will be derived from SHAKE128 of the aez_key concatenated with the rekey_data field, to fill a new shake_output structure. The client should set rekey_data at random. After sending one of these RELAY_REKEY cells, the client uses the new aez_key to encrypt all of its data to this hop, but retains the old aez_key for decrypting the data coming back from the relay. When the relay receives a RELAY_REKEY cell, it sends a RELAY_REKEY cell back towards the client, with empty rekey_data, and relay_method==0, and then updates its own key material for all additional data it sends and receives to the client. When the client receives this reply, it can discard the old AEZ key, and begin decrypting subsequent inbound cells with the new key. So in summary: the client sends a series of cells encrypted with the old key, and then sends a REKEY cell, followed by relay cells encrypted with the new key: OldKey[data data data ... data rekey] NewKey[data data data...] And after the server receives the REKEY cell, it stops sending relay cells encrypted with the old keys, sends its own REKEY cell with the ACK method, and starts sending cells encrypted with the new key. REKEY arrives somewhere in here I V OldKey[data data data data rekey-ack] NewKey[data data data ...] 2.1. Supporting other cryptography types Each relay cipher must specify its own behavior in the presence of a REKEY cell of each type that it supports. In general, the behavior of method 1 ("shake128-client") is "regenerate keys as if we were calling the original KDF after a CREATE handshake, using SHAKE128 on our current static key material and on a 32-byte random input." The behavior of any unsupported REKEY method must be to close the circuit with an error. The AES-CTR relay cell crypto doesn't support rekeying. See 3.2 below if you disagree. 2.2. How often to re-key? Clients should follow a deterministic algorithm in deciding when to re-key, so as not to leak client differences. This algorithm should be type-specific. For AEZ, I recommend that clients conservatively rekey every 2**32 cells (about 2 TB). And to make sure that this code actually works, the schedule should be after 2**15 cells, and then every 2**32 cells thereafter. It may be beneficial to randomize these numbers. If so, let's try subtracting between 0 and 25% at random. 2.3. How often to allow re-keying? We could define a lower bound to prevent too-frequent rekeying. I'm not sure I see the point here; the process described above is not that costly. 3. Alternative designs 3.1. Should we add some public key cryptography here? We could change the body of a REKEY cell and its ack to be more like CREATE/CREATED. Then we'd have to add a third step from the client to the server to acknowledge receipt of the 'CREATED' cell and changing of the key. So, what would this added complexity and computational load buy us? It would defend against the case where an adversary had compromised the shared key material for a circuit, but was not able to compromise the rekey process. I'm not sure that this is reasonable; the likeliest cases I can think of here seem to be "get compromised, stay compromised" for a circuit. 3.2. Hey, could we use this for forward secrecy with AES-CTR? We could, but the best solution to AES-CTR's limitations right now is to stop using our AES-CTR setup. Anything that supports REKEY will also presumably support AEZ or something better. 3.3. We could upgrade ciphers with this! Yes we could. We could define this not only to change the key, but to upgrade to a better ciphersuite. For example, we could start by negotiating AES-CTR, and then "secretly" upgrade to AEZ. I'm not sure that's worth the complexity, or that it would really be secret in the presence of traffic analysis.

2 1

Proposal 261: AEZ for relay cryptography
by Nick Mathewson 29 Dec '15

29 Dec '15

[Okay, I'm pulling this out of draft stage. Still not sure this is the right primitive, but I'm pretty sure this would be about the right way to do it.] Filename: 261-aez-crypto.txt Title: AEZ for relay cryptography Author: Nick Mathewson Created: 28 Oct 2015 Status: Open 0. History I wrote the first draft of this around October. This draft takes a more concrete approach to the open questions from last time around. 1. Summary and preliminaries This proposal describes an improved algorithm for circuit encryption, based on the wide-block SPRP AEZ. I also describe the attendant bookkeeping, including CREATE cells, and several variants of the proposal. For more information about AEZ, see http://web.cs.ucdavis.edu/~rogaway/aez/ For motivations, see proposal 202. 2. Specifications 2.1. New CREATE cell types. We add a new CREATE cell type that behaves as an ntor cell but which specifies that the circuit will be created to use this mode of encryption. [TODO: Can/should we make this unobservable?] The ntor handshake is performed as usual, but a different PROTOID is used: "ntor-curve25519-sha256-aez-1" To derive keys under this handshake, we use SHAKE256 to derive the following output: struct shake_output { u8 aez_key[48]; u8 chain_key[32]; u8 chain_val_forward[16]; u8 chain_val_backward[16]; }; The first two two fields are constant for the lifetime of the circuit. 2.2. New relay cell payload We specify the following relay cell payload format, to be used when the exit node circuit hop was created with the CREATE format in 2.1 above: struct relay_cell_payload { u32 zero_1; u16 zero_2; u16 stream_id; u16 length IN [0..498]; u8 command; u8 data[498]; // payload_len - 11 }; Note that the payload length is unchanged. The fields are now rearranged to be aligned. The 'recognized' and 'length' fields are replaced with zero_1, zero_2, and the high 7 bits of length, for a minimum of 55 bits of unambigious verification. (Additional verification can be done by checking the other fields for correctness; AEZ users can exploit plaintext redundancy for additional cryptographic checking.) When encrypting a cell for a hop that was created using one of these circuits, clients and relays encrypt them using the AEZ algorithm with the following parameters: Let Chain denote chain_val_forward if this is a forward cell or chain_val_backward otherwise. tau = 0 # We set tau=0 because want no per-hop ciphertext expansion. Instead # we use redundancy in the plaintext to authenticate the data. Nonce = struct { u64 cell_number; u8 is_forward; u8 is_early; } # The cell number is the number of relay cells that have # traveled in this direction on this circuit before this cell. # ie, it's zero for the first cell, two for the second, etc. # # is_forward is 1 for outbound cells, 0 for inbound cells. # is_early is 1 for cells packaged as RELAY_EARLY, 0 for # cells packaged as RELAY. # # Technically these two values would be more at home in AD # than in Nonce; but AEZ doesn't actually distinguish N and AD # internally. Define CELL_CHAIN_BYTES = 32 AD = [ XOR(prev_plaintext[:CELL_CHAIN_BYTES], prev_ciphertext[:CELL_CHAIN_BYTES]), Chain ] # Using the previous cell's plaintext/ciphertext as additional data # guarantees that any corrupt ciphertext received will corrupt the # plaintext, which will corrupt all future plaintexts. Set Chain = AES(chain_key, Chain) xor Chain. # This 'chain' construction is meant to provide forward # secrecy. Each chain value is replaced after each cell with a # (hopefully!) hard-to-reverse construction. This instantiates a wide-block cipher, tweaked based on the cell index and direction. It authenticates part of the previous cell's plaintext, thereby ensuring that if the previous cell was corrupted, this cell will be unrecoverable. 3. Design considerations 3.1. Wide-block pros and cons? See proposal 202, section 4. 3.2. Given wide-block, why AEZ? It's a reasonably fast probably secure wide-block cipher. In particular, it's performance-competitive with AES_CTR, and far better than what we're doing now. See performance appendix. It seems secure-ish too. Several cryptographers I know seem to think it's likely secure enough, and almost surely at least as good as AES. [There are many other competing wide-block SPRP constructions if you like. Many require blocks be an integer number of blocks, or aren't tweakable. Some are slow. Do you know a good one?] 3.3. Why _not_ AEZ? There are also some reasons to consider avoiding AEZ, even if we do decide to use a wide-block cipher. FIRST it is complicated to implement. As the specification says, "The easiness claim for AEZ is with respect to ease and versatility of use, not implementation." SECOND, it's still more complicated to implement well (fast, side-channel-free) on systems without AES acceleration. We'll need to pull the round functions out of fast assembly AES, which is everybody's favorite hobby. THIRD, it's really horrible to try to do it in hardware. FOURTH, it is comparatively new. Although several cryptographers like it, and it is closely related to a system with a security proof, you never know. FIFTH, something better may come along. 4. Alternative designs 4.1. Two keys. We could have a separate AEZ key for forward and backward encryption. This would use more space, however. 4.2. Authenticating things differently In computing the AD, we could replace xor with concat. In computing the AD, we could replace CELL_CHAIN_BYTES with 16, or 509. (Another thing we might dislike about the current proposal is that it appears to requires us to remember 32 bytes of plaintext until we get another cell. But that part is fixable: note that in the structure of AEZ, the AD is processed in the AEZ-hash() function, and then no longer used. We can compute the AEZ-hash() to be used for the next cell after each cell is en/de crypted.) 4.3. Other hashes. We could update the ntor definition used in this to use a better hash than SHA256 inside. 4.4. Less predictable plaintext. A positively silly option would be to reserve the last X bytes of each relay cell's plaintext for random bytes, if they are not used for payload. This might help a little, in a really doofy way. A.1. Performance notes: memory requirements Let's ignore Tor overhead here, but not openssl overhead. IN THE CURRENT PROTOCOL, the total memory required at each relay is: 2 sha1 states, 2 aes states. Each sha1 state uses 96 bytes. Each aes state uses 244 bytes. (Plus 32 bytes counter-mode overhead.) This works out to 704 bytes at each hop. IN THE PROTOCOL ABOVE, using an optimized AEZ implementation, we'll need 128 bytes for the expanded AEZ key schedule. We'll need another 244 bytes for the AES key schedule for the chain key. And there's 32 bytes of chaining values. This gives us 404 bytes at each hop, for a savings of 42%. If we used separate AES and AEZ keys in each direction, we would be looking at 776 bytes, for a space increase of 10%. A.2. Performance notes: CPU requirements on AESNI hosts The cell_ops benchmark in bench.c purports to tell us how long it takes to encrypt a tor cell. But it wasn't really telling the truth, since it only did one SHA1 operation every 2^16 cells, when entries and exits really do one SHA1 operation every end-to-end cell. I expanded it to consider the slow (SHA1) case as well. I ran this on my friendly OSX laptop (2.9 GHz Intel Core i5) with AESNI support: Inbound cells: 169.72 ns per cell. Outbound cells: 175.74 ns per cell. Inbound cells, slow case: 934.42 ns per cell. Outbound cells, slow case: 928.23 ns per cell. Note that So for an n-hop circuit, each cell does the slow case and (n-1) fast cases at the entry; the slow case at the exit, and the fast case at each middle relay. So for 3 hop circuits, the total current load on the network is roughly 425 ns per hop, concentrated at the exit. Then I started messing around with AEZ benchmarks, using the aesni-optimized version of AEZ on the AEZ website. (Further optimizations are probably possible.) For the AES256, I used the usual aesni-based aes construction. Assuming xor is free in comparison to other operations, and CELL_CHAIN_BYTES=32, I get roughly 270 ns per cell for the entire operation. If we were to pick CELL_CHAIN_BYTES=509, we'd be looking at around 303 ns per cell. If we were to pick CELL_CHAIN_BYTES=509 and replace XOR with CONCAT, it would be around 355 ns per cell. If we were to keep CELL_CHAIN_BYTES=32, and remove the AES256-chaining, I see values around 260 ns per cell. (This is all very spotty measurements, with some xors left off, and not much effort done at optimization beyond what the default optimized AEZ does today.) A.3. Performance notes: what if we don't have AESNI? Here I'll test on a host with sse2 and ssse3, but no aesni instructions. From Tor's benchmarks I see: Inbound cells: 1218.96 ns per cell. Outbound cells: 1230.12 ns per cell. Inbound cells, slow case: 2099.97 ns per cell. Outbound cells, slow case: 2107.45 ns per cell. For a 3-hop circuit, that gives on average 1520 ns per cell. [XXXX Do a real benchmark with a fast AEZ backend. First, write one. Preliminary results are a bit disappointing, though, so I'll need to invetigate alternatives as well.]

2 1