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?
