100-tor-spec-udp.txt 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424
  1. Filename: 100-tor-spec-udp.txt
  2. Title: Tor Unreliable Datagram Extension Proposal
  3. Version: $Revision$
  4. Last-Modified: $Date$
  5. Author: Marc Liberatore
  6. Created: 23 Feb 2006
  7. Status: Dead
  8. Overview:
  9. This is a modified version of the Tor specification written by Marc
  10. Liberatore to add UDP support to Tor. For each TLS link, it adds a
  11. corresponding DTLS link: control messages and TCP data flow over TLS, and
  12. UDP data flows over DTLS.
  13. This proposal is not likely to be accepted as-is; see comments at the end
  14. of the document.
  15. Contents
  16. 0. Introduction
  17. Tor is a distributed overlay network designed to anonymize low-latency
  18. TCP-based applications. The current tor specification supports only
  19. TCP-based traffic. This limitation prevents the use of tor to anonymize
  20. other important applications, notably voice over IP software. This document
  21. is a proposal to extend the tor specification to support UDP traffic.
  22. The basic design philosophy of this extension is to add support for
  23. tunneling unreliable datagrams through tor with as few modifications to the
  24. protocol as possible. As currently specified, tor cannot directly support
  25. such tunneling, as connections between nodes are built using transport layer
  26. security (TLS) atop TCP. The latency incurred by TCP is likely unacceptable
  27. to the operation of most UDP-based application level protocols.
  28. Thus, we propose the addition of links between nodes using datagram
  29. transport layer security (DTLS). These links allow packets to traverse a
  30. route through tor quickly, but their unreliable nature requires minor
  31. changes to the tor protocol. This proposal outlines the necessary
  32. additions and changes to the tor specification to support UDP traffic.
  33. We note that a separate set of DTLS links between nodes creates a second
  34. overlay, distinct from the that composed of TLS links. This separation and
  35. resulting decrease in each anonymity set's size will make certain attacks
  36. easier. However, it is our belief that VoIP support in tor will
  37. dramatically increase its appeal, and correspondingly, the size of its user
  38. base, number of deployed nodes, and total traffic relayed. These increases
  39. should help offset the loss of anonymity that two distinct networks imply.
  40. 1. Overview of Tor-UDP and its complications
  41. As described above, this proposal extends the Tor specification to support
  42. UDP with as few changes as possible. Tor's overlay network is managed
  43. through TLS based connections; we will re-use this control plane to set up
  44. and tear down circuits that relay UDP traffic. These circuits be built atop
  45. DTLS, in a fashion analogous to how Tor currently sends TCP traffic over
  46. TLS.
  47. The unreliability of DTLS circuits creates problems for Tor at two levels:
  48. 1. Tor's encryption of the relay layer does not allow independent
  49. decryption of individual records. If record N is not received, then
  50. record N+1 will not decrypt correctly, as the counter for AES/CTR is
  51. maintained implicitly.
  52. 2. Tor's end-to-end integrity checking works under the assumption that
  53. all RELAY cells are delivered. This assumption is invalid when cells
  54. are sent over DTLS.
  55. The fix for the first problem is straightforward: add an explicit sequence
  56. number to each cell. To fix the second problem, we introduce a
  57. system of nonces and hashes to RELAY packets.
  58. In the following sections, we mirror the layout of the Tor Protocol
  59. Specification, presenting the necessary modifications to the Tor protocol as
  60. a series of deltas.
  61. 2. Connections
  62. Tor-UDP uses DTLS for encryption of some links. All DTLS links must have
  63. corresponding TLS links, as all control messages are sent over TLS. All
  64. implementations MUST support the DTLS ciphersuite "[TODO]".
  65. DTLS connections are formed using the same protocol as TLS connections.
  66. This occurs upon request, following a CREATE_UDP or CREATE_FAST_UDP cell,
  67. as detailed in section 4.6.
  68. Once a paired TLS/DTLS connection is established, the two sides send cells
  69. to one another. All but two types of cells are sent over TLS links. RELAY
  70. cells containing the commands RELAY_UDP_DATA and RELAY_UDP_DROP, specified
  71. below, are sent over DTLS links. [Should all cells still be 512 bytes long?
  72. Perhaps upon completion of a preliminary implementation, we should do a
  73. performance evaluation for some class of UDP traffic, such as VoIP. - ML]
  74. Cells may be sent embedded in TLS or DTLS records of any size or divided
  75. across such records. The framing of these records MUST NOT leak any more
  76. information than the above differentiation on the basis of cell type. [I am
  77. uncomfortable with this leakage, but don't see any simple, elegant way
  78. around it. -ML]
  79. As with TLS connections, DTLS connections are not permanent.
  80. 3. Cell format
  81. Each cell contains the following fields:
  82. CircID [2 bytes]
  83. Command [1 byte]
  84. Sequence Number [2 bytes]
  85. Payload (padded with 0 bytes) [507 bytes]
  86. [Total size: 512 bytes]
  87. The 'Command' field holds one of the following values:
  88. 0 -- PADDING (Padding) (See Sec 6.2)
  89. 1 -- CREATE (Create a circuit) (See Sec 4)
  90. 2 -- CREATED (Acknowledge create) (See Sec 4)
  91. 3 -- RELAY (End-to-end data) (See Sec 5)
  92. 4 -- DESTROY (Stop using a circuit) (See Sec 4)
  93. 5 -- CREATE_FAST (Create a circuit, no PK) (See Sec 4)
  94. 6 -- CREATED_FAST (Circuit created, no PK) (See Sec 4)
  95. 7 -- CREATE_UDP (Create a UDP circuit) (See Sec 4)
  96. 8 -- CREATED_UDP (Acknowledge UDP create) (See Sec 4)
  97. 9 -- CREATE_FAST_UDP (Create a UDP circuit, no PK) (See Sec 4)
  98. 10 -- CREATED_FAST_UDP(UDP circuit created, no PK) (See Sec 4)
  99. The sequence number allows for AES/CTR decryption of RELAY cells
  100. independently of one another; this functionality is required to support
  101. cells sent over DTLS. The sequence number is described in more detail in
  102. section 4.5.
  103. [Should the sequence number only appear in RELAY packets? The overhead is
  104. small, and I'm hesitant to force more code paths on the implementor. -ML]
  105. [There's already a separate relay header that has other material in it,
  106. so it wouldn't be the end of the world to move it there if it's
  107. appropriate. -RD]
  108. [Having separate commands for UDP circuits seems necessary, unless we can
  109. assume a flag day event for a large number of tor nodes. -ML]
  110. 4. Circuit management
  111. 4.2. Setting circuit keys
  112. Keys are set up for UDP circuits in the same fashion as for TCP circuits.
  113. Each UDP circuit shares keys with its corresponding TCP circuit.
  114. [If the keys are used for both TCP and UDP connections, how does it
  115. work to mix sequence-number-less cells with sequenced-numbered cells --
  116. how do you know you have the encryption order right? -RD]
  117. 4.3. Creating circuits
  118. UDP circuits are created as TCP circuits, using the *_UDP cells as
  119. appropriate.
  120. 4.4. Tearing down circuits
  121. UDP circuits are torn down as TCP circuits, using the *_UDP cells as
  122. appropriate.
  123. 4.5. Routing relay cells
  124. When an OR receives a RELAY cell, it checks the cell's circID and
  125. determines whether it has a corresponding circuit along that
  126. connection. If not, the OR drops the RELAY cell.
  127. Otherwise, if the OR is not at the OP edge of the circuit (that is,
  128. either an 'exit node' or a non-edge node), it de/encrypts the payload
  129. with AES/CTR, as follows:
  130. 'Forward' relay cell (same direction as CREATE):
  131. Use Kf as key; decrypt, using sequence number to synchronize
  132. ciphertext and keystream.
  133. 'Back' relay cell (opposite direction from CREATE):
  134. Use Kb as key; encrypt, using sequence number to synchronize
  135. ciphertext and keystream.
  136. Note that in counter mode, decrypt and encrypt are the same operation.
  137. [Since the sequence number is only 2 bytes, what do you do when it
  138. rolls over? -RD]
  139. Each stream encrypted by a Kf or Kb has a corresponding unique state,
  140. captured by a sequence number; the originator of each such stream chooses
  141. the initial sequence number randomly, and increments it only with RELAY
  142. cells. [This counts cells; unlike, say, TCP, tor uses fixed-size cells, so
  143. there's no need for counting bytes directly. Right? - ML]
  144. [I believe this is true. You'll find out for sure when you try to
  145. build it. ;) -RD]
  146. The OR then decides whether it recognizes the relay cell, by
  147. inspecting the payload as described in section 5.1 below. If the OR
  148. recognizes the cell, it processes the contents of the relay cell.
  149. Otherwise, it passes the decrypted relay cell along the circuit if
  150. the circuit continues. If the OR at the end of the circuit
  151. encounters an unrecognized relay cell, an error has occurred: the OR
  152. sends a DESTROY cell to tear down the circuit.
  153. When a relay cell arrives at an OP, the OP decrypts the payload
  154. with AES/CTR as follows:
  155. OP receives data cell:
  156. For I=N...1,
  157. Decrypt with Kb_I, using the sequence number as above. If the
  158. payload is recognized (see section 5.1), then stop and process
  159. the payload.
  160. For more information, see section 5 below.
  161. 4.6. CREATE_UDP and CREATED_UDP cells
  162. Users set up UDP circuits incrementally. The procedure is similar to that
  163. for TCP circuits, as described in section 4.1. In addition to the TLS
  164. connection to the first node, the OP also attempts to open a DTLS
  165. connection. If this succeeds, the OP sends a CREATE_UDP cell, with a
  166. payload in the same format as a CREATE cell. To extend a UDP circuit past
  167. the first hop, the OP sends an EXTEND_UDP relay cell (see section 5) which
  168. instructs the last node in the circuit to send a CREATE_UDP cell to extend
  169. the circuit.
  170. The relay payload for an EXTEND_UDP relay cell consists of:
  171. Address [4 bytes]
  172. TCP port [2 bytes]
  173. UDP port [2 bytes]
  174. Onion skin [186 bytes]
  175. Identity fingerprint [20 bytes]
  176. The address field and ports denote the IPV4 address and ports of the next OR
  177. in the circuit.
  178. The payload for a CREATED_UDP cell or the relay payload for an
  179. RELAY_EXTENDED_UDP cell is identical to that of the corresponding CREATED or
  180. RELAY_EXTENDED cell. Both circuits are established using the same key.
  181. Note that the existence of a UDP circuit implies the
  182. existence of a corresponding TCP circuit, sharing keys, sequence numbers,
  183. and any other relevant state.
  184. 4.6.1 CREATE_FAST_UDP/CREATED_FAST_UDP cells
  185. As above, the OP must successfully connect using DTLS before attempting to
  186. send a CREATE_FAST_UDP cell. Otherwise, the procedure is the same as in
  187. section 4.1.1.
  188. 5. Application connections and stream management
  189. 5.1. Relay cells
  190. Within a circuit, the OP and the exit node use the contents of RELAY cells
  191. to tunnel end-to-end commands, TCP connections ("Streams"), and UDP packets
  192. across circuits. End-to-end commands and UDP packets can be initiated by
  193. either edge; streams are initiated by the OP.
  194. The payload of each unencrypted RELAY cell consists of:
  195. Relay command [1 byte]
  196. 'Recognized' [2 bytes]
  197. StreamID [2 bytes]
  198. Digest [4 bytes]
  199. Length [2 bytes]
  200. Data [498 bytes]
  201. The relay commands are:
  202. 1 -- RELAY_BEGIN [forward]
  203. 2 -- RELAY_DATA [forward or backward]
  204. 3 -- RELAY_END [forward or backward]
  205. 4 -- RELAY_CONNECTED [backward]
  206. 5 -- RELAY_SENDME [forward or backward]
  207. 6 -- RELAY_EXTEND [forward]
  208. 7 -- RELAY_EXTENDED [backward]
  209. 8 -- RELAY_TRUNCATE [forward]
  210. 9 -- RELAY_TRUNCATED [backward]
  211. 10 -- RELAY_DROP [forward or backward]
  212. 11 -- RELAY_RESOLVE [forward]
  213. 12 -- RELAY_RESOLVED [backward]
  214. 13 -- RELAY_BEGIN_UDP [forward]
  215. 14 -- RELAY_DATA_UDP [forward or backward]
  216. 15 -- RELAY_EXTEND_UDP [forward]
  217. 16 -- RELAY_EXTENDED_UDP [backward]
  218. 17 -- RELAY_DROP_UDP [forward or backward]
  219. Commands labelled as "forward" must only be sent by the originator
  220. of the circuit. Commands labelled as "backward" must only be sent by
  221. other nodes in the circuit back to the originator. Commands marked
  222. as either can be sent either by the originator or other nodes.
  223. The 'recognized' field in any unencrypted relay payload is always set to
  224. zero.
  225. The 'digest' field can have two meanings. For all cells sent over TLS
  226. connections (that is, all commands and all non-UDP RELAY data), it is
  227. computed as the first four bytes of the running SHA-1 digest of all the
  228. bytes that have been sent reliably and have been destined for this hop of
  229. the circuit or originated from this hop of the circuit, seeded from Df or Db
  230. respectively (obtained in section 4.2 above), and including this RELAY
  231. cell's entire payload (taken with the digest field set to zero). Cells sent
  232. over DTLS connections do not affect this running digest. Each cell sent
  233. over DTLS (that is, RELAY_DATA_UDP and RELAY_DROP_UDP) has the digest field
  234. set to the SHA-1 digest of the current RELAY cells' entire payload, with the
  235. digest field set to zero. Coupled with a randomly-chosen streamID, this
  236. provides per-cell integrity checking on UDP cells.
  237. [If you drop malformed UDP relay cells but don't close the circuit,
  238. then this 8 bytes of digest is not as strong as what we get in the
  239. TCP-circuit side. Is this a problem? -RD]
  240. When the 'recognized' field of a RELAY cell is zero, and the digest
  241. is correct, the cell is considered "recognized" for the purposes of
  242. decryption (see section 4.5 above).
  243. (The digest does not include any bytes from relay cells that do
  244. not start or end at this hop of the circuit. That is, it does not
  245. include forwarded data. Therefore if 'recognized' is zero but the
  246. digest does not match, the running digest at that node should
  247. not be updated, and the cell should be forwarded on.)
  248. All RELAY cells pertaining to the same tunneled TCP stream have the
  249. same streamID. Such streamIDs are chosen arbitrarily by the OP. RELAY
  250. cells that affect the entire circuit rather than a particular
  251. stream use a StreamID of zero.
  252. All RELAY cells pertaining to the same UDP tunnel have the same streamID.
  253. This streamID is chosen randomly by the OP, but cannot be zero.
  254. The 'Length' field of a relay cell contains the number of bytes in
  255. the relay payload which contain real payload data. The remainder of
  256. the payload is padded with NUL bytes.
  257. If the RELAY cell is recognized but the relay command is not
  258. understood, the cell must be dropped and ignored. Its contents
  259. still count with respect to the digests, though. [Before
  260. 0.1.1.10, Tor closed circuits when it received an unknown relay
  261. command. Perhaps this will be more forward-compatible. -RD]
  262. 5.2.1. Opening UDP tunnels and transferring data
  263. To open a new anonymized UDP connection, the OP chooses an open
  264. circuit to an exit that may be able to connect to the destination
  265. address, selects a random streamID not yet used on that circuit,
  266. and constructs a RELAY_BEGIN_UDP cell with a payload encoding the address
  267. and port of the destination host. The payload format is:
  268. ADDRESS | ':' | PORT | [00]
  269. where ADDRESS can be a DNS hostname, or an IPv4 address in
  270. dotted-quad format, or an IPv6 address surrounded by square brackets;
  271. and where PORT is encoded in decimal.
  272. [What is the [00] for? -NM]
  273. [It's so the payload is easy to parse out with string funcs -RD]
  274. Upon receiving this cell, the exit node resolves the address as necessary.
  275. If the address cannot be resolved, the exit node replies with a RELAY_END
  276. cell. (See 5.4 below.) Otherwise, the exit node replies with a
  277. RELAY_CONNECTED cell, whose payload is in one of the following formats:
  278. The IPv4 address to which the connection was made [4 octets]
  279. A number of seconds (TTL) for which the address may be cached [4 octets]
  280. or
  281. Four zero-valued octets [4 octets]
  282. An address type (6) [1 octet]
  283. The IPv6 address to which the connection was made [16 octets]
  284. A number of seconds (TTL) for which the address may be cached [4 octets]
  285. [XXXX Versions of Tor before 0.1.1.6 ignore and do not generate the TTL
  286. field. No version of Tor currently generates the IPv6 format.]
  287. The OP waits for a RELAY_CONNECTED cell before sending any data.
  288. Once a connection has been established, the OP and exit node
  289. package UDP data in RELAY_DATA_UDP cells, and upon receiving such
  290. cells, echo their contents to the corresponding socket.
  291. RELAY_DATA_UDP cells sent to unrecognized streams are dropped.
  292. Relay RELAY_DROP_UDP cells are long-range dummies; upon receiving such
  293. a cell, the OR or OP must drop it.
  294. 5.3. Closing streams
  295. UDP tunnels are closed in a fashion corresponding to TCP connections.
  296. 6. Flow Control
  297. UDP streams are not subject to flow control.
  298. 7.2. Router descriptor format.
  299. The items' formats are as follows:
  300. "router" nickname address ORPort SocksPort DirPort UDPPort
  301. Indicates the beginning of a router descriptor. "address" must be
  302. an IPv4 address in dotted-quad format. The last three numbers
  303. indicate the TCP ports at which this OR exposes
  304. functionality. ORPort is a port at which this OR accepts TLS
  305. connections for the main OR protocol; SocksPort is deprecated and
  306. should always be 0; DirPort is the port at which this OR accepts
  307. directory-related HTTP connections; and UDPPort is a port at which
  308. this OR accepts DTLS connections for UDP data. If any port is not
  309. supported, the value 0 is given instead of a port number.
  310. Other sections:
  311. What changes need to happen to each node's exit policy to support this? -RD
  312. Switching to UDP means managing the queues of incoming packets better,
  313. so we don't miss packets. How does this interact with doing large public
  314. key operations (handshakes) in the same thread? -RD
  315. ========================================================================
  316. COMMENTS
  317. ========================================================================
  318. [16 May 2006]
  319. I don't favor this approach; it makes packet traffic partitioned from
  320. stream traffic end-to-end. The architecture I'd like to see is:
  321. A *All* Tor-to-Tor traffic is UDP/DTLS, unless we need to fall back on
  322. TCP/TLS for firewall penetration or something. (This also gives us an
  323. upgrade path for routing through legacy servers.)
  324. B Stream traffic is handled with end-to-end per-stream acks/naks and
  325. retries. On failure, the data is retransmitted in a new RELAY_DATA cell;
  326. a cell isn't retransmitted.
  327. We'll need to do A anyway, to fix our behavior on packet-loss. Once we've
  328. done so, B is more or less inevitable, and we can support end-to-end UDP
  329. traffic "for free".
  330. (Also, there are some details that this draft spec doesn't address. For
  331. example, what happens when a UDP packet doesn't fit in a single cell?)
  332. -NM