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