latest network spec draft w/ bit buckets & data structures [draft]
<auto97841-revL73yDgGBWk0Htik3J/[email protected]> Wed, 23 Jul 2003 17:12:40 -0700
| Newsgroups | gmane.comp.security.invisiblenet.iip.devel |
|---|---|
| Message-ID | <[email protected]> |
'lo y'all attached is the network_spec.html as it stands today, including an 80+% done section on the client access layer. (follow the link to #ClientAccessLayer up until #Analysis). Before its done I'm planning on drawing up the bit buckets in the typical fashion you see on all those network protocol diagrams (you know, 32 byte wide rows segmented off for each section), as well as describe more clearly what messages are sent in response to what events or other messages (though hopefully those are already aparent). The reason I'm posting this up incomplete is that the red stuff in that section describes stuff I'm not great at - various crypto algorithms and properties. I'm going to try to get a reference implementation for serializing and deserializing the messages and associated data structures by friday so Hezekiah and Jeremiah can work through them as well as the spec to implement the python stuff. If anyone could give the crypto stuff in that section (and other aspects too, of course) a glance to see if there's something obviously stupid, I'd appreciate it. One thing I'm concerned about (and reason #14 why I'm trying to get a reference implementation of the serialization/deserialization stuff) is that each actual message sent will require two public key operations (one on serialization and one on deserialization) [see #Payload]. I'd like to make sure this'll give us satisfactory performance ok, 'nuff blabbin. you know how to reach me. -jrandom
network_spec.html
(text/html, 80.4 KB)
<html>
<header>
<title>I2P Network Spec Draft 2003.07.23</title>
</header>
<body><a name="Contents"> </a>
<table border="1" >
<tr>
<td width="10%" nowrap valign="top">
<ol>
<li><a href="#Todo">Todo</a></li>
<li><a href="#NetworkOverview">Network Overview</a><ol>
<li><a href="#NetworkGoals">Network Goals and Assumptions</a><ol>
<li><a href="#Goals">Goals</a></li>
<li><a href="#Assumptions">Assumptions</a></li></ol></li>
<li><a href="#NetworkTopology">Network Topology</a><ol>
<li><a href="#Routers">Routers</a></li>
<li><a href="#Tunnels">Tunnels</a><ol>
<li><a href="#TunnelCreation">Tunnel Creation</a></li>
<li><a href="#TunnelOperation">Tunnel Operation</a></li>
<li><a href="#TunnelVerification">Tunnel Verification</a></li>
<li><a href="#TunnelModification">Tunnel Modification</a></li></ol>
<li><a href="#Destinations">Destinations</a></li></ol></li>
<li><a href="#Routing">Routing</a><ol>
<li><a href="#RouterLocation">Router Location</a></li>
<li><a href="#DestinationLocation">Destination Location</a></li>
<li><a href="#DistributedHashTable">Distributed Hash Table</a></li></ol></li>
<li><a href="#UserAndUsageProfiles">User and Usage Profiles</a><ol>
<li><a href="#UserProfiles">User Profiles</a></li><ol>
<li><a href="#JoeSixpack">Joe Sixpack</a></li>
<li><a href="#JanePirate">Jane Pirate</a></li>
<li><a href="#SamTinfoil">Sam Tinfoil</a></li></ol></li>
<li><a href="#UsageProfiles">Usage Profiles</a><ol>
<li><a href="#InstantMessaging">Instant Messaging</a></li>
<li><a href="#FileTransfer">File Transfer</a></li>
<li><a href="#AnonymousEmail">Anonymous Email</a></li></ol></li></ol></li></ol></li>
<li><a href="#NetworkDesign">Network Design</a><ol>
<li><a href="#IdentitiesAndCertificates">Identities and Certificates</a></li>
<li><a href="#Protocols">Protocols</a><ol>
<li><a href="#RouterJoinsNetwork">Router joins the network</a></li>
<li><a href="#RouterLeavesNetwork">Router leaves the network</a></li>
<li><a href="#DestinationJoinsNetwork">Destination joins the network</a></li>
<li><a href="#DestinationLeavesNetwork">Destination leaves the network</a></li>
<li><a href="#DestinationMoves">Destination moves between routers</a></li>
<li><a href="#RouterCreatesTunnel">Router creates a tunnel</a></li>
<li><a href="#RouterTestDestroyTunnel">Router tests / destroys a tunnel</a></li>
<li><a href="#MessageDelivery">Message delivery</a></li>
<li><a href="#RouterAdjustsTunnel">Router adjusts a tunnel</a></li></ol></li>
<li><a href="#MessageData">Message Data</a></li>
<li><a href="#Encryption">Encryption</a></li></ol></li>
<li><a href="#NetworkDetails">Network Details</a><ol>
<li><a href="#Transports">Transports</a></li>
<li><a href="#NetworkMessageByteStructure">Network Message Byte Structure</a></li></ol></li>
<li><a href="#ClientAccessLayer">Client Access Layer</a><ol>
<li><a href="#ClientAccessLayerMessages">Client Access Layer Messages</a><ol>
<li><a href="#ClientToRouterMessages">Client To Router</a></li>
<li><a href="#ClientAdminToRouterMessages">Client Admin To Router</a></li>
<li><a href="#RouterToClientMessages">Router To Client</a></li>
<li><a href="#RouterToClientAdminMessages">Router To Client Admin</a></li>
<li><a href="#BidirectionalMessages">Bidirectional</a></li></ol></li>
<li><a href="#ClientAccessLayerDataStructures">Client Access Layer Data Structures</a><ol>
<li><a href="#SessionConfig">SessionConfig</a></li>
<li><a href="#Destination">Destination</a></li>
<li><a href="#LeaseRevocation">LeaseRevocation</a></li>
<li><a href="#SessionId">SessionId</a></li>
<li><a href="#LeaseRevocationPrivateKey">LeaseRevocationPrivateKey</a></li>
<li><a href="#Lease">Lease</a></li>
<li><a href="#Payload">Payload</a></li>
<li><a href="#MessageId">MessageId</a></li>
<li><a href="#AuthenticationKey">AuthenticationKey</a></li>
<li><a href="#BandwidthLimits">BandwidthLimits</a></li>
<li><a href="#RouterIdentity">RouterIdentity</a></li>
<li><a href="#RouterInfo">RouterInfo</a></li>
<li><a href="#RouterAddress">RouterAddress</a></li>
<li><a href="#TunnelId">TunnelId</a></li>
<li><a href="#AbuseReason">AbuseReason</a></li>
<li><a href="#AbuseSeverity">AbuseSeverity</a></li></ol></li>
</ol></li>
<li><a href="#Analysis">Analysis</a><ol>
<li><a href="#Attacks">Attacks</a><ol>
<li><a href="#TrafficAnalysis">Traffic Analysis</a></li>
<li><a href="#IntersectionAttack">Intersection Attack</a></li>
<li><a href="#FloodingAttacks">Flooding Attacks</a></li>
<li><a href="#LegalAttacks">Legal Attacks</a></li></ol></li>
<li><a href="#Performance">Performance</a></li></ol></li>
<li><a href="#Ideas">Ideas</a></li>
</ol>
</td>
<td valign="top">
<font color="red">
<h1>Todo <a name="Todo"></a></h1>
<ul>
<li>Describe how to detect and recover from failures to contact routers at their
addresses</li>
<li>Explain why the topology and routing meets the goals</li>
<li>Analysis</li>
<li>Deal with <a href="#Ideas">ideas</a></li>
<li>Finish the red questions</li>
</ul>
</font>
<h1>Network Overview<a name="NetworkOverview"></a> <font size="-1"><a href="#Contents">(top)</a></font></h1>
<h2>Network Goals and Assumptions<a name="NetworkGoals"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<h3>Goals<a name="Goals"></a></h3>
<ul>
<li>User determined anonymity - from identifiable to militant grade anonymity</li>
<li>Scalability beyond millions of concurrent users</li>
<li>Operate regardless of network obstrutions</li>
<li>Able to operate even when an active global opponent tries to shut it down</li>
</ul>
<h3>Assumptions<a name="Assumptions"></a></h3>
<ul>
<li>Local computer is trusted (does not have key loggers, does not distributed secrets, etc)</li>
<li>Cryptography used cannot be practically defeated (including hash collisions and decryption)</li>
<li>User understand their anonymity choices and does not violate them through other means</li>
</ul>
<h2>Network Topology<a name="NetworkTopology"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
There are three toplogical constructs in this network:
<ul>
<li><b>Routers</b> - the software that routes messages to the appropriate destination</li>
<li><b>Tunnels</b> - sequences of routers that pass messages down the tunnel</li>
<li><b>Destinations</b> - mobile end points where messages are delivered to</li>
</ul>
<img src="topology.png" alt="network topology"><p />
Routers communicate with other routers to manage tunnels, distribute routing tables,
deliver messages, detect attacks, and detect failures. <p />
Destinations connect to a particular router and authorizes that router to build tunnels on its behalf,
thereby enabling the router to recieving and forward to the destination any messages destined to it.
Destinations also communicate with the router to instruct it to deliver a message to another destination.
Finally, destinations move between routers, instructing routers to rebuild, extend, or tear down old tunnels. <p />
Tunnels are one way pipes for delivering messages. Messages sent to a tunnel's entry point are
piped down the network of routers forming the tunnel along with verifying information to assure that the
data is not tagged along the way and encrypted instructions to the endpoint on how to handle the message.
Once the message reaches the endpoint of the tunnel, that router unwraps the tunnel-specific encryption to
determine how to handle it. The unwrapped message may not have further instructions, in which case the
endpoint consults a local mapping to determine whether to deliver that message to a local destination, forward
to another destination, or forward it to another tunnel. However, the unwrapped message may specify that it requires
forwarding to another destination or router, thereby allowing tunnels to be used as source routed messages. <p /.
Tunnels may be configured with several options, such as whether to reoder messages before passing them down,
whether to include dummy traffic, whether to pad messages to a constant size, what constraints to place on
forwarding messages past the endpoint, and how many messages that tunnel can handle in a time period.<p />
Outbound messages are handled by having a destination instruct its router to deliver a message to another
destination. The router then uses a tunnel built facing away from itself towards no particular router in
the network and forwards the message along it. Once it reaches the end of the tunnel, the endpoint searches
for a tunnel that can recieve messages targetting the intended destination, and once it finds one, it delivers
it there. This essentially builds the network into a series of disjointed tunnels delivering messages to mobile
destinations.
<h3>Routers <a name="Routers"></a></h3>
Routers are long lasting processes with their own public/private key pair. Routers should accept network messages at a
variety of addresses on several transports. Routers may allow destinations to connect to them and build appropriate
tunnels to meet the destination's anonymity, latency, bandwidth, and reliability needs. Routers should honor the protocols
described <a href="#Protocols">below</a>. Routers may attempt to hide their very existance with stegonographic techniques.
Router software should run on a variety of operating systems be able to be written in a variety of languages.
<h3>Tunnels <a name="Tunnels"></a></h3>
Each tunnel is constructed of three components - a gateway, a series of intermediary routers, and an endpoint.
<h4>Tunnel creation <a name="TunnelCreation"></a></h4>
To create a tunnel, the creating router sends a message to each of the routers that will make up the tunnel
specifying the tunnel's identifier, the next step in the tunnel, a private configuration key, a key that message verification
information will be signed with, and any configuration options for the tunnel (such as how many messages to let through
in a time period, a payment certificate, or a period during which the tunnel should operate). The endpoint and gateway
both recieve additional information - the endpoint is given a public/private keypair for the tunnel (which is seperate
from that router's public key), as well as an instruction as to where messages from the tunnel should be delivered (to a
destination or to another router). The gateway is given the tunnel endpoint's public key, as well as the signing keypair for
generating message verification information. The router creating the tunnel may then update the distributed routing table to
reflect the reachability of the location that the endpoint is configured to deliver
messages to.<p />
<h4>Tunnel operation<a name="TunnelOperation"></a></h4>
Gateways recieve messages addressed to the tunnel via:
<ul>
<li><code>{payload, tunnel}</code>: simply tunnel the message, specifying a null nextStep for the endPoint</li>
<li><code>{payload, tunnel, E(nextStep, endpointPublicKey)}</code>: tunnel the message and instruct the endpoint to
forward the message on to the nextStep (which is a destination, tunnel, or router and contains a certificate)</li>
<li><code>{payload, tunnel, nextStep}</code>: tunnel the message and instruct the endpoint to forward the message on
to the nextStep (which is a destination, tunnel, or router and contains a certificate). Both the tunnel and the endpoint
may decide whether the certificate provided is satisfactory (e.g. the certificate may be a hashcash calculation of N bits
of an entangling of payload, tunnel, nextStep, and date, or the certificate may be a payment certificate delivered to a
satisfactory account)</li>
</ul>
Once recieving the message and determining that it is valid, the gateway uses or constructs an nextStep structure
(encrypted to the endPoint's public key), builds a verification structure to pass the message along the tunnel, and
passes it along at the next available moment. <p />
The resulting touple passed from the gateway through the tunnel to the end is <br />
<code>{payload, tunnel, E(nextStep, endpointPublicKey), deliverySignature}</code><p />
The deliverySignature is a signed hash of the rest of the message's bytes (payload, tunnel, and encrypted nextStep),
signed by the gateway's signing key. Each router along the way verifies the signature and the hash, passing along
the message only if it matches. <p />
<h4>Tunnel verification<a name="TunnelVerification"></a></h4>
Periodically, the controlling router or any router with the endpointPublicKey can test the tunnel by sending a message down
the tunnel and checking whether the message is received at the location the endpoint is supposed to deliver it to.
<h4>Tunnel modification<a name="TunnelModification"></a></h4>
The tunnel may be modified either by the gateway or by the controlling router to either change the operational options,
adjust the routers in the tunnel, or change where the endpoint delivers messages. Routers in the tunnel accept commands to
modify their next step or their operation by recieving a control message encrypted with the step's configuration key. The
endpoint accepts a command to change where the it should deliver messages when encrypted with the tunnel endpoint's private
key.
<h3>Destinations<a name="Destinations"></a></h3>
Destinations are the mobile endpoints where messages are delivered to and are identified by their public keys. After routers
create tunnels for destinations, they authorize updates to the distributed routing tables defining locations where messages
can be delivered. Destinations can be distributed as simple public keys or they may also include a certificate (e.g. hashcash
based on the public key or a receipt for real cash payment). Routers and applications may decide not to build tunnels for or
deliver messages to destinations with insufficient payment.
<h2>Routing<a name="Routing"></a></h2>
Routing in the network is handled both locally and through a distributed hash table. Each router keeps information on its
peers and other routers it has contacted. In addition, each router has their own RouterInfo data structure which contains:<br />
<code>{routerIdentity, (routerAddress)*, (peerIdentityHash)*, (stats)*, (options)*, versionNum, signature}</code>
<ul>
<li><code>routerIdentity</code>: the router's identification, which itself is a public key with which messages addressed to
this router can be encrypted plus an optional certificate</li>
<li><code>(routerAddress)*</code>: set of 0 or more physical addresses that messages can be delivered to that the router
will recieve. Each routerAddress itself is the structure: <code>{style, expiration, ttlCost, (details)*}</code>, with
style defining the general communication mechanism (tcp sockets, email, polling http, etc), expiration is the date after
which the address should not be used, ttlCost is a generic estimated delay describing how long delivery to this address
may take, and details provides a set of 0 or more options specific to each address style (such as hostname, port number,
email address, etc)</li>
<li><code>(peerIdentityHash)*</code>: set of 0 or more hashcodes of the identities of peers the router has contacted, which
may be used in choosing routers for building tunnels.</li>
<li><code>(stats)*</code>: set of 0 or more name-value pairs containing historical statistical information the router has
accumulated. Everything may be entirely false or nonexistant.</li>
<li><code>(options)*</code>: set of 0 or more options advertising what the router will or will not do, what minimums for bandwidth,
latency, or reliability it may require for peering, fees for tunneling or forwarding, and the like</li>
<li><code>versionNum</code>: higher version numbers replace older routerInfo structures</li>
<li><code>signature</code>: signature of the router that the structure is authentic (though the stats may be incorrect and the
rest of the structure may be incomplete</li>
</ul>
These RouterInfo data structures are stored in the distributed hash table at <code>H(routerIdentity)</code> and will not be
inserted or propogated unless the signature matches.<p />
Another structure used for routing is the RouterSighting, which contains:<br />
<code>{sightedRouter, sightedBy, sightedDate, expiration, sightedRouterSignature, sightedBySignature}</code>
<ul>
<li><code>sightedRouter</code>: routerIdentity of the router that was seen</li>
<li><code>sightedBy</code>: routerIdentity of the router that saw the other router</li>
<li><code>sightedDate</code>: date on which the router was sighted</li>
<li><code>expiration</code>: date after which the router will most likely not be able to see the sighted router</li>
<li><code>sightedRouterSignature</code>: signature of the router that was seen</li>
<li><code>sightedBySignature</code>: signature of the router that saw the other router</li>
</ul>
These RouterSighting structures are useful for trusted links, where the sightedRouter does not want to advertize their address,
but they still want to be reachable. They trust the sightedBy router by giving them an address they can use, then create the
RouterSighting structure, leaving sightedBySignature blank, and give it to the sightedBy router, which then signs it and inserts
it into the distributed hash table at <code>H(sightedRouter)</code>.<p />
The next structure used for routing is the Lease, which contains:<br />
<code>{destination, gatewayRouter, tunnel, startDate, endDate, revocationPublicKey, signature}</code>
<ul>
<li><code>destination</code>: H(destination) of the location creating the lease</li>
<li><code>gatewayRouter</code>: H(gatewayRouter's identity) of the router serving as the gateway to a tunnel</li>
<li><code>tunnel</code>: name of the tunnel on the gatewayRouter that delivers messages to the destination</li>
<li><code>startDate</code>: date after which the tunnel should be used</li>
<li><code>endDate</code>: date after which the tunnel should not be used</li>
<li><code>revocationPublicKey</code>: public key that may be used to revoke this lease if the destination is unable
to do so (usually the private key for revocation is held by the router that created the tunnel)</li>
<li><code>signature</code>: signature of the Lease by the destination</li>
</ul>
The set of signed leases are stored in the distributed hash table at <code>H(destination)</code><p />
On the other side of the Lease is the LeaseRevocation - a signed statement that a lease is no longer valid.
The LeaseRevocation passes through the network just as the Lease does, except it destroys the referred to
Lease in its wake. LeaseRevocations need not necessarily be kept around after destroying a Lease at a particular
router, but they may be for a small period of time in case other copies of that Lease are still floating around.
The LeaseRevocation structure contains:<br />
<ul>
<li><code>destination</code>: H(destination) of the location creating the lease</li>
<li><code>gatewayRouter</code>: H(gatewayRouter's identity) of the router serving as the gateway to a tunnel</li>
<li><code>tunnel</code>: name of the tunnel on the gatewayRouter that delivers messages to the destination</li>
<li><code>startDate</code>: date after which the tunnel should be used</li>
<li><code>endDate</code>: date after which the tunnel should not be used</li>
<li><code>signature</code>: signature of the LeaseRevocation by the private key associated with the Lease's
revocationPublicKey</li>
</ul>
<h3>Router location<a name="RouterLocation"></a></h3>
When a router wants to contact another router, it can check two places. First, it looks in its own local routing tables for
the router in case it has already contacted it either directly or through another router. If it doesn't find the router there,
it does a lookup in the distributed hash table for <code>H(routerIdentity)</code>, which will return the router's RouterInfo
plus any RouterSightings. If the RoutingInfo has an address the current router can use, it can contact them that way. If not,
the router does lookups in the distributed hash table for <code>H(routerSighting.sightedBy)</code> trying to find a reachable
router, and going on recursively from there (limited by various constraints, depending on the reason for contacting the remote
router). <p />
<font color="red"><b>[Finding a way to contact a router should be quick - is it? Prove it]</b><br />
<b>[prove DHT get(k) is O(log(n))]</b></font>
<h3>Destination location<a name="DestinationLocation"></a></h3>
When a router wants to send a message to a destination, it first checks its local destination routing tables to see if it has
already found a way to do so. If not, it does a distributed hash table lookup for H(destination) which will retrieve a set of
Lease structures for the destination. The router then chooses which of them to use to deliver the message. If necessary, it then
does a router lookup to find a contactable address for the gateway router.
<h3>Distributed hash table<a name="DistributedHashTable"></a></h3>
The routing information for the network is distributed between the routers randomly and cached according to their popularity.
When a router wants to insert a value into the hash table, it compares the hash of the key to be inserted with the hash of the
router's peers to select the next routers to forward the message to. It then forwards the messages to the K closest matches
that it didn't get the request from. <font color="red"><b>[What value of K? 1? 3? log(numPeers)? What impact will this
have on bandwidth vs. latency?]</b></font>. For inserts, prior to forwarding the message it verifies the signatures for the
four types of things that can be inserted (RouterInfo, RouterSighting, Lease, LeaseRevocation). If the signatures don't
match, the message is dropped. If they do, the router may cache the information locally prior to forwarding it on. When a
router wants to get a value out of the hash table, it compares the hash of the key to be fetched as with inserts, though it
remembers what peer sent it the request. If/when it recieves a match, it forwards the message back along that path,
verifying its authenticity and potentially caching the data. Each message within the hash table has a hops to live number
that is decremented at each step.<p />
This distributed hash table has the property of no maintenance cost, as compared to Chord or Tapestry. This makes the hash table
aim towards the emergent properties of Freenet. <font color="red"><b>[Is this a good thing? Should we add the structural DHT overhead to guarantee
O(log(n)) lookups / inserts in exchange for maintenance messages?]</b></font>
<h2>User and Usage Profiles<a name="UserAndUsageProfiles"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<h3>User profiles<a name="UserProfiles"></a></h3>
<font color="red"><b>[Show how these three users would configure their destinations to meet their needs]</b></font>
<h4>Joe Sixpack<a name="JoeSixpack"></a></h4>
Just wants to use applications that run over the network, and is not concerned with anonymity.
<h4>Jane Pirate<a name="JanePirate"></a></h4>
Wants to run applictaions over the network without worrying about DMCA/EUCD compliance
<h4>Sam Tinfoil<a name="SamTinfoil"></a></h4>
Believes They are out to get them, in fear for one's life.
<h3>Usage profiles<a name="UsageProfiles"></a></h3>
<font color="red"><b>[Show how these three applications could be implemented over the network]</b></font>
<h4>Instant messaging<a name="InstantMessaging"></a></h4>
Low latency, small messages delivered every few seconds (or more frequently)
<h4>File transfer<a name="FileTransfer"></a></h4>
Low latency isn't necessary as long as the overall clock time stays small
(delay + high bandwidth)
<h4>Anonymous email<a name="AnonymousEmail"></a></h4>
Latency is not an issue, and messages may require bandwidth.
<h1>Network Design<a name="NetworkDesign"></a> <font size="-1"><a href="#Contents">(top)</a></font></h1>
<h2>Identities and Certificates<a name="IdentitiesAndCertificates"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red"><b>[define data structures, algorithms, and performance characteristics]</b></font>
<h2>Protocols<a name="Protocols"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
There are a number of events which require collaboration between network components - below they are enumerated along with
the message sequences necessary to facilitate each.
<h3>Router joins the network<a name="RouterJoinsNetwork"></a></h3>
When a new router wants to join the network, it first must build its own identity -
which includes a keypair plus perhaps a certificate (hashcash or realcash, depending
upon what routers it connects to). After it has that, it retrieves a set of seed nodes
to connect to (seed nodes are plain text versions of the various RouterInfo structures).
Once it has the identity plus a set of seed nodes, it builds its own RouterInfo
structure and then connects to some of the seed nodes closest to the hashcode for its
own identity and does a hash table put(H(newRouterIdent), newRouterInfo). The routers
recieving the message handle it like all other hash table operations (validate, cache,
propogate). To assist in rapid network integration, the routers recieving the message
may decide to send back a few hash table entries to the new router, including other
RouterInfo structures and Leases.
<h3>Router leaves the network<a name="RouterLeavesNetwork"></a></h3>
When a router is no longer reachable at any of its addresses, or its H(routerIdentity)
hash table entry isn't accessible, it is considered no longer a part of the network.
The hash table entries are removed when routers are unable to contact it, or when the
router updates its RouterInfo structure to have no addresses and no peers.
<h3>Destination joins the network<a name="DestinationJoinsNetwork"></a></h3>
When a new destination wants to join the network, first it must generate its identity
and create/retrieve an appropriate certificate. It then locates a trusted router
(typically run by the same person who owns the destination). The destination then
connects to the trusted router and instructs it to create a session, specifying various
configuration options and proving its ownership of the destination's identity. Several
of the options define how many inbound (for recieving messages at the destination) and
outbound (for sending messages from the destination) tunnels to create and other
anonymity requirements. The trusted router authenticates the information and selects a
set of routers to fashion the various tunnels requested by the user. <p />
For each of those
soon-to-be tunnels, it contacts to the various routers, as described <a href="#TunnelCreation">above</a>
After each tunnel is created, the trusted router provides the destination with the various criteria it
needs to authorize a lease (<code>{H(tunnelGatewayRouterIdentity), tunnelIdentifier, startDate,
endDate}</code>), which the destination then authorizes by signing it, creating a
lease revocation keypair, creating a Lease structure out of that information, and then providing
the Lease and the revocation private key to the trusted router. The trusted router then
inserts the Lease into the hash table at H(destinationIdentity).<p />
Once all of the tunnels have been built, the trusted router notifies the destination that
it has joined the network successfully.
<h3>Destination leaves the network<a name="DestinationLeavesNetwork"></a></h3>
When a destination is leaving the network, it should instruct the router it is connected with to
revoke all of the leases for the destination. If the destination fails to do so but the router
detects that it can no longer communicate with the destination, the router may decide to revoke
the leases without being instructed to do so. The revocation occurs by inserting a LeaseRevocation
structure (<code>{destination, gatewayRouter, tunnel, startDate, endDate, signature}</code>) signed
by the Lease's revocation private key. This LeaseRevocation is inserted at H(destination), and when
a router with a LeaseRevocation sees a Lease it refers to, it drops the Lease (and may drop the
LeaseRevocation, pass it on to the router that sent it recieved the Lease from, or both).
<h3>Destination moves between routers<a name="DestinationMoves"></a></h3>
When a destination wants to disconnect from a router (Router1) and move to another router (Router2),
it connects to Router2 and creates a session (it may or may not ask Router2 to go ahead and create
tunnels). Once it has successfully connected to Router2, it then instructs Router2 to send a message
to Router1 to have all messages destined for the destination passed on to Router2. This instruction must
be signed by the destination. Router1 then contacts the endpoints of all of the destination's tunnels and
instructs them to forward messages to Router2 instead of Router1, authenticated by the tunnel's
configuration key. This leaves the existing tunnels intact and essentially just changes what the endpoint
does. If however the destination wants a whole new set of tunnels and endpoints, it should simply disconnect
from Router1, have Router1 destroy all the previous tunnels, and reconnect to Router2 (this adds security in
that Router1 doesn't know where the destination went, or whether its coming back).
<h3>Router creates tunnel<a name="RouterCreatesTunnel"></a></h3>
See section <a href="#TunnelCreation">above</a>.
<h3>Router tests and/or destroys tunnel<a name="RouterTestDestroyTunnel"></a></h3>
Periodically, the tunnel's gateway will send a message down the tunnel with the nextStep encrypted to the
tunnel's endpoint, instructing it to forward the message back to the gateway itself. If the message isn't
recieved or the average reception time is too slow, it ceases to run the tunnel. In addition, the tunnel's
creator will periodically send a message down the tunnel in the same way (with an encrypted nextStep pointing
at the creator), and if it isn't recieved or the tunnel performs too poorly, it considers the tunnel dead
and attempts to contact each router making up the tunnel to instruct them to tear it down (authenticated by
the various configuration keys). After tearing it down, the creating router inserts a LeaseRevocation into
the distributed hash table, propogating the fact that the destination formerly reachable through that tunnel
is no longer reachable there.
<h3>Message delivery<a name="MessageDelivery"></a></h3>
<img src="topology-delivery.png"><p />
The first thing that happens in a normal message delivery is that the destination passes the local router
both the payload of the message and the destination to which it should be delivered. The local router then
should do a lookup for H(targetDestination) to find a lease to which the message should be delivered. The
message is then passed down an arbitrary outbound tunnel with the nextStep specifying either a gateway/tunnel
pair (if the local router found a lease it wants to use) or the original target destination. If the local
router did not specify a gateway/tunnel pair, the outbound tunnel endpoint does a lease lookup when it recieves
the message. Once a gateway/tunnel pair is known, the outbound tunnel endpoint does a lookup for an address
at which the gateway may be reached as described <a href="#RouterLocation">above</a>. After a contact mechanism
is known, the outbound tunnel endpoint forwards the message to it for delivery.
The recieving tunnel gateway accepts the message, creates a verification structure, and passes it down the tunnel
to the target destination, which then delivers it to the destination. <p />
Failures may occur at various points, and message delivery may not be guaranteed. Tunnels should be tested
sufficiently that they can be considered fairly reliable and the underlying transports must not deliver messages
partially, though the loss of an entire message is possible. <font color="red"><b>Discuss how ACKs can be implemented
to build reliable delivery</b></font>. Applications requiring guaranteed message delivery
should use systems of acknowledgements or redundancy as appropriate.
<h3>Router adjusts tunnel<a name="RouterAdjustsTunnel"></a></h3>
If the router that created the tunnel decides its performance is poor, rather than tear it down it may instead
reconstruct it by replacing steps without removing the gateway. It does so by contacting the new routers as if
they were part of a newly created tunnel (possibly nominating a new endpoint). After the new routers are in place,
it readjusts the routers in the old tunnel by sending them messages instructing them to update their 'next hop' to
a different router.
<h2>Message Data<a name="MessageData"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red"><b>[Explicitly review the data points alluded to in the <a href="#NetworkTopology">network topology</a> section]</b></font>
<h2>Encryption<a name="Encryption"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red"><b>[Define what encryption standards and methods are to be used for the various signing, encryption, and hashing features]</b></font>
<h1>Network Details<a name="NetworkDetails"></a> <font size="-1"><a href="#Contents">(top)</a></font></h1>
<h2>Transports<a name="Transports"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red"><b>[Define UDP, TCP, HTTP, Polling HTTP transports]</b></font>
<h2>Network Message Byte Structure<a name="NetworkMessageByteStructure"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red"><b>[Define the byte by byte structure for the inter-router message structures so that other router implementations can be made]</b></font>
<h1>Client Access Layer<a name="ClientAccessLayer"></a> <font size="-1"><a href="#Contents">(top)</a></font></h1>
Communication between clients and routers goes on asynchronously over sockets as messages. APIs in different languages can be
developed to simplify this operation, but the various APIs are outside the scope of this specification. The socket
communication between the client and the router is asynchronous over bidirectional TCP sockets and is currently not
encrypted, but may be in the future.
<p />
All messages sent between the client and the router begin with a 4 byte unsigned number in network byte order
specifying the size of the remaining message. After that comes a 1 byte unsigned number in network byte order specifying
the type of message, after which the rest of the message is formatted according to the type of message,
as specified below. If there is a fatal error causing either the client or the router to desire to cancel
sending a message part way through, it should drop its connection. Administrative sessions are not
stateful (aka each administrative message from client to router must provide authentication), but
normal client sessions are stateful and survive disconnects. Client sessions expire when either the
client sends a DestroySessionMessage or the router times out the session according to its own
configurable timer. If a client sends any message other than a CreateSessionMessage when there is no
valid session, the router must reply with a SessionStatusMessage specifying that the session is not
valid.<p />
For public keys, the key listed in these structures are the exponent only - the rest of the key is:<br />
<font color="red"><b>[insert known good primes for the various PKI components]</b></font><p />
<h2>Client access layer messages<a name="ClientAccessLayerMessages"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<table border="1">
<tr><td nowrap><b>Type</b></td><td nowrap><b>Message name</b></td><td nowrap><b>Direction</b></td><td nowrap><b>Admin?</b></td><td nowrap><b>Fields</b></td><td><b>Contents</b></td></tr>
<tr><td colspan="6"><b>Client to Router<a name="ClientToRouterMessages"></a></b><hr></td></tr>
<tr><td valign="top">1</td><td valign="top">CreateSessionMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionConfig">SessionConfig</a></td><td>
The content of the message is a SessionConfig structure, serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>This is what the client sends to its local trusted router to join the network</i></td></tr>
<tr><td valign="top">2</td><td valign="top">ReconfigureSessionMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#SessionConfig">SessionConfig</a> </td><td>
The content of the message is a SessionId structure followed by a
SessionConfig structure, both serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>This is what the client sends to the router to have a session changed - various
options reconfigured and possibly some resources released</i></td></tr>
<tr><td valign="top">3</td><td valign="top">DestroySessionMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a></td><td>
The content of the message is a SessionId structure, serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>This is what the client sends to the router to have a session destroyed and all
resources released</i></td></tr>
<tr><td valign="top">4</td><td valign="top">CreateLeaseMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#LeaseRevocationPrivateKey">LeaseRevocationPrivateKey</a>, <a href="#Lease">Lease</a></td><td>
The content of the message is a SessionId structure, followed by a LeaseRevocationPrivateKey and then
a Lease structre, all serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>This is how the client grants a lease to the router for a tunnel, including the
private key the router can use to revoke the lease later on if necessary.</i></td></tr>
<tr><td valign="top">5</td><td valign="top">SendMessageMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#Destination">Destination</a>, <a href="#Payload">Payload</a></td><td>
The content of the message is a SessionId structure, followed by a Destination structure and then
a Payload structre, all serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>This is how a client sends a message (the payload) to the destination. The API
implementation of this access layer should provide transparent encryption of the payload to the destination's public key
in the same way that it should handle transparent decryption of the payload when recieved via deliverMessage below - the
private keys should never be given to the router. As such, the router shouldn't do any encryption of the message beyond
transport layer encryption, but the access libraries should.</i></td></tr>
<tr><td valign="top">6</td><td valign="top">RecieveMessageBeginMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#MessageId">MessageId</a></td><td>
The content of the message is a SessionId structure, followed by a MessageId structure, all serialized as
specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Request the router to deliver a message that it was previously notified of</i></td></tr>
<tr><td valign="top">7</td><td valign="top">RecieveMessageEndMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#MessageId">MessageId</a></td><td>
The content of the message is a SessionId structure, followed by a MessageId structure, all serialized as
specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the router that delivery of a message was completed
successfully and that the router can discard the message</i></td></tr>
<tr><td colspan="6"><b>Client Admin to Router<a name="ClientAdminToRouterMessages"></b><hr></td></tr>
<tr><td valign="top">9</td><td valign="top">GetBandwidthLimitsMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a></td><td>
The content of the message is an AuthenticationKey structure serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Request that the router tell the application what its current bandwidth limits are</i></td></tr>
<tr><td valign="top">10</td><td valign="top">SetBandwidthLimitsMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a>, <a href="#BandwidthLimits">BandwidthLimits</a></td><td>
The content of the message is an AuthenticationKey structure, followed by a BandwidthLimits structure, both serialized as
specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Configure the router with new bandwidth limits</i></td></tr>
<tr><td valign="top">11</td><td valign="top">GetTrustedRoutersMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a></td><td>
The content of the message is an AuthenticationKey structure serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Retrieve the set of trusted routers</i></td></tr>
<tr><td valign="top">12</td><td valign="top">SetTrustedRoutersMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a>, H(<a href="#RouterIdentity">RouterIdentity</a>)[]</td><td>
The content of the message is an AuthenticationKey structure, followed by a list of zero or more hashes derived from the
RouterIdentity data structure. The AuthenticationKey serialization is listed below, and the hash is
<font color="red">the SHA-256 hash of the RouterIdentity</font>.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Configure what routers the local router should trust</i></td></tr>
<tr><td valign="top">13</td><td valign="top">GetAddressVisibilityMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a></td><td>
The content of the message is an AuthenticationKey structure serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Determine if the router is hiding its addresses or not</i></td></tr>
<tr><td valign="top">14</td><td valign="top">SetAddressVisibilityMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a>, boolean</td><td>
The content of the message is an AuthenticationKey structure serialized as specified below, followed by a one byte unsigned number
in network byte order set to zero if only trusted routers should be given addresses with which to contact the router, or set to one if the router is
allowed to publish its addresses more freely</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Configure the router to hide or publish its addresses</i></td></tr>
<tr><td valign="top">15</td><td valign="top">GetAddressRotationPeriodMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a></td><td>
The content of the message is an AuthenticationKey structure serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Determine after how long the router will automatically rotate its addresses</i></td></tr>
<tr><td valign="top">16</td><td valign="top">SetAddressRotationPeriodMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a>, #seconds delay</td><td>
The content of the message is an AuthenticationKey structure serialized as specified below followed by a 2 byte unsigned number
in network byte order specifying the number of seconds after which the router is obliged to rotate its contact addresses. If
this number is all zeroes, then the router is never obliged to rotate its contact addresses.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Configure the router to periodically rotate its addresses</i></td></tr>
<tr><td valign="top">17</td><td valign="top">ForceAddressRotationMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a></td><td>
The content of the message is an AuthenticationKey structure serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Instruct the router to rotate its addresses as soon as possible</i></td></tr>
<tr><td valign="top">18</td><td valign="top">GetPeersMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a></td><td>
The content of the message is an AuthenticationKey structure serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Retrieve the set of peers the router knows about and will communicate with</i></td></tr>
<tr><td valign="top">19</td><td valign="top">SetPeersMessage</td><td nowrap valign="top">Client to Router</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#AuthenticationKey">AuthenticationKey</a>, <a href="#RouterInfo">RouterInfo</a>[]</td><td>
The content of the message is an AuthenticationKey structure, followed by a list of zero or more RouterInfo structures, all
serialized as specified below. </td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Configure the set of peers the router knows about and will communicate with</i></td></tr>
<tr><td colspan="6"><b>Router to Client<a name="RouterToClientMessages"></b><hr></td></tr>
<tr><td valign="top">20</td><td valign="top">SessionStatusMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, status code</td><td>
The content of the message is a SessionId structure serialized as specified below, followed by a one byte unsigned number in
network byte order specifying the status of the session. Status values include zero for destroyed, one for created, two
for updated, and three for invalid session.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Instruct the client as to the status of its session</i></td></tr>
<tr><td valign="top">21</td><td valign="top">RequestLeaseMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#RouterIdentity">RouterIdentity</a>, <a href="#TunnelId">TunnelId</a>, Start date, End date</td><td>
The content of the message is a SessionId structure, followed by the RouterIdentity for the router serving as the inbound
gateway of the tunnel being created, the TunnelId, the start date, and finally the end date for the lease, all of
which are serialized as specified below. Dates are formatted as 8 byte unsigned numbers in network byte order specifying the number
of seconds since midnight on January 1, 1970 in the GMT time zone. The value of all zeroes means null (no end or start
date).</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Request that a client authorize the creation of an inbound tunnel through a Lease</i></td></tr>
<tr><td valign="top">22</td><td valign="top">MessageStatusMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#MessageId">MessageId</a>, delivery code</td><td>
The content of the message is an SessionId structure, followed by the MessageId structure, and finally a one byte unsigned number
in network byte order determining the delivery status, all of which are serialized as specified below. The delivery status
values include 0 for failed, 1 for accepted, 2 for likely delivered, 3 for guaranteed delivery.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Notify the client of the delivery status of the last message sent via a SendMessageMessage</i></td></tr>
<tr><td valign="top">23</td><td valign="top">MessageAvailableMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#MessageId">MessageId</a>, #bytes in message</td><td>
The content of the message is a SessionId structure followed by a MessageId structure and then a four byte unsigned number in
network byte order specifying the size of the message in bytes, with the structures serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Notify the client that a new inbound message is available for it</i></td></tr>
<tr><td colspan="6"><b>Router to Client Admin<a name="RouterToClientAdminMessages"></b><hr></td></tr>
<tr><td valign="top">24</td><td valign="top">BandwidthLimitsMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#BandwidthLimits">BandwidthLimits</a></td><td>
The content of the message is the BandwidthLimits structure serialized as specified below. </td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the client what the router's current bandwidth limits are</i></td></tr>
<tr><td valign="top">25</td><td valign="top">TrustedRoutersMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">Yes</td><td valign="top">H(<a href="#RouterIdentity">RouterIdentity</a>)[]</td><td>
The content of the message is a list of zero or more hashes derived from the
RouterIdentity data structure. The hash is <font color="red">the SHA-256 hash of the RouterIdentity</font>.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the client what routers are currently trusted</i></td></tr>
<tr><td valign="top">26</td><td valign="top">AddressVisibilityMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">Yes</td><td valign="top">boolean</td><td>
The content of the message is a one byte unsigned number in network byte order set to zero if only trusted routers should be given
addresses with which to contact the router, or set to one if the router is allowed to publish its addresses more
freely.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the client whether the router currently publishes its address information publicly</i></td></tr>
<tr><td valign="top">27</td><td valign="top">AddressRotationPeriodMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">Yes</td><td valign="top"># seconds delay</td><td>
The content of the message is a 2 byte unsigned number in network byte order specifying the number of seconds after which the router is
obliged to rotate its contact addresses. If this number is all zeroes, then the router is never obliged to rotate its
contact addresses.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the client after how long the router will automatically rotate its addresses</i></td></tr>
<tr><td valign="top">28</td><td valign="top">LastAddressRotationMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">Yes</td><td valign="top">Last update date</td><td>
The content of the message is an 8 byte unsigned number in network byte order specifying the number of seconds since midnight
on January 1, 1970 in the GMT time zone it was when the last address was rotated. If the value is zero, then the address
has never been rotated.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the client when the last address rotation was</i></td></tr>
<tr><td valign="top">29</td><td valign="top">PeersMessage</td><td nowrap valign="top">Router to Client</td><td nowrap valign="top">Yes</td><td valign="top"><a href="#RouterInfo">RouterInfo</a>[]</td><td>
The content of the message is a list of zero or more RouterInfo structures, all serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Provide the client with all of the routers that the local router is communicating with</i></td></tr>
<tr><td colspan="6"><b>Bidirectional<a name="BidirectionalMessages"></b><hr></td></tr>
<tr><td valign="top">30</td><td valign="top">ReportAbuseMessage</td><td nowrap valign="top">Bidirectional</td><td nowrap valign="top">No</td><td valign="top"><a href="#SessionId">SessionId</a>, <a href="#AbuseSeverity">AbuseSeverity</a>, <a href="#AbuseReason">AbuseReason</a>, <a href="#MessageId">MessageId</a></td><td>
The content of the message is a SessionId structure, followed by an AbuseSeverity structure, then an AbuseReason structure,
and then optionally a MessageId structure, all serialized as specified below.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the other party that they are under attack, potentially with reference to a
particular messageId. If the router is under attack, the client may decide to migrate to another router, and if a client
is under attack, the router may rebuild its routers or shitlist some of the peers that sent it messages delivering the
attack.</i></td></tr>
<tr><td valign="top">31</td><td valign="top">DisconnectMessage</td><td nowrap valign="top">Bidirectional</td><td nowrap valign="top">No</td><td valign="top">reason</td><td>
The content of the message is a UTF formatted string specifying the reason for disconnect. The string may be zero
length.</td></tr>
<tr><td></td><td colspan="5" valign="top"><i>Tell the other party that there are problems and the current connection is about to
be destroyed. This does not necessarily end a session.</i></td></tr>
</table>
<h2>Client access layer data structures<a name="ClientAccessLayerDataStructures"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<h3>SessionConfig<a name="SessionConfig"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The SessionConfig data structure is the session's Destination, serialized, followed by an 8 byte unsigned number in network byte order
specifying the number of seconds since midnight on January 1, 1970 in the GTM time zone, with that number signed by the
<a href="#Destination">Destination</a>'s private key using <font color="red">an ElGamal signature algorithm</font>. After the number of seconds signed by
the algorithm is a one byte unsigned number in network byte order specifying the number of
<a href="#LeaseRevocation">LeaseRevocation</a>s in the SessionConfig, followed by
the actual list of zero or more <a href="#LeaseRevocation">LeaseRevocation</a> structures. After that list comes a two byte
unsigned number in network byte order specifying
how many bytes make up the set of key/value pairs. Finally there is a list of zero or more key/value pairs providing keys
specific to the router implementation. Keys are formatted as a non zero length list of UTF-8 characters, excluding "=" or ";".
After each key comes the "=" UTF-8 character, followed by zero or more UTF-8 characters up until either a ";" UTF-8 character
is reached or the end of the key/value pair length is reached.
<h3>Destination<a name="Destination"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The Destination is the identity plus join certificate for a particular network endpoint. It is stored as a 2048 bit public key,
followed by a 1 byte unsigned number in network byte order specifying the join certificate type, then by a 1 byte unsigned number in network byte order
specifying the size of the join certificate, and finally the raw payload of the join certificate. For join certificate type of
zero, the join certificate is null and the payload is ignored. For join certificate type of one, the join certificate is a
hashcash calculation, and the payload is a one byte unsigned number in network byte order specifying the number of bits (K) for the hash
collision, followed by a non-trivial hash collision against the first K bytes of the public key. The hash function is the
hashcash function specified at <a href="http://www.cypherspace.org/hashcash/hashcash.pdf">http://www.cypherspace.org/hashcash/hashcash.pdf</a>.
Other join certificate types, such as real cash payment certificates, can be added later.
<h3>LeaseRevocation<a name="LeaseRevocation"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The LeaseRevocation is very similar to a Lease for data points. It contains the serialized Destination, followed by the
serialized <a href="#RouterIdentity">RouterIdentity</a> of the <a href="#Lease">Lease</a>'s gateway, then the serialization of
the <a href="#TunnelId">TunnelId</a>, then a pair of 8 byte unsigned numbers in network
order specifying the start and end date of the lease (where the numbers are the total seconds since midnight on January 1, 1970 in
the GMT timezone, or if all zeroes, a null value), followed by a signature verifying the validity of the revocation. The
signature is by the <a href="#LeaseRevocationPrivateKey">LeaseRevocationPrivateKey</a> and uses the <font color="red">ElGamal signature algorithm</font>.
<h3>SessionId<a name="SessionId"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The sessionId is a 2 byte unsigned number in network byte order that identifies the session between the router and the client.
<h3>LeaseRevocationPrivateKey<a name="LeaseRevocationPrivateKey"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The key is a 2048 bit public key.
<h3>Lease<a name="Lease"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The Lease contains the serialized Destination, followed by the serialized <a href="#RouterIdentity">RouterIdentity</a> at which messages should be delivered,
then the serialized <a href="#TunnelId">TunnelId</a>, then a pair of 8 byte unsigned numbers in network byte order specifying the
start and end date of the lease
(where the numbers are the total seconds since midnight on January 1, 1970 in the GMT timezone, or if all zeroes, a null value),
followed by a serialized 2048 bit public key which serves as the public key that the
<a href="#LeaseRevocationPrivateKey">LeaseRevocationPrivateKey</a> counters, and
finally a signature by the destination's key using the <font color="red">ElGamal signature algorithm</font>.
<h3>Payload<a name="Payload"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The Payload is the contents of the message encrypted via <font color="red">ElGamal and AES256</font> to the
<a href="#Destination">Destination</a>'s public key. The first 64 bytes
<font color="red">[ElGamal require 2x the size encrypted, and the 256 bit AES key is, well, 32 bytes]</font> are the
ElGamal encrypted private key for the rest of the message. The next 8 bytes make up a number in network byte order specifying the
real size of the
payload (which may be less than or equal to the remaining number of bytes in the data structure). These 8 bytes are encrypted
with AES256 using the private key encrypted in the first 64 bytes. The remainder is encrypted with AES256 and represents the
actual contents of the message that will be delivered to the destination. The private 256 bit AES keys will be changed frequently
if not in each message, providing perfect forward security with regard to the messages passed over the network (though if the
private key of the destination is compromised, all messages recorded will be broken, so endpoints should periodically change their
destination). AES256 will be used in counter mode. <font color="red">[Should the beginning of the AES encrypted data be an
SHA-256 hash of the encrypted payload?]</font>
<h3>MessageId<a name="MessageId"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The sessionId is a 1 byte unsigned number in network byte order that identifies the message number that the current router/client session is
referring to.
<h3>AuthenticationKey<a name="AuthenticationKey"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The AuthenticationKey is an <font color="red">SHA-256</font> hash of the the passphrase required to access the administrative
functions of the router.
<h3>BandwidthLimits<a name="BandwidthLimits"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The BandwidthLimits are mappings of router to class and class to limit, where zero or more routers are assigned to a class and
each class has a set average and peak upload and download rate, measured in bytes/second. The BandwidthLimits object is
serialized by specifying a one byte unsigned number in network byte order determining the unique class ID, then a 32 byte block containing
the user specified name for the class (no character encoding is specified - for example, plain ASCII can use these 32 bytes
as up to 64 characters [or more], and UTF-8 can use a lot less). After that is a 1 byte unsigned number in network byte order specifying the
number of routers making up this class. If the value is zero, this class is considered to be the default class, to be used for
communication with all routers who are not in other classes. After that byte comes the <font color="red">SHA-256</font> of
each router's <a href="#RouterIdentity">RouterIdentity</a> in the class. Then comes four 4 byte unsigned numbers in network byte order specifying the average download
bytes per second, average upload bytes per second, peak download bytes per second, and peak upload bytes per second, respectively.
This entire sequence is repeated for each class, and there must be at least one class defined (the default class).
<h3>RouterIdentity<a name="RouterIdentity"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The RouterIdentity is an identity plus join certificate for a particular network endpoint. It is stored as a 2048 bit public key,
followed by a 1 byte unsigned number in network byte order specifying the join certificate type, then by a 1 byte unsigned number in network byte order
specifying the size of the join certificate, and finally the raw payload of the join certificate. For join certificate type of
zero, the join certificate is null and the payload is ignored. For join certificate type of one, the join certificate is a
hashcash calculation, and the payload is a one byte unsigned number in network byte order specifying the number of bits (K) for the hash
collision, followed by a non-trivial hash collision against the first K bytes of the public key. The hash function is the
hashcash function specified at <a href="http://www.cypherspace.org/hashcash/hashcash.pdf">http://www.cypherspace.org/hashcash/hashcash.pdf</a>.
Other join certificate types, such as real cash payment certificates, can be added later.
<h3>RouterInfo<a name="RouterInfo"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The RouterInfo structure contains the serialized <a href="#RouterIdentity">RouterIdentity</a>, followed by a 2 byte unsigned number in network byte order determining the
version of the RouterInfo, then a 1 byte unsigned number in network byte order of RouterAddress structures included and then the serialization
of those RouterAddress structures. After this comes a 1 byte unsigned number in network byte order specifying how many peers the RouterInfo
includes, followed by the <font color="red">SHA-256</font> hash of those peers' <a href="#RouterIdentity">RouterIdentity</a>. Following this is a set of
option key/value pairs, serialized as an initial two byte unsigned number in network byte order specifying how many bytes make up the set of
key/value pairs, followed by a list of zero or more key/value pairs providing options or other information the router provides,
such as statistics, configuration options, or minimal join certificate size. Keys are formatted as a non zero length list of
UTF-8 characters, excluding "=" or ";". After each key comes the "=" UTF-8 character, followed by zero or more UTF-8 characters
up until either a ";" UTF-8 character is reached or the end of the key/value pair length is reached. Finishing off the
RouterInfo structure is a a signature by the router's private key with <font color="red">ElGamal</font>.
<h3>RouterAddress<a name="RouterAddress"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The RouterAddress structure contains a 1 byte unsigned number in network byte order specifying the relative cost of using the address, where
0 means free and 255 means really expensive. After that comes an 8 byte unsigned number in network byte order specifying the number of seconds
since midnight on January 1, 1970 GMT at which the address should no longer be used, or if all zeroes, that the address never
expires. Next up comes a 1 byte unsigned number in network byte order determining the transport protocol for use in contacting this address.
The protocol values are currently not defined, but will include protocols such as bidirectional TCP, UDP, direct HTTP, polling
HTTP, and email. Finally there is a is a set of option key/value pairs, serialized as an initial two byte unsigned number in network
order specifying how many bytes make up the set of key/value pairs, followed by a list of zero or more key/value pairs
providing options necessary for configuring the particular transport to communicate with the address, such as IP address, port
number, email address, URL, etc. Keys are formatted as a non zero length list of UTF-8 characters, excluding "=" or ";". After
each key comes the "=" UTF-8 character, followed by zero or more UTF-8 characters up until either a ";" UTF-8 character is
reached or the end of the key/value pair length is reached.
<h3>TunnelId<a name="TunnelId"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The TunnelId is a 4 byte unsigned number in network byte order that identifies the tunnel id that the messages may pass through on the router.
<h3>AbuseReason<a name="AbuseReason"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The AbuseReason is a 1 byte unsigned number in network byte order specifying the size of the reason, followed by that many bytes in which the
there may be a description of the cause of abuse in whatever character encoding or language it chooses.
<h3>AbuseSeverity<a name="AbuseSeverity"></a> <font size="-1"><a href="#Contents">(top)</a></font></h3>
The AbuseSeverity is a 1 byte unsigned number in network byte order specifying the severity of the abuse, with 0 being minimally abusive and
255 being completely abusive.
<hr>
<h1>Analysis<a name="Analysis"></a> <font size="-1"><a href="#Contents">(top)</a></font></h1>
<h2>Attacks<a name="Attacks"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<h3>Traffic analysis<a name="TrafficAnalysis"></a></h3>
Nothing ever leaves the mixnet, and only trusted routers know a client is connected to them directly.
<font color="red"><b>[Is that enough? Can more sophisticated analysis attacks go on even without leaving the mixnet?]</b></font><p />
To some extent a traffic analysis attack is possible, even easier than on many other networks. This is by
design, but in this network's case, the attack should not be damaging to anonymity. This is vulnerable to colluding
evil nodes participating in tunnels and watching where payloads are delivered. Since messages are sent down two
sets of tunnels where the originator doesn't know the routers making up the destination tunnel, traditional layered
encryption isn't possible. Instead, simple cryptographic verification structures are passed along with the payload
down the tunnels, assuring that the payload or target is not modified during its outbound journey, and the router acting
as gateway to the inbound journey has some responsability not to modify the message before rebuilding new verification
structures. <p />
It is possible for colluding routers to participate in both the inbound and outbound tunnels, in which case those routers
would then know for sure that they are participating in inbound and outbound tunnels, respectively. If an entire inbound
tunnel is compromised (other than the endpoint, which should be the router on which the destination is located), those
colluding nodes will not be certain that the next hop is the endpoint, and depending on the transport method used, they
may not know the physical location of the next hop. <p />
If a router knows that it is the gateway to a tunnel, it is either an inbound tunnel or an outbound tunnel. If it is an
outbound tunnel, it is the trusted local router. If it is an inbound tunnel, it will not know what destination the
tunnel handles messages for without crawling all of the Lease structures in the DHT (which are keyed by destination, not
tunnel). An extensive attack can gather a significant portion of the Leases to figure out what destination the gateway
handles though. Other routers in an inbound tunnel cannot determine what destination they are operating for without
knowing all Lease structures, as they only know the tunnel ID - which is not globally unique (gateway + tunnel ID is
unique). Even if they know all of the Lease structures, it is still not certain that the destination named is
associated with the tunnel. <p />
Even if all routers are colluding - both in the outbound tunnel (except the source) and in the inbound tunnel
(except the endpoint), it is still possible to maintain anonymity by using relayed transports. To make taking over
all of the routers in the tunnels more expensive, tunnels should be rebuilt and torn down periodically.<p />
<h3>Intersection attack<a name="IntersectionAttack"></a></h3>
Can this be defeated by allowing routers and tunnels to delay their messages indefinitely, causing
delivery to occur even when the user is offline?
<h3>Flooding attacks<a name="FloodingAttacks"></a></h3>
<h4>Flood the specific router a destination is located on</h4>
Either update low level transport network to block packets from attackers or migrate the destination to another router
<h4>Flood the specific router a gateway to a tunnel is located on</h4>
Switch physical addresses, and if that doesn't solve the problem, Send a notification down the tunnel that its being flooded
<font color="red"><b>[update router message handling to accept this as an instruction to rebuild the tunnel]</b></font>
<h4>Flood the gateway of a tunnel with all of the messages it can accept</h4>
These messages are delivered to the destination through the tunnel normally, but if a significant number of the inbound tunnels
are flooded, no one will be able to contact the destination. If the destination detects that it is getting bad messages or
that not enough "real" messages are being delivered, it can instruct its router to build new tunnels
<h4>DHT put(k, v) with invalid v</h4>
Dropped at the first step since v is validated. Penalize the router that gave the invalid data (perhaps remove from routing
table)
<h4>DHT put(k, v) flood with valid v</h4>
If more than <font color="red"><b>[x? average of puts for that type of v, % of bandwidth?]</b></font> are specified for any particular k or from any
particular peer, drop them and potentially penalize the router.
<h4>DHT get or put with excessive hops to live</h4>
Reset all hops to live so they never exceed <font color="red"><b>[5, 10, log(n), 42?]</b></font>.
<h4>DHT get(k) of consistent k</h4>
Not a problem, as the value is often cached. Remember keys searched for but not found for a period of time.
<h4>DHT get(k) with different value of k</h4>
If one router requests more than <font color="red"><b>[x? % of keyspace? % of cache?]</b></font> keys in a period of time, ignore further requests
and penalize them. <font color="red"><b>[Perhaps limit DHT get/put messages to N per timeslice?]</b></font>
<h4>Stack the DHT with routers in a particular keyspace then drop out once they control some important keys</h4>
Caching should help alleviate this, plus its hard to generate valid public keys in a particular keyspace, even harder if
the network requires routers to have certificates attached to their keys, requiring hashcash or actual payments.
<h4>Create too many tunnels</h4>
Require that a tunnel creator offer some sort of exchange for participating in the tunnel (hashcash or real cash)
<h4>Segmenting attack by application (using statistics about each message's characteristics)</h4>
Since we don't force all messages in the network to have the same size, it is open to a segmenting attack. To help
minimize that, applications should use messages with a wide range of sizes and characteristics.
<font color="red"><b>[This will probably not be a problem. Prove why.]</b></font>
<h3>Legal attacks<a name="LegalAttacks"></a></h3>
<h4>Outlaw or otherwise prevent running the application with user defined security</h4>
Migrate publicly visible routers outside the jurisdiction, use trusted routers
within it, build up large quantities of "throw away" routers, move between routers
frequently, and use stegonographic transports. This defeats the harvesting attack of
finding all routers within a jurisdiction, as only trusted or stegonographically hidden
routers can be harvested.
<h4>Network blocking</h4>
Add new transports to blend in with other non-blocked protocols and use stegonographic
transports.<p />
<font color="red"><b>[WHAT ELSE?!]</b></font>
<h2>Performance<a name="Performance"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red">
Performance model:
<table border="0">
<tr><td><b>Variable</b></td><td><b>Definition</b></td></tr>
<tr><td valign="top">N </td><td valign="top"> Number of routers in the network </td></tr>
<tr><td valign="top">H </td><td valign="top"> Average number of hops in each tunnel</td></tr>
<tr><td valign="top">T </td><td valign="top"> Average message delivery time per hop
<i>(perhaps split up by latency percentile?)</i></td></tr>
<tr><td valign="top">D </td><td valign="top"> Average dispatch time (reception until relay)</td></tr>
<tr><td valign="top">C </td><td valign="top"> % of the routing table cached at each router</td></tr>
<tr><td valign="top">S </td><td valign="top"> % of routers with only secret addresses</td></tr>
<tr><td valign="top">Q </td><td valign="top"> Average number of hops from a router's secret address to a public one</td></tr>
<tr><td valign="top">F </td><td valign="top"> % of tunnels failing on or before use prior to detection</td></tr>
<tr><td valign="top">G </td><td valign="top"> % of routers operating reliably (high uptime, high bandwidth, correct operation)</td></tr>
<tr><td valign="top">B </td><td valign="top"> % of routers operating poorly (low uptime, slow operation, loses messages)</td></tr>
<tr><td valign="top">M </td><td valign="top"> % of routers flooding or other malicious behavior</td></tr>
<tr><td valign="top">J </td><td valign="top"> % of routers joining the network at once</td></tr>
<tr><td valign="top">L </td><td valign="top"> % of destinations creating/updating leases at once</td></tr>
<tr><td valign="top">A </td><td valign="top"> Average number of destinations located at each router</td></tr>
<tr><td valign="top">K </td><td valign="top"> Avarage message size</td></tr>
<tr><td valign="top">I </td><td valign="top"> Average number inbound tunnels per destination</td></tr>
<tr><td valign="top">O </td><td valign="top"> Average number of tunnels outbound per router</td></tr>
<tr><td valign="top">R </td><td valign="top"> % of messages requiring reliable delivery</td></tr>
<tr><td valign="top">E </td><td valign="top"> % of tunnels failing but detected before use</td></tr>
<tr><td valign="top">P </td><td valign="top"> % of routers requiring certificates for use</td></tr>
<tr><td valign="top">U </td><td valign="top"> Average time required to calculate a certificate</td></tr>
<tr><td valign="top">V </td><td valign="top"> Average number of tunnels each router can participate in</td></tr>
<tr><td valign="top">W </td><td valign="top"> Average number of peers each router connects to</td></tr>
</table>
Formulas:
<table border="0">
<tr><td><b>Name</b></td><td><b>Formula</b></td><td><b>Rationale</b></td></tr>
<tr><td valign="top" nowrap>Initial latency</td>
<td valign="top" nowrap>2HT+T+2*(100%-C)*T*LOG(W:N)</td>
<td>The logic to this is: <br />2*tunnelTime + interTunnelTime + routingTime. <br />LOG(W:N) uses is log base W of N.</td>
</tr>
<tr><td valign="top" nowrap>Follow on latency</td>
<td valign="top" nowrap>2HT+T</td>
<td>The logic to this is: <br />2*tunnelTime + interTunnelTime. <br />no routingTime as the gateway is cached</td>
</tr>
</table>
Assume the vast majority of users are able to broadcast their physical addresses in their <a href="#RouterInfo">RouterInfo</a> structures,
finding a way to contact a router should take no longer than doing the DHT get(H(routerIdentity)), and may even
take O(1) time if the routing info is already known. Given H = 5 hops, T = 100ms, C = 10%, W = 20, the initial latency
would be 2*5*100+100+2*.9*100*LOG(20:5,000,000) = 1000+100+2*.9*100*5.15 = <b>2027ms</b>. Follow on latency would be
<b>1100ms</b>. Dropping T to 80ms saves about 300ms, dropping N to 100,000, and H to 2 hops, and the initial latency
falls to <b>952ms</b> and the follow on latency to <b>400ms</b>.<p />
</font>
<font color="red">
<h1>Ideas<a name="Ideas"></a> <font size="-1"><a href="#Contents">(top)</a></font></h1>
<ul>
<li>Perhaps within RouterInfo.stats store some ping times to known major locations
(e.g. MAE-East, MAE-West, BBC, etc) so that routers can at least have some untrusted
stats to work with, rather than going completely randomly? Correlated with traceroutes?
<b>Good idea or bad?</b></li>
<li>Integrate reputations by inserting expirable certificates about routers and
destinations at H(routerIdentity) and H(destinationIdentity) with certificates
from the reporting router or destination. Check for certificates when
determining whether to use routers in tunnels. <b>Good idea or bad?</b></li>
<li>Have routers also publish their RouterInfo at FirstNBits(H(routerIdentity), N)
so people can find routers in a key space easiliy. <b>Good idea or bad?</b></li>
<li>Should we do DHT inserts entangled with the date, ala
DHT put(H(routerInfo+thisWeek), routerInfo) so as to force periodic migration of
data among routers in case the DHT isn't caching enough and gets hotspots? To
make it so things don't get hard to reach all at once
(e.g. on monday @ midnight), perhaps make this a rolling process - migrate
all entries w/ H(routerInfo) beginning with '0' on the 1st and 17th of the month,
'1' on the 2nd and 18th of the month, '2' on the 3rd and 19th of the month, and so
on. <b>Good idea, bad idea, or unnecessary at the moment?</b></li>
<li>Should we have payment certificates that are not specific to a particular
operation inserted into the DHT after being presented for a service? e.g. if
router R1 has a realCash certificate for $0.01 that it presents to router R2 for
it to provide tunnel services, have R2 first does a DHT get(H(certificate)),
retrieving a CertificatePayment stating <code>{certificate, currentPubKey}</code>,
and if R1 provides the valid private key, R2 accepts the transaction and does an
update to the CertificatePayment to change the public/private key.
<b>Good idea, bad idea, and/or should this be tied in with reputation systems?
This doesn't work w/ DHTs that cache since there are multiple instances of
certificate and the key change may not propogate to all of them, allowing double
spends!@!! damn. And we can't just have R1 give R2 the certificate, as there's
no double spend protection that way either. Oh well.</b></li>
<li>Should we have a payment certificate attached to each real message sent (basically
a hashcash of the payload + destination + date)? This would make plain DoS harder,
though not affect DDoS</li>
</ul>
</font>
</td>
</tr>
</table>
</body>
</html>