Merge branch 'packed_and_fragmented'

1 files changed, 325 insertions, 0 deletions

diff --git a/proposals/340-packed-and-fragmented.md b/proposals/340-packed-and-fragmented.md
new file mode 100644
index 0000000..e7f08f4
--- /dev/null
+++ b/proposals/340-packed-and-fragmented.md
@@ -0,0 +1,325 @@
+```
+Filename: 340-packed-and-fragmented.md
+Title: Packed and fragmented relay messages
+Author: Nick Mathewson
+Created: 31 May 2022
+Status: Open
+```
+
+# Introduction
+
+Tor sends long-distance messages on circuits via _relay cells_.  The
+current relay cell format allows one _relay message_ (e.g., "BEGIN" or
+"DATA" or "END") per relay cell. We want to relax this 1:1 requirement,
+between messages and cells, for two reasons:
+
+ * To support relay messages that are longer than the current 498-byte
+   limit.  Applications would include wider handshake messages for
+   postquantum crypto, UDP messages, and SNIP transfer in walking
+   onions.
+
+ * To transmit small messages more efficiently.  Several message types
+   (notably `SENDME`, `XON`, `XOFF`, and several types from
+   [proposal 329](./329-traffic-splitting.txt)) are much smaller than
+   the relay cell size, and could be sent comparatively often.
+
+In this proposal, we describe a way to decouple relay cells from relay
+messages.  Relay messages can now be packed into multiple cells or split
+across multiple cells.
+
+This proposal combines ideas from
+[proposal 319](./319-wide-everything.md) (fragmentation) and
+[proposal 325](./325-packed-relay-cells.md) (packed cells).  It requires
+[ntor v3](./332-ntor-v3-with-extra-data.md) and prepares for
+[next-generation relay cryptography](./308-counter-galois-onion).
+
+## A preliminary change: Relay encryption, version 1.5
+
+We are fairly sure that, whatever we do for our next batch of relay
+cryptography, we will want to increase the size of the data used to
+authenticate relay cells to 128 bits.  (Currently it uses a 4-byte tag
+plus 2 bytes of zeros.)
+
+To avoid proliferating formats, I'm going to suggest that we make the
+other changes in this proposal changes concurrently with a change in our
+relay cryptography, so that we do not have too many incompatible cell
+formats going on at the same time.
+
+The new format for a decrypted relay _cell_ will be:
+
+   recognized [2 bytes]
+   digest     [14 bytes]
+   body       [509 - 16 = 493 bytes]
+
+"Digest" and "recognized" are computed as before; the only difference
+is that they occur _before_ the rest of the cell, and that "digest" is
+truncated to 14 bytes instead of 4.
+
+If we are lucky, we won't have to build this encryption at all, and we
+can just move to some version of GCM-UIV or other RPRP that reserves 16
+bytes for an authentication tag or similar cryptographic object.
+
+## New relay message packing
+
+Relay _messages_ now follow the following format:
+
+  Header
+    command   u8
+    length    u16
+    stream_id u16
+  Body
+    data      u8[length]
+
+We require that "command" is never 0.
+
+Messages can be split across relay cells; multiple messages can occur in
+a single relay cell.  We enforce the following rules:
+
+  * Headers may not be split across cells.
+  * If a 0 byte follows any relay message, there are no more messages in
+    that cell.
+  * A relay cell may not be "empty": it must have at least some part of
+    some message.
+
+Unless specified elsewhere, **all** message types may be packed, and
+**all** message types may be fragmented.
+
+Every command has an associated maximum length for its messages.  If not
+specified elsewhere, the maximum length for every message is 498 bytes
+(for legacy reasons).
+
+Receivers MUST validate that headers are well-formed and have valid
+lengths while handling the cell in which the header is encoded.  If the
+header is invalid, the receiver must destroy the circuit.
+
+### Some examples
+
+
+## Negotiation
+
+This message format requires a new `Relay` subprotocol version to
+indicate support.  If a client wants to indicate support for this
+format, it sends the following extension as part of its `ntor3`
+handshake:
+
+   RELAY_PROTOCOL
+     version    u8
+
+The `version` field is the `Relay` subprotocol version that the client
+wants to use. The relay must send back the same extension in its ntor3
+handshake to acknowledge support.
+
+## Migration
+
+We add a consensus parameter, "streamed-relay-messages", with default
+value 0, minimum value 0, and maximum value 1.
+
+If this value is 0, then clients will not (by default) negotiate this
+relay protocol.  If it is 1, then clients will negotiate it when relays
+support it.
+
+For testing, clients can override this setting.  Once enough relays
+support this proposal, we'll change the consensus parameter to 1.
+Later, we'll change the default to 1 as well.
+
+## Packing decisions
+
+We specify the following greedy algorithm for making decisions about
+fragmentation and packing.  Other algorithms are possible, but this one
+is fairly simple, and using it will help avoid distinguishability
+issues:
+
+Whenever a client or relay is about to send a cell that would leave
+at least 32 bytes unused in a relay cell, it checks to see whether there
+is any pending data to be sent in the same circuit (in a data cell).  If
+there is, then it adds a DATA message to the end of the current cell,
+with as much data as possible.  Otherwise, the client sends the cell
+with no packed data.
+
+## Onion services
+
+Negotiating this for onion services will happen in a separate proposal;
+it is not a current priority, since there is nothing sent over
+rendezvous circuits that we currently need to fragment or pack.
+
+## Miscellany
+
+### Handling `RELAY_EARLY`
+
+The `RELAY_EARLY` status for a command is determined based on the relay
+cell in which the command's _header_ appeared.
+
+### Handling `SENDME`s
+
+SENDME messages may not be fragmented; the body and the command must
+appear in the same cell.  (This is necessary so authenticated sendmes
+can have a reasonable implementation.)
+
+### An exception for `DATA`.
+
+Data messages may not be fragmented.  (There is never a reason to do
+this.)
+
+### Extending message-length maxima
+
+For now, the maximum length for every message is 498 bytes, except as
+follows:
+
+   - `DATAGRAM` messages (see proposal 339) have a maximum body length
+     of 1967 bytes.  (This works out to four relay cells, and
+     accommodates most reasonable MTU choices)
+
+Any increase in maximum length for any other message type requires a new
+Relay subprotocol version.  (For example, if we later want to allow
+EXTEND2 messages to be 2000 bytes long, we need to add a new proposal
+saying so, and reserving a new subprotocol version.)
+
+# Appendix: Example cells
+
+
+Here is an example of the simplest case: one message, sent in one relay
+cell.  Here it is a BEGIN message.
+
+```
+  Cell 1:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY             [1 byte]
+    relay cell header
+       recognized     0                 [2 bytes]
+       digest         (...)             [14 bytes]
+    message header:
+       command        BEGIN             [1 byte]
+       length         23                [2 bytes]
+       stream_id      (...)             [2 bytes]
+    message body
+      "www.torproject.org:443\0"        [23 bytes]
+    end-of-messages marker
+      0                                 [1 byte]
+    padding up to end of cell
+      random                            [464 bytes]
+
+```
+
+Here's an example with fragmentation only: a large EXTEND2 message split
+across two relay cells.
+
+```
+  Cell 1:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY_EARLY       [1 byte]
+    relay cell header
+       recognized     0                 [2 bytes]
+       digest         (...)             [14 bytes]
+    message header:
+       command        EXTEND            [1 byte]
+       length         800               [2 bytes]
+       stream_id      0                 [2 bytes]
+    message body
+       (extend body, part 1)            [488 bytes]
+
+  Cell 2:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY             [1 byte]
+    relay cell header
+      recognized     0                 [2 bytes]
+      digest         (...)             [14 bytes]
+    message body, continued
+      (extend body, part 2)            [312 bytes]
+    end-of-messages marker
+      0                                [1 byte]
+    padding up to end of cell
+      random                           [180 bytes]
+
+```
+
+Here is an example with packing only: A begin_dir message and a data
+message in the same cell.
+
+```
+  Cell 1:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY             [1 byte]
+    relay cell header
+       recognized     0                 [2 bytes]
+       digest         (...)             [14 bytes]
+    message header:
+       command        BEGIN_DIR         [1 byte]
+       length         0                 [2 bytes]
+       stream_id      32                [2 bytes]
+    message body:
+       (empty)        ---               [0 bytes]
+    message header:
+       command        DATA              [1 byte]
+       length         25                [2 bytes]
+       stream_id      32                [2 bytes]
+    message body:
+       "HTTP/1.0 GET /tor/foo\r\n\r\n"  [25 bytes]
+    end-of-messages marker
+      0                                 [1 byte]
+    padding up to end of cell
+      random                            [457 bytes]
+
+```
+
+Here is an example with packing and fragmentation: a large DATAGRAM cell, a
+SENDME cell, and an XON cell.  (Note that this sequence of cells would not
+actually be generated by the algorithm described in "Packing decisions"
+above; this is only an example of what parties need to accept.)
+
+```
+  Cell 1:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY             [1 byte]
+    relay cell header
+       recognized     0                [2 bytes]
+       digest         (...)            [14 bytes]
+    message header:
+       command        DATAGRAM         [1 byte]
+       length         1200             [2 bytes]
+       stream_id      99               [2 bytes]
+    message body
+       (datagram body, part 1)         [488 bytes]
+
+  Cell 2:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY             [1 byte]
+    relay cell header
+      recognized     0                 [2 bytes]
+      digest         (...)             [14 bytes]
+    message body, continued
+      (datagram body, part 2)          [493 bytes]
+
+  Cell 3:
+    Cell header
+       circid         ..                [4 bytes]
+       command        RELAY             [1 byte]
+    relay cell header
+      recognized     0                 [2 bytes]
+      digest         (...)             [14 bytes]
+    message body, continued
+      (datagram body, part 3)          [219 bytes] (488+493+219=1200)
+    message header:
+       command        SENDME           [1 byte]
+       length         23               [2 bytes]
+       stream_id      0                [2 bytes]
+    message body:
+       version        1                [1 byte]
+       datalen        20               [2 bytes]
+       data           (digest to ack)  [20 bytes]
+    message header:
+       command        XON              [1 byte]
+       length         1                [2 bytes]
+       stream_id      50               [2 bytes]
+    message body:
+       version        1                [1 byte]
+    end-of-messages marker
+      0                                [1 byte]
+    padding up to end of cell
+      random                           [239 bytes]
+```