Filename: xxx-combine-intro-and-rend-points.txt Title: Combine Introduction and Rendezvous Points Version: $Revision$ Last-Modified: $Date$ Author: Karsten Loesing, Christian Wilms Created: 27-Jun-2008 Status: Open Change history: 27-Jun-2008 Initial proposal for or-dev Overview: Establishing a connection to a hidden service currently involves two Tor relays, introduction and rendezvous point, and 10 more relays distributed over four circuits to connect to them. The introduction point is established in the mid-term by a hidden service to transfer introduction requests from client to the hidden service. The rendezvous point is set up by the client for a single hidden service request and actually transfers end-to-end encrypted application data between client and hidden service. There are some reasons for separating the two roles of introduction and rendezvous point: (1) Plausible deniability: A relay shall not be made responsible that it relays data for a certain hidden service; in the original design as described in [1] an introduction point relays no application data, and a rendezvous points neither knows the hidden service nor can it decrypt the data. (2) Scalability: The hidden service shall not have to maintain a number of open circuits proportional to the expected number of client requests. (3) Attack resistance: The effect of an attack on the only visible parts of a hidden service, its introduction points, shall be as small as possible. However, elimination of a separate rendezvous connection as proposed by Øverlier and Syverson [2] is the most promising approach to improve the delay in connection establishment. From all substeps of connection establishment extending a circuit by only a single hop is responsible for a major part of delay. Reducing on-demand circuit extensions from two to one results in a decrease of mean connection establishment times from 39 to 29 seconds [3]. Particularly, eliminating the delay on hidden-service side allows the client to better observe progress of connection establishment, thus allowing it to use smaller timeouts. Proposal 114 introduced new introduction keys for introduction points and provides for user authorization data in hidden service descriptors; it will be shown in this proposal that introduction keys in combination with new introduction cookies provide for the first security property of plausible deniability. Further, eliminating the need for a separate introduction connection benefits the overall network load by decreasing the number of circuit extensions. After all, having only one connection between client and hidden service reduces the overall protocol complexity. Design: 1. Hidden Service Configuration Hidden services should be able to choose whether they would like to use this protocol. This might be opt-in for 0.2.1.x and opt-out for later major releases. 2. Contact Point Establishment When preparing a hidden service, a Tor client selects a set of relays to act as contact points instead of introduction points. The contact point combines both roles of introduction and rendezvous point as proposed in [2]. The only requirement for a relay to be picked as contact point is its capability of performing this role. This can be determined from the Tor version number that needs to be equal or higher than the first version that implements this proposal. The easiest way to implement establishment of contact points is to introduce v2 ESTABLISH_INTRO cells and use the currently unused auth type number 1 for contact points. V Format byte: set to 255 [1 octet] V Version byte: set to 2 [1 octet] KLEN Key length [2 octets] PK Bob's public key [KLEN octets] HS Hash of session info [20 octets] AUTHT The auth type that is supported [1 octet] AUTHL Length of auth data [2 octets] AUTHD Auth data [variable] SIG Signature of above information [variable] The hidden service does not create a fixed number of contact points, like 3 in the current protocol. It uses a minimum of 3 contact points, but increases this number depending on the history of client requests within the last hour. The hidden service also increases this number depending on the frequency of failing contact points in order to defend against attacks on its contact points. When client authorization as described in proposal 121 is used, a hidden service can also use the number of authorized clients as first estimate for the required number of contact points. 3. Hidden Service Descriptor Creation A hidden service needs to issue a fresh introduction cookie for each established introduction point. By requiring clients to use this cookie in a later connection establishment, an introduction point cannot access the hidden service that it works for. Together with the fresh introduction key that was introduced in proposal 114, this results in plausible deniability for the contact point. The v2 hidden service descriptor format contains an "intro-authentication" field that may contain introduction-point specific keys. The hidden service creates a random string, comparable to the rendezvous cookie, and includes it in the descriptor as introduction cookie. Existing clients that do not understand this new protocol simply ignore that cookie. Further, the hidden service lists in the "protocol-versions" field that it supports this protocol. 4. Connection Establishment When establishing a connection to a hidden service a client learns about the capability of using the new protocol from the hidden service descriptor. It may choose whether to use this new protocol or not, whereas older clients cannot understand the new capability and can only use the current protocol. Client using version 0.2.1.x should be able to opt-in for using the new protocol, which should change to opt-out for later major releases. When using the new capability the client creates a v2 INTRODUCE1 cell that extends an unversioned INTRODUCE1 cell by adding the content of an ESTABLISH_RENDEZVOUS cell. Further, the client sends this cell using the new cell type 41 RELAY_INTRODUCE1_VERSIONED to the introduction point, because unversioned and versioned INTRODUCE1 cells are indistinguishable: Cleartext V Version byte: set to 2 [1 octet] PK_ID Identifier for Bob's PK [20 octets] AUTHT The auth type that is supported [1 octet] AUTHL Length of auth data [2 octets] AUTHD Auth data [variable] Encrypted to Bob's PK: VER Version byte: set to 3. [1 octet] AUTHT The auth type that is supported [1 octet] AUTHL Length of auth data [2 octets] AUTHD Auth data [variable] IP Rendezvous point's address [4 octets] PORT Rendezvous point's OR port [2 octets] ID Rendezvous point identity ID [20 octets] KLEN Length of onion key [2 octets] KEY Rendezvous point onion key [KLEN octets] RC Rendezvous cookie [20 octets] g^x Diffie-Hellman data, part 1 [128 octets] The cleartext part contains the rendezvous cookie as auth data for the currently unused auth type 1. The contact point remembers the rendezvous cookie just as a rendezvous point would do. The encrypted part contains the introduction cookie as auth data for the likewise unused auth type 1. The rendezvous cookie is contained as before, but the remaining rendezvous point information is left empty, as there is no separate rendezvous point. 5. Rendezvous Establishment The contact point recognizes a v2 INTRODUCE1 cell with auth type 1 as a request to be used in the new protocol. It remembers the contained rendezvous cookie, replies to the client with an INTRODUCE_ACK cell (omitting the RENDEZVOUS_ESTABLISHED cell), and forwards the encrypted part of the INTRODUCE1 cell as INTRODUCE2 cell to the hidden service. 6. Introduction at Hidden Service The hidden services recognizes an INTRODUCE2 cell containing an introduction cookie as authorization data. In this case, it does not extend a circuit to a rendezvous point, but sends a RENDEZVOUS1 cell directly back to its contact point as usual. 7. Rendezvous at Contact Point The contact point processes a RENDEZVOUS1 cell just as a rendezvous point does. The only difference is that the hidden-service-side circuit is not exclusive for the client connection, but shared among multiple client connections. Security Implications: (1) Plausible deniability One of the original reasons for the separation of introduction and rendezvous points is that a relay shall not be made responsible that it relays data for a certain hidden service. In the current design an introduction point relays no application data and a rendezvous points neither knows the hidden service nor can it decrypt the data. This property is also fulfilled in this new design. A contact point only learns a fresh introduction key instead of the hidden service key, so that it cannot recognize a hidden service. Further, the introduction cookie, which is unknown to the contact point, prevents it from accessing the hidden service itself. The only way for a contact point to access a hidden service is to look up whether it is contained in the descriptors of known hidden services. A contact point can plausibly deny knowledge of any hidden services, so that it cannot know for which hidden service it is working. In addition to that, it cannot learn the data that it transfers, because all communication between client and hidden service are end-to-end encrypted. (2) Scalability Another goal of the existing hidden service protocol is that a hidden service does not have to maintain a number of open circuits proportional to the expected number of client requests. The rationale behind this is better scalability. The new protocol eliminates the need for a hidden service to extend circuits on demand, which has a positive effect circuits establishment times and overall network load. The solution presented here to establish a number of contact points proportional to the history of connection requests reduces the number of circuits to a minimum number that fits the hidden service's needs. (3) Attack resistance The third goal of separating introduction and rendezvous points is to limit the effect of an attack on the only visible parts of a hidden service which are the contact points in this protocol. In theory, the new protocol is more vulnerable to this attack. An attacker who can take down a contact point does not only eliminate an access point to the hidden service, but also breaks current client connections to the hidden service using that contact point. Øverlier and Syverson proposed the concept of valet nodes as additional safeguard for introduction/contact points [4]. Unfortunately, this increases hidden service protocol complexity conceptually and from an implementation point of view. Therefore, it is not included in this proposal. However, in practice attacking a contact point (or introduction point) is not as rewarding as it might appear. The cost for a hidden service to set up a new contact point and publish a new hidden service descriptor is minimal compared to the efforts necessary for an attacker to take a Tor relay down. As a countermeasure to further frustrate this attack, the hidden service raises the number of contact points as a function of previous contact point failures. Further, the probability of breaking client connections due to attacking a contact point is minimal. It can be assumed that the probability of one of the other five involved relays in a hidden service connection failing or being shut down is higher than that of a successful attack on a contact point. (4) Resistance against Locating Attacks Clients are no longer able to force a hidden service to create or extend circuits. This further reduces an attacker's capabilities of locating a hidden server as described by Øverlier and Syverson [5]. Compatibility: The presented protocol does not raise compatibility issues with current Tor versions. New relay versions support both, the existing and the proposed protocol as introduction/rendezvous/contact points. A contact point acts as introduction point simultaneously. Hidden services and clients can opt-in to use the new protocol which might change to opt-out some time in the future. References: [1] Roger Dingledine, Nick Mathewson, and Paul Syverson, Tor: The Second-Generation Onion Router. In the Proceedings of the 13th USENIX Security Symposium, August 2004. [2] Lasse Øverlier and Paul Syverson, Improving Efficiency and Simplicity of Tor Circuit Establishment and Hidden Services. In the Proceedings of the Seventh Workshop on Privacy Enhancing Technologies (PET 2007), Ottawa, Canada, June 2007. [3] Christian Wilms, Improving the Tor Hidden Service Protocol Aiming at Better Performance, diploma thesis, June 2008, University of Bamberg. [4] Lasse Øverlier and Paul Syverson, Valet Services: Improving Hidden Servers with a Personal Touch. In the Proceedings of the Sixth Workshop on Privacy Enhancing Technologies (PET 2006), Cambridge, UK, June 2006. [5] Lasse Øverlier and Paul Syverson, Locating Hidden Servers. In the Proceedings of the 2006 IEEE Symposium on Security and Privacy, May 2006.