\chapter{An attack-resistant name service}
\label{nameservice}

This chapter presents the design of an attack-resistant name service,
using the group trust metric described in Chapter~\ref{groupmetric} to
provide high assurance even under attack.

For the purpose of this chapter, name service is the problem of
finding the appropriate public key corresponding to a given name. This
problem is quite thorny in practice. Determining who owns the rights
to a given name is not well-defined. Rather, it is the subject of
social, economic, legal, and political issues. Real world CA's have
misbehaved. Cite VeriSign/Microsoft.

We address these issues by separating mechanism from policy. This
requires policy to be formally specified. Thus, the policy language
must be rich and flexible enough to accommodate the policies desired.

Probably the only workable policy is ``first-come, first-served,'' as
it's the only one that's understandable.

Choice of namespaces: flat, hierarchical, hash-based. Also cite SDSI
for relative namespaces.

\section{Related work}

There are many designs and implementations of systems to bind keys to
names. The most popular is the X.509 family of standards, loosely
synonymouse with the Public Key Infrastructure (PKI). In this
framework, authority for the namespace is assigned to one or more
\emph{certification authorities} (CA's), generally composed of
\emph{root CA's} that delegate authority over some or all of the
namespace to various subsidiary CA's. A consequence of this design
decision is the \emph{root vulnerability}---the compromise of any of
the root CA's leads to catastrophic security failure.

Root vulnerability is a serious concern. Even though individual CA's
may be well managed (with private keys reasonably well protected),
modern applications depending on PKI such as Web browsers ship with
dozens of root CA keys enabled. Further, the grouwing popularity of CA
software for off-the-shelf platforms (such as Entrust/PKI and
Entegrity's Notary) implies that CA's will be deployed in contexts
where it is difficult or impossible to protect the CA with a high
degree of assurance.

Often, the CA given root authority is implementing a fairly simple and
well defined policy. For example, VeriSign's Class 1 certificates are
issued on a first-come, first-served basis. Domain name registrars
issue second level domains on an effectively first-come, first-served
basis, with the possibility of revoking the name (and issuing it to
someone else) for non-payment of the bill, or as the result of a
dispute. Actual implementation of these policies is at the whim of
whoever holds the CA's private key. An attacker who succeeds in
compromising the CA key can reassign names completely at will, with no
regard to any policy.

It is possible to implement well defined policies and avoid root
compromise. The naming service presented in this chapter factors the
name service problem into to sub-problems: a \emph{policy language}
for expressing policies formally, and a \emph{distributed trusted
third party} for implementing the policies. In cases where the complex
blend of factors controlling ownership of names can be distilled into
a formal policy, our naming service can provide much higher assurance
with lower certification cost than existing PKI's.

A design factored in this way can only be successful if two goals are
met: the policy language should be rich enough to express a range of
policies useful in the real world, and the distributed trusted third
party should be trustworthy. Section~\ref{policylang} presents such a
policy language, and Section~\ref{dttp} presents a distributed network
based on an attack-resistant trust metric.

The policy language introduces the concept of \emph{asymmetry} between
initial registration of a name and updates to that name. In
traditional PKI designs, the authority granted to the CA is total, so
the CA has equal power to register and update name/key
bindings. However, there are many interesting asymmetrical policies
where the power to update is more restricted than the power to
register. The first-come, first-served policy is an extreme
example. Authority to register new names is trivially granted, but
authority to update existing names is never granted.

\section{Policy language}
\label{policylang}

The goals of the policy language are:

\begin{itemize}

\item Flexibility: different policies can be specified for different
parts of the namespace.

\item Low certification cost if security against unauthorized
registrations is not important.

\item High security if higher certification cost is tolerated.

\item Good security against unauthorized updates.

\item Low vulnerability to root compromise.

\end{itemize}

Meeting all these goals requires a moderately complex language. In
practice, a simpler policy, such as first-come first-served, may be a
better choice. First-come first-served is poor at assigning names
consistent with some other concept of ownership (such as trademarks),
but its limitations are easily understood and analyzed.

Before defining the policy language itself, we define the space of
\emph{names} and \emph{requests} over which the policies are
defined. Names are similar to familiar Internet hostnames and e-mail
addresses, such as ``raph@cs.berkeley.edu''. As in DNS, names are
hierarchically structured. Thus, the parent of
``raph@cs.berkeley.edu'' is ``cs.berkeley.edu'', its parent in turn is
``berkeley.edu'', and so on. Names with children are \emph{domains.}

Each request is either a \emph{registration} or an \emph{update}
request, and in either case contains a name, a value (such as a public
key) to be bound to that name, and policies to be associated with that
name. In addition to standard names, there are special namespaces for
policy fragments and groups. Each request is also accompanied by a
signature from zero or more public keys.

This design does not address read access to the database. Always
allowing lookups is reasonable and consistent with existing Internet
practice. Read access control is a plausible extension, however.

A request is processed as follows:

\begin{itemize}

\item The signatures on the request are verified, resulting in a list
of public keys that signed the request.

\item The body of the request is used to retrieve an appropriate policy
from the database.

\item The policy is evaluated over the list of public keys signing the
request, resulting in a boolean value.

\item If the boolean value is \emph{true,} then the database is
updated as per the request.

\end{itemize}

This workflow is similar to that of PolicyMaker\emph{BFL96} and other
trust management systems.

For registration requests, the appropriate policy is the
\emph{registration policy} of the parent. For update requests, the
appropriate policy is the \emph{update policy} of the name. The update
policy for a name is fixed upon registration of the name. It cannot
itself be directly updated. The registration policy for a domain can
be updated.

The policy language is defined as follows:

\[
\begin{array}{rcl}
policy & ::= & int\ 'of'\ group \\
       & | &  policy\ '\wedge'\ policy \\
       & | & policy\ '\vee'\ policy \\
       & | & 0 \\
       & | & 1 \\
       & | & '*'\ policy\mbox{-}name
\end{array}
\]


\[
\begin{array}{rcl}
group & ::= & '\{'\ key\ '\}' \\
        & | & group\ '\cup'\ group \\
        & | & group\ '\cap'\ group \\
        & | & '*'\ group\mbox{-}name
\end{array}
\]

\[
\begin{array}{rcl}
key & ::= & key\mbox{-}hash \\
      & | & '*'\ key\mbox{-}name
\end{array}
\]

\[
\begin{array}{rcl}
policy\mbox{-}name & ::= & id\ '?'\ name
\end{array}
\]

\[
\begin{array}{rcl}
group\mbox{-}name & ::= & id\ '@@'\ name
\end{array}
\]

\[
\begin{array}{rcl}
key\mbox{-}name ::= name
\end{array}
\]

As stated above, the goal of this policy constraint language is to
enable a DNS-like naming hierarchy with a flexible, varying degree of
control. A particular goal is to preserve the security of delegated
sections of namespace even when the nodes in control of the root, or
high-level domains, are compromised. At the same time, if a delegated
name turns out to be improperly granted, it should be possible to
recall it.

The policy constraint language provides a mechanism to balance these
two goals. It easy expresses both the first come, first served policy,
by trivially granting registration requests, but never granting update
requests. Similarly, the policy of central control is easily
represented by symmetrical registration and update policies.

Evaluation of whether a given policy meets a policy constraint
expressed in the policy constraint language is a co-NP complete
problem. Here we present a brief proof outline in the form of a
reduction to 3-SAT, which is a well known NP-complete problem.

Present pseudocode algorithm for implementing policy constraint
language.

\section{Implementation of naming service}

In order to avoid a single point of failure, we choose a peer-to-peer
network architecture for the implementation of the naming service. For
simplicitly, we choose a two-level architecture, with a relatively
small number of ``server'' nodes, and most clients contacting the
server nodes to retrieve names and certificates.

All servers have knowledge of all other servers. Thus, notification of
server joins and leaves are broadcast operations. When the number of
servers is on the order of the square root of the total number of
peers, network traffic is optimized. This square-root behavior is
neither as bad as flat broadcast networks, such as the original
Gnutella protocol, nor as good as the logarithmic performance of
systems such as Chord\cite{chord:sigcomm01}.

Not all nodes store records for all names registered in the
system. Rather, there is a ``responsible server'' relation, generally
based on a hash function so that the set of responsible servers for a
given name is effectively random. An average of 10 to 20 servers
should be responsible for each name. This average is a tunable
parameter. As it increases, security improves, but overall network
traffic also increases.

There are essentially two different authorization decisions in the
system. The first, evaluated by nodes when processing registration and
update requests, is whether the request is valid. The second,
evaluated by clients when performing queries, is whether the node
responding to the query is trustworthy to provide the correct answer.
Our design mirrors the fundamental asymmetry of these two decisions.
Essentially, for \emph{mutation} requests, clients send the request to
all responsible nodes for the name, regardless of whether such nodes
are to be considered trustworthy. However, for \emph{query} requests,
clients only consider responses from nodes which are both responsible
for the name and considered trustworthy.

Our design mixes up this clear separation a bit, because nodes
processing mutation requests also function in the client role when
they retrieve the policy and policy constraint associated with the
parent name.

\subsection{Responsible servers}

This subsection presents a simple, effective relation for determining
which nodes are responsible for which names.

Each server has an ID, which is the 160-bit SHA-1 hash of its public
key. Similarly, the SHA-1 hash of any name gives a value in this
space, ie the id of name $x$ is $H(x)$.

We define a ``distance metric'' $d(n_1, n_2)$ to be the absolute value
of $n_1 - n_2$ interpreted using 160-bit two's complement arithemetic.
This metric induces a ``ring'' topology on the space of ID's.

With this definition, a server with id $n_s$ is responsible for name
$x$ iff $d(n_s, H(x)) < \Delta d$, where $\Delta d$ is a tunable
parameter of the system. A reasonable target is that 10 to 20 good
servers are responsible for any given name, i.e. $\Delta d$ is equal
to 5 to 10 times $2^{160}$ divided by the number of good servers.

\subsection{Mutation requests}

In this subsection, we describe in detail the algorithm used by nodes
to authenticate mutation requests. Overall, this authentication process
strongly resembles PolicyMaker\cite{BFL96}.

There is no consistency guarantee for mutation requests. In
particular, two registrations coming in at roughly the same time may
lead to inconsistency, with different nodes giving different answers
to the same query. Improving consistency is an interesting research
direction. Perhaps the most profitable approach is to adapt the
Byzantine fault tolerance research\cite{CL99}.

\subsection{Query requests}

In this subsection, we describe and analyze the algorithm used by
clients to validate responses to query requests. This process is
strongly dependent on a group trust metric, and we discuss how the
security properties of the trust metric affect the security of the
system as a whole.

The client's first step is to determine a set of responsible and
trustworthy servers. In our design, we simply determine the set of all
trustworthy servers first, then apply the ``responsibility'' relation
as a filter. It is tempting to consider only a subset of all
trustworthy nodes. Such a design might be considerably more efficient
(as is demonstrated by the Distributed Hash Tree work such as
Chord\cite{chord:hotos} and Kademlia\cite{maymounkov-kademlia}), but
unfortunately the security of the group trust metric as described in
Chapter~\ref{groupmetric} depends on knowledge of the entire trust graph.

Armed with this list (which is expected to contain on the order of 10
or 20 nodes), the client sends the request separately to each node.

Finally, as the responses come trickling back, the client waits until
a majority of nodes queried provide a consistent response. If no single
response is in the majority, then the lookup is considered to have
failed, with no trustworthy binding to that name.

Note that in the common case, when all nodes provide the same answer,
the client accepts the binding as soon as the earliest half of nodes
respond. Thus, individual server failures are tolerated, and request
latency is equal to the median latency of server nodes.

\subsection{Security analysis}

The voting semantics of the validation of responses to queries is a
good match to the guarantees provided by the group trust metric.

Assuming no conflicts during the registration phase, then all good
nodes responsible for a name will yield the same (``correct'') answer
to a query. Thus, if at least one half of the subset of responsible
nodes accepted by the trust metric are good, then the correct answer
will be obtained.

The group trust metric can guarantee that a fraction of the total
nodes accepted is good, but this is not the same as guaranteeing that
a fraction of the accepted nodes responsible for a name is
good. Indeed, it is likely that an attacker would be able to mount a
successful attack against a single name at low cost.