commit 310780e27bb9e828bed88218597e83b262adf813 Author: Isis Lovecruft isis@torproject.org Date: Thu Sep 10 06:05:58 2015 +0000

Update prop#188 to match implementation from #7144.

* ADD a new section detailing loose-source routed circuits, including: - How the circuit should appear to the OP, the bridge, and the bridge guard, - How the hop(s) in the path is/are chosen, - How the first hop is handled and how circuit extension is handled, in a generalised sense (i.e. not specific to a bridge using bridge guards), - Which cell types are used and how they are chosen, - When the original create cell is answered (in relation to when cells are sent to the other additional hops), - What should be done when relay cells are received when the additional hops in the loose-source routed circuit are not fully constructed, - How the circuit crypto and cell digests for incoming/outgoing relay cells works (again, in a generalised sense, i.e. not specific to bridges using bridge guards), - How and whether a given relay cell is treated as "recognized", - Under what circumstances (based on whether a stream is attached and which relay command was sent) should cause a node which uses loose-source routed circuits to drop a relay cell or mark a circuit for close, and, - When and what statistics should be gathered for loose-source routed circuits.

* UPDATE and clarify the example loose-source routed circuit construction (the original one from the proposal which was specific to a client using a bridge that uses bridge guards).

* CHANGE the "Make it harder to tell clients from bridges" section which described the tradeoffs between using CREATE versus CREATE_FAST cells for the first additional hop (i.e. the bridge guard). Those concerns is no longer entirely relevant, since, in the meantime, we've introduced the NTor handshake and it's extremely likely that both the client and the bridge will use CREATE2 for all their hops.

* ADD a new section on enumerating bridges via the behaviours inherent to bridge reachability testing.

* REMOVE open question (from the very end of the proposal) regarding whether the standard guard selection algorithms are adequate. They are. (Even if they are convoluted and overly-complicated.) --- proposals/188-bridge-guards.txt | 458 +++++++++++++++++++++++++++++++-------- 1 file changed, 369 insertions(+), 89 deletions(-)

diff --git a/proposals/188-bridge-guards.txt b/proposals/188-bridge-guards.txt index 5a5a005..c4d354f 100644 --- a/proposals/188-bridge-guards.txt +++ b/proposals/188-bridge-guards.txt @@ -1,7 +1,8 @@ Filename: 188-bridge-guards.txt Title: Bridge Guards and other anti-enumeration defenses -Author: Nick Mathewson +Author: Nick Mathewson, Isis Lovecruft Created: 14 Oct 2011 +Modified: 10 Sep 2015 Status: Open

1. Overview @@ -76,111 +77,317 @@ Status: Open 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 +3.1. Loose-Source Routed Circuit Construction

- This example doesn't add anything to the design above, but has some - interesting inline notes. + Alice, an OP, is using a bridge, Bob, and she has chosen the + following path through the network:

- - 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 -> Bob -> Charlie -> Deidra

- - 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. + However, Bob has decided to take advantage of the loose-source + routing circuit characteristic (for example, in order to use a bridge + guard), and Bob has chosen N additional loose-source routed hop(s), + through which he will transparently relays cells.

- - Bob receives the RELAY_EARLY cell, and decrypts it with KB_f. - He then sees that it's an extend cell for him. + NOTE: For the purposes of bridge guards, N is always 1. However, for + completion's sake, the following details of the circuit construction + are generalized to include N > 1. Additionally, the following steps + should hold for a hop at any position in Alice's circuit that has + decided to take advantage of the loose-source routing feature, not + only for bridge ORs.

- So far, this is exactly the same as the current procedure that - Alice and Bob would follow. Now we diverge: + From Alice's perspective, her circuit path matches the one diagrammed + above. However, the overall path of the circuit is:

- - 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. + Alice -> Bob -> Guillaume -> Charlie -> Deidra

- - Now Bob encrypts the Extend cell body with KG_f and sends it - as a RELAY_EARLY cell to Guillaume. + From Bob's perspective, the circuit's path is:

- - 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. + Alice -> Bob -> Guillaume -> Charlie -> UNKNOWN

- Note that Guillaume is behaving exactly as a regular node - would upon receiving an Extend cell. + Interestingly, because Bob's behaviour towards Guillaume and choices + of cell types is that of a normal OP, Guillaume's perspective of the + circuit's path is:

- - 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). + Bob -> Guillaume -> Charlie -> UNKNOWN

- - 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. + That is, to Guillaume, Bob appears (for the most part) to be a + normally connecting client. (See §4.1 for more detailed analysis.)

- - 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. +3.1.1. Detailed Steps of Loose-Source Routed Circuit Construction

- Note that this design does not require that our stream cipher - operations be commutative, even though they are. + 1. Connection from OP

- Note also that this design requires no change in behavior from any - node other than Bob the bridge. + Alice has connected to Bob, and she has sent to Bob either a + CREATE/CREATE_FAST or CREATE2 cell.

- 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. + 2. Loose-Source Path Selection

-4. Other ideas and alternative designs + In anticipation of Alice's first RELAY_EARLY cell (which will + contain an EXTEND cell to Alice's next hop), Bob begins + constructing a loose-source routed circuit. To do so, Bob chooses + N additional hop(s):

- In addition to the design above, there are more ways to try to - prevent enumeration. + 2.a. For the first additional hop, H_1, Bob chooses a suitable + entry guard node, Guillaume, using the same algorithm as OPs. + See "§5 Guard nodes" of path-spec.txt for additional + information on the selection algorithm.

-4.1. Make it harder to tell clients from bridges + 2.b. Each additional hop, [H_2, ..., H_N], is chosen at random + from a list of suitable, non-excluded ORs.

- 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.) + 3. Loose-Source Routed Circuit Extension and Cell Types

- 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. + Bob now follows the same procedure as OPs use to complete the key + exchanges with his chosen additional hop(s).

- (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.) + While undergoing these following substeps, Bob SHOULD continue to + proceed with Step 4, below, in parallel, as an optimization for + speeding up circuit construction.

- 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. + 3.a. Create Cells + + Bob sends the appropriate type of create cell to Guillaume. + For ORs new enough to support the NTor handshake (nearly all + of them at this point), Bob sends a CREATE2 cell. Otherwise, + for ORs which only support the older TAP handshake, Bob sends + either a CREATE or CREATE_FAST cell, using the same + decision-making logic as OPs. + + See §4.1 for more information the distinguishability of + bridges based upon whether they use CREATE versus + CREATE_FAST. Also note that the CREATE2 cell has since + become ubiquitous after this proposal was originally drafted. + Thus, because we prefer ORs which use loose-source routing to + behave (as much as possible) like OPs, we now prefer to use + CREATE2. + + 3.b. Created Cells + + Later, when Bob receives a corresponding CREATED/CREATED_FAST + or CREATED2 cell from Guillaume, Bob extracts key material + for the shared forward and reverse keys, KG_f and KG_b, + respectively. + + 3.c. Extend Cells + + When N > 1, for each additional hop, H_i, in [H_2, ..., H_N], + Bob chooses the appropriate type of extend cell for H_i, and + sends this extend cell to H_i-1, who transforms it into a + create cell in order to perform the extension. To choose + which type of extend cell to send, Bob uses the same + algorithm as an OP to determine whether to use EXTEND or + EXTEND2. Similar to the CREATE* cells above, for most modern + ORs, this will very likely mean an EXTEND2 cell. + + 3.d. Extended Cells + + When a corresponding EXTENDED/EXTENDED2 cell is received for + an additional hop, H_i, Bob extracts the shared forward and + reverse keys, Ki_f and Ki_b, respectively. + + 4. Responding to the OP + + Now that the additional hops in Bob's loose-source routed circuit + are chosen, and construction of the loose-source routed circuit + has begun, Bob answers Alice's original CREATE/CREATE_FAST or + CREATE2 cell (from Step 1) by sending the corresponding created + cell type. + + Alice has now built a circuit through Bob, and the two share the + negotiated forward and reverse keys, KB_n and KB_p, respectively. + + Note that Bob SHOULD do this step in tandem with the loose-source + routed circuit construction procedure outlined in Step 3, above. + + 5. OP Circuit Extension + + 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_n and sends it as a + RELAY_EARLY cell to Bob. + + Bob's behaviour is now dependent on whether the loose-source + routed circuit construction steps (as outlined in Step 3, above) + have already completed. + + 5.a. The Loose-Source Routed Circuit Construction is Incomplete + + If Bob has not yet finished the loose-source routed circuit + construction, then Bob MUST store the first outgoing + (i.e. exitward) RELAY_EARLY cell received from Alice until + the loose-source routed circuit construction has been + completed. + + If any incoming (i.e. toward the OP) RELAY* cell is received + while the loose-source routed circuit is not fully + constructed, Bob MUST drop the cell. + + If Bob has already stored Alice's first RELAY_EARLY cell, and + Alice sends any additional RELAY* cell, then Bob SHOULD mark + the entire circuit for close with END_CIRC_REASON_TORPROTOCOL. + + 5.b. The Loose-Source Routed Circuit Construction is Completed + + Later, when the loose-source routed circuit is fully + constructed, Bob MUST send any stored cells from Alice + outward by following the procedure described in Step 6.a. + + 6. Relay Cells + + When receiving a RELAY* cell in either direction, Bob MAY keep + statistics on the number of relay cells encountered, as well as + the number of relay cells relayed. + + 6.a. Outgoing Relay Cells + + Bob decrypts the RELAY* cell with KB_n. If the cell becomes + recognized, Bob should now follow the relay command checks + described in Step 6.c. + + Bob MUST encrypt the relay cell's underlying payload to each + additional hop in the loose-source routed circuit, in + reverse: for each additional hop, H_i, in [H_N, ..., H_1], + Bob encrypts the relay cell payload to Ki_f, the shared + forward key for the hop H_i. + + Bob MUST update the forward digest, DG_f, of the relay cell, + regardless of whether or not the cell is recognized. See + 6.c. for additional information on recognized cells. + + Bob now sends the cell outwards through the additional hops. + At each hop, H_i, the hop removes a layer of the onionskin by + decrypting the cell with Ki_f, and then hop H_i forwards the + cell to the next addition additional hop H_i+1. When the + final additional hop, H_N, received the cell, the OP's cell + command and payload should be processed by H_N in the normal + manner for an OR. + + 6.b. Incoming Relay Cells + + Bob MUST decrypt the relay cell's underlying payload from + each additional hop in the loose-source routed circuit (in + forward order, this time): For each additional hop, H_i, in + [H_1, ..., H_N], Bob decrypts the relay cell payload with + Ki_b, the shared backward key for the hop H_i. + + If the cell has becomes recognized after all decryptions, Bob + should now follow the relay command checks described in Step + 6.c. + + Bob MUST update the backward digest, DG_b, of the relay cell, + regardless of whether or not the cell is recognized. See + 6.c. for additional information on recognized cells. + + Bob encrypts the cell towards the OP with KB_p, and sends the + cell inwards. + + 6.c. Recognized Cells + + If a relay cell, either incoming or outgoing, becomes + recognized (i.e. Bob sees that the cell was intended for him) + after decryption, and there is no stream attached to the + circuit, then Bob SHOULD mark the circuit for close if the + relay command contained within the cell is any of the + following types: + + - RELAY_BEGIN + - RELAY_CONNECTED + - RELAY_END + - RELAY_RESOLVE + - RELAY_RESOLVED + - RELAY_BEGIN_DIR + + Apart from the above checks, Bob SHOULD essentially treat + every cell as "unrecognized" by following the en-/de-cryption + procedures in Steps 6.a. and 6.b. regardless of whether the + cell is actually recognized or not. That is, since this is a + loose-source routed circuit, Bob SHOULD relay cells not + intended for him *and* cells intended for him through the + leaky pipe, no matter what the cell's underlying payload and + command are. + +3.1.2. Example Loose-Source Circuit Construction + + For example, given the following circuit path chosen by Alice: + + Alice -> Bob -> Charlie -> Deidra + + when Alice wishes to extend to node Charlie, and Bob the bridge is + using only one additional loose-source routed hop, Guillaume, as his + bridge guard, the following steps are taken: + + - Alice packages the extend into a RELAY_EARLY cell and encrypts + the RELAY_EARLY cell with KB_f to Bob. + + - Bob receives the RELAY_EARLY cell from Alice, and he follows + the procedure (outlined in §3.1.1. Step 6.a.) by: + + * Decrypting the cell with KB_f, + * Encrypting the cell to the forward key, KG_f, which Bob + shares with his guard node, Guillaume, + * Updating the cell forward digest, DG_f, and + * Sending the cell as a RELAY_EARLY cell to Guillaume. + + - When Guillaume receives the cell from Bob, he processes it by: + + * Decrypting the cell with KG_f. Guillaume now sees that it + is a RELAY_EARLY cell containing an extend cell "intended" + for him, containing: "Extend (Charlie's address) (Charlie's + OR Port) (Onionskin) (Charlie's ID)". + * Performing the circuit extension to the specified node, + Charlie, by acting 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". + * Making an extended cell for Bob which contains + "E(KG_b, EXTENDED g^y KH)", and + * Sending the extended cell to Bob. Note that Charlie and + Guillaume are both still behaving in a manner identical to + regular ORs. + + - Bob receives the extended cell from Guillaume, and he follows + the procedure (outlined in §3.1.1. Step 6.b.) by: + + * Decrypting the cell with KG_b, + * Encrypting the cell to Alice with KB_b, + * Updating the cell backward digest, DG_b, and + * Sending the cell to Alice. + + - Alice receives the cell, and she decrypts it with KB_b, just + as she would have if Bob had extended to Charlie directly. + She then processes the extended cell contained within to + extract shared keys with Charlie. Note that Alice's behaviour + is identical to regular OPs. + +3.2. Additional Notes on the Construction

-4.2. Client-enforced bridge guards + Note that this design does not require that our stream cipher + operations be commutative, even though they are. + + Note also that this design requires no change in behavior from any + node other than Bob, and as we can see in the above example in §3.1.2 + for Alice's circuit extension, Alice, Guillaume, and Charlie behave + identical to a normal OP and normal ORs. + + Finally, observe that even though the circuit N hops 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 RELAY_EARLY cells, then he continues to + relay Alice's cells as RELAY_EARLY, until the appropriate maximum + number of RELAY_EARLY cells is reached. Afterwards, further + RELAY_EARLY cells from Alice are repackaged by Bob as normal RELAY + cells. + +4. Alternative designs + +4.1. 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 @@ -191,7 +398,7 @@ Status: Open

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

-4.3. Separate bridge-guards and client-guards +4.2. 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 @@ -209,11 +416,84 @@ Status: Open through the bridge to a node it controls, and finding out where the extend request arrives from).

-5. Other considerations +5. Additional bridge enumeration methods and protections + + In addition to the design above, there are more ways to try to + prevent enumeration. + + 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.) + +5.1. Make it harder to tell clients from bridges + + When using the older TAP circuit handshake protocol, one of the + giveaways is that the first hop in a circuit is created with + CREATE_FAST cells, but all subsequent hops are created with CREATE + cells. + + However, because nearly everything in the network now uses the newer + NTor circuit handshake protocol, clients send CREATE2 cells to all + hops, regardless of position. Therefore, in the above design, it's + no longer quite so simple to distinguish an OP connecting through + bridge from an actual OP, since all of the circuits that extend + through a bridge now reach its guards through CREATE2 cells (whether + the bridge originated them or not), and only as a fallback (e.g. if + an additional node in the loose-source routed path does not support + NTor) will the bridge ever use CREATE/CREATE_FAST. (Additionally, + when using the fallback mathod, the behaviour for choosing either + CREATE or CREATE_FAST is identical to normal OP behaviour.) + + 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. + + [XXX For further research: we should study the methods by which a + bridge guard can determine that they are acting as a guard for a + bridge, rather than for a normal OP, and which methods are likely to + be more accurate or efficient than others. -IL] + +5.2. Bridge Reachability Testing + + Currently, a bridge's reachability is tested both by the bridge + itself (called "self-testing") and by the BridgeAuthority. + +5.2.1. Bridge Reachability Self-Testing + + Before a bridge uploads its descriptors to the BridgeAuthority, it + creates a special type of testing circuit which ends at itself: + + Bob -> Guillaume -> Charlie -> Bob + + Thus, going to all this trouble to later use loose-source routing in + order to relay Alice's traffic through Guillaume (rather than + connecting directly to Charlie, as Alice intended) is diminished by + the fact that Charlie can still passively enumerate bridges by + waiting to be asked to connect to a node which is not contained + within the consensus. + + We could get around this option by disabling self-testing for bridges + entirely, by automatically setting "AssumeReachable 1" for all bridge + relays… although I am not sure if this is wise. + +5.2.2. Bridge Reachability Testing by the BridgeAuthority + + After receiving Bob's descriptors, the BridgeAuthority attempts to + connect to Bob's ORPort by making a direct TLS connection to the + bridge's advertised ORPort. + + Should we change this behaviour? One the one hand, at least this + does not enable any random OR in the entire network to enumerate + bridges. On the other hand, any adversary who can observe packets + from the BridgeAuthority is capable of enumeration. + +6. 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?