-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Nick, Roger, Lasse, Paul, and list, Nick, you wanted to have the new proposals for 0.2.1.x in until end of June. This is the first out of three proposals that I think are worth considering for 0.2.1.x. This proposal is also quite important for the NLnet project, because it exhibits the potential for major performance improvements. Certainly, it needs some discussion of anonymity and security issues. If you think that there is too little time for this discussion, we should schedule this proposal for 0.2.2.x. However, this would be a pity as it wouldn't go with the NLnet project schedule. The other two proposals that I plan to submit this week-end are minor extensions of proposals 114 and 121. Sorry for the delay in sending you these proposals; be assured that it's not just soccer that kept me from working on them. ;) Roger, are there any security/anonymity concerns about having separate introduction points that are not covered here? You once said there are issues that need to be better understood. Which are that? Lasse and Paul, I'd be particularly interested in how you like the idea of having your protocol simplification specified/implemented without valet nodes. The main reason is that valet nodes increase both protocol and implementation complexity, which inevitably leads to more bugs (as shown before...). Therefore, I'd rather leave that concept out if possible. As always, comments are highly appreciated! - --Karsten -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFIZPEv0M+WPffBEmURAoFDAJ46d35ylw6GlOrbRNVFNsvOYAoEfACgyK5J jYuEahTZuvKuc3sBNvI5lX0= =shlr -----END PGP SIGNATURE-----
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.
Attachment:
xxx-combine-intro-and-rend-points.txt.sig
Description: Binary data