Re: Nym servers with single-use reply blocks

[Nick Mathewson <nickm@alum.mit.edu>]

On Mon, 2002-04-22 at 03:24, Roger Dingledine wrote:
[...]
> 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.

* Since a reply block is good for at most a single time window (one day,
I believe), the DoS attack could require regular intervention.

* You could require a proof-of-work phase here to try to increase the
expense of doing a DoS.  How hard this would be, I'm not sure.

> 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.

How is the user to know which messages to download, if, as you suggest
below, they're encrypted immediately upon receipt in order to avoid
legal issues?  [One way: encrypt the first n bytes of each message
separately, and allow Alice to retrieve these headers separately.  This
may be enough, but may not be.

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

* IMO, both approaches are worthwhile.

* A hybrid approach might make sense: forward messages until the reserve
of reply blocks runs out; otherwise, store them.

* Is there any value in a Nym which only a set of senders can use?  If
so, you can prevent DoS attacks in those cases by requiring incoming
messages to be signed.

-- 
Nick