source: router/doc/tunnel-alt-creation.html @ 113fbc1d

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

2006-02-15 jrandom

  • Merged in the i2p_0_6_1_10_PRE branch to the trunk, so CVS HEAD is no longer backwards compatible (and should not be used until 0.6.1.1 is out)
  • Property mode set to 100644
File size: 8.2 KB
Line 
1<code>$Id: tunnel-alt-creation.html,v 1.1.2.1 2006/02/01 20:28:34 jrandom Exp $</code>
2<pre>
31) <a href="#tunnelCreate.overview">Tunnel creation</a>
41.1) <a href="#tunnelCreate.requestRecord">Tunnel creation request record</a>
51.2) <a href="#tunnelCreate.hopProcessing">Hop processing</a>
61.3) <a href="#tunnelCreate.replyRecord">Tunnel creation reply record</a>
71.4) <a href="#tunnelCreate.requestPreparation">Request preparation</a>
81.5) <a href="#tunnelCreate.requestDelivery">Request delivery</a>
91.6) <a href="#tunnelCreate.endpointHandling">Endpoint handling</a>
101.7) <a href="#tunnelCreate.replyProcessing">Reply processing</a>
112) <a href="#tunnelCreate.notes">Notes</a>
12</pre>
13
14<h2 id="tunnelCreate.overview">1) Tunnel creation encryption:</h2>
15
16<p>The tunnel creation is accomplished by a single message passed along
17the path of peers in the tunnel, rewritten in place, and transmitted
18back to the tunnel creator.  This single tunnel message is made up
19of a fixed number of records (8) - one for each potential peer in
20the tunnel.   Individual records are asymmetrically encrypted to be
21read only by a specific peer along the path, while an additional
22symmetric layer of encryption is added at each hop so as to expose
23the asymmetrically encrypted record only at the appropriate time.</p>
24
25<h3 id="tunnelCreate.requestRecord">1.1) Tunnel creation request record</h3>
26
27<p>Cleartext of the record, visible only to the hop being asked:</p><pre>
28  bytes     0-3: tunnel ID to receive messages as
29  bytes    4-35: local router identity hash
30  bytes   36-39: next tunnel ID
31  bytes   40-71: next router identity hash
32  bytes  72-103: AES-256 tunnel layer key
33  bytes 104-135: AES-256 tunnel IV key
34  bytes 136-167: AES-256 reply key
35  bytes 168-183: reply IV
36  byte      184: flags
37  bytes 185-188: request time (in hours since the epoch)
38  bytes 189-192: next message ID
39  bytes 193-222: uninterpreted / random padding</pre>
40
41<p>The next tunnel ID and next router identity hash fields are used to
42specify the next hop in the tunnel, though for an outbound tunnel
43endpoint, they specify where the rewritten tunnel creation reply
44message should be sent.  In addition, the next message ID specifies the
45message ID that the message (or reply) should use.</p>
46
47<p>The flags field currently has two bits defined:</p><pre>
48 bit 0: if set, allow messages from anyone
49 bit 1: if set, allow messages to anyone, and send the reply to the
50        specified next hop in a tunnel message</pre>
51
52<p>That cleartext record is ElGamal 2048 encrypted with the hop's
53public encryption key and formatted into a 528 byte record:</p><pre>
54  bytes   0-15: SHA-256-128 of the current hop's router identity
55  bytes 16-527: ElGamal-2048 encrypted request record</pre>
56
57<p>Since the cleartext uses the full field, there is no need for
58additional padding beyond <code>SHA256(cleartext) + cleartext</code>.</p>
59
60<h3 id="tunnelCreate.hopProcessing">1.2) Hop processing</h3>
61
62<p>When a hop receives a TunnelBuildMessage, it looks through the 8
63records contained within it for one starting with their own identity
64hash (trimmed to 8 bytes).  It then decryptes the ElGamal block from
65that record and retrieves the protected cleartext.  At that point,
66they make sure the tunnel request is not a duplicate by feeding the
67AES-256 reply key into a bloom filter and making sure the request
68time is within an hour of current.  Duplicates or invalid requests
69are dropped.</p>
70
71<p>After deciding whether they will agree to participate in the tunnel
72or not, they replace the record that had contained the request with
73an encrypted reply block.  All other records are AES-256/CBC
74encrypted with the included reply key and IV (though each is
75encrypted separately, rather than chained across records).</p>
76
77<h3 id="tunnelCreate.replyRecord">1.3) Tunnel creation reply record</h3>
78
79<p>After the current hop reads their record, they replace it with a
80reply record stating whether or not they agree to participate in the
81tunnel, and if they do not, they classify their reason for
82rejection.  This is simply a 1 byte value, with 0x0 meaning they
83agree to participate in the tunnel, and higher values meaning higher
84levels of rejection.  The reply is encrypted with the AES session
85key delivered to it in the encrypted block, padded with random data
86until it reaches the full record size:</p><pre>
87  AES-256-CBC(SHA-256(padding+status) + padding + status, key, IV)</pre>
88
89<h3 id="tunnelCreate.requestPreparation">1.4) Request preparation</h3>
90
91<p>When building a new request, all of the records must first be
92built and asymmetrically encrypted.  Each record should then be
93decrypted with the reply keys and IVs of the hops earlier in the
94path.  That decryption should be run in reverse order so that the
95asymmetrically encrypted data will show up in the clear at the
96right hop after their predecessor encrypts it.</p>
97
98<p>The excess records not needed for individual requests are simply
99filled with random data by the creator.</p>
100
101<h3 id="tunnelCreate.requestDelivery">1.5) Request delivery</h3>
102
103<p>For outbound tunnels, the delivery is done directly from the tunnel
104creator to the first hop, packaging up the TunnelBuildMessage as if
105the creator was just another hop in the tunnel.  For inbound
106tunnels, the delivery is done through an existing outbound tunnel
107(and during startup, when no outbound tunnel exists yet, a fake 0
108hop outbound tunnel is used).</p>
109
110<h3 id="tunnelCreate.endpointHandling">1.6) Endpoint handling</h3>
111
112<p>When the request reaches an outbound endpoint (as determined by the
113'allow messages to anyone' flag), the hop is processed as usual,
114encrypting a reply in place of the record and encrypting all of the
115other records, but since there is no 'next hop' to forward the
116TunnelBuildMessage on to, it instead places the encrypted reply
117records into a TunnelBuildReplyMessage and delivers it to the
118reply tunnel specified within the request record.  That reply tunnel
119forwards the reply records down to the tunnel creator for
120processing, as below.</p>
121
122<p>When the request reaches the inbound endpoint (also known as the
123tunnel creator), the router processes each of the replies, as below.</p>
124
125<h3 id="tunnelCreate.replyProcessing">1.7) Reply processing</h3>
126
127<p>To process the reply records, the creator simply has to AES decrypt
128each record individually, using the reply key and IV of each hop in
129the tunnel after the peer (in reverse order).  This then exposes the
130reply specifying whether they agree to participate in the tunnel or
131why they refuse.  If they all agree, the tunnel is considered
132created and may be used immediately, but if anyone refuses, the
133tunnel is discarded.</p>
134
135<h2 id="tunnelCreate.notes">2) Notes</h2>
136<ul>
137<li>This does not prevent two hostile peers within a tunnel from
138tagging one or more request or reply records to detect that they are
139within the same tunnel, but doing so can be detected by the tunnel
140creator when reading the reply, causing the tunnel to be marked as
141invalid.</li>
142<li>This does not include a proof of work on the asymmetrically
143encrypted section, though the 16 byte identity hash could be cut in
144half with the later replaced by a hashcash function of up to 2^64
145cost.  This will not immediately be pursued, however.</li>
146<li>This alone does not prevent two hostile peers within a tunnel from
147using timing information to determine whether they are in the same
148tunnel.  The use of batched and synchronized request delivery
149could help (batching up requests and sending them off on the
150(ntp-synchronized) minute).  However, doing so lets peers 'tag' the
151requests by delaying them and detecting the delay later in the
152tunnel, though perhaps dropping requests not delivered in a small
153window would work (though doing that would require a high degree of
154clock synchronization).  Alternately, perhaps individual hops could
155inject a random delay before forwarding on the request?</li>
156<li>Are there any nonfatal methods of tagging the request?</li>
157<li>This strategy came about during a discussion on the I2P mailing list
158    between Michael Rogers, Matthew Toseland (toad), and jrandom regarding
159    the predecessor attack.  See: <ul>
160    <li><a href="http://dev.i2p.net/pipermail/i2p/2005-October/001073.html">Summary</a></li>
161    <li><a href="http://dev.i2p.net/pipermail/i2p/2005-October/001064.html">Reasoning</a></li>
162    </ul></li>
163</ul>
Note: See TracBrowser for help on using the repository browser.