diff options
Diffstat (limited to 'spec/tor-spec/relay-cells.md')
-rw-r--r-- | spec/tor-spec/relay-cells.md | 219 |
1 files changed, 219 insertions, 0 deletions
diff --git a/spec/tor-spec/relay-cells.md b/spec/tor-spec/relay-cells.md new file mode 100644 index 0000000..f1f7997 --- /dev/null +++ b/spec/tor-spec/relay-cells.md @@ -0,0 +1,219 @@ +<a id="tor-spec.txt-6.1"></a> + +# Relay cells {#relay-cells} + +Within a circuit, the OP and the end node use the contents of +relay cells to tunnel end-to-end commands and TCP connections +("Streams") across circuits. End-to-end commands can be initiated +by either edge; streams are initiated by the OP. + +End nodes that accept streams may be: + +- exit relays (RELAY_BEGIN, anonymous), +- directory servers (RELAY_BEGIN_DIR, anonymous or non-anonymous), +- onion services (RELAY_BEGIN, anonymous via a rendezvous point). + +The body of each unencrypted relay cell consists of an +enveloped relay message, encoded as follows: + +| Field | Size +| ----- | ---- +| Relay command | 1 byte +| 'Recognized' | 2 bytes +| StreamID | 2 bytes +| Digest | 4 bytes +| Length | 2 bytes +| Data | Length bytes +| Padding | CELL_BODY_LEN - 11 - Length bytes + +> TODO: When we implement [prop340](../proposals/340-packed-and-fragmented.md), +> we should clarify which parts of the above are about +> the relay cell, and which are the enveloped message. + +The relay commands are: + +| Command | Identifier | Type | Description +| ------- | ---------- | ---- | ----------- +| <th>Core protocol</th> +| 1 | [BEGIN] | **F** | Open a stream +| 2 | [DATA] | **F**/**B** | Transmit data +| 3 | [END] | **F**/**B** | Close a stream +| 4 | [CONNECTED] | **B** | Stream has successfully opened +| 5 | [SENDME] | **F**/**B**, **C?** | Acknowledge traffic +| 6 | [EXTEND] | **F**, **C** | Extend a circuit with TAP (obsolete) +| 7 | [EXTENDED] | **B**, **C** | Finish extending a circuit with TAP (obsolete) +| 8 | [TRUNCATE] | **F**, **C** | Remove nodes from a circuit (unused) +| 9 | [TRUNCATED] | **B**, **C** | Report circuit truncation (unused) +| 10 | [DROP] | **F**/**B**, **C** | Long-range padding +| 11 | [RESOLVE] | **F** | Hostname lookup +| 12 | [RESOLVED] | **B** | Hostname lookup reply +| 13 | [BEGIN_DIR] | **F** | Open stream to directory cache +| 14 | [EXTEND2] | **F**, **C** | Extend a circuit +| 15 | [EXTENDED2] | **B**, **C** | Finish extending a circuit +| 16..18 | Reserved | | For UDP; see [prop339]. +| <th>Conflux</th> +| 19 | [CONFLUX_LINK][prop329] | **F**, **C** | Link circuits into a bundle +| 20 | [CONFLUX_LINKED][prop329] | **B**, **C** | Acknowledge link request +| 21 | [CONFLUX_LINKED_ACK][prop329] | **F**, **C** | Acknowledge CONFLUX_LINKED message (for timing) +| 22 | [CONFLUX_SWITCH][prop329] | **F**/**B**, **C** | Switch between circuits in a bundle +| <th>Onion services</th> +| 32 | [ESTABLISH_INTRO] | **F**, **C** | Create introduction point +| 33 | [ESTABLISH_RENDEZVOUS] | **F**, **C** | Create rendezvous point +| 34 | [INTRODUCE1] | **F**, **C** | Introduction request (to intro point) +| 35 | [INTRODUCE2] | **B**, **C** | Introduction request (to service) +| 36 | [RENDEZVOUS1] | **F**, **C** | Rendezvous request (to rendezvous point) +| 37 | [RENDEZVOUS2] | **B**, **C** | Rendezvous request (to client) +| 38 | [INTRO_ESTABLISHED] | **B**, **C** | Acknowledge ESTABLISH_INTRO +| 39 | [RENDEZVOUS_ESTABLISHED] | **B**, **C** | Acknowledge ESTABLISH_RENDEZVOUS +| 40 | [INTRODUCE_ACK] | **B**, **C** | Acknowledge INTRODUCE1 +| <th>Circuit padding</th> +| 41 | [PADDING_NEGOTIATE][circ-padding] | **F**, **C** | Negotiate circuit padding +| 42 | [PADDING_NEGOTIATED][circ-padding] | **B**, **C** | Negotiate circuit padding +| <th>Flow control</th> +| 43 | [XON][prop324] | **F**/**B** | Stream-level flow control +| 44 | [XOFF][prop324] | **F**/**B** | Stream-level flow control + +[prop324]: ../proposals/324-rtt-congestion-control.txt +[prop329]: ../proposals/329-traffic-splitting.md +[prop339]: ../proposals/339-udp-over-tor.md +[circ-padding]: ../padding-spec/circuit-level-padding.md#circuit-level-padding +[BEGIN]: ./opening-streams.md#opening +[CONNECTED]: ./opening-streams.md#opening +[DATA]: ./opening-streams.md#transmitting +[DROP]: ./opening-streams.md#transmitting +[BEGIN_DIR]: ./opening-streams.md#opening-a-directory-stream +[END]: ./closing-streams.md#closing-streams +[RESOLVE]: ./remote-hostname-lookup.md +[RESOLVED]: ./remote-hostname-lookup.md +[EXTEND]: ./create-created-cells.md#EXTEND +[EXTEND2]: ./create-created-cells.md#EXTEND +[EXTENDED]: ./create-created-cells.md#EXTEND +[EXTENDED2]: ./create-created-cells.md#EXTEND +[TRUNCATE]: ./tearing-down-circuits.md +[TRUNCATED]: ./tearing-down-circuits.md +[SENDME]: ./flow-control.md#sendme-message-format +[ESTABLISH_INTRO]: ../rend-spec/introduction-protocol.md#EST_INTRO +[INTRO_ESTABLISHED]: ../rend-spec/introduction-protocol.md#INTRO_ESTABLISHED +[INTRODUCE1]: ../rend-spec/introduction-protocol.md#SEND_INTRO1 +[INTRODUCE2]: ../rend-spec/introduction-protocol.md#PROCESS_INTRO2 +[INTRODUCE_ACK]: ../rend-spec/introduction-protocol.md#SEND_INTRO1 +[ESTABLISH_RENDEZVOUS]: ../rend-spec/rendezvous-protocol.md#EST_REND_POINT +[RENDEZVOUS_ESTABLISHED]: ../rend-spec/rendezvous-protocol.md#EST_REND_POINT +[RENDEZVOUS1]: ../rend-spec/rendezvous-protocol.md#JOIN_REND +[RENDEZVOUS2]: ../rend-spec/rendezvous-protocol.md#JOIN_REND + +- **F** (Forward): Must only be sent by the originator of the circuit. +- **B** (Backward): Must only be sent by other nodes in the circuit + back towards the originator. +- **F**/**B** (Forward or backward): May be sent in either direction. +- **C**: (Control) must have a zero-valued stream ID. + (Other commands must have a nonzero stream ID.) + +The 'recognized' field is used as a simple indication that the cell +is still encrypted. It is an optimization to avoid calculating +expensive digests for every cell. When sending cells, the unencrypted +'recognized' MUST be set to zero. + +When receiving and decrypting cells the 'recognized' will always be +zero if we're the endpoint that the cell is destined for. For cells +that we should relay, the 'recognized' field will usually be nonzero, +but will accidentally be zero with P=2^-16. + +When handling a relay cell, if the 'recognized' in field in a +decrypted relay cell is zero, the 'digest' field is computed as +the first four bytes of the running digest of all the bytes that have +been destined for this hop of the circuit or originated from this hop +of the circuit, seeded from Df or Db respectively (obtained in +[Setting circuit keys](./setting-circuit-keys.md#setting-circuit-keys)), +and including this relay cell's entire body +(taken with the digest field set to zero). Note that these digests +_do_ include the padding bytes at the end of the cell, not only those up +to "Len". If the digest is correct, the cell is considered "recognized" +for the purposes of decryption (see +[Routing relay cells](./routing-relay-cells.md#routing-relay-cells)). + +(The digest does not include any bytes from relay cells that do +not start or end at this hop of the circuit. That is, it does not +include forwarded data. Therefore if 'recognized' is zero but the +digest does not match, the running digest at that node should +not be updated, and the cell should be forwarded on.) + +All relay messages pertaining to the same tunneled stream have the same +stream ID. StreamIDs are chosen arbitrarily by the OP. No stream +may have a StreamID of zero. Rather, relay messages that affect the +entire circuit rather than a particular stream use a StreamID of zero +-- they are marked in the table above as "**C**" ([control") style +cells. (Sendme cells are marked as "sometimes control" because they +can include a StreamID or not depending on their purpose -- see +[Flow control](./flow-control.md#flow-control).) + +The 'Length' field of a relay cell contains the number of bytes in +the relay cell's body which contain the body of the message. +The remainder of +the unencrypted relay cell's body is padded with padding bytes. +Implementations +handle padding bytes of unencrypted relay cells as they do padding +bytes for other cell types; see [Cell Packet format](./cell-packet-format.md#cell-packet-format). + +<span id="relay-cell-padding">The +'Padding' field is used to make relay cell contents unpredictable, to +avoid certain attacks (see +[proposal 289](../proposals/289-authenticated-sendmes.txt) +for rationale). Implementations +SHOULD fill this field with four zero-valued bytes, followed by as many +random bytes as will fit. (If there are fewer than 4 bytes for padding, +then they should all be filled with zero.</span> + +Implementations MUST NOT rely on the contents of the 'Padding' field. + +If the relay cell is recognized but the relay command is not +understood, the cell must be dropped and ignored. Its contents +still count with respect to the digests and flow control windows, though. + +<a id="tor-spec.txt-6.1.1"></a> + +## Calculating the 'Digest' field {#digest-field} + +The 'Digest' field itself serves the purpose to check if a cell has been +fully decrypted, that is, all onion layers have been removed. Having a +single field, namely 'Recognized' is not sufficient, as outlined above. + +When ENCRYPTING a relay cell, an implementation does the following: + +```text +# Encode the cell in binary (recognized and digest set to zero) +tmp = cmd + [0, 0] + stream_id + [0, 0, 0, 0] + length + data + padding + +# Update the digest with the encoded data +digest_state = hash_update(digest_state, tmp) +digest = hash_calculate(digest_state) + +# The encoded data is the same as above with the digest field not being +# zero anymore +encoded = cmd + [0, 0] + stream_id + digest[0..4] + length + data + + padding + +# Now we can encrypt the cell by adding the onion layers ... +``` + + When DECRYPTING a relay cell, an implementation does the following: + +```text +decrypted = decrypt(cell) + +# Replace the digest field in decrypted by zeros +tmp = decrypted[0..5] + [0, 0, 0, 0] + decrypted[9..] + +# Update the digest field with the decrypted data and its digest field +# set to zero +digest_state = hash_update(digest_state, tmp) +digest = hash_calculate(digest_state) + +if digest[0..4] == decrypted[5..9] + # The cell has been fully decrypted ... +``` + +The caveat itself is that only the binary data with the digest bytes set to +zero are being taken into account when calculating the running digest. The +final plain-text cells (with the digest field set to its actual value) are +not taken into the running digest. |