latest net draft / goals
<auto97841-revL73yDgGBWk0Htik3J/[email protected]> Sun, 13 Jul 2003 14:58:16 -0700
| Newsgroups | gmane.comp.security.invisiblenet.iip.devel |
|---|---|
| Message-ID | <[email protected]> |
'lo. latest draft of the network stuff is attached. The bulk of the change is to the traffic analysis attack description. Also the performance model was filled in a little bit more to match the spreadsheet. Finally, the message delivery section was slightly modified, specifying that the source should fetch the destination from the routing table DHT rather than leave it to the outbound tunnel's endpoint, as that minimizes information leaked to that endpoint which could be useful to a global active attacker. any thoughts on this, the router architecture, or the model spreadsheet? I'm hoping that we can review / revise by our Tuesday meeting so that we can write up stubs for the access layer (so we can develop apps & the network seperately, as well as test both). -jrandom
network_spec.html
(text/html, 52.5 KB)
<html>
<header>
<title>Network Spec Proposal 2003.07.13</title>
</header>
<body><a name="Contents"> </a>
<table border="1" >
<tr>
<td width="30%" 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="#MessageByteStructure">Message Byte Structure</a></li>
<li><a href="#ClientAccessLayer">Client Access Layer</a></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 revokation keypair, creating a Lease structure out of that information, and then providing
the Lease and the revokation 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 revokation occurs by inserting a LeaseRevokation
structure (<code>{destination, gatewayRouter, tunnel, startDate, endDate, signature}</code>) signed
by the Lease's revocation private key. This LeaseRevokation is inserted at H(destination), and when
a router with a LeaseRevokation sees a Lease it refers to, it drops the Lease (and may drop the
LeaseRevokation, 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 LeaseRevokation 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>Message Byte Structure<a name="MessageByteStructure"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
<font color="red"><b>[Define the byte by byte structure for the message data, certificates, and keys so that other router implementations can be made]</b></font>
<h2>Client Access Layer<a name="ClientAccessLayer"></a> <font size="-1"><a href="#Contents">(top)</a></font></h2>
Client applications access routers either through an API or a socket protocol. For simplicity, only the messages the router
and client exchange are described here, leaving the actual access layer (wire protocol, proprietary API, or standard API) open
for description by the implementing software.<p />
<b>Client to Router</b>:<ul>
<li><b>* <code>create session {sessionConfig}</code></b>: This is what the client sends to its local trusted router to join the network.</li>
<li><b>* <code>reconfigure session {sessionID, sessionConfig}</code></b>
This is what the client sends to the router to have a session changed - various options reconfigured and
possibly some resources released</li>
<li><b>* <code>destroy session {sessionID}</code></b>:
This is what the client sends to the router to have a session destroyed and all resources released</li>
<li><b>* <code>create lease {sessionID, Lease, leaseRevokationPrivateKey}</code></b>:
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.</li>
<li><b>* <code>send message {sessionID, payload, destination}</code></b>:
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.</li>
<li><b>* <code>recieve message {sessionID, msgID}</code></b>:
Request the router to deliver a message that it was previously notified of</li>
<li><b>* <code>report abuse {sessionID, destination, msgID, reason}</code></b>:
Tell the router that the message delivered and or the destination specified was abusive. The
router should then consider whether to adjust or tear down the tunnel that message came from,
to switch addresses, to move towards trusted links, or some other abuse avoidance technique.</li>
<li><b>= <code>get bandwidth limit {auth}</code></b></li>
<li><b>= <code>set bandwidth limit {auth, BandwidthLimits}</code></b></li>
<li><b>= <code>get trusted routers {auth}</code></b></li>
<li><b>= <code>set trusted routers {auth, Identity[]}</code></b></li>
<li><b>= <code>get address visibility {auth}</code></b></li>
<li><b>= <code>set address visibility {auth, boolean}</code></b></li>
<li><b>= <code>get address rotation period {auth}</code></b></li>
<li><b>= <code>set address rotation period {auth, numHours}</code></b></li>
<li><b>= <code>force address rotation {auth}</code></b></li>
<li><b>= <code>add peers {auth, RouterInfo[]}</code></b></li>
<li><b>= <code>get peers {auth}</code></b></li>
</ul>
<b>Router to Client:</b><ul>
<li><b>* <code>session status {sessionID, ['Created','Updated','Destroyed']}</code></b>:
The message is a description of what the status was reached.
The sessionID is the newly created session id (if successful), else null.</li>
<li><b>* <code>request lease {sessionID, gwRouterHash, tunnel, start, end}</code></b>:
This is what a router sends to a client to ask it to authorize the advertisement of the client's destination on
a tunnel.</li>
<li><b>* <code>message status {sessionID, msgID, ['Accepted','Sent','Failed']}</code></b>:
Notify the client how the previous message was handled</li>
<li><b>* <code>message available {sessionID, msgID}</code></b>:
Notify the client that a message may be picked up at its convenience</li>
<li><b>* <code>deliver message {sessionID, msgID, payload}</code></b>:
Deliver the message to the client following the encryption/decryption guidelines above</li>
<li><b>* <code>report abuse {sessionID, reason}</code></b>:
Tell the client that the router is under attack and may not be able to provide satisfactory performance.
The client may then recreate a session with more tunnels or simply migrate to another router.</li>
<li><b>= <code>bandwidth limits {BandwidthLimits}</code></b></li>
<li><b>= <code>trusted routers {Identity[]}</code></b></li>
<li><b>= <code>address visibility {boolean}</code></b></li>
<li><b>= <code>address rotation period {numHours}</code></b></li>
<li><b>= <code>last address rotation date {date}</code></b></li>
<li><b>= <code>peers {RouterInfo[]}</code></b></li>
</ul>
<i><b>Key: "*" are normal methods, "=" are administrative methods</b></i><p />
<b><font color="red">Todo: describe data structures, define bitbuckets, and formalize semantics</font></b>
<hr>
<b>SessionConfig:</b><ul>
<li><b>myDestination</b>: full (public key, certificate) destination of the client </li>
<li><b>authenticationSignature</b>: signature of the destination's private key</li>
<li><b>leaseRevokation[]</b>: set of LeaseRevokation objects to destroy old tunnels</li>
<li><b>numInboundTunnels</b>: how many tunnels should be made available to recieve messages</li>
<li><b>numOutboundTunnels</b>: how many tunnels should be made available to send out messages</li>
<li><b>lengthOfInboundTunnels</b>: how long each inbound tunnel should be</li>
<li><b>lengthOfOutboundTunnels</b>: how long each outbound tunnel should be</li>
<li><b>messagesPerInboundTunnelPerMinute</b>: how many messages the inbound tunnel should support per minute</li>
<li><b>messagesPerOutboundTunnelPerMinute</b>: how many messages the outbound tunnel should support per minute</li>
<li><b>inboundReorderingRequired</b>: whether the inbound messages should be reordered before delivery</li>
<li><b>outboundReorderingRequired</b>: whether the outbound messages should be reordered before delivery</li>
<li><b>inboundPoolSize</b>: how many messages should be grouped together for reordering or bursting on inbound tunnels</li>
<li><b>outboundPoolSize</b>: how many messages should be grouped together for reordering or bursting on outbound tunnels</li>
<li><b>inboundDummyTrafficRequired</b>: whether inbound tunnels should constantly be sending messages (dummy messages when no real ones exist)</li>
<li><b>outboundDummyTrafficRequired</b>: whether outbound tunnels should constantly be sending messages (dummy messages when no real ones exist)</li>
<li><b>inboundTunnelLifetime</b>: how long inbound tunnels should operate before being torn down</li>
<li><b>outboundTunnelLifetime</b>: how long outbound tunnels should operate before being torn down</li>
</ul>
<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 RouterInfo 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>