commit 4fc32990cfa29e31db04005fe35bc8e239d9fcd8 Author: David Goulet dgoulet@torproject.org Date: Fri May 24 10:05:58 2019 -0400

tor-spec: Add authenticated SENDMEs

This merges proposal 289 into tor-spec.txt.

Most of the circuit-level flow control section has been rewritten to be clearer and better detail version 0 and 1.

Closes #30365

Signed-off-by: David Goulet dgoulet@torproject.org --- proposals/289-authenticated-sendmes.txt | 2 +- tor-spec.txt | 108 ++++++++++++++++++++++++++------ 2 files changed, 89 insertions(+), 21 deletions(-)

diff --git a/proposals/289-authenticated-sendmes.txt b/proposals/289-authenticated-sendmes.txt index c9eada6..3ae9e3e 100644 --- a/proposals/289-authenticated-sendmes.txt +++ b/proposals/289-authenticated-sendmes.txt @@ -1,6 +1,6 @@ Filename: 289-authenticated-sendmes.txt Title: Authenticating sendme cells to mitigate bandwidth attacks -Author: Rob Jansen, Roger Dingledine +Author: Rob Jansen, Roger Dingledine, David Goulet Created: 2016-12-01 Status: Open

diff --git a/tor-spec.txt b/tor-spec.txt index b2b26eb..1a211bc 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -1861,32 +1861,91 @@ see tor-design.pdf.

To control a circuit's bandwidth usage, each OR keeps track of two 'windows', consisting of how many RELAY_DATA cells it is allowed to - originate (package for transmission), and how many RELAY_DATA cells - it is willing to consume (receive for local streams). These limits - do not apply to cells that the OR receives from one host and relays - to another. + originate or willing to consume. + + These two windows are respectively named: the package window (packaged for + transmission) and the deliver window (delivered for local streams). + + Because of our leaky-pipe topology, every relay on the circuit has a pair + of windows, and the OP has a pair of windows for every relay on the + circuit. These windows do not apply to relayed cells, however, and a relay + that is never used for streams will never decrement its window or cause the + client to decrement a window.

Each 'window' value is initially set based on the consensus parameter - 'circwindow' in the directory (see dir-spec.txt), or to 1000 data cells - if no 'circwindow' value is given, - in each direction (cells that are not data cells do not affect - the window). When an OR is willing to deliver more cells, it sends a - RELAY_SENDME cell towards the OP, with Stream ID zero and an empty - body. When an OR receives a RELAY_SENDME cell with stream ID zero, it - increments its packaging window. (The body SHOULD be ignored.) + 'circwindow' in the directory (see dir-spec.txt), or to 1000 data cells if + no 'circwindow' value is given. In each direction, cells that are not + RELAY_DATA cells do not affect the window. + + An OR or OP (depending on the stream direction) sends a RELAY_SENDME cell + to indicate that it is willing to receive more cells when its deliver + window goes down below a full increment (100). For example, if the window + started at 1000, it should send a RELAY_SENDME when it reaches 900. + + When an OR or OP receives a RELAY_SENDME, it increments its package window + by a value of 100 (circuit window increment) and proceeds to sending the + remaining RELAY_DATA cells. + + If a package window reaches 0, the OR or OP stops reading from TCP + connections for all streams on the corresponding circuit, and sends no more + RELAY_DATA cells until receiving a RELAY_SENDME cell. + + If a deliver window goes below 0, the circuit should be torn down. + + Starting with tor-0.4.1.1-alpha, authenticated SENDMEs are supported + (version 1, see below). This means that both the OR and OP need to remember + the rolling digest of the cell that precedes (triggers) a RELAY_SENDME. + This can be known if the package window gets to a multiple of the circuit + window increment (100). + + When the RELAY_SENDME version 1 arrives, it will contain a digest that MUST + match the one remembered. This represents a proof that the end point of the + circuit saw the sent cells. On failure to match, the circuit should be torn + down. + + To ensure unpredictability, random bytes should be added to at least one + RELAY_DATA cell within one increment window. In other word, every 100 cells + (increment), random bytes should be introduced in at least one cell. + +7.3.1 SENDME Cell Format + + A circuit-level RELAY_SENDME cell always has its StreamID=0.

- Each of these cells increments the corresponding window by 100. + An OR or OP must obey these two consensus parameters in order to know which + version to emit and accept.

- The OP behaves identically, except that it must track a packaging - window and a delivery window for every OR in the circuit. + 'sendme_emit_min_version': Minimum version to emit. + 'sendme_accept_min_version': Minimum version to accept.

- An OR or OP sends cells to increment its delivery window when the - corresponding window value falls under some threshold (900). + If a RELAY_SENDME version is received that is below the minimum accepted + version, the circuit should be closed.

- If a packaging window reaches 0, the OR or OP stops reading from - TCP connections for all streams on the corresponding circuit, and - sends no more RELAY_DATA cells until receiving a RELAY_SENDME cell. -[this stuff is badly worded; copy in the tor-design section -RD] + The RELAY_SENDME payload contains the following: + + VERSION [1 byte] + DATA_LEN [2 bytes] + DATA [DATA_LEN bytes] + + The VERSION tells us what is expected in the DATA section of length + DATA_LEN and how to handle it. The recognized values are: + + 0x00: The rest of the payload should be ignored. + + 0x01: Authenticated SENDME. The DATA section MUST contain: + + DIGEST [20 bytes] + + If the DATA_LEN value is less than 20 bytes, the cell should be + dropped and the circuit closed. If the value is more than 20 bytes, + then the first 20 bytes should be read to get the DIGEST value. + + The DIGEST is the rolling digest value from the RELAY_DATA cell that + immediately preceded (triggered) this RELAY_SENDME. This value is + matched on the other side from the previous cell sent that the OR/OP + must remember. + + If the VERSION is unrecognized or below the minimum accepted version (taken + from the consensus), the circuit should be torn down.

7.4. Stream-level flow control

@@ -2111,3 +2170,12 @@ see tor-design.pdf. Describes the padding capabilities of the relay.

"1" -- Relay supports circuit-level padding. + +9.12. "FlowCtrl" + + Describes the flow control protocol at the circuit and stream level. If + there is no FlowCtrl advertised, tor supports the unauthenticated flow + control features (version 0). + + "1" -- supports authenticated circuit level SENDMEs as of proposal 289 in + Tor 0.4.1.1-alpha.