Nym servers with single-use reply blocks

[Roger Dingledine <arma@mit.edu>]

Current nymservers, such as nym.alias.net, maintain a set of (email
address, reply block) pairs to allow users to receive mail without
revealing their identities. When mail arrives to bob@nym.alias.net, the
nymserver attaches the payload to the associated reply block and sends
it off into the mix-net. Because these nymservers use the cypherpunk
(type 1) remailer network, these reply blocks are \emph{persistent}
or \emph{long-lived} nyms --- the mix network does not drop replayed
messages, so the reply blocks can be used again and again. Reply block
management is much simpler in this model because users only need to
replace a reply block when one of the nodes it uses stops working.

Because the Mixminion design protects against replay attacks by dropping
messages with headers that have been seen recently, reply blocks are
necessarily single-use. There are a number of approaches we could take
to implementing nymservers when reply blocks are single-use.

The approach most similar to currently deployed nymservers involves
keeping a set of reply blocks around and using one for each incoming
message. As long as the owner of the pseudonym keeps the nymserver
well-stocked, no messages will be lost. But it's hard to know at what
rate to supply the nymserver with new nyms; indeed, this approach is
vulnerable to a DoS attack to use up all the available reply blocks and
block further messages from getting delivered.

A more robust design uses an imap-like protocol: messages arrive and queue
at the nymserver, and the user periodically checks the status of his mail
and sends a sufficient batch of reply blocks so the nymserver can deliver
that mail. The above flooding attack still works, but now it's exactly
like flooding a normal imap mailbox, and the usual techniques (e.g.,
allowing the user to delete mails at the server or specify which mails to
download and let the others expire) work fine. The user can send a set
of hashes or other indices to the server after successfully receiving
some messages, to indicate that those messages can now be deleted.

Of course, there are different legal implications and responsibilities for
the two proposals. In the first case, no mail is stored on the server;
whereas in the second the server has to keep mail for each recipient
until it's retrieved. The owner of the pseudonym could provide a public
key which the nymserver uses to immediately encrypt all incoming messages,
to limit the amount of time the nymserver keeps plaintext messages.

What other issues (legal, practical, design, implementation, deployment)
did I leave out? Are there cleaner simpler approaches that don't suck?

--Roger
(these ideas came from a napkin George was writing on a couple days ago)