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

[Qingping Hou]

On 02/11/2014 01:53 PM, George Kadianakis wrote:
>> 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.
> 

That is a good call :) And the HS can also do the same attack after received
R_a. This is

Anyway, the point here is if the negotiated shared random number is random from
the attacker's point of view (i.e. it's the same as generating a random number
by herself), then this attack is almost the same as the following attack for HSv3:

1) attacker picks RP as herself
2) attacker sends introduction cell
3) attacker checks whether the last hop of HS circuit is controlled by her
  3.a) if yes, attack succeed, circuit is shorten to 2 hops
  3.b) if not, go back to 2)

while in HS5h:

1) attacker picks R_a and sends H(R_a)
2) attacker receives R_h
3) attacker computes shared random number and check to see if it maps to the
node she controlled
  3.a) if yes, attack succeed, circuit is shorten to 2 hops
  3.b) if not, go back to 1)

Both attacks shorten the circuit to 2 hops, and I think the only difference is
the speed of the attack here.

For HSv3, 3 messages need to be transmitted:
1. attacker -> introduction point [introduce1 cell]
2. introduction point -> HS [introduce2 cell]
3. HS -> RP [rendezvous cell]

NOTE: the RP is controlled by the attacker here.

For HS5h, 4 messages need to be transmitted:
1. attacker -> introduction point [H(R_a)]
2. introduction point -> HS [H(R_a)]
3. attacker -> introduction point [R_h]
4. introduction point -> attacker [R_h]

Even though HS5h needs to send one more message, the circuit build up time for
HSv3 (from HS to RP) will probably take longer. So maybe the attacker can
attack less frequently under HSv3.

If that's the case, then we can turn the random number generation into a
computation heavy process so it takes client longer to compute R_a and HS
longer to compute R_h. But then it causes extra load on HS.

Another random thought, if HS reuses the circuit (i.e. when we have virtual
circuit implemented), it will take attacker longer to complete an attacker
under HS5h.

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

I was thinking if the overhead of downloading consensus is not too high, we can
do the following during the random number negotiation process:

1) client sends {H(R_a), C_consensus_ver}
2) HS sends {R_h, HS_consensus_ver}

Now each side know the version of consensus from the other side, they pick the
newest one. The side with the older version will have to download the new
consensus before moving on. This can force nodes update consensus more
frequently as well.

Also, synchronizing consensus is based on the idea that we pick random RP using
the same scheme that's used in router_choose_random_node. It might be possible
to come up with a scheme to map a random number to a node with none
synchronized node list (i.e. different version of valid consensuses). But I
haven't think hard enough on this part yet ;p Will work on this in the
following days.