Re: Minion paper comments

[Roger Dingledine <arma@mit.edu>]

On Mon, Jan 13, 2003 at 10:47:41AM -0500, Adam Shostack wrote:
> Its good work there.
> 
> I question one of your high level decisions, reply blocks on three
> grounds:
> 
> 1) Its not clear how useful it is (more below)
> 2) Its a new mechanism that has effects throughout the design
> 3) It makes the entire design more complex.
> 
> Usefulness:  Without email client integration, reply blocks are
> unlikely to be used.  They're complex, clunky, and hard.  (Can I email
> alice today?)

SURBs are a building block. You're not generally meant to use them
yourself. But once we combine them with nymservers, then we basically
have remote pop servers from which you can anonymously retrieve your mail.

Users who don't need to keep anonymity can mail alice@nym.alias.net and
it will work its way to alice, whoever she is. Those who want double
blinding can deliver the mail via the Mixminion network to the nymserver.

Near as I can tell it, type i remailers still get quite a bit of use,
because they're the only way to do nyms. Yet they're very insecure.

The complexity from the design comes not simply from the secure reply
blocks, but also from the goal of wanting to combine the anonymity sets
of forward messages and replies. We could have used any of a number of
simpler designs if we were ok with letting nodes distinguish forwards
from replies.

> A high level goal that's missing is N: deployability.  We have order
> zero remailers, and order zero remailer users.  Those need to be
> fixed.

That's the first goal in Section 3 (page 3). Do you think we should
emphasize it more?

> I'm not sure if type 1s are used because of reply blocks, or because
> people can use them without a client.

I'll let the remops here speculate about why type i's are still in use.
Len/Peter/others?

> In section IV.A, you confuse anonymity (without a name) with
> pseudonymity.  In "1", If Alice is anonymous, its (A)^x_i, not (A)^X 
> In 3, Alice and Bob remain pseudonymous for their conversation.

Hrm. Our notation seems all screwed up here, doesn't it. Certainly the
messages that use reply blocks should be using ^y_i, since there's no
such thing as a multi-use reply block. And I agree -- I don't understand
the notion of "Alice communicating anonymously with a pseudonym". The
Mixminion network provides forward anonymity, meaning I guess (A),
and Alice can choose to sign her messages with some key (pseudonym)
that persists between messages.

Hm.

> At the end of IV.a, I think a brief review of LBCs are in order, if
> you choose to keep them.  I think that its worth removing
> psuedonymity, because I think that the baroque design needed (new
> primitives?) is a net loss.

What do you mean here by 'removing pseudonymity'? Do you mean worth
allowing mix nodes to distinguish between forwards and replies?

If so, then you may be right. We tried to push through our goals and get
the simplest design we could that met all of them. But it might not be
worth keeping all of them. Here's an argument Nick gave me a few days
ago for why it might be ok:

* If Mixminion takes off, it may well be because of the nymserver
  feature. Most use will be sending mail to nyms.
* Since for a given message M delivered to a nym, there will be a
  corresponding M' when it's delivered to the nym's owner, then about
  half the traffic on the network will be forwards, and half replies.
* So while we did in fact cut the anonymity sets in half, each of them
  is still large enough to be something.

But it's not like we're actually designing new primitives here. BEAR has
been around a little while, and when you look at its actual construction,
it's not as sketchy as it seems at first.

> In 4B, I think that perhaps a once use oracle might be ok, in order to
> simplify.  As there are other attacks (peelback) with reply blocks,
> being an oracle, which is usually invoked in the context of order
> zillions of messages, may be ok.
> 
> In 5A, what's the speed effect of not updating keys per message?

Nick?

> In 5C 'The fewer exit nodes,' I'm not sure I buy this; is one exit
> node with 10 messages really worse than 10 nodes with one message?

Well, the intersection attack, which is one of the most effective attacks
against Mixminion, requires that the adversary observe the sender and
the receiver.

If observing a single node means you get to observe many receivers,
then we've made this attack even easier.

Part of the unspoken security hope from a free-route mix network is that
actual global adversaries are rare, and it's worth protecting against the
not-so-global ones too. If we seriously thought most adversaries would be
global, then we'd probably be using a cascade. (I speak only for myself
in this paragraph, and my intuition changes weekly. Anonymity is hard. :)

> In VII, I don't buy your more liability claim.  Do you mean civil or
> criminal?  Where's the legal support?  (This goes back to my
> questioning of SURB.)

<wave hands here>
I'd be interested in hearing your take on this one.

--Roger