nym-desc.tex

About this Document

   George wrote the first version of this in August 2002, and added
   the API section in September 2003.  The "nym-spec.txt" and
   "api-spec.txt" files in doc/spec are more recent, but may miss
   good points in this draft.

======================================================================

Specification of a nym server running on top of Mixminion.

We assume that the underlying anonymizing network (in this case
Mixminion) provides the following anonymous communications
primitives:

(A) -> B: M   - An anonymous party A sends a message M to a named party
                B. M has a maximum length of L.
A -> (B): M   - A named party A sends a message M to an anonymous
                recipient B. M has a maximum length of L.
(A) -> (B): M - An anonymous sender A sends a message M to an
                anonymous recipient B. M has a maximum length of L.
(B)[ID]       - A Single Use Reply Block (SURB) destined to B. A label
                ID can be used to differentiate between different
                SURBs.

Implementing the anonymous primitives using Mixminion

We assume the existence of the following procedures from the mixminion
specifications: 

PROCEDURE: Create a single header.
Inputs: A_1 .. A_N (addresses of intermediate nodes), 
	PK_1 .. PK_N (Public keys of intermediate nodes),
	SK_1 .. SK_N (Secret keys to be shared with intermediate nodes),
        R Routing type and information of last header (FWD, DROP, SWAP, etc.)
Output: H (The header)

PROCEDURE: Construct a message.
Input: H1 (header containing keys SK1_1... SK1_N)
       and H2 (either a header containing keys SK2_1... SK2_N if
         we constructed it, or a header with unknown keys if we're
         using a reply block and a SURB secret key.)
       P (Payload)
Output: M (the message)

PROCEDURE: Decode a message.
Input:  TAG field of sub-header or header where 
        TAG = ( Encrypt(KEY, nHops | seed) | padding up to 44b).
        M the body of the message.
Output: P, the plaintext of the message.


We will define the following operations:
(An API for mixminion clients)

PROCEDURE: Create SURB
Input: -
Output: ID of the generated SURB. 
	SURB data.

The above procedure generates a SURB that is addressed to the local
machine given the local configuration.

PROCEDURE: Send Anonymous
Input: Address as specified in the ``Routing information'' section of
	the mixminion spec.
       OR 
       SURB provided by another user.
       Message to be encoded and sent.
Output: -

The above procedure sends a sender anonymous (and recipient anonymous
if a SURB is provided) message.

PROCEDURE: Send
Input: SURB provided by another user.
       Message to be encoded and sent.
Output: -

The ``Send'' procedure sends a normal (non-anonymous) message to an
anonymous address.

PROCEDURE: Receive Anonymous 
Input: -
Output: ID, the id of the SURB used to encode this message.
	Message, the message received (decoded)

The ID can be zero (0) if the message received did not use a SURB, and
therefore is not anonymous. It is important to make sure that
information that is to remain anonymous is not sent back as a reply.

It is important to note that in order to create the new procedures
from the ones provided in the mixminion specification a lot of
internal state is required in the client. Hopefully this state should
be preconfigured in the ``anonymous communication stack'' and then
hidden from the layer above that should only need the operations above
to use the anonymity layer. In particular additional information
required includes:
- Lists of mixes, with reliability statistics or another strategy to
choose routes with.
- Secret keys under which the TAG field is encrypted or public/private
key pairs to decode normal mixminion headers.
- A strategy to compute the route lengths.
- A knowledge of the local host parameters, and preferred modes of
delivery (IP or SMTP).


The requirements of the Nym Server are:

- The Nym server allows users without any special software (besides
  standard SMTP) to send email [RFC2821] to anonymous recipients.
- The Nym server should not be trusted or relied upon to maintain the
  anonymity of the users. (However, it should be trusted not to deny
  service to honest users.)
- The Nym server should not be required to maintain more state than
  its administrator wishes. In particular the administrator should
  have the option not to store unencrypted messages or SURBs.
- The nym server should provide reliable service, even if the
  anonymous communication channels do not. In particular it should
  ensure that if recipients follow the protocols correctly, the nym
  server will reliably deliver their mail. (Unreliable transport to
  the nym server will still be unreliable.)
- Clients that do not benefit from any anonymity properties do not
  need any special software.
[Is this redundant with the first item above? -RD]
- Clients and Nym servers need not run anonymous remailer nodes
  themselves. They can function by simply acting as clients to the
  anonymous network, sending and receiving anonymous messages. However,
  a nym server which runs a remailer node seems to provide stronger
  anonymity by blending its messages with other remailer traffic.


The Nym model

Users (recipients) run special software called the Nym client, that
understands Mixminion and Nym server commands. They anonymously create
a nym account on the nym server. After this setup phase any email
received by the Nym server for the nym is anonymously forwarded to
the appropriate user. The Nym server makes sure that the message has
correctly arrived to the user before it is deleted.

   Rest           Nym                      Anonymous
 of the --SMTP--> Server <---Mixminion---> User
  World                                    (Nym Client)

Client and Server Databases

The design aims to minimize the information the client and server must
store, while maintaining high reliability.

Client:

list of {
  Full Nym Name (Nym)
  Server Address (A)
  Server Verification key (KSv)
  Client Signature Key (KCs) + Verification key (KCv)
  Client Decryption Key (KCd) + Encryption key (KCe)
  Kill phrase (KP)
}

Server:

Server Signature Key (KSs) + Verification key (KSv)
Server Address (A)

list of {
  Full Nym Name (Nym)
  Client Verification key (KCv)
  Client Encryption key (KCe)
  Hash of Kill Phrase (H(KP))
  Should it store SURBS? (SS)
  list of i = 1..n {
    SURBS ((Nym)[i])
  }
  list of j=1..m {
    Message (M[j])
  }
}

Nym Server Public Information

A Nym server should advertise its address for SMTP, as well as its address
for anonymous access if applicable. If it advertises an address, it must
also list a public verification key to allow others to verify messages
sent by it; and policy files must be available concerning the creation
of nyms (acceptable names, whether it stores SURBs), and the conditions
of service (maximum message sizes, how often SURBs should be given,
lifetime of accounts, etc.)

Protocols

Initialization:

The client chooses a Nym Name (Nym) which will be the base of its
email address on the nym server. The client also provides the server
with public keys to encrypt (KCe) and verify (KCv) messages. The Kill
Phrase is used in case the Signature keys are stolen or lost, to allow
the user to be able to destroy the Nym account.

In order to create the account the Client provides some means for the
server to contact her back, in the form of SURBs.

(C) -> NymServer: {CREATE,Nym, KCv, A, KSv, KCe, H(KP), SS,n,(C)[1]..(C)[n]}KCs

The Nym Server can deny an account creation request for a variety of
reasons, which should be communicated to the user using one of the
Messages. The server could be full, the Nym already in use, or rude.
It is important for Nym server operators to have a clear policy on
which nyms are acceptable and which are not.

NymServer -> (C)[x]: {ACCEPT|DENY, A, KSv, Nym, KCv, Message}KSs

(It's safe to send 'Nym' back to C in cleartext, because the remailer
network wraps the message in several layers of encryption, which C
privately peels off.)

On Server receiving messages:

The Nym Server runs an SMTP [RFC2821] service. When a message received
is addressed to a particular nym, it is encrypted under the nym's key
(KCe) and stored on permanent storage. If the Server has a SURB on
hand that corresponds to the nym, it forwards the message. Otherwise,
it waits for more SURBs. At the end of any MESSAGE the nym server can
specify the number of additional SURBs that it requires to flush all
messages. The client is not obliged to send the specified number of
SURBs, but the server may stop receiving mail for this particular Nym,
or drop the account.

[a) If servers may drop accounts that get too much mail, did we just
 introduce a serious DoS problem? This needs fleshing out.
 b) If we take in Mixminion messages and deliver them to SURBs, we have
 no space to add things at the end. Perhaps "number of requested surbs"
 needs to go in the header (ugh)? (But we *can't*, because we can't see
 inside the SURB. Hrm.) -RD]

A -> NymServer: M (with SMTP to: NymB)
NymServer -> (B): {MESSAGE, A, KSv, NymB, KCv,
                   n,{M}KCe[1]..{M}KCe[n],m, info}KSs
[Do we need to say KSv and NymB and KCv, above? It seems we're supporting
multiple keys per nym? And I guess we're choosing either to be redundant
or to not store all the info in the reply block header? -RD]
(B) -> NymServer: {RECEIVED,  NymB, KCv, A, KSv, n,
                   H({M}KCe[1])..H({M}KCe[n]), m, (B)[1]..(B)[m]}KCs

To kill a Nym:

(A) -> NymServer: {KILL, NymA, KP}

Since a nym's signature key might be compromised or lost it is
important to have a backup but abuse-proof mechanism to destroy nyms
on the server, along with all the stored information. Therefore if the
server receives a kill message with a ``Kill phrase'', where the hash
of the kill phrase matches the one stored for the nym, it must destroy
all information about that nym.

Sending messages

[Since we have decided that the SMTP mechanism is general we do not
  need a specific sending ability for the Nym server -GD]

Multiplexed reliable mix communications and Information dispersal techniques

[Since many different protocols might be using the anonymous
  communication infrastructure it could be helpful if we create a port
  abstraction using either an identifier at the beginning of the
  payload or different mailbox names for the Local delivery present in
  the last header of the message -GD] 
[In order to avoid retransmissions, that could help traffic analysis,
  an idea would be to send the messages of the above protocol using a
  forward error correcting scheme. The Server, and clients, could
  measure the reliability of the network, by sending messages to
  themselves, and encode each message in a (n out of m) fashion. Maybe
  someone who is knowledgeable about such schemes would like to comment? -GD]

References

[RFC2821] J. Klensin, Editor, Simple Mail Transfer Protocol