Hi all,
We are a university research group and following is a proposal for possible optimization on Tor's rendezvous circuit design. It's not written as a formal Tor proposal yet because I want to have a discussion with the community first, get some feedbacks and make sure it does not introduce new vulnerabilities.
So please feel free to comment if you have any thoughts or find any holes :)
PS: a txt version of the proposal is attached in this mail as well.
------------------------------------------------------
The changes described in this document is focused on speeding up hidden service while at least keeping the same level of anonymity as current version provides.
Naming conventions:
HSv3: current version of hidden service protocol HS5h: hidden service protocol that uses 5 hops HS: hidden service client: The onion proxy that tries to communicate with HS HSDir: hidden service directory RP: rendezvous point
1. The 5 hops rendezvous circuit
The setup on HS side is the same as HSv3. HS picks couple introduction points and uploads the descriptor to HSDir. The main difference is how to pick the RP. In HS5h, Instead of letting the client pick whatever node it wants, both client and HS use negotiation protocol to pick a RP collaboratively.
Following is a high level description for the rendezvous circuit setup process in HS5h:
(0) client fetches descriptor for a hidden service. (1) client connects to introduction point. (2) since client and HS are connected via introduction point, they can negotiate a random number using this channel. (For more details, see [RAND_NEGO]) (3) both client and HS maps that random number to a random onion router using the same scheme, so they end up with the same node. This is the candidate RP. (4) both client and HS create a 3 hops circuit using RP as last hop. (5) RP joins the circuit originates from HS to the circuit originates from client. (6) now client and HS are connected. Because their original circuits share the same endpoint(the RP), the length of the path is 5 hops.
Improvement:
(1) Reduction in circuit setup time. Both the client and HS only build 3 hops circuit now. While In current protocol(HSv3), HS needs to build a 4 hops circuit. (2) A shorter circuit means less transmission delay. It uses only one more hop compared to HSv3's Tor2Web mode. Also the circuit length for HS5h's Tor2Web mode can be further reduced to 3 hops. (3) Less setup time on client side for the first connection. In HSv3, a client has to first setup a 3 hops circuit to RP before sending INTRODUCTION1 cell to the introduction point. While in HS5h, this process is removed.
Possible drawback:
(1) An extra step is needed: random number negotiation. This result ins more communication between two nodes and Introduction point needs to remember states for the negotiation.
We think this negotiation step will not introduce a noticeable delay to the whole process. Firstly, it reuses the connection to introduction point for both sides so it requires no extra circuits build up. Secondly, the bottle neck is circuit setup, cell/stream transmission delay is actually pretty low.
2. Negotiate random numbers between two nodes [RAND_NEGO]
H(a) here means digest of message a.
(1) client generates a random number R_a and sends the digest H(R_a) to HS (2) HS remembers H(R_a), generates a random number R_h and sends it back to the client (3) client receives R_h and sends back R_a to HS (4) HS checks R_a against H(R_a) to make sure it's not generated after client receives R_h. (5) Now both client and HS compute a shared random number using R_a and R_c. (for instance, simply add up these two number)
The negotiation protocol can be very simple here because only two parties are involved and the random number does not need to be remained secret.
Note that at step 2), if HS is able to recover R_a from H(R_a), it can take control over R_c. So to mitigate this, we can use a variant of Diffie-Hellman handshake:
(1) client generates a public key g^x and sends the digest H(g^x) to HS (2) HS remembers H(g^x), generates a public key g^y and sends it back to the client (3) client receives g^y and sends back g^x to HS (4) HS checks g^x against H(g^x) to make sure it's not generated after client receives g^y. (5) Now both client and HS compute a shared random number: R_c = g^(xy)
3. Rough anonymity analysis for HSv3 and HS5h
3.1. Assumptions, attack rules and constraints
In this section, we assume 3 hops being the minimal circuit length to keep the origin node of a circuit anonymous from the destination.
Two simple attack rules are used to remove nodes from a circuit:
1. If node A is picked by the attacker, then he can pick himself as node A. 2. If the identity of node A is known by the attacker, then he can connect directly to it.
To defense against these attack rules, following constraints need to be enforced for a circuit:
1. No one except the circuit originator can have total control over choice of all nodes on the circuit. Note that it's OK even if the originator does not have total control.
2. Identity for all nodes on the circuit, except the last hop, must remain secret. i.e. only known by circuit originator.
3.2. Why 6 hops is the minimal circuit length for HSv3
First let's begin with an ASCII graph for HSv3 rendezvous circuit:
Client -> (a1) -> (a2) -> (RP) <- (b3) <- (b2) <- (b1) <- HS
Client chooses 3 ORs: a1, a2, RP. HS chooses the other 3 ORs: b3, b2, b1.
Now consider HS as the malicious side. In order to get closer to client, the best it can do is to connect directly to RP, which reduces the circuit length to 3 hops:
Client -> (a1) -> (a2) -> (RP) <- HS
If client is the malicious side, the best it can do is to choose itself as RP, which also reduces the circuit length to 3 hops:
Client <- (b3) <- (b2) <- (b1) <- HS
Taking any node from the original 6 hops circuit will result in 2 hops circuit in either case. As noted above, 3 hops is assumed to be the minimal circuit length.
3.3. Why HS5h only needs 5 hops
HS5h makes use of the fact that the last hop of a circuit is different from all previous hops. Since last hop will be in direct contact with the destination host, its identity does not need to be remain secret. We only have to make sure the last hop cannot be determined by any malicious host at will. Otherwise the malicious side can just pick himself as last hop and thus shorten the circuit.
This is where hop negotiation come into play. A negotiated hop is guaranteed to be a random node and cannot be determined by anyone. So it can be used as the last hop for both client and HS. Since the last hop for both sides overlaps, it's effectively acting as a rendezvous point. In comparison, in HSv3, the rendezvous point is picked and controlled by the client. Therefore it can not be used as the last hop for HSs' rendezvous circuit.
Again, following is an ASCII graph for a HS5h rendezvous circuit:
Client -> (a1) -> (a2) -> (RP) <- (b2) <- (b1) <- HS
Now if the client is malicious, it can only connects directly to the RP, i.e. pick the second last hop as himself. Therefore HS can still maintain a 3 hops distance from the malicious client:
Client -> (RP) <- (b2) <- (b1) <- HS
While in HSv3, the client can pick himself as the RP.
And because this is a symmetric scheme, the same argument goes for malicious HS:
Client -> (a1) -> (a2) -> (RP) <- HS
Either cases, we maintained a 3 hops circuit.
3.4. Summary
We took 3 as the minimal circuit length because that's the default setup in Tor. The analysis should work for any number.
To generalize it, if N is the minimal circuit length, then:
1) without node negotiation, the minimal rendezvous circuit length is 2N. 2) with node negotiation, the minimal rendezvous circuit length is 2N-1.
4. Other possible speed optimization under HS5h
4.1 Optimistic rendezvous mode
Similar to optimistic_data for AP connections, we can implement optimistic_rendezvous mode under HS5h. The basic idea is to optimistically assume any picked candidate RP will be willing to act as a RP.
Since now we need to maintain state in introduction point to help with node negotiation, we can use it to communicate with HS when establishing the rendezvous circuit. So both client and HS can launch circuits to newly negotiated RP simultaneously. If this candidate RP refuses to be a rendezvous point to one side, the other side can be notified via introduction point. Then client and HS can go through the negotiation process again to pick a new candidate RP.
This mode can also be implemented under HSv3 as well. In HSv3, wait for RENDEZVOUS_ESTABLISHED cell and sending INTRODUCE1 cell has to be a sequential operation. With optimistic_rendezvous mode, this can be done in parallel.
NOTE: we need to test RENDEZVOUS_ESTABLISHED rate in real tor network. If the rate is low, then this mode will slow down the setup process instead.
To make this mode work even better, we can have all OR explicitly mark whether it is willing to be a rendezvous point in it's descriptor. This should greatly increase the success rate for receiving RENDEZVOUS_ESTABLISHED.
5. Hazards
a) How to design the scheme for mapping a random number to the same node between client and server?
This will be trivia if it's easy to synchronize node list between two onion proxy. The problem is: how much overhead will be caused by synchronizing node list (or consensus).
b) How much overhead will be introduced by maintaining state for node negotiation?
Since in HS5h, both introduction point and hidden service need to maintain state for node negotiation.
To do so, the client can send something like a negotiation identifier in the initial introduction request. Then for introduction point, it can mark the circuit from the client with this ID. For HS, it can hash the negotiation state structure into a hash table with ID as the key.
Theoretically, this overhead should be low, because the "negotiation ID" is just like rendezvous cookie.