Proposal 121: Added INTRODUCE1V cell type, improved replay protection for INTRODUCE2 cells, described limitations for auth protocols, improved hidden service protocol without client authorization, added second, more scalable authorization protocol, rewrote existing authorization protocol; changes based on discussion with Nick

svn:r16074

1 files changed, 292 insertions, 131 deletions

diff --git a/doc/spec/proposals/121-hidden-service-authentication.txt b/doc/spec/proposals/121-hidden-service-authentication.txt
index 5137ccc57..30a31523b 100644
--- a/doc/spec/proposals/121-hidden-service-authentication.txt
+++ b/doc/spec/proposals/121-hidden-service-authentication.txt
@@ -19,6 +19,13 @@ Change history:
   28-Apr-2008  Updated most parts of the concrete authorization protocol
   04-Jul-2008  Add a simple algorithm to delay descriptor publication for
                different clients of a hidden service
+  19-Jul-2008  Added INTRODUCE1V cell type (1.2), improved replay
+               protection for INTRODUCE2 cells (1.3), described limitations
+               for auth protocols (1.6), improved hidden service protocol
+               without client authorization (2.1), added second, more
+               scalable authorization protocol (2.2), rewrote existing
+               authorization protocol (2.3); changes based on discussion
+               with Nick
 
 Overview:
 
@@ -28,9 +35,9 @@ Overview:
   parts of the hidden service descriptor, (2) at the introduction point,
   and (3) at Bob's Tor client before contacting the rendezvous point. A
   service provider will be able to restrict access to his service at these
-  three points to authorized clients only. Further, the proposal contains a
-  first instance of an authorization protocol for the presented
-  infrastructure.
+  three points to authorized clients only. Further, the proposal contains
+  specific authorization protocols as instances that implement the
+  presented authorization infrastructure.
 
   This proposal is based on v2 hidden service descriptors as described in
   proposal 114 and introduced in version 0.2.0.10-alpha.
@@ -38,7 +45,7 @@ Overview:
   The proposal is structured as follows: The next section motivates the
   integration of authorization mechanisms in the hidden service protocol.
   Then we describe a general infrastructure for authorization in hidden
-  services, followed by a specific authorization protocol for this
+  services, followed by specific authorization protocols for this
   infrastructure. At the end we discuss a number of attacks and non-attacks
   as well as compatibility issues.
 
@@ -269,15 +276,24 @@ Details:
   not specify here.
 
   In order to understand a v1 ESTABLISH_INTRO cell, the implementation of
-  a relay must have a certain Tor version, which would probably be some
-  0.2.1.x. Hidden services need to be able to distinguish relays being
-  capable of understanding the new v1 cell formats and perform
-  authorization. We propose to use the version number that is contained in
-  networkstatus documents to find capable introduction points.
+  a relay must have a certain Tor version. Hidden services need to be able
+  to distinguish relays being capable of understanding the new v1 cell
+  formats and perform authorization. We propose to use the version number
+  that is contained in networkstatus documents to find capable
+  introduction points.
 
   The current INTRODUCE1 cells as described in section 1.8 of rend-spec is
   not designed to carry authorization data and has no version number, too.
-  We propose the following version 1 of INTRODUCE1 cells:
+  Unfortunately, unversioned INTRODUCE1 cells consist only of a fixed-size,
+  seemingly random PK_ID, followed by the encrypted INTRODUCE2 cell. This
+  makes it impossible to distinguish unversioned INTRODUCE1 cells from any
+  later format. In particular, it is not possible to introduce some kind of
+  format and version byte for newer versions of this cell. That's probably
+  where the comment "[XXX011 want to put intro-level auth info here, but no
+  version. crap. -RD]" that was part of rend-spec some time ago comes from.
+
+  We propose that new versioned INTRODUCE1 cells use the new cell type 41
+  RELAY_INTRODUCE1V (where V stands for versioned):
 
   Cleartext
      V      Version byte: set to 1                [1 octet]
@@ -292,24 +308,6 @@ Details:
   of the contained INTRODUCE2 cell. A calculation follows below when
   describing the INTRODUCE2 cell format we propose to use.
 
-  Unfortunately, v0 INTRODUCE1 cells consist only of a fixed-size,
-  seemingly random PK_ID, followed by the encrypted INTRODUCE2 cell. This
-  makes it impossible to distinguish v0 INTRODUCE1 cells from any later
-  format. In particular, it is not possible to introduce some kind of
-  format and version byte for newer versions of this cell. That's probably
-  where the comment "[XXX011 want to put intro-level auth info here, but no
-  version. crap. -RD]" that was part of rend-spec some time ago comes from.
-
-  Processing of v1 INTRODUCE1 cells therefore requires knowledge about the
-  context in which they are used. As a result, we propose that when
-  receiving a v1 ESTABLISH_INTRO cell, an introduction point only accepts
-  v1 INTRODUCE1 cells later on. Hence, the same introduction point cannot
-  be used to accept both v0 and v1 INTRODUCE1 cells for the same service.
-  (Another solution would be to distinguish v0 and v1 INTRODUCE1 cells by
-  their size, as v0 INTRODUCE1 cells can only have specific cell sizes,
-  depending on the version of the contained INTRODUCE2 cell; however, this
-  approach does not appear very clean.)
-
   1.3. Client authorization at hidden service
 
   The time when a hidden service receives an INTRODUCE2 cell constitutes
@@ -342,9 +340,10 @@ Details:
   proposed format of v3 INTRODUCE2 cells is as follows:
 
      VER    Version byte: set to 3.               [1 octet]
-     AUTHT  The auth type that is supported       [1 octet]
+     AUTHT  The auth type that is used            [1 octet]
      AUTHL  Length of auth data                  [2 octets]
      AUTHD  Auth data                            [variable]
+     TS     Timestamp (seconds since 1-1-1970)   [4 octets]
      IP     Rendezvous point's address           [4 octets]
      PORT   Rendezvous point's OR port           [2 octets]
      ID     Rendezvous point identity ID        [20 octets]
@@ -354,38 +353,24 @@ Details:
      g^x    Diffie-Hellman data, part 1        [128 octets]
 
   The maximum possible length of authorization data is related to the
-  enclosing INTRODUCE1 cell. A v3 INTRODUCE2 cell with
+  enclosing INTRODUCE1V cell. A v3 INTRODUCE2 cell with
   1024 bit = 128 octets long public keys without any authorization data
   occupies 306 octets (AUTHL is only used when AUTHT has a value != 0),
   plus 58 octets for hybrid public key encryption (see
   section 5.1 of tor-spec on hybrid encryption of CREATE cells). The
-  surrounding v1 INTRODUCE1 cell requires 24 octets. This leaves only 110
+  surrounding INTRODUCE1V cell requires 24 octets. This leaves only 110
   of the 498 available octets free, which must be shared between
   authorization data to the introduction point _and_ to the hidden
   service.
 
   When receiving a v3 INTRODUCE2 cell, Bob checks whether a client has
-  provided valid authorization data to him. He will only then build a
-  circuit to the provided rendezvous point and otherwise will drop the
+  provided valid authorization data to him. He also requires that the
+  timestamp is no more than 30 minutes in the past or future and that the
+  rendezvous cookie has not been used in the past 60 minutes to prevent
+  replay attacks by rogue introduction points. If all checks pass, Bob
+  builds a circuit to the provided rendezvous point and otherwise drops the
   cell.
 
-  There might be several attacks based on the idea of replaying existing
-  cells to the hidden service. In particular, someone (the introduction
-  point or an evil authenticated client) might replay valid INTRODUCE2
-  cells to make the hidden service build an arbitrary number of circuits to
-  (maybe long gone) rendezvous points. Therefore, we propose that hidden
-  services maintain a history of received INTRODUCE2 cells within the last
-  hour and only accept INTRODUCE2 cells matching the following rules:
-
-    (1) no duplicate requests coming from the same client and containing
-        the same rendezvous cookie, and
-    (2) a maximum of 10 cells coming from the same client with different
-        rendezvous cookies.
-
-  This allows a client to retry connection establishment using the same
-  rendezvous point for 3 times and a total number of 10 connection
-  establishments (not requests in the transported protocol) per hour.
-
   1.4. Summary of authorization data fields
 
   In summary, the proposed descriptor format and cell formats provide the
@@ -401,7 +386,7 @@ Details:
       - the fields intro-authorization and service-authorization in
         hidden service descriptors,
       - a maximum of 215 octets in the ESTABLISH_INTRO cell, and
-      - one part of 110 octets in the INTRODUCE1 cell.
+      - one part of 110 octets in the INTRODUCE1V cell.
 
   (3) For performing authorization at the hidden service we can use:
       - the fields intro-authorization and service-authorization in
@@ -428,91 +413,267 @@ Details:
   and is also a bad idea, because in case of HTTP the requested URL may be
   contained in the Host and Referer fields.
 
-  2. An authorization protocol based on group and user passwords
-
-  In the following we discuss an authorization protocol for the proposed
-  authorization architecture that performs authorization at the directory
-  and the hidden service, but not at the introduction point.
-  The protocol relies on a distinct asymmetric (client-key) and a
-  symmetric key (descriptor-cookie) for
-  each client. The asymmetric key replaces the service's permanent key and
-  the symmetric key is used as descriptor cookie as described above.
-
-  2.1. Client authorization at directory
-
-  The symmetric key of 128 bits length is used as descriptor cookie for
-  publishing/fetching
-  hidden service descriptors and for encrypting/decrypting the contained
-  introduction points. Further, the asymmetric key replaces the service's
-  permanent key that is used to encode and sign a v2 hidden service descriptor.
-  The result is a v2 hidden service descriptor with the following format:
-  
-      descriptor-id =
-          H(H(client-key)[:10] | H(time-period | descriptor-cookie | replica))
-      descriptor-content = {
-        descriptor-id,
-        version,
-        client-key,
-        H(time-period | descriptor-cookie | replica),
-        timestamp,
-        protocol-versions,
-        { introduction-points } encrypted with descriptor-cookie
-      } signed with private-key
-
-  Whenever a
-  server decides to remove authorization for a client, he can simply stop
-  publishing hidden service descriptors using the descriptor cookie.
-  The fact that there needs to be a separate
-  hidden service descriptor for each user leads to a large number of
-  such descriptors. However, this is the only way for a service
-  provider to remove a client's authorization without remains. We assume
-  that distributing the directory of hidden service descriptors as
-  implemented by proposal 114 provides the necessary scalability to do so.
-
-  2.2. Client authorization at introduction point
-
-  There is no need to perform authorization at the introduction point in
-  this protocol. Only authorized clients can decrypt the introduction
-  point part of a hidden service descriptor. This contains the
-  introduction key that was introduced by proposal 114 and that is required
-  to get an INTRODUCE1 cell passed at the introduction point.
-
-  2.3. Client authorization at hidden service
-
-  Authorization at the hidden service also makes use of the
-  descriptor cookie. The client include this descriptor cookie,
-  in INTRODUCE2 cells that it sends to the server.
-  The server compares authorization data of incoming INTRODUCE2 cells with
-  the locally stored value that it would expect. The authorization type
-  number of this protocol for INTRODUCE2 cells is "2".
-
-  2.4. Providing authorization data
-
-  The Tor client of a hidden service needs to know the client keys
-  and descriptor cookies of all authorized clients. We decided to
-  create a new configuration option that specifies a comma-separated list
-  of human-readable client names:
-
-  HiddenServiceAuthorizeClient client-name,client-name,...
-
-  When a hidden service is configured, the client keys and descriptor
-  cookies for all configured client names are either read from a file
-  or generated and appended to that file. The file format is:
+  1.6. Limitations for authorization protocols
+
+  There are two limitations of the current hidden service protocol for
+  authorization protocols that shall be identified here.
+
+    1. The three cell types ESTABLISH_INTRO, INTRODUCE1V, and INTRODUCE2
+       restricts the amount of data that can be used for authorization.
+       This forces authorization protocols that require per-user
+       authorization data at the introduction point to restrict the number
+       of authorized clients artifically. A possible solution could be to
+       split contents among multiple cells and reassemble them at the
+       introduction points.
+
+    2. The current hidden service protocol does not specify cell types to
+       perform interactive authorization between client and introduction
+       point or hidden service. If there should be an authorization
+       protocol that requires interaction, new cell types would have to be
+       defined and integrated into the hidden service protocol.
+
+
+  2. Specific authorization protocol instances
+
+  In the following we present three specific authorization protocols that
+  make use of (parts of) the new authorization infrastructure:
+
+    1. The first protocol does not really perform client authorization, but
+       requires clients to have downloaded a service descriptor before
+       establishing a connection in order to prevent introduction points
+       from accessing a service.
+
+    2. The second protocol allows a service provider to restrict access
+       to clients with a previously received secret key only, but does not
+       attempt to hide service activity from others.
+
+    3. The third protocol, albeit being feasible for a limited set of about
+       16 clients, performs client authorization and hides service activity
+       from everyone but the authorized clients.
+
+  These three protocol instances together are intended to replace the
+  existing hidden service protocol versions 0 and 2 in the long run and
+  shall therefore be considered hidden service protocol version 3. All
+  changes in this version 3 are designed to be fully backward-compatible to
+  version 2 and can be run in parallel to version 0.
+
+  2.1. Services without client authorization
+
+  Although hidden services without client authorization could be run as
+  before, this proposal allows us to add a new security property at almost
+  no costs: Denying the introduction points to access the hidden service.
+  While this constitutes a defense against rogue introduction points, it
+  also reduces responsibility of a Tor node operator for the doings of a
+  hidden service offering illegal or unethical contents.
+
+  The original hidden service design used the service's permanent key to
+  establish introduction points. If an introduction point wanted to access
+  the service, it could easily download the service's descriptor using its
+  permanent key ID and establish a connection or generate an INTRODUCE2
+  cell itself and forward it directly to the service.
+
+  Hidden service protocol version 2 made it more difficult for introduction
+  points to find out which service they are serving. Here, the hidden
+  service created a fresh introduction key for each introduction point
+  which 1) did not reveal the hidden service's identity and 2) did not
+  allow downloading the service's descriptor. However, the introduction
+  point could still generate an INTRODUCE2 cell itself and establish a
+  connection to the service to find out what it is serving.
+
+  Beginning with this proposal can include a so-called "introduction
+  cookie" in v2 hidden service descriptors and v3 INTRODUCE2 cells. If
+  both, service and client implement this proposal, a service receiving a
+  v3 INTRODUCE2 cell with an introduction cookie in it can be sure that the
+  client has downloaded its descriptor before. As long as hidden services
+  also permit v2 INTRODUCE2 cells, introduction points can work around this
+  safeguard. But the earlier this protocol is introduced, the earlier the
+  services can stop supporting version 2 introductions.
+
+  A hidden service generates a unique introduction cookie for each
+  established introduction point and puts it in the "intro-authentication"
+  field in its descriptor for auth-type "1". Further, the service sets the
+  "protocol-versions" field to "2,3" to announce that it understands both,
+  requests with and without introduction cookie. Clients that understand
+  protocol version 3 include the introduction cookie in the v3 INTRODUCE2
+  cell as auth-type "1" that they send to the service. (Clients that don't
+  understand the protocol v3 do not recognize the authorization data and
+  send a v2 INTRODUCE2 cell as usual.) The hidden service can compare a
+  received introduction cookie with the value that it expects and grant or
+  deny service correspondingly.
+
+  2.2. Service with large-scale client authorization
+
+  The first client authorization protocol aims at performing access control
+  while consuming as little additional resources as possible. A service
+  provider should be able to permit access to a large number of clients
+  while denying access for everyone else. However, the price for
+  scalability is that the service won't be able to hide its activity from
+  unauthorized or formerly authorized clients.
+
+  The main idea of this protocol is to encrypt the introduction-point part
+  in hidden service descriptors to authorized clients using symmetric keys.
+  This ensures that nobody else but authorized clients can learn which
+  introduction points a service currently uses, nor can someone send a
+  valid INTRODUCE1 message without knowing the introduction key. Therefore,
+  a subsequent authorization at the introduction point is not required.
+
+  A service provider generates symmetric "descriptor cookies" for his
+  clients and distributes them outside of Tor. The suggested key size is
+  128 bits, so that descriptor cookies can be encoded in 22 base64 chars
+  (which can hold up to 22 * 5 = 132 bits, leaving 4 bits to encode the
+  authorization type "2" and allow a client to distinguish this
+  authorization protocol from others like the one proposed below).
+  Typically, the contact information for a hidden service using this
+  authorization protocol looks like this:
+
+    v2cbb2l4lsnpio4q.onion Ll3X7Xgz9eHGKCCnlFH0uz
+
+  When generating a hidden service descriptor, the service encrypts the
+  introduction-point part with a single randomly generated symmetric
+  128-bit session key using AES-CTR as described for v2 hidden service
+  descriptors in rend-spec. Afterwards, the service encrypts the session
+  key to all descriptor cookies using AES.
+
+  ### What would be a simple solution to include n encrypted session keys
+  ### in the descriptor? The format may be binary and has no strict upper
+  ### size limit. An authorized client should be able to efficiently find
+  ### the session key that is encrypted for him/her. It should be
+  ### impossible to track certain authorized clients over time by finding
+  ### that the session key was encrypted for them in different descriptors.
+  ### It should be hard to determine the exact number of authorized
+  ### clients.
+  ###
+  ### Here comes the voodoo I've conceived:
+  ###
+  ###   ATYPE  Authorization type: set to 2.                      [1 octet]
+  ###   ALEN   Number of authorized clients div 16                [1 octet]
+  ### for each symmetric descriptor cookie:
+  ###   ID     Client ID: H(descriptor cookie | IV)[:4]          [4 octets]
+  ###   SKEY   Session key encrypted with descriptor cookie     [16 octets]
+  ### (end of client-specific part)
+  ###   RND    Random data  [(16 - (number-of-clients mod 16)) * 20 octets]
+  ###   IV     AES initialization vector                        [16 octets]
+  ###   IPOS   Intro points, encrypted with session key  [remaining octets]
+
+  An authorized client needs to configure Tor to use the descriptor cookie
+  when accessing the hidden service. Therefore, a user adds the contact
+  information that she received from the service provider to her torrc
+  file. Upon downloading a hidden service descriptor, Tor finds the
+  encrypted introduction-point part and attempts to decrypt it using the
+  configured descriptor cookie. (In the rare event of two or more client
+  IDs being equal a client tries to decrypt all of them.)
+
+  Upon sending the introduction, the client includes her descriptor cookie
+  as auth type "2" in the INTRODUCE2 cell that she sends to the service.
+  The hidden service checks whether the included descriptor cookie is
+  authorized to access the service and either responds to the introduction
+  request, or not.
+
+  2.3. Authorization for limited number of clients
+
+  A second, more sophisticated client authorization protocol goes the extra
+  mile of hiding service activity from unauthorized clients. With all else
+  being equal to the preceding authorization protocol, the second protocol
+  publishes hidden service descriptors for each user separately and gets
+  along with encrypting the introduction-point part of descriptors to a
+  single client. This allows the service to stop publishing descriptors for
+  removed clients. As long as a removed client cannot link descriptors
+  issued for other clients to the service, it cannot derive service
+  activity any more. The downside of this approach is limited scalability.
+  Even though the distributed storage of descriptors (cf. proposal 114)
+  tackles the problem of limited scalability to a certain extent, this
+  protocol should not be used for services with more than 16 clients. (In
+  fact, Tor should refuse to advertise services for more than this number
+  of clients.)
+
+  A hidden service generates an asymmetric "client key" and a symmetric
+  "descriptor cookie" for each client. The client key is used as
+  replacement for the service's permanent key, so that the service uses a
+  different identity for each of his clients. The descriptor cookie is used
+  to store descriptors at changing directory nodes that are unpredictable
+  for anyone but service and client, to encrypt the introduction-point
+  part, and to be included in INTRODUCE2 cells. Once the service has
+  created client key and descriptor cookie, he tells them to the client
+  outside of Tor. The contact information string looks similar to the one
+  used by the preceding authorization protocol (with the only difference
+  that it has "3" encoded as auth-type in the remaining 4 of 132 bits
+  instead of "2" as before).
+
+  When creating a hidden service descriptor for an authorized client, the
+  hidden service uses the client key and descriptor cookie to compute
+  secret ID part and descriptor ID:
+
+    secret-id-part = H(time-period | descriptor-cookie | replica)
+
+    descriptor-id = H(client-key[:10] | secret-id-part)
+
+  The hidden service also replaces permanent-key in the descriptor with
+  client-key and encrypts introduction-points with the descriptor cookie.
+
+     ATYPE  Authorization type: set to 3.                         [1 octet]
+     IV     AES initialization vector                           [16 octets]
+     IPOS   Intro points, encr. with descriptor cookie   [remaining octets]
+
+  When uploading descriptors, the hidden service needs to make sure that
+  descriptors for different clients are not uploaded at the same time (cf.
+  Section 1.1) which is also a limiting factor for the number of clients.
+
+  When a client is requested to establish a connection to a hidden service
+  it looks up whether it has any authorization data configured for that
+  service. If the user has configured authorization data for authorization
+  protocol "3", the descriptor ID is determined as described in the last
+  paragraph. Upon receiving a descriptor, the client decrypts the
+  introduction-point part using its descriptor cookie. Further, the client
+  includes its descriptor cookie as auth-type "3" in INTRODUCE2 cells that
+  it sends to the service.
+
+  2.4. Hidden service configuration
+
+  A hidden service that implements this proposal and that is meant to use
+  the new protocols (including the protocol without client authorization as
+  described in 2.1) adds version 3 to the list of supported hidden service
+  protocols:
+
+    HiddenServiceVersion version,version,... (Default: 0, 2, 3)
+
+  If the service shall perform client authorization, another config option
+  is set to either "1" for the protocol described in 2.2 or "2" for the
+  protocol in 2.3 (auth type numbers differ from the internally used
+  numbers primarily to avoid user questions about the whereabouts of auth
+  type 1). This config option also includes a comma-separated list of
+  human-readable client names, so that Tor can create authorization data
+  for these clients:
+
+    HiddenServiceAuthorizeClient auth-type client-name,client-name,...
+
+  If this option is configured, HiddenServiceVersion is automatically
+  reconfigured to contain only version numbers of 3 or higher. If this
+  config option is not set but the configured hidden service version
+  includes 3, the protocol without client authorization as described in 2.1
+  is offered to clients (possibly in parallel to versions 0 and 2).
+
+  Tor stores all generated authorization data for the authorization
+  protocols described in Sections 2.2 and 2.3 in a new file using the
+  following file format:
 
      "client-name" human-readable client identifier NL
-     "service-address" onion-address NL
      "descriptor-cookie" 128-bit key ^= 22 base64 chars NL
+
+  If the authorization protocol of Section 2.3 is used, Tor also generates
+  and stores the following data:
+
+     "service-address" client-specific-onion-address NL
      "client-key" NL a public key in PEM format
 
-  On client side, we propose to add a new configuration option that
-  contains a service name, the service identifier (H(client-key)[:10]),
-  and the descriptor cookie that are required to access a hidden service.
-  The configuration option has the following syntax:
-  
-  HidServAuth service-name service-address descriptor-cookie
-  
-  Whenever the user tries to access the given onion address, the given
-  descriptor cookie is used for authorization.
+  2.5. Client configuration
+
+  Clients need to make their authorization data known to Tor using another
+  configuration option that contains a service name (mainly for the sake of
+  convenience), the service address, and the descriptor cookie that is
+  required to access a hidden service (the authorization protocol number is
+  encoded in the descriptor cookie):
+
+    HidServAuth service-name service-address descriptor-cookie
 
 Security implications: