source: router/doc/udp.html @ 65975df

Last change on this file since 65975df was 65975df, checked in by zzz <zzz@…>, 15 years ago

2006-02-19 jrandom

  • Moved the current net's reseed URL to a different location than where the old net looks (dev.i2p.net/i2pdb2/ vs …/i2pdb/)
  • More aggressively expire inbound messages (on receive, not just on send)
  • Add in a hook for breaking backwards compatibility in the SSU wire protocol directly by including a version as part of the handshake. The version is currently set to 0, however, so the wire protocol from this build is compatible with all earlier SSU implementations.
  • Increased the number of complete message readers, cutting down substantially on the delay processing inbound messages.
  • Delete the message history file on startup
  • Reworked the restart/shutdown display on the console (thanks bd_!)
  • Property mode set to 100644
File size: 32.1 KB
Line 
1<code>$Id: udp.html,v 1.19 2006/02/15 00:33:32 jrandom Exp $</code>
2
3<h1>Secure Semireliable UDP (SSU)</h1>
4<b>DRAFT</b>
5
6<p>
7The goal of this protocol is to provide secure, authenticated,
8semireliable, and unordered message delivery, exposing only a minimal
9amount of data easily discernible to third parties.  It should
10support high degree communication as well as TCP-friendly congestion
11control, and may include PMTU detection.   It should be capable of
12efficiently moving bulk data at rates sufficient for home users.
13In addition, it should support techniques for addressing network
14obstacles, like most NATs or firewalls.</p>
15
16<h2><a name="addressing">Addressing and introduction</a></h2>
17
18<p>To contact an SSU peer, one of two sets of information is necessary:
19a direct address, for when the peer is publicly reachable, or an
20indirect address, for using a third party to introduce the peer. 
21There is no restriction on the number of addresses a peer may have.</p>
22
23<pre>
24    Direct: ssu://host:port/introKey[?opts=[A-Z]*]
25  Indirect: ssu://tag@relayhost:port/relayIntroKey/targetIntroKey[?opts=[A-Z]*]
26</pre>
27
28<p>These introduction keys are delivered through an external channel
29and must be used when establishing a session key.  For the indirect
30address, the peer must first contact the relayhost and ask them for
31an introduction to the peer known at that relayhost under the given
32tag.  If possible, the relayhost sends a message to the addressed
33peer telling them to contact the requesting peer, and also gives
34the requesting peer the IP and port on which the addressed peer is
35located.  In addition, the peer establishing the connection must
36already know the public keys of the peer they are connecting to (but
37not necessary to any intermediary relay peer).</p>
38
39<p>Each of the addresses may also expose a series of options - special
40capabilities of that particular peer.  For a list of available
41capabilities, see <a href="#capabilities">below</a>.</p>
42
43<h2><a name="header">Header</a></h2>
44
45<p>All UDP datagrams begin with a MAC and an IV, followed by a variable
46size payload encrypted with the appropriate key.  The MAC used is
47HMAC-MD5, truncated to 16 bytes, while the key is a full AES256
48key.  The specific construct of the MAC is the first 16 bytes from:</p>
49<pre>
50  HMAC-MD5(payload || IV || (payloadLength ^ protocolVersion), macKey)
51</pre>
52
53<p>The payload itself is AES256/CBC encrypted with the IV and the
54sessionKey, with replay prevention addressed within its body,
55explained below.  The payloadLength in the MAC is a 2 byte unsigned
56integer in 2s complement.</p>
57 
58<p>The protocolVersion is a 2 byte unsigned integer in 2s complement,
59and currently set to 0.  Peers using a different protocol version will
60not be able to communicate with this peer, though earlier versions not
61using this flag are.</p>
62
63<h2><a name="payload">Payload</a></h2>
64
65<p>Within the AES encrypted payload, there is a minimal common structure
66to the various messages - a one byte flag and a four byte sending
67timestamp (*seconds* since the unix epoch).  The flag byte contains
68the following bitfields:</p>
69<pre>
70  bits 0-3: payload type
71     bit 4: rekey?
72     bit 5: extended options included
73  bits 6-7: reserved
74</pre>
75
76<p>If the rekey flag is set, 64 bytes of keying material follow the
77timestamp.  If the extended options flag is set, a one byte option
78size value is appended to, followed by that many extended option
79bytes, which are currently uninterpreted.</p>
80
81<p>When rekeying, the first 32 bytes of the keying material is fed
82into a SHA256 to produce the new MAC key, and the next 32 bytes are
83fed into a SHA256 to produce the new session key, though the keys are
84not immediately used.  The other side should also reply with the
85rekey flag set and that same keying material.  Once both sides have
86sent and received those values, the new keys should be used and the
87previous keys discarded.  It may be useful to keep the old keys
88around briefly, to address packet loss and reordering.</p>
89
90<pre>
91 Header: 37+ bytes
92 +----+----+----+----+----+----+----+----+
93 |                  MAC                  |
94 |                                       |
95 +----+----+----+----+----+----+----+----+
96 |                   IV                  |
97 |                                       |
98 +----+----+----+----+----+----+----+----+
99 |flag|        time       | (optionally  |
100 +----+----+----+----+----+              |
101 | this may have 64 byte keying material |
102 | and/or a one+N byte extended options) |
103 +---------------------------------------|
104</pre>
105
106<h2><a name="messages">Messages</a></h2>
107
108<h3><a name="sessionRequest">SessionRequest (type 0)</a></h3>
109<table border="1">
110<tr><td align="right" valign="top"><b>Peer:</b></td>
111    <td>Alice to Bob</td></tr>
112<tr><td align="right" valign="top"><b>Data:</b></td>
113    <td><ul>
114        <li>256 byte X, to begin the DH agreement</li>
115        <li>1 byte IP address size</li>
116        <li>that many byte representation of Bob's IP address</li>
117        <li>N bytes, currently uninterpreted (later, for challenges)</li>
118        </ul></td></tr>
119<tr><td align="right" valign="top"><b>Key used:</b></td>
120    <td>introKey</td></tr>
121</table>
122
123<pre>
124 +----+----+----+----+----+----+----+----+
125 |         X, as calculated from DH      |
126 |                                       |
127                 .   .   .               
128 |                                       |
129 +----+----+----+----+----+----+----+----+
130 |size| that many byte IP address (4-16) |
131 +----+----+----+----+----+----+----+----+
132 |           arbitrary amount            |
133 |        of uninterpreted data          |
134                 .   .   .               
135 |                                       |
136 +----+----+----+----+----+----+----+----+
137</pre>
138
139<h3><a name="sessionCreated">SessionCreated (type 1)</a></h3>
140<table border="1">
141<tr><td align="right" valign="top"><b>Peer:</b></td>
142    <td>Bob to Alice</td></tr>
143<tr><td align="right" valign="top"><b>Data:</b></td>
144    <td><ul>
145        <li>256 byte Y, to complete the DH agreement</li>
146        <li>1 byte IP address size</li>
147        <li>that many byte representation of Alice's IP address</li>
148        <li>2 byte port number (unsigned, big endian 2s complement)</li>
149        <li>4 byte relay tag which Alice can publish (else 0x0)</li>
150        <li>4 byte timestamp (seconds from the epoch) for use in the DSA
151            signature</li>
152        <li>40 byte DSA signature of the critical exchanged data
153            (X + Y + Alice's IP + Alice's port + Bob's IP + Bob's port + Alice's
154            new relay tag + Bob's signed on time), encrypted with another
155            layer of encryption using the negotiated sessionKey.  The IV
156            is reused here.</li>
157        <li>8 bytes padding, encrypted with an additional layer of encryption
158            using the negotiated session key as part of the DSA block</li>
159        <li>N bytes, currently uninterpreted (later, for challenges)</li>
160        </ul></td></tr>
161<tr><td align="right" valign="top"><b>Key used:</b></td>
162    <td>introKey, with an additional layer of encryption over the 40 byte
163        signature and the following 8 bytes padding.</td></tr>
164</table>
165
166<pre>
167 +----+----+----+----+----+----+----+----+
168 |         Y, as calculated from DH      |
169 |                                       |
170                 .   .   .               
171 |                                       |
172 +----+----+----+----+----+----+----+----+
173 |size| that many byte IP address (4-16) |
174 +----+----+----+----+----+----+----+----+
175 | Port (A)| public relay tag  |  signed
176 +----+----+----+----+----+----+----+----+
177   on time |                             |
178 +----+----+                             |
179 |              DSA signature            |
180 |                                       |
181 |                                       |
182 |                                       |
183 |         +----+----+----+----+----+----+
184 |         |     (8 bytes of padding)
185 +----+----+----+----+----+----+----+----+
186           |                             |
187 +----+----+                             |
188 |           arbitrary amount            |
189 |        of uninterpreted data          |
190                 .   .   .               
191 |                                       |
192 +----+----+----+----+----+----+----+----+
193</pre>
194
195<h3><a name="sessionConfirmed">SessionConfirmed (type 2)</a></h3>
196<table border="1">
197<tr><td align="right" valign="top"><b>Peer:</b></td>
198    <td>Alice to Bob</td></tr>
199<tr><td align="right" valign="top"><b>Data:</b></td>
200    <td><ul>
201        <li>1 byte identity fragment info:<pre>
202bits 0-3: current identity fragment #
203bits 4-7: total identity fragments</pre></li>
204        <li>2 byte size of the current identity fragment</li>
205        <li>that many byte fragment of Alice's identity.</li>
206        <li>on the last identity fragment, the signed on time is
207            included after the identity fragment, and the last 40
208            bytes contain the DSA signature of the critical exchanged
209            data (X + Y + Alice's IP + Alice's port + Bob's IP + Bob's port
210            + Alice's new relay key + Alice's signed on time)</li>
211        </ul></td></tr>
212<tr><td align="right" valign="top"><b>Key used:</b></td>
213    <td>sessionKey</td></tr>
214</table>
215
216<pre>
217 <b>Fragment 1 through N-1</b>
218 +----+----+----+----+----+----+----+----+
219 |info| cursize |                        |
220 +----+----+----+                        |
221 |      fragment of Alice's full         |
222 |            identity keys              |
223                 .   .   .               
224 |                                       |
225 +----+----+----+----+----+----+----+----+
226 
227 <b>Fragment N:</b>
228 +----+----+----+----+----+----+----+----+
229 |info| cursize |                        |
230 +----+----+----+                        |
231 |      fragment of Alice's full         |
232 |            identity keys              |
233                 .   .   .               
234 |                                       |
235 +----+----+----+----+----+----+----+----+
236 |  signed on time   |                   |
237 +----+----+----+----+                   |
238 |  arbitrary amount of uninterpreted    |
239 |        data, up from the end of the   |
240 |  identity key to 40 bytes prior to    |
241 |       end of the current packet       |
242 +----+----+----+----+----+----+----+----+
243 | DSA signature                         |
244 |                                       |
245 |                                       |
246 |                                       |
247 |                                       |
248 +----+----+----+----+----+----+----+----+
249</pre>
250 
251<h3><a name="relayRequest">RelayRequest (type 3)</a></h3>
252<table border="1">
253<tr><td align="right" valign="top"><b>Peer:</b></td>
254    <td>Alice to Bob</td></tr>
255<tr><td align="right" valign="top"><b>Data:</b></td>
256    <td><ul>
257        <li>4 byte relay tag</li>
258        <li>1 byte IP address size</li>
259        <li>that many byte representation of Alice's IP address</li>
260        <li>2 byte port number (of Alice)</li>
261        <li>1 byte challenge size</li>
262        <li>that many bytes to be relayed to Charlie in the intro</li>
263        <li>Alice's intro key (so Bob can reply with Charlie's info)</li>
264        <li>4 byte nonce of alice's relay request</li>
265        <li>N bytes, currently uninterpreted</li>
266        </ul></td></tr>
267<tr><td align="right" valign="top"><b>Key used:</b></td>
268    <td>introKey (or sessionKey, if Alice/Bob is established)</td></tr>
269</table>
270 
271<pre>
272 +----+----+----+----+----+----+----+----+
273 |      relay tag    |size| that many    |
274 +----+----+----+----+----+         +----|
275 | bytes for Alice's IP address     |port
276 +----+----+----+----+----+----+----+----+
277  (A) |size| that many challenge bytes   |
278 +----+----+                             |
279 | to be delivered to Charlie            |
280 +----+----+----+----+----+----+----+----+
281 | Alice's intro key                     |
282 |                                       |
283 |                                       |
284 |                                       |
285 +----+----+----+----+----+----+----+----+
286 |       nonce       |                   |
287 +----+----+----+----+                   |
288 | arbitrary amount of uninterpreted data|
289 +----+----+----+----+----+----+----+----+
290</pre>
291
292<h3><a name="relayResponse">RelayResponse (type 4)</a></h3>
293<table border="1">
294<tr><td align="right" valign="top"><b>Peer:</b></td>
295    <td>Bob to Alice</td></tr>
296<tr><td align="right" valign="top"><b>Data:</b></td>
297    <td><ul>
298        <li>1 byte IP address size</li>
299        <li>that many byte representation of Charlie's IP address</li>
300        <li>2 byte port number</li>
301        <li>1 byte IP address size</li>
302        <li>that many byte representation of Alice's IP address</li>
303        <li>2 byte port number</li>
304        <li>4 byte nonce sent by Alice</li>
305        <li>N bytes, currently uninterpreted</li>
306        </ul></td></tr>
307<tr><td align="right" valign="top"><b>Key used:</b></td>
308    <td>introKey (or sessionKey, if Alice/Bob is established)</td></tr>
309</table>
310
311<pre>
312 +----+----+----+----+----+----+----+----+
313 |size| that many bytes making up        |
314 +----+                        +----+----+
315 | Charlie's IP address        | Port (C)|
316 +----+----+----+----+----+----+----+----+
317 |size| that many bytes making up        |
318 +----+                        +----+----+
319 | Alice's IP address          | Port (A)|
320 +----+----+----+----+----+----+----+----+
321 |       nonce       |                   |
322 +----+----+----+----+                   |
323 | arbitrary amount of uninterpreted data|
324 +----+----+----+----+----+----+----+----+
325</pre>
326
327<h3><a name="relayIntro">RelayIntro (type 5)</a></h3>
328<table border="1">
329<tr><td align="right" valign="top"><b>Peer:</b></td>
330    <td>Bob to Charlie</td></tr>
331<tr><td align="right" valign="top"><b>Data:</b></td>
332    <td><ul>
333        <li>1 byte IP address size</li>
334        <li>that many byte representation of Alice's IP address</li>
335        <li>2 byte port number (of Alice)</li>
336        <li>1 byte challenge size</li>
337        <li>that many bytes relayed from Alice</li>
338        <li>N bytes, currently uninterpreted</li>
339        </ul></td></tr>
340<tr><td align="right" valign="top"><b>Key used:</b></td>
341    <td>sessionKey</td></tr>
342</table>
343
344<pre>
345 +----+----+----+----+----+----+----+----+
346 |size| that many bytes making up        |
347 +----+                        +----+----+
348 | Alice's IP address          | Port (A)|
349 +----+----+----+----+----+----+----+----+
350 |size| that many bytes of challenge     |
351 +----+                                  |
352 | data relayed from Alice               |
353 +----+----+----+----+----+----+----+----+
354 | arbitrary amount of uninterpreted data|
355 +----+----+----+----+----+----+----+----+
356</pre>
357
358<h3><a name="data">Data (type 6)</a></h3>
359<table border="1">
360<tr><td align="right" valign="top"><b>Peer:</b></td>
361    <td>Any</td></tr>
362<tr><td align="right" valign="top"><b>Data:</b></td>
363    <td><ul>
364        <li>1 byte flags:<pre>
365   bit 0: explicit ACKs included
366   bit 1: ACK bitfields included
367   bit 2: reserved
368   bit 3: explicit congestion notification
369   bit 4: request previous ACKs
370   bit 5: want reply
371   bit 6: extended data included
372   bit 7: reserved</pre></li>
373        <li>if explicit ACKs are included:<ul>
374          <li>a 1 byte number of ACKs</li>
375          <li>that many 4 byte MessageIds being fully ACKed</li>
376          </ul></li>
377        <li>if ACK bitfields are included:<ul>
378          <li>a 1 byte number of ACK bitfields</li>
379          <li>that many 4 byte MessageIds + a 1 or more byte ACK bitfield.
380              The bitfield uses the 7 low bits of each byte, with the high
381              bit specifying whether an additional bitfield byte follows it
382              (1 = true, 0 = the current bitfield byte is the last).  These
383              sequence of 7 bit arrays represent whether a fragment has been
384              received - if a bit is 1, the fragment has been received.  To
385              clarify, assuming fragments 0, 2, 5, and 9 have been received,
386              the bitfield bytes would be as follows:<pre>
387byte 0
388   bit 0: 1 (further bitfield bytes follow)
389   bit 1: 1 (fragment 0 received)
390   bit 2: 0 (fragment 1 not received)
391   bit 3: 1 (fragment 2 received)
392   bit 4: 0 (fragment 3 not received)
393   bit 5: 0 (fragment 4 not received)
394   bit 6: 1 (fragment 5 received)
395   bit 7: 0 (fragment 6 not received)
396byte 1
397   bit 0: 0 (no further bitfield bytes)
398   bit 1: 0 (fragment 7 not received)
399   bit 1: 0 (fragment 8 not received)
400   bit 1: 1 (fragment 9 received)
401   bit 1: 0 (fragment 10 not received)
402   bit 1: 0 (fragment 11 not received)
403   bit 1: 0 (fragment 12 not received)
404   bit 1: 0 (fragment 13 not received)</pre></li>
405          </ul></li>
406        <li>If extended data included:<ul>
407          <li>1 byte data size</li>
408          <li>that many bytes of extended data (currently uninterpreted)</li</ul></li>
409        <li>1 byte number of fragments</li>
410        <li>that many message fragments:<ul>
411          <li>4 byte messageId</li>
412          <li>3 byte fragment info:<pre>
413  bits 0-6: fragment #
414     bit 7: isLast (1 = true)
415  bits 8-9: unused
416bits 10-23: fragment size</pre></li>
417          <li>that many bytes</li></ul>
418        <li>N bytes padding, uninterpreted</li>
419        </ul></td></tr>
420<tr><td align="right" valign="top"><b>Key used:</b></td>
421    <td>sessionKey</td></tr>
422</table>
423
424<pre>
425 +----+----+----+----+----+----+----+----+
426 |flag| (additional headers, determined  |
427 +----+                                  |
428 | by the flags, such as ACKs or         |
429 | bitfields                             |
430 +----+----+----+----+----+----+----+----+
431 |#frg|     messageId     |   frag info  |
432 +----+----+----+----+----+----+----+----+
433 | that many bytes of fragment data      |
434                  .  .  .                                       
435 |                                       |
436 +----+----+----+----+----+----+----+----+
437 |     messageId     |   frag info  |    |
438 +----+----+----+----+----+----+----+    |
439 | that many bytes of fragment data      |
440                  .  .  .                                       
441 |                                       |
442 +----+----+----+----+----+----+----+----+
443 |     messageId     |   frag info  |    |
444 +----+----+----+----+----+----+----+    |
445 | that many bytes of fragment data      |
446                  .  .  .                                       
447 |                                       |
448 +----+----+----+----+----+----+----+----+
449 | arbitrary amount of uninterpreted data|
450 +----+----+----+----+----+----+----+----+
451</pre>
452
453<h3><a name="peerTest">PeerTest (type 7)</a></h3>
454<table border="1">
455<tr><td align="right" valign="top"><b>Peer:</b></td>
456    <td><a href="#peerTesting">Any</a></td></tr>
457<tr><td align="right" valign="top"><b>Data:</b></td>
458    <td><ul>
459        <li>4 byte nonce</li>
460        <li>1 byte IP address size</li>
461        <li>that many byte representation of Alice's IP address</li>
462        <li>2 byte port number</li>
463        <li>Alice's introduction key</li>
464        <li>N bytes, currently uninterpreted</li>
465        </ul></td></tr>
466<tr><td align="right" valign="top"><b>Key used:</b></td>
467    <td>introKey (or sessionKey if the connection has already been established)</td></tr>
468</table>
469
470<pre>
471 +----+----+----+----+----+----+----+----+
472 |    test nonce     |size| that many    |
473 +----+----+----+----+----+              |
474 |bytes making up Alice's IP address     |
475 |----+----+----+----+----+----+----+----+
476 | Port (A)| Alice or Charlie's          |
477 +----+----+                             |
478 | introduction key (Alice's is sent to  |
479 | Bob and Charlie, while Charlie's is   |                                      |
480 | sent to Alice)                        |
481 |         +----+----+----+----+----+----+
482 |         | arbitrary amount of         |
483 |----+----+                             |
484 | uninterpreted data                    |
485 +----+----+----+----+----+----+----+----+
486</pre>
487
488<h2><a name="congestioncontrol">Congestion control</a></h2>
489
490<p>SSU's need for only semireliable delivery, TCP-friendly operation,
491and the capacity for high throughput allows a great deal of latitude in
492congestion control.  The congestion control algorithm outlined below is
493meant to be both efficient in bandwidth as well as simple to implement.</p>
494
495<p>Packets are scheduled according to the the router's policy, taking care
496not to exceed the router's outbound capacity or to exceed the measured
497capacity of the remote peer.  The measured capacity should operate along the
498lines of TCP's slow start and congestion avoidance, with additive increases
499to the sending capacity and multiplicative decreases in face of congestion.
500Veering away from TCP, however, routers may give up on some messages after
501a given period or number of retransmissions while continuing to transmit
502other messages.</p>
503 
504<p>The congestion detection techniques vary from TCP as well, since each
505message has its own unique and nonsequential identifier, and each message
506has a limited size - at most, 32KB.  To efficiently transmit this feedback
507to the sender, the receiver periodically includes a list of fully ACKed
508message identifiers and may also include bitfields for partially received
509messages, where each bit represents the reception of a fragment.  If
510duplicate fragments arrive, the message should be ACKed again, or if the
511message has still not been fully received, the bitfield should be
512retransmitted with any new updates.</p>
513
514<p>The simplest possible implementation does not need to pad the packets to
515any particular size, but instead just places a single message fragment into
516a packet and sends it off (careful not to exceed the MTU).  A more efficient
517strategy would be to bundle multiple message fragments into the same packet,
518so long as it doesn't exceed the MTU, but this is not necessary.  Eventually,
519a set of fixed packet sizes may be appropriate to further hide the data
520fragmentation to external adversaries, but the tunnel, garlic, and end to
521end padding should be sufficient for most needs until then.</p>
522
523<h2><a name="keys">Keys</a></h2>
524
525<p>All encryption used is AES256/CBC with 32 byte keys and 16 byte IVs.
526The MAC and session keys are negotiated as part of the DH exchange, used
527for the HMAC and encryption, respectively.  Prior to the DH exchange,
528the publicly knowable introKey is used for the MAC and encryption.</p>
529
530<p>When using the introKey, both the initial message and any subsequent
531reply use the introKey of the responder (Bob) - the responder does
532not need to know the introKey of the requestor (Alice).  The DSA
533signing key used by Bob should already be known to Alice when she
534contacts him, though Alice's DSA key may not already be known by
535Bob.</p>
536
537<p>Upon receiving a message, the receiver checks the from IP address
538with any established sessions - if there is one or more matches,
539those session's MAC keys are tested sequentially in the HMAC.  If none
540of those verify or if there are no matching IP addresses, the
541receiver tries their introKey in the MAC.  If that does not verify,
542the packet is dropped.  If it does verify, it is interpreted
543according to the message type, though if the receiver is overloaded,
544it may be dropped anyway.</p>
545
546<p>If Alice and Bob have an established session, but Alice loses the
547keys for some reason and she wants to contact Bob, she may at any
548time simply establish a new session through the SessionRequest and
549related messages.  If Bob has lost the key but Alice does not know
550that, she will first attempt to prod him to reply, by sending a
551DataMessage with the wantReply flag set, and if Bob continually
552fails to reply, she will assume the key is lost and reestablish a
553new one.</p>
554
555<p>For the DH key agreement,
556<a href="http://www.faqs.org/rfcs/rfc3526.html">RFC3526</a> 2048bit
557MODP group (#14) is used:</p>
558<pre>
559  p = 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
560  g = 2
561</pre>
562
563<p>The DSA p, q, and g are shared according to the scope of the
564identity which created them.</p>
565
566<h2><a name="replay">Replay prevention</a></h2>
567
568<p>Replay prevention at the SSU layer occurs by rejecting packets
569with exceedingly old timestamps or those which reuse an IV.  To
570detect duplicate IVs, a sequence of Bloom filters are employed to
571"decay" periodically so that only recently added IVs are detected.</p>
572
573<p>The messageIds used in DataMessages are defined at layers above
574the SSU transport and are passed through transparently.  These IDs
575are not in any particular order - in fact, they are likely to be
576entirely random.  The SSU layer makes no attempt at messageId
577replay prevention - higher layers should take that into account.</p>
578
579<h2><a name="introduction">Introduction</a></h2>
580
581<p>Indirect session establishment by means of a third party introduction
582is necessary for efficient NAT traversal.  Charlie, a router behind a
583NAT or firewall which does not allow unsolicited inbound UDP packets,
584first contacts a few peers, choosing some to serve as introducers.  Each
585of these peers (Bob, Bill, Betty, etc) provide Charlie with an introduction
586tag - a 4 byte random number - which he then makes available to the public
587as methods of contacting him.  Alice, a router who has Charlie's published
588contact methods, first sends a RelayRequest packet to one or more of the
589introducers, asking each to introduce her to Charlie (offering the
590introduction tag to identify Charlie).  Bob then forwards a RelayIntro
591packet to Charlie including Alice's public IP and port number, then sends
592Alice back a RelayResponse packet containing Charlie's public IP and port
593number.  When Charlie receives the RelayIntro packet, he sends off a small
594random packet to Alice's IP and port (poking a hole in his NAT/firewall),
595and when Alice receive's Bob's RelayResponse packet, she begins a new
596full direction session establishment with the specified IP and port.</p>
597
598<!--
599  should Bob wait for Charlie to ack the RelayIntro packet to avoid
600  situations where that packet is lost yet Alice gets Charlie's IP with
601  Charlie not yet punching a hole in his NAT for her to get through? 
602  Perhaps Alice should send to multiple Bobs at once, hoping that at
603  least one of them gets through
604-->
605
606<h2><a name="peerTesting">Peer testing</a></h2>
607
608<p>The automation of collaborative reachability testing for peers is
609enabled by a sequence of PeerTest messages.  With its proper
610execution, a peer will be able to determine their own reachability
611and may update its behavior accordingly.  The testing process is
612quite simple:</p>
613
614<pre>
615        Alice                  Bob                  Charlie
616    PeerTest -------------------&gt;
617                             PeerTest--------------------&gt;
618                                &lt;-------------------PeerTest
619         &lt;-------------------PeerTest
620         &lt;------------------------------------------PeerTest
621    PeerTest------------------------------------------&gt;
622         &lt;------------------------------------------PeerTest
623</pre>
624
625<p>Each of the PeerTest messages carry a nonce identifying the
626test series itself, as initialized by Alice.  If Alice doesn't
627get a particular message that she expects, she will retransmit
628accordingly, and based upon the data received or the messages
629missing, she will know her reachability.  The various end states
630that may be reached are as follows:</p>
631
632<ul>
633<li>If she doesn't receive a response from Bob, she will retransmit
634up to a certain number of times, but if no response ever arrives,
635she will know that her firewall or NAT is somehow misconfigured,
636rejecting all inbound UDP packets even in direct response to an
637outbound packet.  Alternately, Bob may be down or unable to get
638Charlie to reply.</li>
639
640<li>If Alice doesn't receive a PeerTest message with the
641expected nonce from a third party (Charlie), she will retransmit
642her initial request to Bob up to a certain number of times, even
643if she has received Bob's reply already.  If Charlie's first message
644still doesn't get through but Bob's does, she knows that she is
645behind a NAT or firewall that is rejecting unsolicited connection
646attempts and that port forwarding is not operating properly (the
647IP and port that Bob offered up should be forwarded).</li>
648
649<li>If Alice receives Bob's PeerTest message and both of Charlie's
650PeerTest messages but the enclosed IP and port numbers in Bob's
651and Charlie's second messages don't match, she knows that she is
652behind a symmetric NAT, rewriting all of her outbound packets with
653different 'from' ports for each peer contacted.  She will need to
654explicitly forward a port and always have that port exposed for
655remote connectivity, ignoring further port discovery.</li>
656
657<li>If Alice receives Charlie's first message but not his second,
658she will retransmit her PeerTest message to Charlie up to a
659certain number of times, but if no response is received she knows
660that Charlie is either confused or no longer online.</li>
661</ul>
662
663<p>Alice should choose Bob arbitrarily from known peers who seem
664to be capable of participating in peer tests.  Bob in turn should
665choose Charlie arbitrarily from peers that he knows who seem to be
666capable of participating in peer tests and who are on a different
667IP from both Bob and Alice.  If the first error condition occurs
668(Alice doesn't get PeerTest messages from Bob), Alice may decide
669to designate a new peer as Bob and try again with a different nonce.</p>
670
671<p>Alice's introduction key is included in all of the PeerTest
672messages so that she doesn't need to already have an established
673session with Bob and so that Charlie can contact her without knowing
674any additional information.  Alice may go on to establish a session
675with either Bob or Charlie, but it is not required.</p>
676
677<h2><a name="messageSequences">Message sequences</a></h2>
678
679<h3><a name="establishDirect">Connection establishment (direct)</a></h3>
680
681<pre>
682        Alice                         Bob
683    SessionRequest---------------------&gt;
684          &lt;---------------------SessionCreated
685    SessionConfirmed-------------------&gt;
686    SessionConfirmed-------------------&gt;
687    SessionConfirmed-------------------&gt;
688    SessionConfirmed-------------------&gt;
689          &lt;--------------------------Data
690</pre>
691
692<h3><a name="establishIndirect">Connection establishment (indirect)</a></h3>
693
694<pre>
695        Alice                         Bob                  Charlie
696    RelayRequest ----------------------&gt;
697         &lt;--------------RelayResponse    RelayIntro-----------&gt;
698         &lt;--------------------------------------------Data (ignored)
699    SessionRequest--------------------------------------------&gt;
700         &lt;--------------------------------------------SessionCreated
701    SessionConfirmed------------------------------------------&gt;
702    SessionConfirmed------------------------------------------&gt;
703    SessionConfirmed------------------------------------------&gt;
704    SessionConfirmed------------------------------------------&gt;
705         &lt;---------------------------------------------------Data
706</pre>
707
708<h2><a name="sampleDatagrams">Sample datagrams</a></h2>
709
710<b>Minimal data message (no fragments, no ACKs, no NACKs, etc)</b><br />
711<i>(Size: 39 bytes)</i>
712
713<pre>
714 +----+----+----+----+----+----+----+----+
715 |                  MAC                  |
716 |                                       |
717 +----+----+----+----+----+----+----+----+
718 |                   IV                  |
719 |                                       |
720 +----+----+----+----+----+----+----+----+
721 |flag|        time       |flag|#frg|    |
722 +----+----+----+----+----+----+----+    |
723 |  padding to fit a full AES256 block   |
724 +----+----+----+----+----+----+----+----+
725</pre>
726
727<b>Minimal data message with payload</b><br />
728<i>(Size: 46+fragmentSize bytes)</i>
729
730<pre>
731 +----+----+----+----+----+----+----+----+
732 |                  MAC                  |
733 |                                       |
734 +----+----+----+----+----+----+----+----+
735 |                   IV                  |
736 |                                       |
737 +----+----+----+----+----+----+----+----+
738 |flag|        time       |flag|#frg|
739 +----+----+----+----+----+----+----+----+
740   messageId    |   frag info  |         |
741 +----+----+----+----+----+----+         |
742 | that many bytes of fragment data      |
743                  .  .  .                                       
744 |                                       |
745 +----+----+----+----+----+----+----+----+
746</pre> 
747
748<h2><a name="capabilities">Peer capabilities</a></h2>
749
750<dl>
751 <dt>B</dt>
752 <dd>If the peer address contains the 'B' capability, that means
753     they are willing and able to participate in peer tests as
754     a 'Bob' or 'Charlie'.</dd>
755 <dt>C</dt>
756 <dd>If the peer address contains the 'C' capability, that means
757     they are willing and able to serve as an introducer - serving
758     as a Bob for an otherwise unreachable Alice.</dd>
759</dl>
Note: See TracBrowser for help on using the repository browser.