source: router/doc/tunnel-alt.html @ a12ede0

Last change on this file since a12ede0 was a12ede0, checked in by zzz <zzz@…>, 16 years ago

2006-01-17 jrandom

  • First pass of the new tunnel creation crypto, specified in the new router/doc/tunnel-alt-creation.html (referenced in the current router/doc/tunnel-alt.html). It isn't actually used anywhere yet, other than in the test code, but the code verifies the technical viability, so further scrutiny would be warranted.
  • Property mode set to 100644
File size: 26.3 KB
1<code>$Id: tunnel-alt.html,v 1.9 2005/07/27 14:04:07 jrandom Exp $</code>
31) <a href="#tunnel.overview">Tunnel overview</a>
42) <a href="#tunnel.operation">Tunnel operation</a>
52.1) <a href="#tunnel.preprocessing">Message preprocessing</a>
62.2) <a href="#tunnel.gateway">Gateway processing</a>
72.3) <a href="#tunnel.participant">Participant processing</a>
82.4) <a href="#tunnel.endpoint">Endpoint processing</a>
92.5) <a href="#tunnel.padding">Padding</a>
102.6) <a href="#tunnel.fragmentation">Tunnel fragmentation</a>
112.7) <a href="#tunnel.alternatives">Alternatives</a>
122.7.1) <a href="#tunnel.reroute">Adjust tunnel processing midstream</a>
132.7.2) <a href="#tunnel.bidirectional">Use bidirectional tunnels</a>
142.7.3) <a href="#tunnel.backchannel">Backchannel communication</a>
152.7.4) <a href="#tunnel.variablesize">Variable size tunnel messages</a>
163) <a href="#tunnel.building">Tunnel building</a>
173.1) <a href="#tunnel.peerselection">Peer selection</a>
183.1.1) <a href="#tunnel.selection.exploratory">Exploratory tunnel peer selection</a>
193.1.2) <a href="#tunnel.selection.client">Client tunnel peer selection</a>
203.2) <a href="#tunnel.request">Request delivery</a>
213.3) <a href="#tunnel.pooling">Pooling</a>
223.4) <a href="#tunnel.building.alternatives">Alternatives</a>
233.4.1) <a href="#tunnel.building.telescoping">Telescopic building</a>
243.4.2) <a href="#tunnel.building.nonexploratory">Non-exploratory tunnels for management</a>
254) <a href="#tunnel.throttling">Tunnel throttling</a>
265) <a href="#tunnel.mixing">Mixing/batching</a>
29<h2>1) <a name="tunnel.overview">Tunnel overview</a></h2>
31<p>Within I2P, messages are passed in one direction through a virtual
32tunnel of peers, using whatever means are available to pass the
33message on to the next hop.  Messages arrive at the tunnel's
34gateway, get bundled up and/or fragmented into fixed sizes tunnel messages,
35and are forwarded on to the next hop in the tunnel, which processes and verifies
36the validity of the message and sends it on to the next hop, and so on, until
37it reaches the tunnel endpoint.  That endpoint takes the messages
38bundled up by the gateway and forwards them as instructed - either
39to another router, to another tunnel on another router, or locally.</p>
41<p>Tunnels all work the same, but can be segmented into two different
42groups - inbound tunnels and outbound tunnels.  The inbound tunnels
43have an untrusted gateway which passes messages down towards the
44tunnel creator, which serves as the tunnel endpoint.  For outbound
45tunnels, the tunnel creator serves as the gateway, passing messages
46out to the remote endpoint.</p>
48<p>The tunnel's creator selects exactly which peers will participate
49in the tunnel, and provides each with the necessary configuration
50data.  They may have any number of hops, but may be constrained with various
51proof-of-work requests to add on additional steps.  It is the intent to make
52it hard for either participants or third parties to determine the length of
53a tunnel, or even for colluding participants to determine whether they are a
54part of the same tunnel at all (barring the situation where colluding peers are
55next to each other in the tunnel).</p>
57<p>Beyond their length, there are additional configurable parameters
58for each tunnel that can be used, such as a throttle on the frequency of
59messages delivered, how padding should be used, how long a tunnel should be
60in operation, whether to inject chaff messages, and what, if any, batching
61strategies should be employed.</p>
63<p>In practice, a series of tunnel pools are used for different
64purposes - each local client destination has its own set of inbound
65tunnels and outbound tunnels, configured to meet its anonymity and
66performance needs.  In addition, the router itself maintains a series
67of pools for participating in the network database and for managing
68the tunnels themselves.</p>
70<p>I2P is an inherently packet switched network, even with these
71tunnels, allowing it to take advantage of multiple tunnels running
72in parallel, increasing resilience and balancing load.  Outside of
73the core I2P layer, there is an optional end to end streaming library
74available for client applications, exposing TCP-esque operation,
75including message reordering, retransmission, congestion control, etc.</p>
77<h2>2) <a name="tunnel.operation">Tunnel operation</a></h2>
79<p>Tunnel operation has four distinct processes, taken on by various
80peers in the tunnel.  First, the tunnel gateway accumulates a number
81of tunnel messages and preprocesses them into something for tunnel
82delivery.  Next, that gateway encrypts that preprocessed data, then
83forwards it to the first hop.  That peer, and subsequent tunnel
84participants, unwrap a layer of the encryption, verifying that it isn't
85a duplicate, then forward it on to the next peer. 
86Eventually, the message arrives at the endpoint where the messages
87bundled by the gateway are split out again and forwarded on as
90<p>Tunnel IDs are 4 byte numbers used at each hop - participants know what
91tunnel ID to listen for messages with and what tunnel ID they should be forwarded
92on as to the next hop, and each hop chooses the tunnel ID which they receive messages
93on.  Tunnels themselves are short lived (10 minutes at the
94moment), and even if subsequent tunnels are built using the same sequence of
95peers, each hop's tunnel ID will change.</p>
97<h3>2.1) <a name="tunnel.preprocessing">Message preprocessing</a></h3>
99<p>When the gateway wants to deliver data through the tunnel, it first
100gathers zero or more I2NP messages, selects how much padding will be used,
101fragments it across the necessary number of 1KB tunnel messages, and decides how
102each I2NP message should be handled by the tunnel endpoint, encoding that
103data into the raw tunnel payload:</p>
105<li>the first 4 bytes of the SHA256 of the remaining preprocessed data concatenated
106    with the IV, using the IV as will be seen on the tunnel endpoint (for
107    outbound tunnels) or the IV as was seen on the tunnel gateway (for inbound
108    tunnels) (see below for IV processing).</li>
109<li>0 or more bytes containing random nonzero integers</li>
110<li>1 byte containing 0x00</li>
111<li>a series of zero or more { instructions, message } pairs</li>
114<p>The instructions are encoded with a single control byte, followed by any
115necessary additional information.  The first bit in that control byte determines
116how the remainder of the header is interpreted - if it is not set, the message
117is either not fragmented or this is the first fragment in the message.  If it is
118set, this is a follow on fragment.</p>
120<p>With the first bit being 0, the instructions are:</p>
122<li>1 byte control byte:<pre>
123      bit 0: is follow on fragment?  (1 = true, 0 = false, must be 0)
124   bits 1-2: delivery type
125             (0x0 = LOCAL, 0x01 = TUNNEL, 0x02 = ROUTER)
126      bit 3: delay included?  (1 = true, 0 = false)
127      bit 4: fragmented?  (1 = true, 0 = false)
128      bit 5: extended options?  (1 = true, 0 = false)
129   bits 6-7: reserved</pre></li>
130<li>if the delivery type was TUNNEL, a 4 byte tunnel ID</li>
131<li>if the delivery type was TUNNEL or ROUTER, a 32 byte router hash</li>
132<li>if the delay included flag is true, a 1 byte value:<pre>
133      bit 0: type (0 = strict, 1 = randomized)
134   bits 1-7: delay exponent (2^value minutes)</pre></li>
135<li>if the fragmented flag is true, a 4 byte message ID</li>
136<li>if the extended options flag is true:<pre>
137   = a 1 byte option size (in bytes)
138   = that many bytes</pre></li>
139<li>2 byte size of the I2NP message or this fragment</li>
142<p>If the first bit being 1, the instructions are:</p>
144<li>1 byte control byte:<pre>
145      bit 0: is follow on fragment?  (1 = true, 0 = false, must be 1)
146   bits 1-6: fragment number
147      bit 7: is last? (1 = true, 0 = false)</pre></li>
148<li>4 byte message ID (same one defined in the first fragment)</li>
149<li>2 byte size of this fragment</li>
152<p>The I2NP message is encoded in its standard form, and the
153preprocessed payload must be padded to a multiple of 16 bytes.</p>
155<h3>2.2) <a name="tunnel.gateway">Gateway processing</a></h3>
157<p>After the preprocessing of messages into a padded payload, the gateway builds
158a random 16 byte IV value, iteratively encrypting it and the tunnel message as
159necessary, and forwards the tuple {tunnelID, IV, encrypted tunnel message} to the next hop.</p>
161<p>How encryption at the gateway is done depends on whether the tunnel is an
162inbound or an outbound tunnel.  For inbound tunnels, they simply select a random
163IV, postprocessing and updating it to generate the IV for the gateway and using
164that IV along side their own layer key to encrypt the preprocessed data.  For outbound
165tunnels they must iteratively decrypt the (unencrypted) IV and preprocessed
166data with the IV and layer keys for all hops in the tunnel.  The result of the outbound
167tunnel encryption is that when each peer encrypts it, the endpoint will recover
168the initial preprocessed data.</p>
170<h3>2.3) <a name="tunnel.participant">Participant processing</a></h3>
172<p>When a peer receives a tunnel message, it checks that the message came from
173the same previous hop as before (initialized when the first message comes through
174the tunnel).  If the previous peer is a different router, or if the message has
175already been seen, the message is dropped.  The participant then encrypts the
176received IV with AES256/ECB using their IV key to determine the current IV, uses
177that IV with the participant's layer key to encrypt the data, encrypts the
178current IV with AES256/ECB using their IV key again, then forwards the tuple
179{nextTunnelId, nextIV, encryptedData} to the next hop.  This double encryption
180of the IV (both before and after use) help address a certain class of
181confirmation attacks.</p>
183<p>Duplicate message detection is handled by a decaying Bloom filter on message
184IVs.  Each router maintains a single Bloom filter to contain the XOR of the IV and
185the first block of the message received for all of the tunnels it is participating
186in, modified to drop seen entries after 10-20 minutes (when the tunnels will have
187expired).  The size of the bloom filter and the parameters used are sufficient to
188more than saturate the router's network connection with a negligible chance of
189false positive.  The unique value fed into the Bloom filter is the XOR of the IV
190and the first block so as to prevent nonsequential colluding peers in the tunnel
191from tagging a message by resending it with the IV and first block switched.</p>
193<h3>2.4) <a name="tunnel.endpoint">Endpoint processing</a></h3>
195<p>After receiving and validating a tunnel message at the last hop in the tunnel,
196how the endpoint recovers the data encoded by the gateway depends upon whether
197the tunnel is an inbound or an outbound tunnel.  For outbound tunnels, the
198endpoint encrypts the message with its layer key just like any other participant,
199exposing the preprocessed data.  For inbound tunnels, the endpoint is also the
200tunnel creator so they can merely iteratively decrypt the IV and message, using the
201layer and IV keys of each step in reverse order.</p>
203<p>At this point, the tunnel endpoint has the preprocessed data sent by the gateway,
204which it may then parse out into the included I2NP messages and forwards them as
205requested in their delivery instructions.</p>
207<h3>2.5) <a name="tunnel.padding">Padding</a></h3>
209<p>Several tunnel padding strategies are possible, each with their own merits:</p>
212<li>No padding</li>
213<li>Padding to a random size</li>
214<li>Padding to a fixed size</li>
215<li>Padding to the closest KB</li>
216<li>Padding to the closest exponential size (2^n bytes)</li>
219<p>These padding strategies can be used on a variety of levels, addressing the
220exposure of message size information to different adversaries.  After gathering
221and reviewing some <a href="">statistics</a>
222from the 0.4 network, as well as exploring the anonymity tradeoffs, we're starting
223with a fixed tunnel message size of 1024 bytes.  Within this however, the fragmented
224messages themselves are not padded by the tunnel at all (though for end to end
225messages, they may be padded as part of the garlic wrapping).</p>
227<h3>2.6) <a name="tunnel.fragmentation">Tunnel fragmentation</a></h3>
229<p>To prevent adversaries from tagging the messages along the path by adjusting
230the message size, all tunnel messages are a fixed 1024 bytes in size.  To accommodate
231larger I2NP messages as well as to support smaller ones more efficiently, the
232gateway splits up the larger I2NP messages into fragments contained within each
233tunnel message.  The endpoint will attempt to rebuild the I2NP message from the
234fragments for a short period of time, but will discard them as necessary.</p>
236<p>Routers have a lot of leeway as to how the fragments are arranged, whether
237they are stuffed inefficiently as discrete units, batched for a brief period to
238fit more payload into the 1024 byte tunnel messages, or opportunistically padded
239with other messages that the gateway wanted to send out.</p>
241<h3>2.7) <a name="tunnel.alternatives">Alternatives</a></h3>
243<h4>2.7.1) <a name="tunnel.reroute">Adjust tunnel processing midstream</a></h4>
245<p>While the simple tunnel routing algorithm should be sufficient for most cases,
246there are three alternatives that can be explored:</p>
248<li>Have a peer other than the endpoint temporarily act as the termination
249point for a tunnel by adjusting the encryption used at the gateway to give them
250the plaintext of the preprocessed I2NP messages.  Each peer could check to see
251whether they had the plaintext, processing the message when received as if they
253<li>Allow routers participating in a tunnel to remix the message before
254forwarding it on - bouncing it through one of that peer's own outbound tunnels,
255bearing instructions for delivery to the next hop.</li>
256<li>Implement code for the tunnel creator to redefine a peer's "next hop" in
257the tunnel, allowing further dynamic redirection.</li>
260<h4>2.7.2) <a name="tunnel.bidirectional">Use bidirectional tunnels</a></h4>
262<p>The current strategy of using two separate tunnels for inbound and outbound
263communication is not the only technique available, and it does have anonymity
264implications.  On the positive side, by using separate tunnels it lessens the
265traffic data exposed for analysis to participants in a tunnel - for instance,
266peers in an outbound tunnel from a web browser would only see the traffic of
267an HTTP GET, while the peers in an inbound tunnel would see the payload
268delivered along the tunnel.  With bidirectional tunnels, all participants would
269have access to the fact that e.g. 1KB was sent in one direction, then 100KB
270in the other.  On the negative side, using unidirectional tunnels means that
271there are two sets of peers which need to be profiled and accounted for, and
272additional care must be taken to address the increased speed of predecessor
273attacks.  The tunnel pooling and building process outlined below should
274minimize the worries of the predecessor attack, though if it were desired,
275it wouldn't be much trouble to build both the inbound and outbound tunnels
276along the same peers.</p>
278<h4>2.7.3) <a name="tunnel.backchannel">Backchannel communication</a></h4>
280<p>At the moment, the IV values used are random values.  However, it is
281possible for that 16 byte value to be used to send control messages from the
282gateway to the endpoint, or on outbound tunnels, from the gateway to any of the
283peers.  The inbound gateway could encode certain values in the IV once, which
284the endpoint would be able to recover (since it knows the endpoint is also the
285creator).  For outbound tunnels, the creator could deliver certain values to the
286participants during the tunnel creation (e.g. "if you see 0x0 as the IV, that
287means X", "0x1 means Y", etc).  Since the gateway on the outbound tunnel is also
288the creator, they can build a IV so that any of the peers will receive the
289correct value.  The tunnel creator could even give the inbound tunnel gateway
290a series of IV values which that gateway could use to communicate with
291individual participants exactly one time (though this would have issues regarding
292collusion detection)</p>
294<p>This technique could later be used deliver message mid stream, or to allow the
295inbound gateway to tell the endpoint that it is being DoS'ed or otherwise soon
296to fail.  At the moment, there are no plans to exploit this backchannel.</p>
298<h4>2.7.4) <a name="tunnel.variablesize">Variable size tunnel messages</a></h4>
300<p>While the transport layer may have its own fixed or variable message size,
301using its own fragmentation, the tunnel layer may instead use variable size
302tunnel messages.  The difference is an issue of threat models - a fixed size
303at the transport layer helps reduce the information exposed to external
304adversaries (though overall flow analysis still works), but for internal
305adversaries (aka tunnel participants) the message size is exposed.  Fixed size
306tunnel messages help reduce the information exposed to tunnel participants, but
307does not hide the information exposed to tunnel endpoints and gateways.  Fixed
308size end to end messages hide the information exposed to all peers in the
311<p>As always, its a question of who I2P is trying to protect against.  Variable
312sized tunnel messages are dangerous, as they allow participants to use the
313message size itself as a backchannel to other participants - e.g. if you see a
3141337 byte message, you're on the same tunnel as another colluding peer.  Even
315with a fixed set of allowable sizes (1024, 2048, 4096, etc), that backchannel
316still exists as peers could use the frequency of each size as the carrier (e.g.
317two 1024 byte messages followed by an 8192).  Smaller messages do incur the
318overhead of the headers (IV, tunnel ID, hash portion, etc), but larger fixed size
319messages either increase latency (due to batching) or dramatically increase
320overhead (due to padding).  Fragmentation helps ammortize the overhead, at the
321cost of potential message loss due to lost fragments.</p>
323<p>Timing attacks are also relevent when reviewing the effectiveness of fixed
324size messages, though they require a substantial view of network activity
325patterns to be effective.  Excessive artificial delays in the tunnel will be
326detected by the tunnel's creator, due to periodic testing, causing that entire
327tunnel to be scrapped and the profiles for peers within it to be adjusted.</p>
329<h2>3) <a name="tunnel.building">Tunnel building</a></h2>
331<p>When building a tunnel, the creator must send a request with the necessary
332configuration data to each of the hops and wait for all of them to agree before
333enabling the tunnel.  The requests are encrypted so that only the peers who need
334to know a piece of information (such as the tunnel layer or IV key) has that
335data.  In addition, only the tunnel creator will have access to the peer's
336reply.  There are three important dimensions to keep in mind when producing
337the tunnels: what peers are used (and where), how the requests are sent (and
338replies received), and how they are maintained.</p>
340<h3>3.1) <a name="tunnel.peerselection">Peer selection</a></h3>
342<p>Beyond the two types of tunnels - inbound and outbound - there are two styles
343of peer selection used for different tunnels - exploratory and client.
344Exploratory tunnels are used for both network database maintenance and tunnel
345maintenance, while client tunnels are used for end to end client messages.  </p>
347<h4>3.1.1) <a name="tunnel.selection.exploratory">Exploratory tunnel peer selection</a></h4>
349<p>Exploratory tunnels are built out of a random selection of peers from a subset
350of the network.  The particular subset varies on the local router and on what their
351tunnel routing needs are.  In general, the exploratory tunnels are built out of
352randomly selected peers who are in the peer's "not failing but active" profile
353category.  The secondary purpose of the tunnels, beyond merely tunnel routing,
354is to find underutilized high capacity peers so that they can be promoted for
355use in client tunnels.</p>
357<h4>3.1.2) <a name="tunnel.selection.client">Client tunnel peer selection</a></h4>
359<p>Client tunnels are built with a more stringent set of requirements - the local
360router will select peers out of its "fast and high capacity" profile category so
361that performance and reliability will meet the needs of the client application.
362However, there are several important details beyond that basic selection that
363should be adhered to, depending upon the client's anonymity needs.</p>
365<p>For some clients who are worried about adversaries mounting a predecessor
366attack, the tunnel selection can keep the peers selected in a strict order -
367if A, B, and C are in a tunnel, the hop after A is always B, and the hop after
368B is always C.  A less strict ordering is also possible, assuring that while
369the hop after A may be B, B may never be before A.  Other configuration options
370include the ability for just the inbound tunnel gateways and outbound tunnel
371endpoints to be fixed, or rotated on an MTBF rate.</p>
373<p>In the initial implementation, only random ordering has been implemented,
374though more strict ordering will be developed and deployed over time, as well
375as controls for the user to select which strategy to use for individual clients.</p>
377<h3>3.2) <a name="tunnel.request">Request delivery</a></h3>
379<p>A new tunnel request preparation, delivery, and response method has been
380<a href="tunnel-alt-creation.html">devised</a>, which reduces the number of
381predecessors exposed, cuts the number of messages transmitted, verifies proper
382connectivity, and avoids the message counting attack of traditional telescopic
383tunnel creation.  The old technique is listed below as an <a
386<p>Peers may reject tunnel creation requests for a variety of reasons, though
387a series of four increasingly severe rejections are known: probabalistic rejection
388(due to approaching the router's capacity, or in response to a flood of requests),
389transient overload, bandwidth overload, and critical failure.  When received,
390those four are interpreted by the tunnel creator to help adjust their profile of
391the router in question.</p>
393<h3>3.3) <a name="tunnel.pooling">Pooling</a></h3>
395<p>To allow efficient operation, the router maintains a series of tunnel pools,
396each managing a group of tunnels used for a specific purpose with their own
397configuration.  When a tunnel is needed for that purpose, the router selects one
398out of the appropriate pool at random.  Overall, there are two exploratory tunnel
399pools - one inbound and one outbound - each using the router's exploration
400defaults.  In addition, there is a pair of pools for each local destination -
401one inbound and one outbound tunnel.  Those pools use the configuration specified
402when the local destination connected to the router, or the router's defaults if
403not specified.</p>
405<p>Each pool has within its configuration a few key settings, defining how many
406tunnels to keep active, how many backup tunnels to maintain in case of failure,
407how frequently to test the tunnels, how long the tunnels should be, whether those
408lengths should be randomized, how often replacement tunnels should be built, as
409well as any of the other settings allowed when configuring individual tunnels.</p>
411<h3>3.4) <a name="tunnel.building.alternatives">Alternatives</a></h3>
413<h4>3.4.1) <a name="tunnel.building.telescoping">Telescopic building</a></h4>
415<p>One question that may arise regarding the use of the exploratory tunnels for
416sending and receiving tunnel creation messages is how that impacts the tunnel's
417vulnerability to predecessor attacks.  While the endpoints and gateways of
418those tunnels will be randomly distributed across the network (perhaps even
419including the tunnel creator in that set), another alternative is to use the
420tunnel pathways themselves to pass along the request and response, as is done
421in <a href="">TOR</a>.  This, however, may lead to leaks
422during tunnel creation, allowing peers to discover how many hops there are later
423on in the tunnel by monitoring the timing or <a
424href="">packet count</a> as
425the tunnel is built.</p>
427<h4>3.4.2) <a name="tunnel.building.nonexploratory">Non-exploratory tunnels for management</a></h4>
429<p>A second alternative to the tunnel building process is to give the router
430an additional set of non-exploratory inbound and outbound pools, using those for
431the tunnel request and response.  Assuming the router has a well integrated view
432of the network, this should not be necessary, but if the router was partitioned
433in some way, using non-exploratory pools for tunnel management would reduce the
434leakage of information about what peers are in the router's partition.</p>
436<h4>3.4.3) <a name="tunnel.building.exploratory">Exploratory request delivery</a></h4>
438<p>A third alternative, used until I2P 0.6.2, garlic encrypts individual tunnel
439request messages and delivers them to the hops individually, transmitting them
440through exploratory tunnels with their reply coming back in a separate
441exploratory tunnel.  This strategy has been dropped in favor of the one outlined
444<h2>4) <a name="tunnel.throttling">Tunnel throttling</a></h2>
446<p>Even though the tunnels within I2P bear a resemblance to a circuit switched
447network, everything within I2P is strictly message based - tunnels are merely
448accounting tricks to help organize the delivery of messages.  No assumptions are
449made regarding reliability or ordering of messages, and retransmissions are left
450to higher levels (e.g. I2P's client layer streaming library).  This allows I2P
451to take advantage of throttling techniques available to both packet switched and
452circuit switched networks.  For instance, each router may keep track of the
453moving average of how much data each tunnel is using, combine that with all of
454the averages used by other tunnels the router is participating in, and be able
455to accept or reject additional tunnel participation requests based on its
456capacity and utilization.  On the other hand, each router can simply drop
457messages that are beyond its capacity, exploiting the research used on the
458normal internet.</p>
460<h2>5) <a name="tunnel.mixing">Mixing/batching</a></h2>
462<p>What strategies should be used at the gateway and at each hop for delaying,
463reordering, rerouting, or padding messages?  To what extent should this be done
464automatically, how much should be configured as a per tunnel or per hop setting,
465and how should the tunnel's creator (and in turn, user) control this operation?
466All of this is left as unknown, to be worked out for
467<a href="">I2P 3.0</a></p>
Note: See TracBrowser for help on using the repository browser.