142-combine-intro-and-rend-points.txt

Filename: 142-combine-intro-and-rend-points.txt
Title: Combine Introduction and Rendezvous Points
Author: Karsten Loesing, Christian Wilms
Created: 27-Jun-2008
Status: Dead

Change history:

  27-Jun-2008  Initial proposal for or-dev
  04-Jul-2008  Give first security property the new name "Responsibility"
               and change new cell formats according to rendezvous protocol
               version 3 draft.
  19-Jul-2008  Added comment by Nick (but no solution, yet) that sharing of
               circuits between multiple clients is not supported by Tor.

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) Responsibility: 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
  responsibility. 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. By convention, the relay recognizes
  version 2 ESTABLISH_INTRO cells as requests to establish a contact point
  rather than an introduction point.

     V      Format byte: set to 255               [1 octet]
     V      Version byte: set to 2                [1 octet]
     KLEN   Key length                           [2 octets]
     PK     Public introduction key           [KLEN octets]
     HS     Hash of session info                [20 octets]
     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 reduces
  responsibility of a contact point for a specific hidden service.

  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 for auth-type "1". By convention, clients recognize existence of
  auth-type 1 as possibility to connect to a hidden service via a contact
  point rather than an introduction point. Older clients that do not
  understand this new protocol simply ignore that cookie.

  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]
     RC     Rendezvous cookie                   [20 octets]
  Encrypted to introduction key:
     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]
     RC     Rendezvous cookie                   [20 octets]
     g^x    Diffie-Hellman data, part 1        [128 octets]

  The cleartext part contains the rendezvous cookie that the contact point
  remembers just as a rendezvous point would do.

  The encrypted part contains the introduction cookie as auth data for the
  auth type 1. The rendezvous cookie is contained as before, but there is
  no further rendezvous point information, 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.

  [Tor does not allow sharing of a single circuit among multiple client
   connections easily. We need to think about a smart and efficient way to
   implement this. Comment by Nick. -KL]

Security Implications:

  (1) Responsibility

  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 cannot directly be made
  responsible 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 on 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.