[tor-dev] [Discussion] 5 hops rendezvous circuit design

[George Kadianakis]

Qingping Hou <dave2008713 at gmail.com> writes:

> 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.
>

I only quickly skimmed the proposal but it looks interesting.

Particularly so as I'm not aware of many proposals that improve the
performance of HSes.

A few comments below.

> So please feel free to comment if you have any thoughts or find any holes :)
>
> <snip>
>
> 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.
>

This seems to suffer from the same early-abort issue that the #8244
commit-and-reveal solution suffers from
(https://lists.torproject.org/pipermail/tor-dev/2013-November/005878.html).

For example, in this specific protocol, the attacker establishes a
channel to the HS, sends her H(R_a) and receives R_h. The attacker
then calculates 'R_a + R_h' and if the result does not point to an
attacker controlled RP, she aborts the protocol. Then she reconnects
and does the same thing again, till she gets a result that is
convenient for her.

>     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:
>

Yes, this is indeed a problem if the random numbers are small (for
example, in [0, <number of ORs>]). A key exchange makes sense here. I
I wonder if there are cheaper solutions that don't involve "expensive"
operations like modular exponentiations

>     (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).
>

Yes, this seems like a central problem to this proposal. Both parties
will probably have to negotiate their consensus version in the
beginning of the protocol to avoid ambiguities later on (since an
attacker can choose between multiple valid consensus versions that
might be convenient for him).