<div>Filename: 214-longer-circids.txt</div><div>Title: Allow 4-byte circuit IDs in a new link protocol</div><div>Author: Nick Mathewson</div><div>Created: 6 Nov 2012</div><div>Status: Open</div><div><br></div><div><br></div>
<div>0. Overview</div><div><br></div><div>   Relays are running out of circuit IDs.  It's time to make the field</div><div>   bigger.</div><div><br></div><div>1. Background and Motivation</div><div><br></div><div>   Long ago, we thought that 65535 circuit IDs would be enough for anybody.</div>
<div>   It wasn't.  But our cell format in link protocols is still:</div><div><br></div><div>    Cell [512 bytes]</div><div>      CircuitID [2 bytes]</div><div>      Command [1 byte]</div><div>      Payload [509 bytes]</div>
<div><br></div><div>    Variable-length cell [Length+5 bytes]</div><div>       CircID   [4 bytes]</div><div>       Command  [1 byte]</div><div>       Length   [2 bytes]</div><div>       Payload  [Length bytes]</div><div><br>
</div><div>   This means that a relay can run out of circuit IDs pretty easily.</div><div><br></div><div>2. Design</div><div><br></div><div>   I propose a new link cell format for relays that support it.  It should</div><div>
   be:</div><div><br></div><div>    Cell [514 bytes]</div><div>       CircuitID [4 bytes]</div><div>       Command [1 byte]</div><div>       Payload [509 bytes]</div><div><br></div><div>    Variable cell (Length+7 bytes)</div>
<div>       CircID   [4 bytes]</div><div>       Command  [1 byte]</div><div>       Length   [2 bytes]</div><div>       Payload  [Length bytes]</div><div><br></div><div>   We need to keep the payload size in fixed-length cells to its current</div>
<div>   value, since otherwise the relay protocol won't work.</div><div><br></div><div>   This new cell format should be used only when the link protocol is 4.</div><div>   (To negotiation link protocol 4, both sides need to use the "v3"</div>
<div>   handshake, and include "4" in their version cells.  If version 4 or</div><div>   later is negotiated, this is the cell format to use.)</div><div><br></div><div>2.1. Better allocation of circuitID space</div>
<div><br></div><div>   In the current Tor design, circuit ID allocation is determined by</div><div>   whose RSA public key has the lower modulus.  How ridiculous!</div><div>   Instead, I propose that when the version 4 link protocol is in use,</div>
<div>   the connection initiator use the low half of the circuit ID space,</div><div>   and the responder use the low half of the circuit ID space.</div><div><br></div><div>3. Discussion</div><div><br></div><div>   * Why 4 bytes?</div>
<div><br></div><div>     Because 3 would result in an odd cell size, and 8 seems like</div><div>     overkill.</div><div><br></div><div>   * Will this be distinguishable from the v3 protocol?</div><div><br></div><div>     Yes. Anybody who knows they're seeing the Tor protocol can probably</div>
<div>     tell by the TLS record sizes which version of the protocol is in</div><div>     use.  Probably not a huge deal though; which approximate range of</div><div>     versions of Tor a client or server is running is not something</div>
<div>     we've done much to hide in the past.</div><div><br></div><div>   * Why a new link protocol and not a new cell type?</div><div><br></div><div>     Because pretty much every cell has a meaningful circuit ID.</div>
<div><br></div><div>   * Okay, why a new link protocol and not a new _set of_ cell types?</div><div><br></div><div>     Because it's a bad idea to mix short and long circIDs on the same</div><div>     channel.  (That would leak which cells go with what kind of</div>
<div>     circuits ID, potentially.)</div><div><br></div><div>   * How hard is this to implement?</div><div><br></div><div>     I wasn't sure, so I coded it up.  I've got a probably-buggy</div><div>     implementation in branch "wide_cird_ids" in my public repository.</div>
<div>     Be afraid!  More testing is needed!</div><div><br></div>