[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[minion-cvs] Check in tenative dir-agreement design
Update of /home/minion/cvsroot/doc/spec
In directory moria.mit.edu:/tmp/cvs-serv30857
Added Files:
dir-agreement.txt
Log Message:
Check in tenative dir-agreement design
--- NEW FILE: dir-agreement.txt ---
Mixminion directory agreement protocol -- draft
Nick Mathewson
13 August 2003
Status
This is a draft document describing a directory agreement protocol
for Type III remailers. If people like it, we'll merge in into
Mix3:3 "dir-spec.txt".
It's substantially identical to what Nick was blathering about at
Defcon.
It doesn't have as much detail as a final specification should. In
particular, it doesn't describe data formats.
It isn't perfect, but it's better than Type II. :)
0. Motivation and design goals
Currently, we have specifications for most of the type III
directory system, including: server descriptor structure, directory
structure, publishing to directories, building directories,
downloading directories, and using directories. One critical
piece remains: directory agreement.
In today's Type II and Type III code, each directory server
publishes an independent description of the network's state. This
enables the following attacks:
(1) An attacker who controls a directory server can redirect
that server's clients toward a restricted set of mixes with
little risk of detection.
(2) An attacker who controls a directory server can feed target
users a modified directory that would make those users
highly distinguishable. Since directories are signed, this
attack leaves a trail--if its victims notice it's happening.
(3) An attacker who eavesdrops on a user or a directory can tell
who is using a particular directory. Knowing who is using
which directory helps the attacker mount statistical
partitioning attacks on the network based on client
knowledge.
(If users try to avoid this attack by using multiple
directories, they only make their situation worse: Instead
of dividing themselves into D possible states of knowledge,
they divide themselves into (2^D-1) possible states
depending on which directories they trust.)
(4) An attacker who wants to DOS a user can do so by knocking
down that user's favorite directory server.
Below, I describe a synchronization protocol that allows multiple
directory servers to arrive at a single directory, signed by all
the directory servers. My requirements are as possible:
- Central coordination between directory servers should not be
an absolute requirement. In particular, the protocol should
succeed even when the directory servers do not agree on who is
a directory server.
- The protocol should allow old directory servers to shut down,
and new directory servers to join, but should not allow
- When the protocol succeeds, it should create a directory
signed by a large quorum of directory servers. If at least
half of the quorum has signed a directory, clients should be
able to trust that directory.
- If an attacker controls less than half of the directory
servers in a quorum, the attacker should not be able to sign
up an arbitrary number of nodes.
- If at least half of the directory servers in a quorum are
running, cooperative, and able to communicate, then they
should produce a signed directory.
- The protocol should discourage social engineering attacks
aiming to fragment a quorum of directory servers. Although
it is impossible to *force* only a single directory to exist
(because people can always modify the software), it would be
best to minimize the number of fragmented directories.
- If a directory server do not obey the protocol, other servers
should be able to prove it.
- Parties other than directory servers should be able to tell
whether the directory servers are obeying the protocol.
Broadly, the protocol works like this:
- Every mix periodically uploads its server descriptors to all
of the directory servers it knows about.
- Every directory server continuously publishes its knowledge of
the network (for consumption by other directory servers).
- Every directory server periodically downloads from other
directories it knows about their knowledge of the network,
and updates the list of mixes it knows about.
- Once a day, directory servers produce a signed directory as
follows:
- Every directory server publishes a signed statement
describing its current view of the network state, and
the list of other directory servers it would like to
vote with.
- The directory servers retrieve each others' signed
statements.
- Based on these signed statements, each directory server
finds a quorum to vote with. All cooperative servers
will agree about who should be in the same quorum with
them.
- Based on the signed statements of the other directory
servers in the quorum, each directory server computes a
reconciled directory. This process is deterministic,
so that all cooperative directory servers in the same
quorum will compute the same reconciled directory.
- Each directory server signs its reconciled directory,
and exchanges these signatures with the other members
of its quorum.
- At this point, every quorum has computed a uniform
directory signed by every cooperative member of the
quorum. The directory servers publish this signed
directory.
Below, I discuss this protocol in more detail.
1. Terminology
Mix -- a Type III remailer server.
Reliable mix -- A mix is 'reliable' if it implements the Type III
remailer protocol correctly, by correctly processing and
delivering the messages it receives.
Honest mix -- A mix is 'honest' if it tries to be reliable, and it
does not attempt to attack the network or break users'
anonymity.
Pinger -- a source of liveness and reliability information about
mixes.
Directory server -- a host that follows the protocol described in
this document.
Cooperative server -- A directory server is 'cooperative' if it
follows the agreement protocol correctly. (It may still be
attempting to subvert the _contents_ of the final directory by
lying about network state.)
Honest server -- A directory server is 'honest' if it is
cooperative, and it attempts to make accurate statements about
network state.
Publication -- In order to 'publish' a file, a directory server
makes that file available at a well-known HTTP URL.
Network view -- A directory server's knowledge and opinions about
mixes and other directory servers. (More information is in 2.2
below.)
2. The protocol in more detail
2.1. Uploading server descriptors to directories
Mixes upload their server descriptors to directory servers as
before. The only change is that every Mix now knows about a
number of directory servers, and uploads every descriptor it
generates to each one of them.
2.2. Pinging
Pinging is outside the scope of this document, except as follows:
Every directory server acts as a pinger in order to obtain
reliability information about all the mixes it can. Additionally,
the directory administrator may decide to incorporate liveness
information from other pingers. The directory distills this
information down to a single "is-reliable" bit for each mix.
2.3. What directory servers know
Every directory tracks the following information about every mix:
- The mix's identity key.
- A list of all valid, non-superseded server descriptors it
knows for the mix.
- Whether it considers the mix reliable (based on pinging).
- Whether it considers the mix 'credible'. (A mix is 'credible'
if the directory server thinks it is honest. Different
directory servers may have different criteria here: Some
directory servers will consider new mixes as automatically
'credible' unless they have evidence of their dishonesty;
others will consider new mixes as 'non-credible' at first,
and list them as 'credible' after a probationary period.)
Directory servers should publish the criteria they use to
judge credibility.
[Rationale: we add 'credibility' for two reasons:
1) Adding a manual step before we include a new mix in the
directory prevents pseudospoofing attacks. (If an
attacker could sign up a hundred reliable mixes and have
them all included in the directory automatically, the
attacker would trivially be able to break user
anonymity.
2) This protocol does not provide a way for directory
server to 'unlist' dishonest mixes---if any server knows
about a mix, the final signed directory will include it.
In this protocol, instead of flushing a bad mix down the
memory hole, you just mark it as 'noncredible'.]
Every directory tracks the following information about every other
directory server:
- The directory server's identity key and URLs.
- Whether it uses that directory server's pinging results in
determining mix reliability.
- Whether it believes that directory server should be part of
a voting quorum.
All of the above information, taken together, forms a directory's
"Network View".
2.3. Directory agreement protocol
(All times in this section are completely arbitrary, and given in
GMT. This protocol assumes loosely synchronized clocks.)
Phase 0: Propagation
Every hour or so, every directory server publishes a signed,
non-binding statement of its Network View (as defined in 2.2
above).
Directory servers periodically retrieve one another's Network
Views in order to learn about new mixes, new directory servers,
and new server descriptors.
Phase 1: Declarations (22:00)
Once a day, at 21:00, every directory server publishes (at some
well known URL) a signed Declaration. A Declaration includes:
1) The date
2) The directory's current World View.
Phase 2: Declarations are collected (22:00-22:50)
Between 21:00 and 22:00, every directory server retrieves every
other directory server's Declaration. The directory server then
re-publishes those declarations at local URLs, along with signed
statements averring that the directory server has received them.
Even after retrieving one another's declarations, directory
servers continue to retrieve the re-published declarations, in
order to assure no directory server has given different
declarations to different servers.
Phase 3: Agreement (23:00)
At 22:00, every directory server calculates what quorum it is
in, calculates how that quorum will vote, and signs the result
of the vote. This predicted-vote-result is called a
'pre-directory'. Because this process is deterministic, every
cooperative directory in the same quorum will reach the same
result.
(The details of this process are described in 2.4 and 2.5
below.)
For auditing purposes: Along with their pre-directories,
directory servers also publish a signed copy of the declarations
they have used to compute the pre-directory.
Phase 4: Pre-directories are collected (23:00-23:50)
Directories collect one another's signed pre-directories as in
Phase 2.
Phase 5: A directory is published (00:00)
Every directory collects the pre-directories from step 4 from
the members of its quorum. If they have cooperated, every
directory server in the quorum will have signed the same
pre-directory. This pre-directory, plus the signatures of each
member of the quorum, forms the final directory.
Phase 6: Clients download the directory (00:01--00:00)
The first time in any day that a client originates a message, it
downloads the most recent directory from some source that it
trusts. If it signed by over half of the expected directory
servers, it uses that directory. Otherwise, it alerts the user.
(See section 3 below.)
2.4. How to compute quorums
In phase 3 of the directory agreement protocol, directory servers
need to compute which quorum they will vote with. This process
needs to be deterministic, so that every cooperating directory
server in a quorum arrives at the same quorum.
[Remember: the end goal is for there to be a single most
trustworthy quorum that all clients use. This quorum-building
algorithm is only designed to minimize the number of competing
quorums when we can't come up with a single most trustworthy one;
and to discourage directory severs from fragmenting the quorum.]
To choose a quorum, directory servers iteratively calculate the
"best" quorum of directory servers, and see if they belong to it.
If they do, they use that quorum. Otherwise, they remove the
servers in that quorum from consideration, and iterate.
(Below, we use "A trusts B" to mean "A believes B should be a part
of a voting quorum" in the interest of brevity.)
To find the "best" quorum from a set of directory servers, we
use the following algorithm:
1. Find the largest set of mutually trusting directory servers.
(A set of servers is 'mutually trusting' if every server in
that set trusts every other server in that set.) If there
is a unique largest set of mutually trusting directory
servers, that set is best. Otherwise, if we have a tie,
proceed to step 2.
2. Let N be the size of the tied sets under consideration. If
N>=5, and any two of the tied sets have at least N/2 common
elements, we compute the 'friendlier' set as follows: Set A
is friendlier than set B if the number of <A_i,B_j> pairs
such that A_i trust B_j is greater than the number of
<B_i,A_j> pairs such B_i trusts A_j.
(Note that 'friendliness' can be cyclical.)
We then compute the 'index' of each set by taking the SHA1
hash of the sorted public keys of all the directory servers
in the hash.
We compute a 'transitive friendliness' relationship as
follows: First, we break cycles in the friendliness graph,
from largest cycle to smallest, by removing the
'is-friendlier-than' relation from the smallest-indexed set
in the friendliness graph. Secondly, we take the transitive
closure of the resulting graph.
Finally, compute the best set as follows: start with "S_0",
the set with the highest index. If there are one or more
sets that are "transitively friendlier" than S_0, choose the
one of those sets with the highest index.
[Discussion: The graph theory here is kinda funky. The idea behind
'friendliness' is to prefer quorum-builders to quorum-breakers,
so that if we start with a quorum containing Dirserv-1 through
Dirserv-N, and then Dirserv-1 stops trusting Dirserv-2, Dirserv-1
is booted from the next day's quorum.
Also note that the idea is not to ensure that the "best" quorum
is the most trustworthy, but that the "best" quorum to which an
honest server belongs is the most trustworthy.]
2.5 How to compute a pre-directory
A 'pre-directory' is the signed portion of a signed directory. It
contains:
- a list of server descriptors for all known mixes
- a list of directory servers in a voting quorum
- and a list of which mixes are recommended
To compute a pre-directory, a directory server first determines
what quorum it will vote with, as described in 2.4 above. It then
takes the Declarations from those directories, and its own
Declaration, and computes the pre-directory as follows:
- It chooses the most recently published live non-superseded
server descriptors for each mix (as in "dir-spec.txt").
- It lists mixes as "recommended" iff they are considered
reliable by enough members of the quorum and they are
considered credible by enough members of the quorum.
[If the quorum has an odd number N members, "enough" is
FLOOR(N/2)+1.]
3. Client behavior
Every client comes pre-installed with a list of directory servers.
This list should be identical with the servers in whatever
long-standing quorum the software maintainer judges the most
trustworthy and reliable. If any user Alice trusts a different set
of directory servers, she can configure her client manually to use
those directory servers instead.
If the client can retrieve a single directory signed by a majority
of its trusted directory servers, it uses that directory.
Otherwise, the client software alerts the user, and has the user
choose.
4. If stuff goes wrong
Here we examine opportunities for the protocol to go wrong, and see
how bad stuff gets. Below, for "an attacker", read "an attacker, a
malfunctioning directory server, a network outage, or Murphy's
Law."
Phase 1. Declarations
- An attacker might publish a dishonest declaration.
[If an attacker controls less than half of the quorum to which
it belongs, it cannot force mixes on to or off of the final
list. If the attacker tries to break the quorum building
process, it cannot force honest servers to join a mostly
dishonest quorum, unless the honest servers trust enough
dishonest directory servers.]
- An attacker might not publish a declaration.
[If the attacker does this, it will not be part of any
quorum.]
Phase 2. Declarations are collected
- An attacker might give different declarations to different
directory servers.
[Since all declarations include a date and are signed, any two
cooperative servers will have proof that they have received
different declarations as soon as one has received the other's
re-published version of the uncooperative directory's
declaration.]
- An attacker might not give its declarations to some servers.
[So long as any cooperative directory server receives a copy,
the other directory servers will eventually retrieve a copy
from that server.]
- An attacker might not give its declaration to any servers.
[If the attacker does this, it will not be part of any
quorum.]
Phase 3. Agreement
- An attacker might pretend not to have received certain
declarations.
[If most directory servers have received and re-published a
server's declarations, any attacker who does this may not be
believed. If the attacker is included in a quorum, the other
members of the quorum will all sign the same pre-directory,
but will not include the attacker's signature.]
- An attacker might compute the pre-directory incorrectly.
[If the attacker does this, the cooperative members of the
quorum will all sign the same pre-directory, while the
attacker's signature of a different pre-directory will not be
included.]
- An attacker might not publish a pre-directory.
[If the attacker does this, the cooperative members of the
quorum will all sign the same pre-directory, while the
attacker's non-formed signature will not be included.]
Phase 4. Pre-directories are collected
- As in phase 2 above
Phase 5. A directory is published
- As in phase 3 above