Request for comments: tor protocol overhaul

[Roger Dingledine]

Here's our newer version (ignore the previous version). The main
changes are:
a) We've changed terminology
b) We've simplified sendmes a lot. Now they might actually work.
c) We've left out the malleability issue for now. There are plenty of
   problems there, but it's not solved yet, and we've got enough to tackle
   for now.

1. Motivation: what does this buy us?
============================================================
First, we can now handle exit policies more easily -- allowing a new
exit connection to something our current exit doesn't allow means just
adding one more hop to the path, not building a whole new path.

Second, when we want change exit points to keep a website from
trivially linking requests, we can do so by changing only the last hop
on the path, which is much cheaper than changing the entire path.

Third, we can partially obscure from the intermediate nodes when we're
changing our exit points. By making circuit-extend cells indistinguishable
from data cells except at the end of the circuit, we no longer have
easily trackable create cells that lay an entire circuit at once; and we
can tear down circuits incrementally as well. So we can consider mixing,
delaying, etc all data cells, without having the circuit-creation process
be the weak point.

Fourth, our signaling system can support long-range dummies (cells that
are only distinguishable from normal data at their last hop).

Fifth, we don't have to track onions for replay anymore.

Sixth, we get forward anonymity: the keys at each hop are ephemeral,
so an adversary who owns a node in the path can't record the stream,
then arrive at each successive hop and demand the stream's decryption.

2. Terminology shift
=====================

OR-to-OR and OP-to-OR connections are now called "pipes". OR-to-OR can
also be "thick pipes".

Paths through the network are still called "circuits".

Cells are still "cells."

"Connection" has no special meaning on its own.

User-to-OP connections and OR-exit connections are both "edge
connections".

"Topics" are now identifiers for "end-to-end streams", or "streams".

Cells that get passed along and decrypted are "relay" cells.  Other
cells are "link" or "control" cells.

3. Changes to cell structure/handling
============================================================
Relay cells have the following payload structure:

   Relay command  [1 byte]
   Stream ID      [8 bytes]
   Payload        [248-1-8=239 bytes]

Because every node in a circuit can now be an exit node, ORs now need
a way to recognize when a relay cell is intended for them. They do
this by checking the Stream ID field: if (after decrypting the cell)
the node recognizes the Stream ID, the relay cell is intended for that
node's use. Otherwise, the node passes the cell to the next node on the
circuit as before.

The Stream ID "zero" (0x0000000000000000) is used for control messages
not attached to a particular end-to-end stream. The zero Stream ID is
always treated as "recognized".

Rather than decrypting relay cells repeatedly with all known keys, the OP
must now check after each decryption to see whether the Stream ID matches
a known Stream ID for the corresponding node.

If a stream ID is accidentally matched even once in a circuit, the whole
circuit is screwed. But 64 bits of stream ID to prevent accidental
matching is plenty. Consider 8 hops to a path and 7 exit connections
per hop. That's 64 possible patterns that might accidentally match at
each cell. We're still looking at 58 bits of security -- so we expect
the first collision to occur after around 2^66 bytes of data.

4. Extending a circuit
============================================================
We use a new relay command, "EXTEND" (value 5) to request that the last
node on a circuit extend the circuit by a single node. The stream ID of
this cell must be zero. The payload should contain:
         Port    [2 bytes]
         Address [4 bytes]
         Onion skin [208 bytes]

Upon receiving an EXTEND relay cell, the last node in the circuit
extracts the port and address portions of the cell, and finds (or opens)
a connection to the next node on the circuit. It then chooses a fresh
ACI, and sends a CREATE cell to that node, with the contents of the
"onion skin" as the payload.

Because we're using single onion layers now (rather than full onions),
we use a different format for the onion. With Diffie-Helman key
agreement, the onion skin contains:

        Symmetric key [16 bytes]
        g^X           [192 bytes]

The first 128 bytes of the skin are encrypted with the node's RSA key. The
rest is encrypted with the symmetric key. We don't need OAEP, because
all bytes of g^X are needed, so attacks against RSA won't influence the
session key.

Upon receiving a create cell, an OR allocates a new circuit with the
provided ACI, and (at its convenience) decrypts the skin and completes
the Diffie-Hellman key agreement by generating g^Y and g^XY. For future
relay cells, the node will use the last 16 bytes of g^XY as the forward
key, and the next-to-last sixteen bytes as the back key. Kudos to Adam
Back for suggesting the idea of an ephemeral key exchange with each hop.

Once it has completed the DH calculation, the OR replies with
an *unencrypted* relay cell, with Relay Command "EXTENDED"
(value 6), Stream ID zero, and contents equal to g^Y.  Once the
OP has received g^Y, it can compute g^XY, and will now share
forward and reverse keys.

5. Truncating a circuit
============================================================
We introduce a "TRUNCATE" (value 7) relay command, with Stream ID zero,
that causes the receiving node to send a DESTROY cell to the next node
in the circuit, and send an acknowledging "TRUNCATED" relay cell (value 8)
back towards the OP.

Also, a node must deliver a TRUNCATED relay cell backward for each
circuit (and a DESTROY cell forward for each circuit) when its forward
connection to another node closes. Thus when an onion router goes
down only the streams at that router or beyond are affected (so the
kill-a-node-and-watch-who-closes attack is less helpful).

6. Flow control
============================================================
Stream-level flow control is still all set. We're only worried
here about circuit-level flow control. Circuit-level sendmes used
to serve two functions: a) letting a node know that he's allowed
to initiate new data relay cells on that circuit, and b) letting the
intermediate nodes know that they're allowed to receive more relay
cells. We do away with b), because providing a) is good enough.

Only Alice is able to initiate forward data relay cells. Any node might be
able to initiate data relay cells backward, if it has an exit connection.

We introduce sendme relay cells. When a given node in the circuit has
consumed 100 data relay cells (total on all streams that end at that
node), he sends a sendme relay cell back to Alice, using a stream ID
of 0. Similarly, when Alice has consumed 100 data relay cells that all
originate from the same node on that circuit, she sends a sendme relay
cell forward to that node.

Only when a sendme ends at Bobn or Alice can that node initiate more
cells.

So each Bob keeps two windows: one for how many cells he can initiate,
and another for how many he can consume. Alice has to remember each
Bob's windows (she can store them in the cpath info, where the per-hop
ciphers already live). It looks like the cpath might have to store data
cell queues also, for when we've got a data cell destined for a node
whose circuit window is empty.