Filename: 202-improved-relay-crypto.txt
Title: Two improved relay encryption protocols for Tor cells
Author: Nick Mathewson
Created: 19 Jun 2012
Status: Meta
Note: This is an important development step in improving our relay
crypto, but it doesn't actually say how to do this.
Overview:
This document describes two candidate designs for a better Tor
relay encryption/decryption protocol, designed to stymie tagging
attacks and better accord with best practices in protocol design.
My hope is that readers will examine these protocols, evaluate their
security and practicality, improve on them, and help to pick one for
implementation in Tor.
In section 1, I describe Tor's current relay crypto protocol, its
drawbacks, how it fits in with the rest of Tor, and some
requirements/desiderata for a replacement. In sections 2 and 3, I
propose two alternative replacements for this protocol. In section
4, I discuss their pros and cons.
1. Background and Motivation
1.0. A short overview of Tor's current protocols
The core pieces of the Tor protocol are the link protocol,
the circuit extend protocol, the relay protocol, and the stream
protocol. All are documented in [TorSpec].
Briefly:
- The link protocol handles all direct pairwise communication
between nodes. Everything else is transmitted over it. It
uses TLS.
- The circuit extend protocol uses public-key crypto to set up
multi-node virtual tunnels, called "circuits", from a client
through one or more nodes.
*** The relay protocol uses established circuits to communicate
from a client to a node on a circuit. That's the one we'll
be talking about here. ***
- The stream protocol is tunneled over relay protocol; clients
use it to tell servers to open anonymous TCP connections, to
send data, and so forth. Servers use it to report success or
failure opening anonymous TCP connections, to send data from
TCP connections back to clients, and so forth.
In more detail: The link protocol's job is to connect two
computers with an encrypted, authenticated stream, to
authenticate one or both of them to the other, and to provide a
channel for passing "cells" between them. The circuit extend
protocol's job is to set up circuits: persistent tunnels that
connect a Tor client to an exit node through a series of
(typically three) hops, each of which knows only the previous and
next hop, and each of which has a set of keys that they share
only with the client. Finally, the relay protocol's job is to
allow a client to communicate bidirectionally with the node(s) on
the circuit, once their shared keys have been established.
(We'll ignore the stream protocol for the rest of this document.)
Note on terminology: Tor nodes are sometimes called "servers",
"relays", or "routers". I'll use all these terms more or less
interchangeably. For simplicity's sake, I will call the party
who is constructing and using a circuit "the client" or "Alice",
even though nodes sometimes construct circuits too.
Tor's internal packets are called "cells". All the cells we deal
with here are 512 bytes long.
The nodes in a circuit are called its "hops"; most circuits are 3
hops long. This doesn't include the client: when Alice builds a
circuit through nodes Bob_1, Bob_2, and Bob_3, the first hop is
"Bob_1" and the last hop is "Bob_3".
1.1. The current relay protocol and its drawbacks
[This section describes Tor's current relay protocol. It is not a
proposal; rather it is what we do now. Sections 2 and 3 have my
proposed replacements for it.]
A "relay cell" is a cell that is generated by the client to send
to a node, or by a node to send to the client. It's called a
"relay" cell because a node that receives one may need to relay
it to the next or previous node in the circuit (or to handle the
cell itself).
A relay cell moving towards the client is called "inbound"; a
cell moving away is called "outbound".
When a relay cell is constructed by the client, the client adds one
layer of crypto for each node that will process the cell, and gives
the cell to the first node in the circuit. Each node in turn then
removes one layer of crypto, and either forwards the cell to the next
node in the circuit or acts on that cell itself.
When a relay cell is constructed by a node, it encrypts it and sends
it to the preceding node in the circuit. Each node between the
originating node and the client then encrypts the cell and passes it
back to the preceding node. When the client receives the cell, it
removes layers of crypto until it has an unencrypted cell, which it
then acts on.
In the current protocol, the body of each relay cell contains, in
its unencrypted form:
Relay command [1 byte]
Zeros [2 bytes]
StreamID [2 bytes]
Digest [4 bytes]
Length [2 bytes]
Data [498 bytes]
(This only adds up to 509 bytes. That's because the Tor link
protocol transfers 512-byte cells, and has a 3 byte overhead per
cell. Not how we would do it if we were starting over at this
point.)
At every node of a circuit, the node relaying a cell
encrypts/decrypts it with AES128-CTR. If the cell is outbound
and the "zeros" field is set to all-zeros, the node additionally
checks whether 'digest' is correct. A correct digest is the
first 4 bytes of the running SHA1 digest of: a shared secret,
concatenated with all the relay cells destined for this node on
this circuit so far, including this cell. If _that's_ true, then
the node accepts this cell. (See section 6 of [TorSpec] for full
detail; see section A.1 for a more rigorous description.)
The current approach has some actual problems. Notably:
* It permits tagging attacks. Because AES_CTR is an XOR-based
stream cipher, an adversary who controls the first node in a
circuit can XOR anything he likes into the relay cell, and
then see whether he/she encounters a correspondingly
defaced cell at some exit that he also controls.
That is, the attacker picks some pattern P, and when he
would transmit some outbound relay cell C at hop 1, he
instead transmits C xor P. If an honest exit receives the
cell, the digest will probably be wrong, and the honest exit
will reject it. But if the attacker controls the exit, he
will notice that he has received a cell C' where the digest
doesn't match, but where C' xor P _does_ have a good digest.
The attacker will then know that his two nodes are on the
same circuit, and thereby be able to link the user (whom the
first node sees) to her activities (which the last node sees).
Back when we did the Tor design, this didn't seem like a
big deal, since an adversary who controls both the first and
last node in a circuit is presumed to win already based on
traffic correlation attacks. This attack seemed strictly
worse than that, since it was trivially detectable in the
case where the attacker _didn't_ control both ends. See
section 4.4 of the Tor paper [TorDesign] for our early
thoughts here; see Xinwen Fu et al's 2009 work for a more
full explanation of the in-circuit tagging attack [XF]; and
see "The 23 Raccoons'" March 2012 "Analysis of the Relative
Severity of Tagging Attacks" mail on tor-dev (and the
ensuing thread) for a discussion of why we may want to care
after all, due to attacks that use tagging to amplify route
capture. [23R]
It also has some less practical issues.
* The digest portion is too short. Yes, if you're an attacker
trying to (say) change an "ls *" into an "rm *", you can
only expect to get one altered cell out of 2^32 accepted --
and all future cells on the circuit will be rejected with
similar probability due to the change in the running hash
-- but 1/2^32 is a pretty high success rate for crypto attacks.
* It does MAC-then-encrypt. That makes smart people cringe.
* Its approach to MAC is H(Key | Msg), which is vulnerable to
length extension attack if you've got a Merkle-Damgard hash
(which we do). This isn't relevant in practice right now,
since the only parties who see the digest are the two
parties that rely on it (because of the MAC-then-encrypt).
1.2. Some feature requirements
Relay cells can originate at the client or at a relay. Relay cells
that originate at the client are given to the first node in the
circuit, and constructed so that they will be decrypted and forwarded
by the first M-1 nodes in the circuit, and finally decrypted and
processed by the Mth node, where the client chooses M. (Usually, the
Mth node is the the last one, which will be an exit node.) Relay
cells that originate at a hop in the circuit are given to the
preceding node, and eventually delivered to the client.
Tor provides a so called "leaky pipe" circuit topology
[TorDesign]: a client can send a cell to any node in the circuit,
not just the last node. I'll try to keep that property, although
historically we haven't really made use of it.
In order to implement telescoping circuit construction (where the
circuit is built by iteratively asking the last node in the
circuit to extend the circuit one hop more), it's vital that the
last hop of the circuit be able to change.
Proposal 188 [Prop188] suggests that we implement a "bridge guards"
feature: making some (non-public) nodes insert an extra hop into
the circuit after themselves, in a way that will make it harder
for other nodes in the network to enumerate them. We
therefore want our circuits to be one-hop re-extensible: when the
client extends a circuit from Bob1 to Bob2, we want Bob1 to be
able to introduce a new node "Bob1.5" into the circuit such that
the circuit runs Alice->Bob1->Bob1.5->Bob2. (This feature has
been called "loose source routing".)
Any new approach should be able to coexist on a circuit
with the old approach. That is, if Alice wants to build a
circuit through Bob1, Bob2, and Bob3, and only Bob2 supports a
revised relay protocol, then Alice should be able to build a
circuit such that she can have Bob1 and Bob3 process each cell
with the current protocol, and Bob2 process it with a revised
protocol. (Why? Because if all nodes in a circuit needed to use
the same relay protocol, then each node could learn information
about the other nodes in the circuit from which relay protocol
was chosen. For example, if Bob1 supports the new protocol, and
sees that the old relay protocol is in use, and knows that Bob2
supports the new one, then Bob1 has learned that Bob3 is some
node that does not support the new relay protocol.)
Cell length needs to be constant as cells move through the
network. For historical reasons mentioned above in section 1.1,
the length of the encrypted part of a relay cell needs to be 509
bytes.
1.3. Some security requirements
Two adjacent nodes on a circuit can trivially tell that they are
on the same circuit, and the first node can trivially tell who
the client is. Other than that, we'd like any attacker who
controls a node on the circuit not to have a good way to learn
any other nodes, even if he/she controls those nodes. [*]
Relay cells should not be malleable: no relay should be able to
alter a cell between an honest sender and an honest recipient in
a way that they cannot detect.
Relay cells should be secret: nobody but the sender and recipient
of a relay cell should be able to learn what it says.
Circuits should resist transparent, recoverable tagging attacks:
if an attacker controls one node in a circuit and alters a relay
cell there, no non-adjacent point in the circuit should be able
to recover the relay cell as it would have received it had the
attacker not altered it.
The above properties should apply to sequences of cells too:
an attacker shouldn't be able to change what sequence of cells
arrives at a destination (for example, by removing, replaying, or
reordering one or more cells) without being detected.
(Feel free to substitute whatever formalization of the above
requirements makes you happiest, and add whatever caveats are
necessary to make you comfortable. I probably missed at least
two critical properties.)
[*] Of course, an attacker who controls two points on a circuit
can probably confirm this through traffic correlation. But
we'd prefer that the cryptography not create other, easier
ways for them to do this.
1.4. A note on algorithms
This document is deliberately agnostic concerning the choice of
cryptographic primitives -- not because I have no opinions about
good ciphers, MACs, and modes of operation -- but because
experience has taught me that mentioning any particular
cryptographic primitive will prevent discussion of anything else.
Please DO NOT suggest algorithms to use in implementing these
protocols yet. It will distract! There will be time later!
If somebody _else_ suggests algorithms to use, for goodness' sake
DON'T ARGUE WITH THEM! There will be time later!
2. Design 1: Large-block encryption
In this approach, we use a tweakable large-block cipher for
encryption and decryption, and a tweak-chaining function TC.
2.1. Chained large-block what now?
We assume the existence of a primitive that provides the desired
properties of a tweakable[Tweak] block cipher, taking blocks of any
desired size. (In our case, the block size is 509 bytes[*].)
It also takes a Key, and a per-block "tweak" parameter that plays
the same role that an IV plays in CBC, or that the counter plays
in counter mode.
The Tweak-chaining function TC takes as input a previous tweak, a
tweak chaining key, and a cell; it outputs a new tweak. Its
purpose is to make future cells undecryptable unless you have
received all previous cells. It could probably be something like
a MAC of the old tweak and the cell using the tweak chaining key
as the MAC key.
(If the initial tweak is secret, I am not sure that TC needs to
be keyed.)
[*] Some large-block cipher constructions use blocks whose size is
the multiple of some underlying cipher's block size. If we wind
up having to use one of those, we can use 496-byte blocks instead
at the cost of 2.5% wasted space.
2.2. The protocol
2.2.1. Setup phase
The circuit construction algorithm needs to produce forward and
backward keys Kf and Kb, the forward and backward tweak chaining
keys TCKf and TCKb, as well as initial tweak values Tf and Tb.
2.2.2. The cell format
We replace the "Digest" and "Zeros" fields of the cell with a
single Z-byte "Zeros" field to determine when the cell is
recognized and correctly decrypted; its length is a security
parameter.
2.2.3. The decryption operations
For a relay to handle an inbound RELAY cell, it sets Tb_next to
TC(TCKb, Tb, Cell). Then it encrypts the cell using the large
block cipher keyed with Kb and tweaked with Tb. Then it sets Tb
to Tb_next.
For a relay to handle an outbound RELAY cell, it sets Tf_next to
TC(TCKf, Tf, Cell). Then it decrypts the cell using the large
block cipher keyed with Kf and tweaked with Tf. Then it sets Tf
to Tf_next. Then it checks the 'Zeros' field on the cell;
if that field is all [00] bytes, the cell is for us.
2.3. Security discussion
This approach is fairly simple (at least, no more complex than
its primitives) and achieves some of our security goals. Because
of the large block cipher approach, any change to a cell will
render that cell undecryptable, and indistinguishable from random
junk. Because of the tweak chaining approach, if even one cell
is missed or corrupted or reordered, future cells will also
decrypt into random junk.
The tagging attack in this case is turned into a circuit-junking
attack: an adversary who tries to mount it can probably confirm
that he was indeed first and last node on a target circuit
(assuming that circuits which turn to junk in this way are rare),
but cannot recover the circuit after that point.
As a neat side observation, note that this approach improves upon
Tor's current forward secrecy, by providing forward secrecy while
circuits are still operational, since each change to the tweak
should make previous cells undecryptable if the old tweak value
isn't recoverable.
The length of Zeros is a parameter for what fraction of "random
junk" cells will potentially be accepted by a router or client.
If Zeros is Z bytes long, then junk cells will be accepted with
P < 2^-(8*Z + 7). (The '+7' is there because the top 7 bits of
the Length field must also be 0.)
There's no trouble using this protocol in a mixed circuit, where
some nodes speak the old protocol and some speak the
large-block-encryption protocol.
3. Design 2: short-MAC-and-pad
In this design, we behave more similarly to a mix-net design
(such as Mixmaster or Mixminion's headers). Each node checks a
MAC, and then re-pads the cell to its chosen length before
decoding the cell.
This design uses as a primitive a MAC and a stream cipher. It
might also be possible to use an authenticating cipher mode,
if we can find one that works like a stream cipher and allows us
to efficiently output authenticators for the stream so far.
NOTE TO AE/AEAD FANS: The encrypt-and-MAC model here could be
replaced with an authenticated encryption mode without too much
loss of generality.
3.1. The protocol
3.1.1 Setup phase
The circuit construction algorithm needs to produce forward and
backward keys Kf and Kb, forward and backward stream cipher IVs
IVf and IVb, and forward and backward MAC keys Mf and Mb.
Additionally, the circuit construction algorithm needs a way for
the client to securely (and secretly? XXX) tell each hop in the
circuit a value 'bf' for the number of bytes of MAC it should
expect on outbound cells and 'bb' for the number of bytes it
should use on cells it's generating. Each node can get a
different 'bf' and 'bb'. These values can be 0: if a node's bf
is 0, it doesn't authenticate cells; if its bb is 0, it doesn't
originate them.
The circuit construction algorithm also needs a way to tell each
the client to securely (and secretly? XXX) tell each hop in the
circuit whether it is allowed to be the final destination for
relay cells.
Set the stream Sf and the stream Sb to empty values.
3.1.2. The cell format
The Zeros and Digest field of the cell format are removed.
3.1.3. The relay operations
Upon receiving an outbound cell, a node removes the first b bytes
of the cell, and puts them aside as 'M'. The node then computes
between 0 and 2 MACs of the stream consisting of all previously
MAC'd data, plus the remainder of the cell:
If b>0 and there is a next hop, the node computes M_relay.
If this node was told to deliver traffic, or it is the last
node in the circuit so far, the node computes M_receive.
M_relay is computed as MAC(stream | "relay"); M_receive is
computed as MAC(stream | "receive").
If M = M_receive, this cell is for the node; it should process
it.
If M = M_relay, or if b == 0, this cell should be relayed.
If a MAC was computed and neither of the above cases was met,
then the cell is bogus; the node should discard it and destroy
the circuit.
The node then removes the first bf bytes of the cell, and pads the
cell at the end with bf zero bytes. Finally, the node decrypts
the whole remaining padded cell with the stream cipher.
To handle an inbound cell, the node simply does a stream cipher
with no checking.
3.1.4. Generating inbound cells.
To generate an inbound cell, a node makes a 509-bb byte RELAY
cell C, encrypts that cell with Kb, appends the encrypted cell to
Sb, and prepends M_receive(Sb) to the cell.
3.1.5. Generating outbound cells
Generating an outbound cell is harder, since we need to know what
padding the earlier nodes will generate in order to know what
padding the later nodes will receive and compute their MACs, but
we also need to know what MACs we'll send to the later nodes in
order to compute which MACs we'll send to the earlier ones.
Mixnet clients have needed to do this for ages, though, so the
algorithms are pretty well settled. I'll give one below in A.3.
3.2. Security discussion
This approach is also simple and (given good parameter choices)
can achieve our goals. The trickiest part is the algorithm that
clients must follow to package cells, but that's not so bad.
It's not necessary to check MACs on inbound traffic, because
nobody but the client can tell scrambled messages from good ones,
and the client can be trusted to keep the client's own secrets.
With this protocol, if the attacker tries to do a tagging attack,
the circuit should get destroyed by the next node in the circuit
that has a nonzero "bf" value, with probability == 1-2^-(8*bf).
(If there are further intervening honest nodes, they also have a
chance to detect the attack.)
Similarly, any attempt to replay, or reorder outbound cells
should fail similarly.
The "bf" values could reveal to each node its position in the
circuit and the client preferences, depending on how we set them;
on the other hand, having a fixed bf value would reveal to the
last node the length of the circuit. Neither option seems great.
This protocol doesn't provide any additional forward secrecy
beyond what Tor has today. We could fix that by changing our use
of the stream cipher so that instead of running in counter mode
between cells, we use a tweaked stream cipher and change the
tweak with each cell (possibly based on the unused portion of the
MAC).
This protocol does support loose source routing, so long as
no padding bytes are added by any router-added nodes.
In a circuit, every node has at least one relay cell sent to it:
even non-exit nodes get a RELAY_EXTEND cell.
4. Discussion
I'm not currently seeing a reason to strongly prefer one of these
approaches over another.
In favor of large-block encryption:
- The space overhead seems smaller: we need to use up fewer
bytes in order to get equivalent looking security.
(For example, if we want to have P < 2^64 that a cell altered
by hop 1 could be accepted by hop 2 or hop 3, *and* we want P
< 2^64 that a cell altered by hop 2 could be accepted by hop
3, the large-block approach needs about 8 bytes for the Zeros
field, whereas the short-MAC-and-pad approach needs 16 bytes
worth of MACs.)
- We get forward secrecy pretty easily.
- The format doesn't leak anything about the length of the
circuit, or limit it.
- We don't need complicated logic to set the 'b' parameters.
- It doesn't need tricky padding code.
In the favor of short-MAC-and-pad:
- All of the primitives used are much better analyzed and
understood. There's nothing esoteric there. The format
itself is similar to older, well-analyzed formats.
- Most of the constructions for the large-block-cipher approach
seem less efficient in CPU cycles than a good stream cipher
and a MAC. (But I don't want to discuss that now; see section
1.4 above!)
Unclear:
- Suppose that an attacker controls the first and last hop of a
circuit, and tries an end-to-end tagging attack. With
large-block encryption, the tagged cell and all future cells
on the circuit turn to junk after the tagging attack, with
P~~100%. With short-MAC-and-pad, the circuit is destroyed at
the second hop, with P ~~ 1- 2^(-8*bf). Is one of these
approaches materially worse for the attacker?
- Can we do better than the "compute two MACs" approach for
distinguishing the relay and receive cases of the
short-MAC-and-pad protocol?
- To what extent can we improve these protocols?
- If we do short-MAC-and-pad, should we apply the forward
security hack alluded to in section 3.2?
5. Acknowledgments
Thanks to the many reviewers of the initial drafts of this
proposal. If you can make any sense of what I'm saying, they
deserve much of the credit.
A. Formal description
Note that in all these cases, more efficient descriptions exist.
A.1. The current Tor relay protocol.
Relay cell format:
Relay command [1 byte]
Zeros [2 bytes]
StreamID [2 bytes]
Digest [4 bytes]
Length [2 bytes]
Data [498 bytes]
Circuit setup:
(Specified elsewhere; the client negotiates with each router in
a circuit the secret AES keys Kf, Kb, and the secret 'digest
keys' Df, and Db. They initialize AES counters Cf and Cb to
0. They initialize the digest stream Sf to Df, and Sb to Db.)
HELPER FUNCTION: CHECK(Cell [in], Stream [in,out]):
1. If the Zeros field of Cell is not [00 00], return False.
2. Let Cell' = Cell with its Digest field set to [00 00 00 00].
3. Let S' = Stream | Cell'.
4. If SHA1(S') = the Digest field of Cell, set Stream to S',
and return True.
5. Otherwise return False.
HELPER FUNCTION: CONSTRUCT(Cell' [in], Stream [in,out])
1. Set the Zeros and Digest field of Cell' to [00] bytes.
2. Set Stream to Stream | Cell'.
3. Construct Cell from Cell' by setting the Digest field to
SHA1(Stream), and taking all other fields as-is.
4. Return Cell.
HELPER_FUNCTION: ENCRYPT(Cell [in,out], Key [in], Ctr [in,out])
1. Encrypt Cell's contents using AES128_CTR, with key 'Key' and
counter 'Ctr'. Increment 'Ctr' by the length of the cell.
HELPER_FUNCTION: DECRYPT(Cell [in,out], Key [in], Ctr [in,out])
1. Same as ENCRYPT.
Router operation, upon receiving an inbound cell -- that is, one
sent towards the client.
1. ENCRYPT(cell, Kb, Cb)
2. Send the decrypted contents towards the client.
Router operation, upon receiving an outbound cell -- that is, one
sent away from the client.
1. DECRYPT(cell, Kf, Cf)
2. If CHECK(Cell, Sf) is true, this cell is for us. Do not
relay the cell.
3. Otherwise, this cell is not for us. Send the decrypted cell
to the next hop on the circuit, or discard it if there is no
next hop.
Router operation, to create a relay cell that will be delivered
to the client.
1. Construct a Relay cell Cell' with the relay command, length,
stream ID, and body fields set as appropriate.
2. Let Cell = CONSTRUCT(Cell', Sb).
3. ENCRYPT(Cell, Kb, Cb)
4. Send the encrypted cell towards the client.
Client operation, receiving an inbound cell.
For each hop H in a circuit, starting with the first hop and
ending (possibly) with the last:
1. DECRYPT(Cell, Kb_H, Cb_H)
2. If CHECK(Cell, Sb_H) is true, this cell was sent from hop
H. Exit the loop, and return the cell in its current
form.
If we reach the end of the loop without finding the right hop,
the cell is bogus or corrupted.
Client operation, sending an outbound cell to hop H.
1. Construct a Relay cell Cell' with the relay command, length,
stream ID, and body fields set as appropriate.
2. Let Cell = CONSTRUCT(Cell', Sf_H)
3. For i = H..1:
A. ENCRYPT(Cell, Sf_i, Cf_i)
4. Deliver Cell to the first hop in the circuit.
A.2. The large-block-cipher protocol
Same as A.1, except for the following changes.
The cell format is now:
Zeros [Z bytes]
Length [2 bytes]
StreamID [2 bytes]
Relay command [1 byte]
Data [504-Z bytes]
Ctr is no longer a counter, but a Tweak value.
Each key is now a tuple of (Key_Crypt, Key_TC)
Streams are no longer used.
HELPER FUNCTION: CHECK(Cell [in], Stream [in,out])
1. If the Zeros field of Cell contains only [00] bytes,
return True.
2. Otherwise return false.
HELPER FUNCTION: CONSTRUCT(Cell' [in], Stream [in,out])
1. Let Cell be Cell', with its "Zeros" field set to Z [00]
bytes.
2. Return Cell'.
HELPER FUNCTION: ENCRYPT(Cell [in,out], Key [in], Tweak [in,out])
2. Encrypt Cell using Key and Tweak
1. Let Tweak' = TC(Key_TC, Tweak, Cell)
3. Set Tweak to Tweak'.
HELPER FUNCTION: DECRYPT(Cell [in,out], Key [in], Tweak [in,out])
1. Let Tweak' = TC(Key_TC, Tweak, Cell)
2. Decrypt Cell using Key and Tweak
3. Set Tweak to Tweak'.
A.3. The short-MAC-and-pad protocol.
Define M_relay(K,S) as MAC(K, S|"relay").
Define M_receive(K,S) as MAC(K, S|"receive").
Define Z(n) as a series of n [00] bytes.
Define BODY_LEN as 509
The cell message format is now:
Relay command [1 byte]
StreamID [2 bytes]
Length [2 bytes]
Data [variable bytes]
Helper function: CHECK(Cell [in], b [in], K [in], S [in,out]):
Let M = Cell[0:b]
Let Rest = Cell[b:...]
If b == 0:
Return (nil, Rest)
Let S' = S | Rest
If M == M_relay(K,S')[0:b]:
Set S = S'
Return ("relay", Rest)
If M == M_receive(K,S')[0:b]:
Set S = S'
Return ("receive", Rest)
Return ("BAD", nil)
HELPER_FUNCTION: ENCRYPT(Cell [in,out], Key [in], Ctr [in,out])
1. Encrypt Cell's contents using AES128_CTR, with key 'Key' and
counter 'Ctr'. Increment 'Ctr' by the length of the cell.
HELPER_FUNCTION: DECRYPT(Cell [in,out], Key [in], Ctr [in,out])
1. Same as ENCRYPT.
Router operation, upon receiving an inbound cell:
1. ENCRYPT(cell, Kb, Cb)
2. Send the decrypted contents towards the client.
Router operation, upon receiving an outbound cell:
1. Let Status, Msg = CHECK(Cell, bf, Mf, Sf)
2. If Status == "BAD", drop the cell and destroy the circuit.
3. Let Cell' = Msg | Z(BODY_LEN - len(Msg))
4. DECRYPT(Cell', Kf, Cf) [*]
5. If Status == "receive" or (Status == nil and there is no
next hop), Cell' is for us: process it.
6. Otherwise, send Cell' to the next node.
Router operation, sending a cell towards the client:
1. Let Body = a relay cell body of BODY_LEN-bb_i bytes.
2. Let Cell' = ENCRYPT(Body, Kb, Cb)
3. Let Sb = Sb | Cell'
4. Let M = M_receive(Mb, Sb)[0:b]
5. Send the cell M | Cell' back towards the client.
Client operation, upon receiving an inbound cell:
For each hop H in the circuit, from first to last:
1. Let Status, Msg = CHECK(Cell, bb_i, Mb_i, Sb_i)
2. If Status = "relay", drop the cell and destroy
the circuit. (BAD is okay; it means that this hop didn't
originate the cell.)
3. DECRYPT(Msg, Kb_i, Cb_i)
4. If Status = "receive", this cell is from hop i; process
it.
5. Otherwise, set Cell = Msg.
Client operation, sending an outbound cell:
Let BF = the total of all bf_i values.
1. Construct a relay cell body Msg of BODY_LEN-BF bytes.
2. For each hop i, let Stream_i = ENCRYPT(Kf_i,Z(CELL_LEN),Cf_i)
3. Let Pad_0 = "".
4. For i in range 1..N, where N is the number of hops:
Let Pad_i = Pad_{i-1} | Z(bf_i)
Let S_last = the last len(Pad_i) bytes of Stream_i.
Let Pad_i = Pad_i xor S_last
Now Pad_i is the padding as it will stand after node i
has processed it.
5. For i in range N..1, where N is the number of hops:
If this is the last hop, let M_* = M_receive. Else let
M_* = M_relay.
Let Body = Msg xor the first len(Msg) bytes of Stream_i
Let M = M_*(Mf, Body | Pad_(i-1))
Set Msg = M[:bf_i] | Body
6. Send Msg outbound to the first relay in the circuit.
[*] Strictly speaking, we could omit the pad-and-decrypt
operation once we know we're the final hop.
R. References
[Prop188] Tor Proposal 188: Bridge Guards and other anti-enumeration defenses
https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/188-bridge-guards.txt
[TorSpec] The Tor Protocol Specification
https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=tor-spec.txt
[TorDesign] Dingledine et al, "Tor: The Second Generation Onion
Router",
https://svn.torproject.org/svn/projects/design-paper/tor-design.pdf
[Tweak] Liskov et al, "Tweakable Block Ciphers",
http://www.cs.berkeley.edu/~daw/papers/tweak-crypto02.pdf
[XF] Xinwen Fu et al, "One Cell is Enough to Break Tor's Anonymity"
[23R] The 23 Raccoons, "Analysis of the Relative Severity of Tagging
Attacks" http://archives.seul.org/or/dev/Mar-2012/msg00019.html
(You'll want to read the rest of the thread too.)