doc/spec/proposals/142-combine-intro-and-rend-points.txt

   1 Filename: 142-combine-intro-and-rend-points.txt
   2 Title: Combine Introduction and Rendezvous Points
   3 Version: $Revision$
   4 Last-Modified: $Date$
   5 Author: Karsten Loesing, Christian Wilms
   6 Created: 27-Jun-2008
   7 Status: Open
   8 Target: 0.2.2.x
   9
  10 Change history:
  11
  12   27-Jun-2008  Initial proposal for or-dev
  13   04-Jul-2008  Give first security property the new name "Responsibility"
  14                and change new cell formats according to rendezvous protocol
  15                version 3 draft.
  16   19-Jul-2008  Added comment by Nick (but no solution, yet) that sharing of
  17                circuits between multiple clients is not supported by Tor.
  18
  19 Overview:
  20
  21   Establishing a connection to a hidden service currently involves two Tor
  22   relays, introduction and rendezvous point, and 10 more relays distributed
  23   over four circuits to connect to them. The introduction point is
  24   established in the mid-term by a hidden service to transfer introduction
  25   requests from client to the hidden service. The rendezvous point is set
  26   up by the client for a single hidden service request and actually
  27   transfers end-to-end encrypted application data between client and hidden
  28   service.
  29
  30   There are some reasons for separating the two roles of introduction and
  31   rendezvous point: (1) Responsibility: A relay shall not be made
  32   responsible that it relays data for a certain hidden service; in the
  33   original design as described in [1] an introduction point relays no
  34   application data, and a rendezvous points neither knows the hidden
  35   service nor can it decrypt the data. (2) Scalability: The hidden service
  36   shall not have to maintain a number of open circuits proportional to the
  37   expected number of client requests. (3) Attack resistance: The effect of
  38   an attack on the only visible parts of a hidden service, its introduction
  39   points, shall be as small as possible.
  40
  41   However, elimination of a separate rendezvous connection as proposed by
  42   Øverlier and Syverson [2] is the most promising approach to improve the
  43   delay in connection establishment. From all substeps of connection
  44   establishment extending a circuit by only a single hop is responsible for
  45   a major part of delay. Reducing on-demand circuit extensions from two to
  46   one results in a decrease of mean connection establishment times from 39
  47   to 29 seconds [3]. Particularly, eliminating the delay on hidden-service
  48   side allows the client to better observe progress of connection
  49   establishment, thus allowing it to use smaller timeouts. Proposal 114
  50   introduced new introduction keys for introduction points and provides for
  51   user authorization data in hidden service descriptors; it will be shown
  52   in this proposal that introduction keys in combination with new
  53   introduction cookies provide for the first security property
  54   responsibility. Further, eliminating the need for a separate introduction
  55   connection benefits the overall network load by decreasing the number of
  56   circuit extensions. After all, having only one connection between client
  57   and hidden service reduces the overall protocol complexity.
  58
  59 Design:
  60
  61   1. Hidden Service Configuration
  62
  63   Hidden services should be able to choose whether they would like to use
  64   this protocol. This might be opt-in for 0.2.1.x and opt-out for later
  65   major releases.
  66
  67   2. Contact Point Establishment
  68
  69   When preparing a hidden service, a Tor client selects a set of relays to
  70   act as contact points instead of introduction points. The contact point
  71   combines both roles of introduction and rendezvous point as proposed in
  72   [2]. The only requirement for a relay to be picked as contact point is
  73   its capability of performing this role. This can be determined from the
  74   Tor version number that needs to be equal or higher than the first
  75   version that implements this proposal.
  76
  77   The easiest way to implement establishment of contact points is to
  78   introduce v2 ESTABLISH_INTRO cells. By convention, the relay recognizes
  79   version 2 ESTABLISH_INTRO cells as requests to establish a contact point
  80   rather than an introduction point.
  81
  82      V      Format byte: set to 255               [1 octet]
  83      V      Version byte: set to 2                [1 octet]
  84      KLEN   Key length                           [2 octets]
  85      PK     Public introduction key           [KLEN octets]
  86      HS     Hash of session info                [20 octets]
  87      SIG    Signature of above information       [variable]
  88
  89   The hidden service does not create a fixed number of contact points, like
  90   3 in the current protocol. It uses a minimum of 3 contact points, but
  91   increases this number depending on the history of client requests within
  92   the last hour. The hidden service also increases this number depending on
  93   the frequency of failing contact points in order to defend against
  94   attacks on its contact points. When client authorization as described in
  95   proposal 121 is used, a hidden service can also use the number of
  96   authorized clients as first estimate for the required number of contact
  97   points.
  98
  99   3. Hidden Service Descriptor Creation
 100
 101   A hidden service needs to issue a fresh introduction cookie for each
 102   established introduction point. By requiring clients to use this cookie
 103   in a later connection establishment, an introduction point cannot access
 104   the hidden service that it works for. Together with the fresh
 105   introduction key that was introduced in proposal 114, this reduces
 106   responsibility of a contact point for a specific hidden service.
 107
 108   The v2 hidden service descriptor format contains an
 109   "intro-authentication" field that may contain introduction-point specific
 110   keys. The hidden service creates a random string, comparable to the
 111   rendezvous cookie, and includes it in the descriptor as introduction
 112   cookie for auth-type "1". By convention, clients recognize existence of
 113   auth-type 1 as possibility to connect to a hidden service via a contact
 114   point rather than an introduction point. Older clients that do not
 115   understand this new protocol simply ignore that cookie.
 116
 117   4. Connection Establishment
 118
 119   When establishing a connection to a hidden service a client learns about
 120   the capability of using the new protocol from the hidden service
 121   descriptor. It may choose whether to use this new protocol or not,
 122   whereas older clients cannot understand the new capability and can only
 123   use the current protocol. Client using version 0.2.1.x should be able to
 124   opt-in for using the new protocol, which should change to opt-out for
 125   later major releases.
 126
 127   When using the new capability the client creates a v2 INTRODUCE1 cell
 128   that extends an unversioned INTRODUCE1 cell by adding the content of an
 129   ESTABLISH_RENDEZVOUS cell. Further, the client sends this cell using the
 130   new cell type 41 RELAY_INTRODUCE1_VERSIONED to the introduction point,
 131   because unversioned and versioned INTRODUCE1 cells are indistinguishable:
 132
 133   Cleartext
 134      V      Version byte: set to 2                [1 octet]
 135      PK_ID  Identifier for Bob's PK             [20 octets]
 136      RC     Rendezvous cookie                   [20 octets]
 137   Encrypted to introduction key:
 138      VER    Version byte: set to 3.               [1 octet]
 139      AUTHT  The auth type that is supported       [1 octet]
 140      AUTHL  Length of auth data                  [2 octets]
 141      AUTHD  Auth data                            [variable]
 142      RC     Rendezvous cookie                   [20 octets]
 143      g^x    Diffie-Hellman data, part 1        [128 octets]
 144
 145   The cleartext part contains the rendezvous cookie that the contact point
 146   remembers just as a rendezvous point would do.
 147
 148   The encrypted part contains the introduction cookie as auth data for the
 149   auth type 1. The rendezvous cookie is contained as before, but there is
 150   no further rendezvous point information, as there is no separate
 151   rendezvous point.
 152
 153   5. Rendezvous Establishment
 154
 155   The contact point recognizes a v2 INTRODUCE1 cell with auth type 1 as a
 156   request to be used in the new protocol. It remembers the contained
 157   rendezvous cookie, replies to the client with an INTRODUCE_ACK cell
 158   (omitting the RENDEZVOUS_ESTABLISHED cell), and forwards the encrypted
 159   part of the INTRODUCE1 cell as INTRODUCE2 cell to the hidden service.
 160
 161   6. Introduction at Hidden Service
 162
 163   The hidden services recognizes an INTRODUCE2 cell containing an
 164   introduction cookie as authorization data. In this case, it does not
 165   extend a circuit to a rendezvous point, but sends a RENDEZVOUS1 cell
 166   directly back to its contact point as usual.
 167
 168   7. Rendezvous at Contact Point
 169
 170   The contact point processes a RENDEZVOUS1 cell just as a rendezvous point
 171   does. The only difference is that the hidden-service-side circuit is not
 172   exclusive for the client connection, but shared among multiple client
 173   connections.
 174
 175   [Tor does not allow sharing of a single circuit among multiple client
 176    connections easily. We need to think about a smart and efficient way to
 177    implement this. Comment by Nick. -KL]
 178
 179 Security Implications:
 180
 181   (1) Responsibility
 182
 183   One of the original reasons for the separation of introduction and
 184   rendezvous points is that a relay shall not be made responsible that it
 185   relays data for a certain hidden service. In the current design an
 186   introduction point relays no application data and a rendezvous points
 187   neither knows the hidden service nor can it decrypt the data.
 188
 189   This property is also fulfilled in this new design. A contact point only
 190   learns a fresh introduction key instead of the hidden service key, so
 191   that it cannot recognize a hidden service. Further, the introduction
 192   cookie, which is unknown to the contact point, prevents it from accessing
 193   the hidden service itself. The only way for a contact point to access a
 194   hidden service is to look up whether it is contained in the descriptors
 195   of known hidden services. A contact point cannot directly be made
 196   responsible for which hidden service it is working. In addition to that,
 197   it cannot learn the data that it transfers, because all communication
 198   between client and hidden service are end-to-end encrypted.
 199
 200   (2) Scalability
 201
 202   Another goal of the existing hidden service protocol is that a hidden
 203   service does not have to maintain a number of open circuits proportional
 204   to the expected number of client requests. The rationale behind this is
 205   better scalability.
 206
 207   The new protocol eliminates the need for a hidden service to extend
 208   circuits on demand, which has a positive effect on circuits establishment
 209   times and overall network load. The solution presented here to establish
 210   a number of contact points proportional to the history of connection
 211   requests reduces the number of circuits to a minimum number that fits the
 212   hidden service's needs.
 213
 214   (3) Attack resistance
 215
 216   The third goal of separating introduction and rendezvous points is to
 217   limit the effect of an attack on the only visible parts of a hidden
 218   service which are the contact points in this protocol.
 219
 220   In theory, the new protocol is more vulnerable to this attack. An
 221   attacker who can take down a contact point does not only eliminate an
 222   access point to the hidden service, but also breaks current client
 223   connections to the hidden service using that contact point.
 224
 225   Øverlier and Syverson proposed the concept of valet nodes as additional
 226   safeguard for introduction/contact points [4]. Unfortunately, this
 227   increases hidden service protocol complexity conceptually and from an
 228   implementation point of view. Therefore, it is not included in this
 229   proposal.
 230
 231   However, in practice attacking a contact point (or introduction point) is
 232   not as rewarding as it might appear. The cost for a hidden service to set
 233   up a new contact point and publish a new hidden service descriptor is
 234   minimal compared to the efforts necessary for an attacker to take a Tor
 235   relay down. As a countermeasure to further frustrate this attack, the
 236   hidden service raises the number of contact points as a function of
 237   previous contact point failures.
 238
 239   Further, the probability of breaking client connections due to attacking
 240   a contact point is minimal. It can be assumed that the probability of one
 241   of the other five involved relays in a hidden service connection failing
 242   or being shut down is higher than that of a successful attack on a
 243   contact point.
 244
 245   (4) Resistance against Locating Attacks
 246
 247   Clients are no longer able to force a hidden service to create or extend
 248   circuits. This further reduces an attacker's capabilities of locating a
 249   hidden server as described by Øverlier and Syverson [5].
 250
 251 Compatibility:
 252
 253   The presented protocol does not raise compatibility issues with current
 254   Tor versions. New relay versions support both, the existing and the
 255   proposed protocol as introduction/rendezvous/contact points. A contact
 256   point acts as introduction point simultaneously. Hidden services and
 257   clients can opt-in to use the new protocol which might change to opt-out
 258   some time in the future.
 259
 260 References:
 261
 262   [1] Roger Dingledine, Nick Mathewson, and Paul Syverson, Tor: The
 263   Second-Generation Onion Router. In the Proceedings of the 13th USENIX
 264   Security Symposium, August 2004.
 265
 266   [2] Lasse Øverlier and Paul Syverson, Improving Efficiency and Simplicity
 267   of Tor Circuit Establishment and Hidden Services. In the Proceedings of
 268   the Seventh Workshop on Privacy Enhancing Technologies (PET 2007),
 269   Ottawa, Canada, June 2007.
 270
 271   [3] Christian Wilms, Improving the Tor Hidden Service Protocol Aiming at
 272   Better Performance, diploma thesis, June 2008, University of Bamberg.
 273
 274   [4] Lasse Øverlier and Paul Syverson, Valet Services: Improving Hidden
 275   Servers with a Personal Touch. In the Proceedings of the Sixth Workshop
 276   on Privacy Enhancing Technologies (PET 2006), Cambridge, UK, June 2006.
 277
 278   [5] Lasse Øverlier and Paul Syverson, Locating Hidden Servers. In the
 279   Proceedings of the 2006 IEEE Symposium on Security and Privacy, May 2006.
 280