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

Tue Feb 11 16:55:05 UTC 2014

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.

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