Filename: 188-bridge-guards.txt Title: Bridge Guards and other anti-enumeration defenses Author: Nick Mathewson Created: 14 Oct 2011 Status: Open

1. Overview

Bridges are useful against censors only so long as the adversary cannot easily enumerate their addresses. I propose a design to make it harder for an adversary who controls or observes only a few nodes to enumerate a large number of bridges.

Briefly: bridges should choose guard nodes, and use the Tor protocol's "Loose source routing" feature to re-route all extend requests from clients through an additional layer of guard nodes chosen by the bridge. This way, only a bridge's guard nodes can tell that it is a bridge, and the attacker needs to run many more nodes in order to enumerate a large number of bridges.

I also discuss other ways to avoid enumeration, recommending some.

These ideas are due to a discussion at the 2011 Tor Developers' Meeting in Waterloo, Ontario. Practically none of the ideas here are mine; I'm just writing up what I remember.

2. History and Motivation

Under the current bridge design, an attacker who runs a node can identify bridges by seeing which "clients" make a large number of connections to it, or which "clients" make connections to it in the same way clients do. This has been a known attack since early versions {XXXX check} of the design document; let's try to fix it.

2.1. Related ideas: Guard nodes

The idea of guard nodes isn't new: since 0.1.1, Tor has used guard nodes (first designed as "Helper" nodes by Wright et al in {XXXX}) to make it harder for an adversary who controls a smaller number of nodes to eavesdrop on clients. The rationale was: an adversary who controls or observes only one entry and one exit will have a low probability of correlating any single circuit, but over time, if clients choose a random entry and exit for each circuit, such an adversary will eventually see some circuits from each client with a probability of 1, thereby building a statistical profile of the client's activities. Therefore, let each client choose its entry node only from among a small number of client-selected "guard" nodes: the client is still correlated with the same probability as before, but now the client has a nonzero chance of remaining unprofiled.

2.2. Related idea: Loose source routing

Since the earliest versions of Onion Routing, the protocol has provided "loose source routing". In strict source routing, the source of a message chooses every hop on the message's path. But in loose source routing, the message traverses the selected nodes, but may also traverse other nodes as well. In other words, the client selects nodes N_a, N_b, and N_c, but the message may in fact traverse any sequence of nodes N_1...N_j, so long as N_1=N_a, N_x=N_b, and N_y=N_c, for 1 < x < y.

Tor has retained this feature, but has not yet made use of it.

3. Design

Every bridge currently chooses a set of guard nodes for its circuits. Bridges should also re-route client circuits through these circuits.

Specifically, when a bridge receives a request from a client to extend a circuit, it should first create a circuit to its guard, and then relay that extend cell through the guard. The bridge should add an additional layer of encryption to outgoing cells on that circuit corresponding to the encryption that the guard will remove, and remove a layer of encryption on incoming cells on that circuit corresponding to the encryption that the guard will add.

3.1. An example

This example doesn't add anything to the design above, but has some interesting inline notes.

- Alice has connected to her bridge Bob, and built a circuit through Bob, with the negotiated forward and reverse keys KB_f and KB_r.

- Alice then wants to extend the circuit to node Charlie. She makes a hybrid-encrypted onionskin, encrypted to Charlie's public key, containing her chosen g^x value. She puts this in an extend cell: "Extend (Charlie's address) (Charlie's OR Port) (Onionskin) (Charlie's ID)". She encrypts this with KB_f and sends it as a RELAY_EARLY cell to Bob.

- Bob receives the RELAY_EARLY cell, and decrypts it with KB_f. He then sees that it's an extend cell for him.

So far, this is exactly the same as the current procedure that Alice and Bob would follow. Now we diverge:

- Instead of connecting to Charlie directly, Bob makes sure that he is connected to his guard, Guillaume. Bob uses a CREATE_FAST cell (or a CREATE cell, but see 4.1 below) to open a circuit to Guillaume. Now Bob and Guillaume share keys KG_f and KG_b.

- Now Bob encrypts the Extend cell body with KG_f and sends it as a RELAY_EARLY cell to Guillaume.

- Guillaume receives it, decrypts it with KG_f, and sees: "Extend (Charlie's address) (Charlie's OR Port) (Onionskin) (Charlie's ID)". Guillaume acts accordingly: creating a connection to Charlie if he doesn't have one, ensuring that the ID is as expected, and then sending the onionskin in a create cell on that connection.

Note that Guillaume is behaving exactly as a regular node would upon receiving an Extend cell.

- Now the handshake finishes. Charlie receives the onionskin and sends Guillaume "CREATED g^y,KH". Guillaume sends Bob "E(KG_r, EXTENDED g^y KH)". (Charlie and Guillaume are still running as regular Tor nodes do today).

- With this extend cell, and with all future relay cells received on this circuit, Bob first decrypts the cell with KG_r, then re-encrypts it with KB_r, then passes it to Alice. When Alice receives the cell, it will be just as she would have received if Bob had extended to Charlie directly.

- With all future outgoing cells that he receives from Alice, Bob first decrypts the cell with KA_f, and if the cell does not have Bob as its destination, Bob encrypts it with KG_f before passing it to Guillaume.

Note that this design does not require that our stream cipher operations be transitive, even though they are.

Note also that this design requires no change in behavior from any node other than Bob the bridge.

Finally, observe that even though the circuit is one hop longer than it would be otherwise, no relay's count of permissible RELAY_EARLY cells falls lower than it otherwise would. This is because the extra hop that Bob adds is done with a CREATE_FAST cell, and so he does not need to send any RELAY_EARLY cells not originated by Alice.

4. Other ideas and alternative designs

In addition to the design above, there are more ways to try to prevent enumeration.

4.1. Make it harder to tell clients from bridges

Right now, there are multiple ways for the node after a bridge to distinguish a circuit extended through the bridge from one originating at the bridge. (This lets the node after the bridge tell that a bridge is talking to it.)

One of the giveaways here is that the first hop in a circuit is created with CREATE_FAST cells, but all subsequent hops are created with CREATE cells. In the above design, it's no longer quite so simple to tell, since all of the circuits that extend through a bridge now reach its guards through CREATE_FAST cells, whether the bridge originated them or not.

(If we adopt a faster circuit extension algorithm -- for example, Goldberg, Stebila, and Ustaoglu's design instantiated over curve25519 -- we could also solve this issue by eliminating CREATE_FAST/CREATED_FAST entirely, which would also help our security margin a little.)

The CREATE/CREATE_FAST distinction is not the only way for a bridge's guard to tell bridges from orginary clients, however. Most importantly, a busy bridge will open far more circuits than a client would. More subtly, the timing on response from the client will be higher and more highly variable that it would be with an ordinary client. I don't think we can make bridges behave wholly indistinguishably from clients: that's why we should go with guard nodes for bridges.

4.2. Client-enforced bridge guards

What if Tor didn't have loose source routing? We could have bridges tell clients what guards to use by advertising those guard in their descriptors, and then refusing to extend circuits to any other nodes. This change would require all clients to upgrade in order to be able to use the newer bridges, and would quite possibly cause a fair amount of pain along the way.

Fortunately, we don't need to go down this path. So let's not!

4.3. Separate bridge-guards and client-guards

In the design above, I specify that bridges should use the same guard nodes for extending client circuits as they use for their own circuits. It's not immediately clear whether this is a good idea or not. Having separate sets would seem to make the two kinds of circuits more easily distinguishable (even though we already assume they are distinguishable). Having different sets of guards would also seem like a way to keep the nodes who guard our own traffic from learning that we're a bridge... but another set of nodes will learn that anyway, so it's not clear what we'd gain.

5. Other considerations

What fraction of our traffic is bridge traffic? Will this alter our circuit selection weights?

Are the current guard selection/evaluation/replacement mechanisms adequate for bridge guards, or do bridges need to get more sophisticated?