1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
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.
|
