Naming service specification, version 1.0

Hi co et al, 

Overall, the spec is good, but there are a few design issues that should
be addressed prior to implementation.  I have two areas of critique for
the design as is - scalability and security - both of which have problems
that need to be addressed.

The naming service as described seems to requires a linear scale delays
during registration and update as the network grows.  Whenever anyone
registers a new EntityInfo, the naming service must send out and recieve
2N messages (N = # name servers, with messages RequestClientExists and
replies of ResponseClientDNE or ResponseClientExists, or for update the
messages are RequestClientUpdated).  

O(N) isn't bad, though as described, I'm not sure that's even the case.
 You mention that not all servers contain all EntityInfo structures -
 though from section 5 paragraph 3, I can't see how a server queries
the other name servers for entries matching the query.  The storage requirements
of having all EntityInfo structures at each server is nontrivial - up
to 10K or more per structure, and at a 5 million destination network
(5M being a low estimate for when there are 5M routers, as each user
will have a destination per *application* that they run), thats 51Gb
of data per server.  Keeping in mind this 51Gb data size for 5M destinations,
 there's significant searching that needs to be done which will cause
significant delays, even on a local disk.

There are also significant security issues, boiling down to both DoS
attacks and nym hijacking.  First, let me address the public/private
key issue - when passing around destinations, you want to pass around
the full Destination structure - PublicKey, SigningPublicKey, and Certificate.
 The network DHT containing Lease structures help find all existing Leases
based on H(destination), not H(destination.publicKey), and not all Destinations
will have valid leases at all times.  If, instead, the naming service
placed the Destination instead of PublicKey in the EntityInfo, even currently
"offline" Destinations (ones with no current Leases in the network DHT)
will be retrievable.

DoS attacks can be both network intensive or starvation based.  One way
to disable the servers would be to start up K new name servers and have
them register with the existing name servers, causing K*N*2 messages
to be passed, as well as K*(total EntityInfo data size, e.g. 51Gb) bytes
to be delivered, affecting /ALL/ name servers.  A network intensive attack
registers K new name servers repeatedly.  A starvation based attack registers
name servers but drops any of the EntityInfo structures it recieves.
 In addition, a mixed attack would be a starvation attack that then floods
the properly behaving name servers with requests, causing them to fire
back ResponseUseAnotherServer until such a point as they send back the
hash of the starved servers, so that any client that submits a request
to any name server - evil or not - will be directed to an evil name server
that doesn't have any data.

The mixed attack described above can also be used to hijack nyms.  The
malicious name servers no long reply with no data, they reply with responses
containing the EntityInfo structures under the given nym - except with
a different hijacking destination, signed by the hijacker's key, so that
there is no way to tell that it isn't a proper and correct response.
 Simpler hijacking tactics operate along the same lines, except they
don't perform the mixed DoS attack, so only requests sent their way are
hijacked.  This can be done probabalistically by creating K malicious
name servers in response to N properly behaving name servers, where K/N
is a large enough value.

Those are the attack concerns that come to mind without digging deeper
into the messaging protocol of the name server (and without further information
about how the client libraries operate - do they cache responses?  choose
servers via round robin, randomly, or through trusted or web of trust
protocols?).  

Even with those concerns, there are ways to get around them.  To address
the massive amount of data necessary (10+K/destination), I'd suggest
that rather than having each name server contain all EntityInfo records,
 you may want to go with a structured distributed lookup system, such
as a hard or sloppy DHT, giving entity lookups under O(log(N)) time,
where N = # servers.  Also, I think that you will need a seperation between
authoritative records and caches, either through a set of trusted master
name server that push out authoritative records to untrusted slave name
servers, or through a CA scheme where the CA signs records and then the
client submits the CA and Destination signed EntityInfo structure to
the untrusted name servers, who propogate it throughout the structured
distributed lookup system.  

This completely prevents hijacking as long as the CA's signing key is
not compromised, and the structured distributed lookup system makes DoS
attacks incredibly expensive.  The distributed lookup system /is/ hard
though, as there is no simple hash key to operate against (is userx:www
stored under H(userx:*), H(*:www), H(us*,*), H(*erx,www), etc?), though
searching distributed databases is a known problem with workable solutions.
 Perhaps the easiest thing to do is to simply allow lookup by nym, not
by service (allowing the lookup system to work off H(userx), giving a
definitive structural location)?

A CA is not hard, and does /not/ provide a single point of failure. 
The naming service performs just as well even if the CA gets temporarily
knocked offline, as the naming service simply verifies signatures against
the CA's known public key and does not need to contact the CA.  Also,
 the CA itself can be distributed across multiple destinations, each
of which will have multiple inbound tunnels, and since it can have high
latency (CA is only contacted on update or registration of a nym), it
can run over transports such as email.  To dissuade nym squatting or
flooding the CA, requests to the CA should be accompanied by some sort
of certificate - either hashcash or some other token.  You really, really,
 really want to have the CA functionality in the architecture from the
start by having a place for the CA's signature on the EntityInfo structures.
 To get up and running quickly, you can have the signature not be validated
and not build the CA software, and once you or someone else has time
to implement the CA, just have the name servers and client libraries
verify the signatures.

I don't mean to sound negative at all - this is an important application
that I2P will truly need to allow good and secure anonymous communication,
 and I just want to make sure the naming service can achieve that task.
 You've definitely made a great start with the design, and thats tremendously
appreciated, and if there's anything I can do to help, please let me
know.

-jrandom



Concerned about your privacy? Follow this link to get
FREE encrypted email: https://www.hushmail.com/?l=2

Free, ultra-private instant messaging with Hush Messenger
https://www.hushmail.com/services.php?subloc=messenger&l=434

Promote security and make money with the Hushmail Affiliate Program: 
https://www.hushmail.com/about.php?subloc=affiliate&l=427